More fun in 2015, Part 13

Probability Level 5

How many integers $a$ with $1\leq{a}\leq{2015}$ can be written as a sum of numbers of the form $5^0,5^1,5^2, \ldots$ , where each power of 5 may be used at most three times?

The answer is 844.

1 solution

Pi Han Goh
May 25, 2015

I define a number of the form "modified base 5 with maximum number 3". And I'm going to use colours to assign that number. For example, $\color{#D61F06}{A_1 A_2 A_3 A_4 A_5} = A_1 \times 5^4 + A_2 \times 5^3 + A_3 \times 5^2 + A_4 \times 5^1 + A_5 \times 5^0$ with integers, $0 \le A_1, A_2, A_3, A_4, A_5 \le 3$ .

Suppose $A_1 < 3$ , then the maximum value of the number is $\color{#D61F06}{23333} = 2\cdot 5^4 + 3(5^3 + 5^2 + 5^1 + 5^0) < 2015$ . So we can have $3\times 4^4=768$ possible values of values of $a$ . But since $a> 0$ , then $\color{#D61F06}{00000}$ is not possible, so there's only $767$ possible values of $a$ .

Now suppose $A_1 = 3, A_2 = 0$ , then the maximum value of the number is $\color{#D61F06}{30333} < 2015$ . So we can have another $4^4 = 64$ possible numbers of $a$ .

Again, suppose $A_1 = 3, A_2 = 1$ , then $A_3 = 0$ else the number will exceed $2015$ because it's minimum value is $\color{#D61F06}{31100} =2025 > 2015$ .

So we just need to check for integer values of $0\leq x,y \leq 3$ such that $\color{#D61F06}{310xy} \leq 2015$ .

It can be easily verified that if $x=0,1$ or $2$ , they each produce 4 values of $y$ . Thus another $4\times3 =12$ solutions.

Lastly, at $x=3$ , $y$ is forced to be $0$ because it already attains a maximum value. $\color{#D61F06}{31030} = 2015$ .

Hence, a total of $767 + 64 + 12 + 1 = \boxed{844}$ solutions.

Moderator note:

There is a simpler way to understand how to do the counting. See Otto's comment below. It effectively establishes the bijection that we want, which avoids having to do multiple case analysis.

Yes! Nice clear solution! (+1)

The way I did it was more along Vishnu's lines. The short version: $2015_{10}=31030_5$ and $31030_4=844_{10}$ . (In base 5, we seek the numbers up to $31030_5$ that do not contain the digit 4; those are in one-to-one correspondence with all the 844 numbers up to $31030_4$ in base 4.)

Otto Bretscher - 6 years ago

I made a stupid stupid silly mistake and didn't get the answer. Your modified base 5 is nothing but base 4 except the numbers are converted to decimal using powers of 5.

2015=31030 in base 5. I made a mistake and got 2015=31010. Damn It!!!!

But this is how I did it:

Since the question asks for the number of numbers , we just need the value of 2015 in base 5 = 31030 and we can work with numbers in base 4 from now on.

31030 in base 4=844 DEC.

And that's your answer. As simple as that. But I was stupid enough to proceed without checking my results. DAMN IT!

vishnu c - 6 years ago

Great! (+1)

Don't be too harsh on yourself because of that silly computational error... it happens to all of us (I get most of the "simple" Brilliant problems wrong for that reason)

Otto Bretscher - 6 years ago

Hi Otto Love your problems and elegant solutions Perhaps you would solve the following problem for me find the sum of the roots of the equation (1/x^2-1)+(1/x^2-2)+(1/x^2-3)+(1/x^2-4)=2010x-4

Des O Carroll - 6 years ago

Also note that if the number was something like 31044 in base 5 instead of 31030 base 5 =2015 DEC, then you have to go to the greatest number in base 5 that's less than the given number such that the number exists in base 4, i.e, no 4's allowed. So you need to replace the 4s with 3s and then get the value of that number in base 4 converted to DEC.

So in my example, you have 31044. The greatest number satisfying my criteria above is: 31033. which is 2018. 3 years later maybe someone will post a similar question : )

vishnu c - 6 years ago

One more thing that I'd like to add is that it's base 4 because you can use 0,1,2,3 to fill up the places. The counting 0 problem here does not arise because counting starts with 1 (in any base).

So if there was some other condition that said that you can only use prime numbers or something like that, then you can use 2, 3 to represent the digits in base 5. Then you'd have to convert the number to base 2 to get the answer straightaway. This time the criteria is different though. You need to change 2 to 0 and 3 to 1 or something like that and then convert all the 4s to 3s if there are any. Damn it! I'm really fed up with silly mistakes.

vishnu c - 6 years ago

@Otto Bretscher , I just solved Part 10 . Basically, it's just tedious work. Like your other question , and with your reference . I just need to find the numbers from 1 to (the period). The rest should be obvious but yet still tedious, got a better approach? For some reason that note Dylan Pentland created reminds me of Graham's number.

Pi Han Goh - 6 years ago

Can you show us your solution, at least a rough outline? Please... I don't have a "silver bullet" solution in this case... I was just checking whether Dylan's observation works for even numbers.

From Dylan's work, we know that the congruency holds for odd $a$ ... let's just look at the even case.

Otto Bretscher - 6 years ago

All the tedious work... Modular arithmetic > Euler Theorem / Fermat Little Theorem mix with CRT.

Check for < 20. Then check for < 15 because in between 2000 to 2015.

And we can easily know that 6 and 16 are the answers for the range < 20 because (...6)^(some integer) = (.... 6)

That's why I asked whether there is a better approach.

Pi Han Goh - 6 years ago

More fun in 2015, Part 13

The answer is 844.

1 solution

Moderator note:

0 pending reports