All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Based on threes! (Posted on 2019-04-09) Difficulty: 3 of 5
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 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$


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 2019-04-09 16:03:12
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (4)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information