 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Based on threes! (Posted on 2019-04-09) How many positive integers less than or equal to 100 cannot be written as the sum of distinct powers of 3?

 No Solution Yet Submitted by Danish Ahmed Khan No Rating Comments: ( Back to comment list | You must be logged in to post comments.) solution with computation by program, with a one-paragraph analytic method | Comment 2 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 base-3: that's 10201. The highest base-3 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 ternary--the same 23 we counted.

DefDbl A-Z
Dim crlf\$

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 2019-04-09 16:03:12 Please log in:

 Search: Search body:
Forums (2)