No computer needed

Calculus Level 3

$\large f(x)=\prod _{ m=0 }^{ \infty }{\frac {\ \ \displaystyle \sum _{ n=0 }^{ m }{ { x }^{ n }\ \ } }{\displaystyle \sum _{ n=0 }^{ \infty }{ { x }^{ n } } } }$

Given $f(x)$ defined as above, define $C=\left\lfloor { 2 }^{ 120 } \times f\left(\frac { 1 }{ 2 } \right) \right\rfloor.$ Then, how many 1's does the binary representation of $C$ contain? That is, what is the binary digit sum of $C?$

Hint: You do not need a computer to solve this problem, nor do you need to calculate $f\left(\frac{1}{2}\right)$ to a high accuracy. There is a more "contest-friendly" way to solve this problem.

Bonus: Can you give a formula for the digit sum of $\left\lfloor { B }^{ 120 } \times f\left(\frac { 1 }{ B } \right) \right\rfloor$ in base $B?$

The answer is 63.

2 solutions

D G
Oct 1, 2017

I used the Pentagonal Number Theorem : the values of the infinite sum correspond to digits in the base B representation of f(1/B); B^120 shifts the digits to the left with respect to the decimal point, so we can terminate the sum at some point after the exponents become negative. It was still a messy calculation that I wouldn't want to do by hand.

Cant add it as a solution because I was stuck and decided to look at the answer, but based on your suggestion of Pentagonal numbers, one can shortcut the calculation by noticing a patern in the difference of the form 10000-101=01011. Based on the position of the three ones on the left side, the number of ones on the right hand side can be calculated as p most significant - p least significant - 1. Then tabulate the powers in the pentagonal expansion:

(k=0 -> 0) k=1 -> 1, 2 k=2 -> 5, 7 k=3 -> 12, 15 k=4 -> 22, 26 k=5 -> 35, 40 k=6 -> 51, 57 k=7 -> 70, 77 k=8 -> 92, 100 k=9 -> 117, 126

The extra line for k=0 is added to make the pattern more clear. As the evens give additions of (1/2)^n, and odds substractions, the pattern above can be applied on every pair 2k, 2k+1. This gives a contribution of 6k+1 for k=0,1,2,3, given a contribution of 1+7+13+19=40. This doesnt yet take into account the (3k^2-k)/2 powers for even k, which give a contribution of 4 (one for each of k=2,4,6 and 8). Becuse 126 > 120, the final pattern lies partially outside the requested range, so we need to compensate for that by ignoring the last 6 ones, given an extra contribution of 19. This combines to give the result 40+4+19 = 63. The bonus can be found through extension of the pattern to arbitrary bases, giving 68*B-73

David Venhoek - 3 years, 8 months ago

Laurent Shorts
Oct 8, 2017

We can show that $f(\frac12)=0.0\,100\,10\,01111\,011\,1000000\,1000\,011111111...$ can be decomposed this way:

1)	0	1 00	1 0	0 1111	(11 digits)
2)	0 11	1 00 0000	1 0 00	0 1111 1111	(23 digits, tot 34)
3)	0 11 11	1 00 0000 0000	1 0 00 00	0 1111 1111 1111	(35 digits, tot 69)

Number of ones:

$n$ )	$n·(n-1)$ ones	$n$ ones	$n$ ones	$2n·(n+1)$ ones	$6n^2+5n$ total digits
4)	12 ones	4 ones	4 ones	40 ones	(60 ones, 116 tot digits)
5)	0 11 1...				(63 ones until 120th digit)

Bonus

For example, with $B=10$ , we have $f(\frac1{10})=0.8\,900\,10\,09999\,899\,9000000\,1000\,099999999...$ :

1)	8	9 00	1 0	0 9999	(11 digits)
2)	8 99	9 00 0000	1 0 00	0 9999 9999	(23 digits, tot 34)
3)	8 99 99	9 00 0000 0000	1 0 00 00	0 9999 9999 9999	(35 digits, tot 69)

$n$ )	$n$ eights, $n·(n-1)$ nines	$n$ nines	$n$ ones	$2n·(n+1)$ nines	$6n^2+5n$ total digits
4)	4 8's, 12 9's	4 9's	4 ones	40 9's	(4 8's and 56 9's and 4 ones, 116 tot digits)
5)	8 99 9...				(5 8's, 59 9's and 4 ones until 120th digit)

For $B=10$ , the total is $5·8+59·9+4·1=575$ .

I haven't verified it, but I'm quite sure the total for any $B$ is $5·(B-2)+59·(B-1)+4·1=\boxed{64B-65}$ .

No computer needed

The answer is 63.

2 solutions

0 pending reports