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

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

jimmy23013 · Accepted Answer · 2014-09-28 21:14:32Z

4

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

edited Sep 28 '14 at 21:14

answered Sep 28 '14 at 20:52

jimmy23013

30.9k6 gold badges65 silver badges133 bronze badges

1

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

add a comment |

Ell · Accepted Answer · 2014-09-28 21:02:02Z

11

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.

edited Sep 28 '14 at 21:02

answered Sep 28 '14 at 10:33

Ell

6,6474 gold badges18 silver badges38 bronze badges

\$\begingroup\$ Wow, that is super, how did you figure that formula out ? Mind if I convert this to CJam ? \$\endgroup\$ – Optimizer Sep 28 '14 at 11:05
\$\begingroup\$ @Optimizer Go ahead! I'll write an explanation when I have some more time. \$\endgroup\$ – Ell Sep 28 '14 at 11:07
1

\$\begingroup\$ +1 if you are still like "Huh?" after reading that explanation :D \$\endgroup\$ – Optimizer Sep 28 '14 at 19:07
\$\begingroup\$ Just to be clear, not because there is any fault in explanation, but because its too complex for my brain :D \$\endgroup\$ – Optimizer Sep 28 '14 at 19:11
1

\$\begingroup\$ 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 \$\endgroup\$ – xnor Sep 28 '14 at 20:13

| show 1 more comment

Dennis · Accepted Answer · 2014-09-28 20:47:29Z

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

proud haskeller · Accepted Answer · 2014-09-29 17:46:19Z

2

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]

edited Sep 29 '14 at 17:46

answered Sep 28 '14 at 12:38

proud haskeller

5,8061 gold badge17 silver badges36 bronze badges

add a comment |

Community · Accepted Answer · 2017-04-13 12:39:06Z

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.

Martin Ender · Accepted Answer · 2014-09-28 15:16:50Z

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

algorithmshark · Accepted Answer · 2014-09-28 21:04:19Z

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

me and my cat · Accepted Answer · 2014-09-30 05:58:48Z

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/

Unrelated String · Accepted Answer · 2019-07-13 06:37:24Z

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Subdivide-Sum Sequence

Challenge

Notes

9 Answers 9

CJam, 17 15

How it works

Python, 82 78

CJam (snapshot), 19 bytes

Test cases

How it works

Haskell, 74 69 55

CJam, 41 bytes

Mathematica, 114 bytes (or 72 bytes)

J - 22 char

JavaScript, 99 89 bytes

Jelly, 10 9 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf math or ask your own question.

Hot Network Questions

Subdivide-Sum Sequence

Challenge

Notes

9 Answers 9

CJam, 17 15

How it works

Python, 82 78

CJam (snapshot), 19 bytes

Test cases

How it works

Haskell, 74 69 55

CJam, 41 bytes

Mathematica, 114 bytes (or 72 bytes)

J - 22 char

JavaScript, 99 89 bytes

Jelly, 10 9 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math or ask your own question.

Related

Hot Network Questions