Maths Olympiad Prep

Library / /156 of 348

Algebra Difficulty 4.9 AIME Find the answer

Let b(n)b(n) be the number of digits in the base -4 representation of nn. Evaluate i=12013b(i)\sum_{i=1}^{2013} b(i).

A number or a short expression. Spacing and $ signs are ignored.

Solution

We have the following: - b(n)=1b(n)=1 for nn between 1 and 3 . - b(n)=3b(n)=3 for nn between 4234=44^{2}-3 \cdot 4=4 and 342+3=513 \cdot 4^{2}+3=51. (Since a42b4+ca \cdot 4^{2}-b \cdot 4+c takes on 3443 \cdot 4 \cdot 4 distinct values over 1a3,0b3,0c31 \leq a \leq 3,0 \leq b \leq 3,0 \leq c \leq 3, with minimum 4 and maximum 51.) - b(n)=5b(n)=5 for nn between 4434334=524^{4}-3 \cdot 4^{3}-3 \cdot 4=52 and 344+342+3=8193 \cdot 4^{4}+3 \cdot 4^{2}+3=819. - b(n)=7b(n)=7 for nn between 46345343341=8204^{6}-3 \cdot 4^{5}-3 \cdot 4^{3}-3 \cdot 4^{1}=820 and 346+344+342+3>20133 \cdot 4^{6}+3 \cdot 4^{4}+3 \cdot 4^{2}+3>2013. Thus i=12013b(i)=7(2013)2(819+51+3)=140912(873)=140911746=12345\sum_{i=1}^{2013} b(i)=7(2013)-2(819+51+3)=14091-2(873)=14091-1746=12345

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.