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.

The rightmost bit position has value 2^0, which is 1 mod 3. The next position represents 2^1, which is -1 mod 3. The values mod 3 alternate +/- 1.

As bits are added, one by one, (from an infinite number of possible positions?), the value mod 3 may go up or down by 1.

With only one bit, there is 50% probability the value will be -1 mod 3, and 50% probability it will be 1 mod 3.

Each subsequent added bit has probability 1/2 of being -1 and 1/2 of being 1. If you work out the transitional probabilities it turns out that in going from n bits to n+1 bits, the probability of each of the three possible mod values becomes the average of the prior probabilities of the other two values, so for example with two bits, the probability is 1/4 of being -1 mod 3 (that is, 0*1/2 + (1/2)*1/2); the probability is 1/2 of being 0 ((1/2)*1/2 + (1/2)*1/2); the probability of being 1 is 1/4 ((1/2)*1/2 + 0*1/2).

Subsequent numbers of bits can be handled in the same manner, transitioning from the previous number of binary digits:

bits    Prob of -1 0 or 1 mod 3
 1       1/2  0  1/2
 2       1/4  1/2  1/4
 3       3/8  1/4  3/8
 4       5/16  3/8  5/16
 5       11/32  5/16  11/32
 6       21/64  11/32  21/64
 7       43/128  21/64  43/128
 8       85/256  43/128  85/256
 9       171/512  85/256  171/512
 10      341/1024  171/512  341/1024
 11      683/2048  341/1024  683/2048
 12      1365/4096  683/2048  1365/4096
 13      2731/8192  1365/4096  2731/8192
 14      5461/16384  2731/8192  5461/16384
 15      10923/32768  5461/16384  10923/32768
 16      21845/65536  10923/32768  21845/65536
 17      43691/131072  21845/65536  43691/131072
 18      87381/262144  43691/131072  87381/262144
 19      174763/524288  87381/262144  174763/524288
 20      349525/1048576  174763/524288  349525/1048576
 21      699051/2097152  349525/1048576  699051/2097152
 22      1398101/4194304  699051/2097152  1398101/4194304
 23      2796203/8388608  1398101/4194304  2796203/8388608
 24      5592405/16777216  2796203/8388608  5592405/16777216
 25      11184811/33554432  5592405/16777216  11184811/33554432
 26      22369621/67108864  11184811/33554432  22369621/67108864
 27      44739243/134217728  22369621/67108864  44739243/134217728
 28      89478485/268435456  44739243/134217728  89478485/268435456
 29      178956971/536870912  89478485/268435456  178956971/536870912
 30      357913941/1073741824  178956971/536870912  357913941/1073741824
 31      715827883/2147483648  357913941/1073741824  715827883/2147483648
 32      1431655765/4294967296  715827883/2147483648  1431655765/4294967296
 33      2863311531/8589934592  1431655765/4294967296  2863311531/8589934592
 
as decimal fractions these are:
 
  1       0.5  0  0.5
  2       0.25  0.5  0.25
  3       0.375  0.25  0.375
  4       0.3125  0.375  0.3125
  5       0.34375  0.3125  0.34375
  6       0.328125  0.34375  0.328125
  7       0.3359375  0.328125  0.3359375
  8       0.33203125  0.3359375  0.33203125
  9       0.333984375  0.33203125  0.333984375
  10      0.3330078125  0.333984375  0.3330078125
  11      0.33349609375  0.3330078125  0.33349609375
  12      0.333251953125  0.33349609375  0.333251953125
  13      0.3333740234375  0.333251953125  0.3333740234375
  14      0.33331298828125  0.3333740234375  0.33331298828125
  15      0.333343505859375  0.33331298828125  0.333343505859375
  16      0.3333282470703125  0.333343505859375  0.3333282470703125
  17      0.33333587646484375  0.3333282470703125  0.33333587646484375
  18      0.333332061767578125  0.33333587646484375  0.333332061767578125
  19      0.3333339691162109375  0.333332061767578125  0.3333339691162109375
  20      0.3333330154418945312  0.3333339691162109375  0.3333330154418945312
  21      0.3333334922790527343  0.3333330154418945312  0.3333334922790527343
  22      0.3333332538604736328  0.3333334922790527343  0.3333332538604736328
  23      0.3333333730697631835  0.3333332538604736328  0.3333333730697631835
  24      0.3333333134651184082  0.3333333730697631835  0.3333333134651184082
  25      0.3333333432674407958  0.3333333134651184082  0.3333333432674407958
  26      0.3333333283662796020  0.3333333432674407958  0.3333333283662796020
  27      0.3333333358168601989  0.3333333283662796020  0.3333333358168601989
  28      0.3333333320915699005  0.3333333358168601989  0.3333333320915699005
  29      0.3333333339542150497  0.3333333320915699005  0.3333333339542150497
  30      0.3333333330228924751  0.3333333339542150497  0.3333333330228924751
  31      0.3333333334885537624  0.3333333330228924751  0.3333333334885537624
  32      0.3333333332557231187  0.3333333334885537624  0.3333333332557231187
  33      0.3333333333721384406  0.3333333332557231187  0.3333333333721384406
  

The middle of the three values, the probability that the number is zero mod 3, is the sought value and the last two of these are the two parts asked for in the puzzle.

For first table:

   10   Pm=1//2:Pp=1//2:Bits=1:Pz=0
   20   for Bits=1 to 33
   30     print Bits,Pm;Pz;Pp
   40     PmNew=(Pp+Pz)//2
   50     PzNew=(Pp+Pm)//2
   60     PpNew=(Pz+Pm)//2
   70     Pp=PpNew:Pz=PzNew:Pm=PmNew
   80   next
   
For second table:

 10   Pm=1//2:Pp=1//2:Bits=1:Pz=0
 20   for Bits=1 to 33
 30     print Bits,Pm/1;Pz/1;Pp/1
 40     PmNew=(Pp+Pz)//2
 50     PzNew=(Pp+Pm)//2
 60     PpNew=(Pz+Pm)//2
 70     Pp=PpNew:Pz=PzNew:Pm=PmNew
 80   next   

Posted by Charlie on 2010-08-27 13:25:04