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

Home > Probability
Number of 1s (Posted on 2010-08-26) Difficulty: 1 of 5
Given number of 1s in the binary representation of a natural number is 32. Find the probability that the number is divisible by 3.

Find the probability if the number of 1s is 33.

No Solution Yet Submitted by Praneeth    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution by reasoning---expanded, part 1 Comment 2 of 2 |

     

     

         <i>   A   priori </i> common sense answers are 1/3  for both 32 and 33 ones, the reasoning  being as follows: without limiting ourselves to a certain length (or a range of lengths) of a randomly chosen bit stream it will be either divisible by 3 (call it R0 ) , or be equal

      TABLE style="BORto 1 mod3 or to 2mod3 with equal probability.<o:p></o:p>

      Dealing with infinite quantity of numbers the chance of drawing ca number whose binary representation Includes , say 32 ones
       and 57 zeroes are the same as drawing a number with 61 ones and 2 zeroes.<o:p></o:p>

      Of course there might be a deviation from the said probability, especially in numbers with low quantity of ones
      e.g. p(R0) = 1 for no-ones-number, <o:p></o:p>

      p(R0) = 0 for 1-ones-numbers,regardless of quantity of zeroes, <o:p></o:p>

      p(R0) = 1/2 for 2-ones-numbers,depending on the parity of the quantity of zeros between the two ones, br><o:p></o:p>

       p(R0) = 3/8 for 3-ones-numbers, depending on the distribution of the a/m parities of zeros between the ones etc<o:p></o:p>

      Having said that , we are going to:<o:p></o:p>

      1.           Address the topic of divisibility by 3 of a binary number.<br><o:p></o:p>

      2.           Provide a simplified process to test (even manually) a given number for divisibility by 3.<br><o:p></o:p>

      3.           Provide a recursive and explicit formulas for p(R0,N), and compare   the results with Charlie's
      findings.<o:p></o:p>

      4.          Calculate the deviation from our "1/3 " assumption.<br><br><o:p></o:p>

       <o:p></o:p>

      Ok, here we go.<o:p></o:p>

       <o:p></o:p>

      The well- known rule of divisibility by 11 is as follows:<o:p></o:p>

      The number N is a multiple of 11 <o:p></o:p>

      iff Sum (digits on the even places)-Sum (digits on the odd places)= 0 mod 11.(rule A1)<o:p></o:p>

       <o:p></o:p>

      e.g. 14641 qualifies since (4+4)-(1+6+1)=0    <o:p></o:p>

       <o:p></o:p>

      Tzidon's expansion (easily derived) of this rule:    <o:p></o:p>

      This "trick" is valid in any base, interpreting 11 as a number equal to (base+1 .<o:p></o:p>

      So an octal number 23475342 does not divide 11(nine), since 4+5+4+2-3-7-3-2=2, but<o:p></o:p>

      23475344 divides! Indeed: 23475344 =11*2122504.<o:p></o:p>

       <o:p></o:p>

       <o:p></o:p>

      Example , related to our problem:  Checking for R03 of the binary number 11010111100011<o:p></o:p>

      Direct count : S(odd)=6 S(even)=5 6-5=1mod3 , i.e. this number is 1mod3.<br><o:p></o:p>

      We will not check the truthfulness of our test , but show how to simplify it.<br><o:p></o:p>

      To do this lets write down few lemmas, -they follow easily from rule A1: <br><o:p></o:p>

      1           Any quantity of leading zeros and/or even number of trailing zeros can be erased
      without affecting the result.<o:p></o:p>

      2          Any even quantity of adjacent zeroes can be erased without affecting the result.<br><o:p></o:p>

      3          Same for even quantity of adjacent ones. <o:p></o:p>

      4          10101 may be erased.<o:p></o:p>

      5          The order of applying 1-4 is arbitrary.<o:p></o:p>

       <o:p></o:p>

       <o:p></o:p>

      After applying those rules, until it is no longer possible, we will be left with either an empty set (N is 0mod3) , 1 , 10 or 101 .<o:p></o:p>

      Let us apply #3 to our binary number 11010111100011===>01. <o:p></o:p>

      Our number is 1mod3. <o:p></o:p>

      Feel free to check if it's true.<o:p></o:p>

      To explain formally how to check a long binary number B000001011..000T,in <o:p></o:p>

      Markov algorithm have  I added  a letter B at the beginning and  a T at the end.<o:p></o:p>

       <o:p></o:p>

      B0===>B<o:p></o:p>

      00T===>T<o:p></o:p>

      00===><o:p></o:p>

      11===><o:p></o:p>

      10101===><o:p></o:p>

      101===> . is 2mod 3<o:p></o:p>

      10===> . is 2mod <o:p></o:p>

      1===> . is 1mod 3<o:p></o:p>

      ===> . IS A MULTIPLE OF 3<o:p></o:p>

       <o:p></o:p>

       Remark: In order to differentiate between the residual <o:p></o:p>

      values and not only provide a  yes/no answer regarding the divisibility <o:p></o:p>

      we erase the trailing zeros   two by two   thus enabling ending up with 10  as well as with a 1 <o:p></o:p>To understand what factors cause a number with n ones to be divisible by three

        I started with 2 "ones." We know that lboth leading and trailing zeroes may be ignored. Although the parity of the quantuity of the  trailng  zeroes affects the non zero residual, it cannot affect the divisibility from yes ti no and vice versa. As 2^k +1 divides 3 only when k is odd, the number of zeros between ywo ones must be even , like 11, 1001,10000001 etc.  Thus  the probability of a number consisting of  two ones and some zeros to be a multiple of 3 is 1/2,   i.e.  p(R03,2)=1/2

        For 3 ones there are two spaces between them, thus creating 4 classes of parity distribtion

        Odd & odd, odd &even,even &  odd and even  & even: 10101,1011,1101,111, - used 1 zero for odd and no zero for even .Out of those four (21,11,13,7) only the 1st qualifies , so p(R03,3)=1/4

       

      In a similar way I calculated few more entries and derived both recursive and direct formulas

      for p(R0,N), which I will present later.

      I had before my eyes the following table:

       

      #of ones     p(R0)

      0                    1

      1                      0

      2                     1/2

      3                       1/4  

      4                     3/8

      5                      5/16

      6                      11/32

      7                        21/64       etc  

       

      The a(k ) value represents the probability of a binary numbers with k ones to be a multiple of 3.
      By the same token  q=1-a(k) is the probability of a binary numbers with k ones  not    to be a multiple of 3,q/2 is 1mod3 and the other half 2mod3.It is easy to show that all numbers 0mod 3 with k+1 ones may be generated  by adding either 1or  01  to the binary numbers with a non zero residual.

      Counting carefully ( there is some overlap!) we get

      a(n)=1/2*(1-a(n-1))

       

      Rem:   a(0)=1

       

      In other words : if  a(n-1)=    w/z

      Then              a(n)       =    (2w+(-1)^n)/(2*z)

      Direct definition can be given once you realize that the numbers 1,1,3,5,11, 21  are the   Jacobsthal numbers

          and that  the denominator is 2^(n-1).

      We can therefore write down a look-up formula:  

       

      a(n)=     JACnumb(n+1)/2^(n-1)

       

      a(32)=   JACnum(33)/2^(31)

      a(33)=   JACnum(34)/2^(32)

       

      i.e.  1431655765/2^(31), 2863311531/2^(32)

      TO BE CONTINUED

       

how can I get rid of all the cryptos disturbing  my text???

Edited on August 30, 2010, 3:19 pm
  Posted by Ady TZIDON on 2010-08-28 13:00:29

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 (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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