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

Home > Just Math
Counting ones (Posted on 2018-06-18) Difficulty: 2 of 5
How many ones are used in writing all of the numbers from 0 to 2018 (inclusive) in binary form?

See The Solution Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution analytic solution, with computer verification Comment 2 of 2 |
2048 = 2^11 so the numbers below this all have 11 or fewer binary digits. Allow leading zeros so that all have exactly 11 bits. From 0 through 2047, there are 2048*11=22528 binary digits, of which half are 1 bits as every ordered set of binary digits is present. That's 11264 1-bits.

But we want to go only through 2018 and so must subtract out the 1 bits from 2019 through 2047. That's

11111100011  through
11111111111

There are 2047-2018 = 29 of these numbers, so

The high-order 6 bits account for 6*29=174 1-bits.

If the range had included 32 numbers there'd be 32*5/2 1-bits accounted for by the low-order five bits, or 80 of them, but two of these are not in the range: in 00001 and 00010. That makes 78 to be subtracted out on this basis.

So 11264 - (174+78) = 11012 1-bits are in the range asked for.

then

DefDbl A-Z
Dim crlf$


Private Sub Form_Load()
 Form1.Visible = True
 Text1.Text = ""
 crlf = Chr(13) + Chr(10)
 
 For i = 1 To 2018
   b$ = base$(i, 2)
   For j = 1 To Len(b)
     If Mid(b, j, 1) = "1" Then tot = tot + 1
   Next
 Next
 
 Text1.Text = Text1.Text & crlf & tot & " done"
  
End Sub

Function base$(n, b)
  v$ = ""
  n2 = n
  Do
    q = Int(n2 / b)
    d = n2 - q * b
    n2 = q
    v$ = Mid("0123456789abcdefghijklmnopqrstuvwxyz", d + 1, 1) + v$
  Loop Until n2 = 0
  base$ = v$
End Function
 
 
finds 11012 also. 

  Posted by Charlie on 2018-06-18 11:13:43
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


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

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