Base Number Counting

How many integers between 1 and 1992 do not contain a 2 when written in base 3? (Source: Mandelbrot)

1328 1993 351 664 127

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.

4 solutions

Leo Yang
Jun 1, 2020

For this problem, we can easily see that any number that does not contain a 2 when written in base 3 must contain only 1s and 0s. This means that the number is a sum of different powers of 3. We can list all the powers of 3 like this: 1, 3, 3^2, 3^3, 3^4, 3^5, 3^6. Then the number of combinations of these numbers or the number of subsets of these numbers is 128. However, we exclude the empty set, so there are 127 possible combinations. We can check that 1+3+3^2+3^3+ ... +3^6 does not exceed 1992 so all 127 combinations are valid. Therefore, the answer to the question is 127.

Brilliant approach, I was entangled in a mess of bijection and creating a binomial.

Mahdi Raza - 1 year ago
Pavan Kartik
Jun 2, 2020

i converted 1992 to base 3 =2201210 and there is a maximum of seven digits in our number. each digit can either be a 0 or a 1( which is 2 options), and since there are 7 digits, there are 2^7=128 possibilities for our number. We exclude the case where all 7 digits are 0(0<1) so now we have 128-1 =127 numbers

The general formula to find the numbers of integers from 1 1 to N N , where 2 3 n 1 N < 3 n 2 \cdot 3^{n-1} \le N < 3^n , which do not contain digit 2 2 when written in base 3 3 is:

n 3 , 2 = 2 n 1 \large n_{3,\overline 2} = 2^n - 1

Since 2 3 6 < 1992 < 3 7 2\cdot 3^6 < 1992 < 3^7 , 199 2 3 , 2 = 2 7 1 = 127 \implies 1992_{3,\overline 2} = 2^7 - 1 = \boxed{127} .

Proof :

1 , 2 2 3 , 2 = 2 1 1 = 1 1 , 10 , 11 6 8 3 , 2 = 2 2 1 = 3 1 , 10 , 11 , 100 , 101 , 110 , 111 18 2 6 3 , 2 = 2 3 1 = 7 \begin{array} {cl} 1, \red{\cancel 2} & \implies 2_{3,\overline 2} = 2^1 - 1 = 1 \\ 1, 10, 11 & \implies 6\to 8_{3,\overline 2} = 2^2 - 1 = 3 \\ 1, 10, 11, 100, 101, 110, 111 & \implies 18 \to 26_{3,\overline 2} = 2^3 - 1 = 7 \end{array}

The question is actually easier than it looks. Let's look at the question. It asks, "How many numbers between 1 and 1992 can be expressed in base 3 without a 2 in it?" The only numbers in base 2 are 0,1. So this question is literally asking how many numbers in base 3 can be also written in base 2 without regrouping. Converting 1992 to ternary, we have 2201210. The largest base 3 number less than 2201210 that can be written in base 2 without regrouping is 1111111. So that is the largest base 2 number we need to count. Converting 1111111 to base 10 we get 127. So that means there are 127 numbers between 1 and 1992 that can be written in base 3 without a 2.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...