How many positive integers less than or equal to 100 cannot be written as the sum of distinct powers of 3?
(In reply to
Puzzle Answer by K Sengupta)
Positive integers that can be written as the sum of distinct powers of 3 must contain only 0s and 1s (no 2s) in its ternary (base 3) representation.
Now we observe that:
100 =3^4 +2*3^2 +1 and hence equal to 10201 in base 3.
The ternary number immediately less than 10201 which is constituted entirely by 0s and 1s is 10111 (94 in base 10).
So the corresponding ordinal value(or, count) is obtained by expressing 10111 as a binary number which is 23 in base 10.
Accordingly, precisely 23 positive integers <= 100 can be written as sum of distinct powers of 3.
Consequently, # positive integers <= 100 which is NOT inclusive of the foregoing property must be 100-23 = 77
Explanation to Puzzle Answer
