I love Threes!

There are 101 non-negative integers less than or equal to 100.

If you want a number to be sum of powers of $3$ , then it's representation in base $3$ can have only the digits $0$ and $1$ .

Observe that the maximum power of $3$ less than 100 is 4. ( $3^4 =81<100$ )

Thus the representation of our numbers (all numbers till 100) can be of maximum length of 5 digits !

For example, $28 = 1001$ in base 3, so it's $3^3+3^0$ .

In our base 3 representation if it's 4 digit and the number can be written as sum of powers of 3, then it can at the max be $1111_3 = 27+9+3+1 = 40$ (in base 10)

Thus all the numbers which have only 0 or 1 in their respective base 3 representation are at max 4 digit are to be firstly counted .

All the 4 digits have 2 choices (0 or 1) so there will be $2^4=16$ numbers which have at the max 4 digit representation in base 3 ( 0 is also included).

What remains to count is numbers which have only 0 or 1 in the base 3 representation and are 5 digit long. They are $10000,10001,10010,10011,10100,10101,10110,10111$ which are $81,82,84,85,90,91,93,94$ respectively in base 10, giving 8 more numbers.

Hence we have 24 numbers less than 100 which can be written as sums of powers of 3. Thus out of the total 101 numbers, the 24 are reduced , hence there'll be $101-24=\boxed{77}$ numbers.

If we write numbers as base 2 with 5 digits such that $1$ in digit $n$ (from right to left) has the value of $3^{n-1}$ . (Ex. $10110 = 3^4 + 3^2 + 3^1$ )

We get $00001, 00010, 00011, 10111 (\text{max})$ .

Now it's the job of combinatorics to count those numbers. $2^{5} - 2^{3} - 1= 23$ .

Therefore, the number of positive integers from $1$ to $100$ that doesn't satisfy that $= 100 - 23 = \boxed{77}$ ~~~ Meow!!!

is the highest power of 3 that can be present. So the given task boils down to the following problem. For a given equation

we have to find all possible combinations of values of

Here all the can only have two possible values 0 or 1.

Solution:

5 nos. possible 3^0 3^1 3^2 3^3 3^4

Take 4 nos. 3^(0,1,2,3).

No of ways they can form a no. = 2^4 -1=15

(-1 for 0)

Take next 4 nos. 3^(0,1,2,4).

No of ways they can form a no. = 2^4 -1=15

Remove common nos. 3^(0,1,2).

No of ways they can form a no. = 2^3 -1=7

Total no of ways a no. cannot be formed = 15+15-7=23

My solution is based on combinatorics. Here it goes: Powers of 3 which can be considered (satisfying the given conditions): 0,1,2,3,4.... (5 distinct values)...... We can choose 1 or 2 or 3 or 4 values at a time.. (can't choose 0 values or 5 values(>100) ) So, 5C1+5C2+5C3+5C4 = 2^5-2 = 30 ...... Now the only thing that remains is to eliminate "selections" that do not satisfy the condition (natural no < 100)... observe all such selections will contain 81 (the largest power ... closest to 100)... For 1 selection: 0 For 2 selection: 1 (81,27) For 3 selection: 3 (81,27,x) ... x= {1,3,9} For 4 selection: 3 (81,27,x,y) ... x,y = {1,3,9} and x not= y So total no of valid selections = 30-(1+3+3)=23 .... (each selection results in a unique natural no. as all constituent elements are +ve and distinct..) So, numbers which cannot be formed 100-23 = 77 values

Hope this helps :-)

I probably did this the hard way, and also couldn't figure out how to write choose in the text editor, but here goes. So you know that the largest power of $3$ you can have is $3^{ 4 }=81$ . Next largest is $27$ , $9$ , $3$ . $1$ . Now we can't add $27$ to $81$ because it will be greater than $100$ . So we can only add combinations of $9$ , $3$ , and $1$ to $81$ . So we have $81$ + 3 choose 1 + 3 choose 2 + 3 choose 3. $27$ can't be added to $81$ , but can be added to combinations of $9$ , $3$ , and $1$ so we have $27$ + 3 choose 1 + 3 choose 2 + 3 choose 3. likewise we have $9$ + 2 choose 1 + 2 choose 2, and finally we have $3$ + 1 choose 1. All we do is total up the number of combinations and we get $23$ , so $100-23=\boxed { 77 }$

The bases solution was already very good. However, if you, like me, don't like working with bases, then you can use this solution. Considering just 1, 3, 9, and 27, we can choose any combination of them to sum up, because the total sum is less than 100. Using set theory, the number of ways is $2^4 = 16$ . Note that this also includes the null set. Therefore, there are actually 15 ways.

Now, including 81, we have to have a sum of any combination of 1, 3, 9, and 27 that is $\le 19$ . 27 can't be used, but any combination of 1, 3, and 9 can be used because $9+3+1 = 13 \le 19$ . Using set theory again, we have $2^3 = 8$ . This time, the null set can be used as we are adding to 81. Therefore, the total possible combinations is $15+8 =23$ , and the answer is $\boxed{77}$ .