3 2 and begins to write them down in ascending order. The first few terms of her sequence look like this:
One day for no apparent reason, Brilli the ant decides to add up different non-negative powers of1 , 3 2 , 3 3 , 1 0 2 4 , 1 0 2 5 , 1 0 5 6 , 1 0 5 7 , 3 2 7 6 8 , 3 2 7 6 9 , 3 2 8 0 0 , 3 2 8 0 1 . . .
If 3 5 4 6 7 0 6 7 3 9 3 is the N th term of this sequence, what is N ?
Details and assumptions:
A term can be the sum of more than two different powers of 3 2 . For example: 3 2 8 0 1 = 3 2 3 + 3 2 1 + 3 2 0 .
A term can be the "sum" of one number. For example: 1 0 2 4 = 3 2 2 is a term of this sequence.
A term, however, can't be the "sum" of zero numbers. In other words, 0 isn't in this sequence.
A term also has to be the sum of distinct numbers. That means 6 5 = 3 2 1 + 3 2 1 + 3 2 0 is not in the sequence.
This problem was inspired by a problem posed in the BdMO-2013 divisional round.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The distinctness of the powers and a specific base instantly forces one to think about base conversions. We try base 3 2 and rewrite the sequence:
1 , 1 0 , 1 1 , 1 0 0 , 1 0 1 , . . .
It's the list of consecutive binary integers (it's obvious since the expansion of terms don't have any additional coefficients). The rest is straightforward.
3 5 4 6 7 0 6 7 3 9 3 = 1 1 1 0 1 0 0 1 3 2
1 1 1 0 1 0 0 1 2 = 2 3 3
∴ N = 2 3 3
Let's write this sequence in a different way.. we will convert each number to base 32:
[ 1 , 1 0 , 1 1 , 1 0 0 , 1 0 1 , 1 1 0 , 1 1 1 , 1 0 0 0 , 1 0 0 1 , . . . ]
Those familiar with binary should recognize a very clear pattern. These are the consecutive natural numbers in base 2!
After some calculations (find the greatest n such that 3 2 n < 3 5 4 6 7 0 6 7 3 9 3 , subtract and repeat), it can be found that 3 5 4 6 7 0 6 7 3 9 3 ≡ 1 1 1 0 1 0 0 1 when represented in base 32. To calculate this number's place in the sequence, we simply convert 1 1 1 0 1 0 0 1 to decimal, as if it were binary.
1 + 8 + 3 2 + 6 4 + 1 2 8 = 2 3 3
Problem Loading...
Note Loading...
Set Loading...
If we rewrite the numbers in the base of 32, we get the consecutive binary natural numbers.
( 3 5 4 6 7 0 6 7 3 9 3 ) 1 0 = ( 1 1 1 0 1 0 0 1 ) 3 2 ,So the answer is ( 1 1 1 0 1 0 0 1 ) 2 = ( 2 3 3 ) 1 0