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
solution by reasoning---expanded, part 1
