current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 2 down vote favorite

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

share|improve this 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 4 hours ago
1  
Congratulations on reaching 50 questions. And such an astonishing variety. Thanks. –  David Carraher 3 hours ago
    
@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 2 hours ago

4 Answers 4

up vote 6 down vote

Python, 82

def f(b):G=(b^b-1)/2+1;return sum(b**(b/G-i-1)*(G*i+(G-1)*b/2)for i in range(b/G))
share|improve this answer
    
Wow, that is super, how did you figure that formula out ? Mind if I convert this to CJam ? –  Optimizer 6 hours ago
    
@Optimizer Go ahead! I'll write an explanation when I have some more time. –  Ell 6 hours ago
up vote 1 down vote

Haskell, 74 69

f n=sum$zipWith((*).(n^))(cycle[0..until odd(`div`2)n-1])[n-1,n-2..0]

examples:

*Main> map f [2..15]
[1,5,6,194,145,22875,28,6053444,58023,2853116705,2882,2103299351334,58008613,2234152501943159]
share|improve this answer
up vote 0 down vote

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.

share|improve this answer
up vote 0 down vote

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}]&
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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