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

 Number of 1s (Posted on 2010-08-26)
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 | Comment 1 of 2

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

 Search: Search body:
Forums (0)