# 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? Sep 28, 2014 at 12:55
• Congratulations on reaching 50 questions. And such an astonishing variety. Thanks. Sep 28, 2014 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. Sep 28, 2014 at 14:58

## 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 ? Sep 28, 2014 at 11:05
• @Optimizer Go ahead! I'll write an explanation when I have some more time.
– Ell
Sep 28, 2014 at 11:07
• +1 if you are still like "Huh?" after reading that explanation :D Sep 28, 2014 at 19:07
• Just to be clear, not because there is any fault in explanation, but because its too complex for my brain :D Sep 28, 2014 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, 2014 at 20:13

# 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. Sep 28, 2014 at 20:57
• Accepting this since it is the shortest, but props to Ell for finding a formula. Oct 26, 2014 at 3:44

# 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 -  +  ";
:*         " 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.)