# Subdivide-Sum Sequence

Consider the digits of any integral base above one, listed in order. Subdivide them exactly in half repeatedly until every chunk of digits has odd length:

Base    Digits              Subdivided Digit Chunks
2       01                  0 1
3       012                 012
4       0123                0 1 2 3
5       01234               01234
6       012345              012 345
7       0123456             0123456
8       01234567            0 1 2 3 4 5 6 7
9       012345678           012345678
10      0123456789          01234 56789
11      0123456789A         0123456789A
12      0123456789AB        012 345 678 9AB
...
16      0123456789ABCDEF    0 1 2 3 4 5 6 7 8 9 A B C D E F
...


Now, for any row in this table, read the subdivided digit chunks as numbers in that row's base, and sum them. Give the result in base 10 for convenience.

For example...

• for base 3 there is only one number to sum: 0123 = 123 = 510
• for base 4 there are 4 numbers to sum: 04 + 14 + 24 + 34 = 124 = 610
• base 6: 0126 + 3456 = 4016 = 14510
• base 11: 0123456789A11 = 285311670510

# Challenge

Write a program that takes in an integer greater than one as a base and performs this subdivide sum procedure, outputting the final sum in base 10. (So if the input is 3 the output is 5, if the input is 6 the output is 145, etc.)

Either write a function that takes and returns an integer (or string since the numbers can get pretty big) or use stdin/stdout to input and output the values.

The shortest code in bytes wins.

# Notes

• You may use any built in or imported base conversion functions.
• There is no upper limit to the input value (besides a reasonable Int.Max). The input values don't stop at 36 just because "Z" stops there.

p.s. this is my fiftieth question :)

• if I use a function, what meaning "..the final sum in base 10" mean? if we return the output, then it's represented internally in the computer in binary. what does "in base 10" mean there? – proud haskeller Sep 28 '14 at 12:55
• Congratulations on reaching 50 questions. And such an astonishing variety. Thanks. – DavidC Sep 28 '14 at 14:29
• @proudhaskeller In that case just give your examples in base 10 if you have any. Though it's also alright if the function returns a string since the numbers can be quite large. Then uses base 10. – Calvin's Hobbies Sep 28 '14 at 14:58

# 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. ";

• Getting the highest power of 2 as x & -x is really clever. – Dennis Sep 28 '14 at 20:57
• Accepting this since it is the shortest, but props to Ell for finding a formula. – Calvin's Hobbies Oct 26 '14 at 3:44

## 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 .

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

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

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

• Wow, that is super, how did you figure that formula out ? Mind if I convert this to CJam ? – Optimizer Sep 28 '14 at 11:05
• @Optimizer Go ahead! I'll write an explanation when I have some more time. – Ell Sep 28 '14 at 11:07
• +1 if you are still like "Huh?" after reading that explanation :D – Optimizer Sep 28 '14 at 19:07
• Just to be clear, not because there is any fault in explanation, but because its too complex for my brain :D – Optimizer Sep 28 '14 at 19:11
• That is magic! You can save some chars by using ~: b/G-i-1 can be b/g+~i and (G-1)*b/2 can be ~-G*b/2 – xnor Sep 28 '14 at 20:13

# CJam (snapshot), 19 bytes

li__,\mf2m1+:*/fb:+


Note that the latest stable release (0.6.2) has a bug that can cause mf to return Integers instead of Longs. Quite paradoxically, this can be circumvented by casting to integer (:i).

To run this with CJam 0.6.2 (e.g., with the online interpreter), you have to use the following code:

li__,\mf:i2m1+:*/fb:+


Alternatively, you can download and build the latest snapshot by executing the following commands:

hg clone http://hg.code.sf.net/p/cjam/code cjam-code
cd cjam-code/
ant


### Test cases

$cjam <(echo 'li__,\mf2m1+:*/fb:+') <<< 3; echo 5$ cjam <(echo 'li__,\mf2m1+:*/fb:+') <<< 4; echo
6
$cjam <(echo 'li__,\mf2m1+:*/fb:+') <<< 6; echo 145$ cjam <(echo 'li__,\mf2m1+:*/fb:+') <<< 11; echo
2853116705


### How it works

