Subdivide-Sum Sequence

Question

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: 012₃ = 12₃ = 5₁₀
• for base 4 there are 4 numbers to sum: 0₄ + 1₄ + 2₄ + 3₄ = 12₄ = 6₁₀
• base 6: 012₆ + 345₆ = 401₆ = 145₁₀
• base 11: 0123456789A₁₁ = 2853116705₁₀

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 :)

Answer 1

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

Answer 2

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, a_n, is .

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

Answer 3

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) ";

Answer 4

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]

Answer 5

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.

Answer 6

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}]&

Answer 7

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

Answer 8

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/

Answer 9

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