How many positive integers less than or equal to 100 cannot be written as the sum of distinct powers of 3?
Here are the 23 integers from 1 through 100 that are represented in base 3 by only the digits 0 and 1:
1 1
3 10
4 11
9 100
10 101
12 110
13 111
27 1000
28 1001
30 1010
31 1011
36 1100
37 1101
39 1110
40 1111
81 10000
82 10001
84 10010
85 10011
90 10100
91 10101
93 10110
94 10111
These are the only positive integers less than or equal to 100 that can be written as the sum of distinct powers of 3, so there are 100  23 = 77 that cannot.
Note that if we were doing this analytically we would start by representing 100 as base3: that's 10201. The highest base3 number under this that uses only 0's and 1's is 10111. From there we can treat it as binary, as all binary numbers less than this are valid. 10111 is binary for 23, the number of such configurations, whether interpreted as binary or as ternarythe same 23 we counted.
DefDbl AZ
Dim crlf$
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For n = 1 To 100
r$ = LTrim(base$(n, 3))
good = 1
For i = 1 To Len(r)
If InStr("01", Mid(r, i, 1)) = 0 Then good = 0: Exit For
Next
If good Then
ct = ct + 1
Text1.Text = Text1.Text & n & " " & r & crlf
End If
Next
Text1.Text = Text1.Text & ct & crlf & " done"
End Sub
Function base$(n, b)
v$ = ""
n2 = n
Do
d = n2 Mod b
n2 = n2 \ b
v$ = Mid("0123456789abcdefghijklmnopqrstuvwxyz", d + 1, 1) + v$
Loop Until n2 = 0
base$ = v$
End Function

Posted by Charlie
on 20190409 16:03:12 