li                     " N := int(input()) ";
_,                  " A := [ 0 1 ... (N - 1) ] ";
_  \mf               " F := factorize(N) ";
2m1+           " F := F - [2] + [1] ";
:*         " L := product(F) ";
/        " A := A.split(L) ";
fb      " A := { base(I, N) : I ∊ A } ";
:+    " R := sum(A) ";


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


examples:

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


## CJam, 41 bytes

This is basically Ell's solution in CJam:

ri:B__(^2/):G/,{_BBG/@-(#G@*G(B2/*+*}/]:+


Try it online here

My original submission:

Doesn't work correctly for base 11 and above

ri:B2%BB{2/_2%!}g?B,s/:i:+AbBb


Will try to see if I can get it to work for base 11 and above, without increasing the size much.

## Mathematica, 114 bytes (or 72 bytes)

Hm, this got longer than I thought:

f@b_:=Tr[#~FromDigits~b&/@({Range@b-1}//.{a___,x_List,c___}/;EvenQ[l=Length@x]:>Join@@{{a},Partition[x,l/2],{c}})]


And ungolfed:

f@b_ := Tr[#~FromDigits~
b & /@ ({Range@b - 1} //. {a___, x_List, c___} /;
EvenQ[l = Length@x] :> Join @@ {{a}, Partition[x, l/2], {c}})]


Alternatively, if I just port Ell's nifty formula, it's 72 bytes:

f=Sum[#^(#/g-i-1)(g*i+(g-1)#/2),{i,0,#/(g=Floor[BitXor[#,#-1]/2+1])-1}]&


# J - 22 char

Function taking a single argument (call it y for the purposes of this golf) on the right.

+/@(#.i.]\~-%2^0{1&q:)


First we use 1&q: to get the number of times y is divisible by 2, and then divide -y by 2 that many times. This gives us the negative of the width that we need to split things into, which is perfect, because ]\ will take overlapping pieces if the argument is positive, and non-overlapping if it's negative.

So then we split up i.y—the integers from 0 to y-1—into vectors of these widths, and use #. to convert them from base y to base 10. Finally, +/ does the summing, and we're done.

Examples: (input at the J REPL is indented, output is flush left)

   +/@(#.i.]\~-%2^0{1&q:) 6
145
f =: +/@(#.i.]\~-%2^0{1&q:)
f 11
2853116705
(,: f every) 1+i.14   NB. make a little table for 1 to 14
1 2 3 4   5   6     7  8       9    10         11   12            13       14
0 1 5 6 194 145 22875 28 6053444 58023 2853116705 2882 2103299351334 58008613
f every 20 30 40x     NB. x for extended precision
5088086 7455971889417360285373 368128332
":"0 f every 60 240 360 480 720 960x   NB. ":"0 essentially means "align left"
717771619660116058603849466
3802413838066881388759839358554647144
37922443403157662566333312695986004014731504774215618040741346803890772359370271801118861585493594866582351161148652
256956662280637244030391695293099315292368
2855150453577666748223324970642938808770913717928692581430408703547858603387919699948659399838672549766810262282841452256553202264
17093564446058417577302441219081667908764017056


## JavaScript, 99 89 bytes

function f(n){m=n/(n&-n);for(r=s=i=0;;){if(!(i%m)){r+=s;s=0;if(i==n)return r;}s=s*n+i++}}


or

function g(n){c=n&-n;for(s=i=0;i<n/c;++i)s+=Math.pow(n,n/c-i-1)*(c*i+(c-1)*n/2);return s}


The second function is similar to Ell's one. The first one uses a more traditional approach. Both are 89 characters in size.

Try here: http://jsfiddle.net/wndv1zz8/1/

# Jelly, 10 9 bytes

Ḷœs&N$ðḅS  Try it online! Essentially just a translation of jimmy23013's CJam answer, except using n & -n directly as the number of chunks to split into.  S The sum of Ḷ the range from 0 to the input minus one œs split into sublists of length equal to & the input bitwise AND N$       its negation
ðḅ     with each sublist converted from base-the-link's-argument.


(The ð has nothing to do with mapping: ḅ just vectorizes over its left argument, and ð is there to separate ḅS off as a new dyadic chain which takes the result of ḶœsÇ as its left argument and the argument to the main link as its right argument.)