Subdivide-Sum Sequence

Python, 82 78

def f(b):G=b^b&b-1;return sum(b**(b/G-i-1)*(G*i+(G-1)*b/2)for i in range(b/G))

Huh?

  • The number of digit groups that the subdivison yields, G, is simply the greatest power of two that divides the number of digits (i.e. the base), b. It's given by G = b ^ (b & (b - 1)), where ^ is bitwise-XOR. If you're familiar with the fact that n is a power of two iff n & (n - 1) = 0 then it should be pretty easy to see why. Otherwise, work out a few cases (in binary) and it'll become clear.

  • The number of digits per group, g, is simply b / G.

  • The first digit group, 012...(g-1), as a number in base b, is F3.

  • The next group, g(g+1)...(2g-1), as a number in base b, is the sum F4.

  • More generally, the n-th group (zero-based), as a number in base b, an, is F5.

  • Recall that there are G groups, hence the sum of all groups is F6.1 F6.2
    which is what the program calculates.


CJam, 17 15

q5*~W*&/\,/fb:+

Works if there is a trailing newline in the input.

A more obvious version for those who don't know x & -x:

q5*~(~&/\,/fb:+

How it works

q5*~               " Push 5 times the input as numbers. ";
W*&/               " Calculate n / (n & -n). (Or n / (n & ~(n-1))) ";
\,                 " List the digits. ";
/                  " Split into chunks. ";
fb:+               " Sum in the correct base. ";

Haskell, 74 69 55

f n=sum[(n-x)*n^mod(x-1)(until odd(`div`2)n)|x<-[1..n]]

examples:

*Main> map f [2..15]
[1,5,6,194,145,22875,28,6053444,58023,2853116705,2882,2103299351334,58008613,2234152501943159]

Tags:

Math

Code Golf