Problems & Puzzles: Puzzles

Puzzle 125. Primes through palindromes

Mr. Huen Y. K. from Singapore, recently sent to me by email an html document attached entitled "Finding large primes is easy!". In this document Mr. Huen proposes to find large primes through the cofactor of odd palindromes with an even number of digits (*). In short he argues that:

The cofactors of odd palindromes with an even number of digits divided by 11 are prime numbers more often than if we choose at random numbers of the same length as the cofactors

As a matter of fact, it can be shown that the cofactors R of numbers N that have been shown composite because they have been divided by K primes (N = p1.p2. ... .pk.R) are more likely to be primes than random numbers Z of the same size than R.

Questions:

1. Can you obtain an expression for p(R)/p(Z), namely the quotient of the relative probabilities of R & Z to be primes numbers?

2. Can you apply your result to the odd palindromes with an even number of digits and verify that/if it matches the Huen's claim?

3. How easy/easier is to hunt primes through the Huen's shortcut?

__________
* Note: You should notice that any palindrome with an even quantity of digits is  always divided by 11.


Solution

Jud McCranie sent (31-1-01) the following synopsis of his research about the Huen's claim & shortcut:

"I find that the cofactor of palindromes with an even number of digits, when divided by 11 are a few more percent more likely than random numbers of the same size.

For example, with 12-digit palindromes, there are 900,000 palindromes between 10^11 and 10^12. 42960 of the cofactors are prime - 4.773%. These cofactors are between 1.0E11/11 and 1.0E12/11. Approximately 3,343,000,000 of the numbers in this range are prime - 4.086%. This gives a ratio of 1.168, so the cofactor of a palindrome is about 16.8% more likely to be prime than a random number in that range.

For 14-digit palindromes, there are 9,000,000 palindromes between 10^13 and 10^14. 358737 of the cofactors are prime - 3.986%. Approximately 3.439% of the numbers between 1.0E13/11 and 1.0E14/11 are prime. This gives a ratio of 1.159, so the cofactor is about 16% more likely to be prime.

For the 16-digit odd palindromes I looked at only ones between 1.0E16 and 2.0E16. You have to take into account the fact that this automatically eliminates numbers divisible by 2 or 5. Of the cofactors when divided by 11, 796645 are prime - 7.966%. These cofactors are between 1.0E15/11 and 2.0E15/11. 3.074% of the numbers in this range are prime. However, this includes numbers that are even or divisible by 5, which are automatically excluded by choosing palindromes ending with the digit 1. So the ratio is 7.966 / (3.074 * 2.5) = 1.037.

So the cofactors of the palindromes seem to be a little more likely to be prime than random numbers of the same size."

***

I (C.R.) got results in the same trend of the McCranie's ones. These are summarized in the following table.

L D #primes(Pal/11) #Pal=10^(L/2-1) p(R) p(Z) p(R)/p(Z)
4

1

4

10

0.400

0.509

0.786

4

3

4

10

0.400

0.434

0.922

4

7

3

10

0.300

0.383

0.783

4

9

3

10

0.300

0.370

0.811

6

1

30

100

0.300

0.263

1.142

6

3

23

100

0.230

0.241

0.954

6

7

24

100

0.240

0.225

1.068

6

9

21

100

0.210

0.220

0.955

8

1

172

1000

0.172

0.177

0.972

8

3

179

1000

0.179

0.167

1.072

8

7

137

1000

0.137

0.159

0.862

8

9

147

1000

0.147

0.157

0.939

10

1

1353

10000

0.135

0.133

1.014

10

3

1311

10000

0.131

0.128

1.027

10

7

1289

10000

0.129

0.123

1.049

10

9

1273

10000

0.127

0.121

1.048

12

1

11150

100000

0.112

0.107

1.041

12

3

10830

100000

0.108

0.103

1.048

12

7

10592

100000

0.106

0.100

1.057

12

9

10388

100000

0.104

0.099

1.046

14

1

93803

1000000

0.094

0.089

1.048

14

3

90814

1000000

0.091

0.087

1.046

14

7

87753

1000000

0.088

0.085

1.037

14

9

86367

1000000

0.086

0.084

1.029

16

1

796645

10000000

0.080

0.077

1.037

16

3

775233

10000000

0.078

0.075

1.036

16

7

757437

10000000

0.076

0.073

1.035

16

9

751701

10000000

0.075

0.073

1.034

* D is the extreme digit of the Palindromes of L digits
* #Pal is the quantity of Palindrome of L digits and extreme digit D
* #primes(Pal/11) is the quantity of primes of the Palindromes after dividing by 11
* p(R) = #primes(Pal/11) / #Pal
* p(Z) is the probability of a number Z of the size of Pal/11 of being prime

The values of the 3rd column are the result of a count of primes that I have made by my own and contain no one supposition. So, this column and the following two (4th & 5th) should be considered objective.

The values of the 6th column is not the product of an exact count of primes but the result of the application of the prime counting function for the average value of Z in the corresponding L & D row, multiplied by the factor 2.5 in order to make a fair comparison of p(Z) against the p(R) value.

I defined the average Z value by the following equation Z=((D+1/2)*10^(L-1))/11; then p(Z) = 2.5/Ln(Z).

The results for p(R)/p(Z) are in good agreement with the values obtained by Jud when he also used the 2.5 factor (L=16, D=1) and thus justify the elections I have made and generalized for the theoretical calculation of Z and p(Z) in any L & D.

The conclusions arising from my table are evident:

For 16=> L=>10 the Huen's shortcut only provides an average benefit of 4% (circa) regarding the purpose of hunting prime numbers, when the proper correspondent type of numbers are compared (palindrome odd numbers not ending in 5 versus random odd numbers not ending in 5 of the same size of the palindrome divided by 11).

Then, hunting prime numbers remains as a hazardous task, even with the Huen's shortcut.

***

Needless to say that my conclusion, now, is also under discussion. It should be viewed only as a counter-thesis to the Huen's thesis (the claimed shortcut) in order to collect more light over the displayed issue (as all the puzzles are intended).

While new criticism arrives, I would say that the following questions remain after the above studies:

* Where does come from this 4% of benefit  associated to the shortcut?
* Will this situation (4%) improve of get worst for L>16, as shortcut?
* Should p(Z) be calculated by another formula "
in order to make a fair comparison of p(Z) against the p(R) value"?...

***

Huen notices also that for any given L & D we may put in correspondence the zero and first 10^(L/2-1) natural numbers to the consecutive Palindromes (for this L & D row), and obtain more primes in the second set (after dividing its members by 11) than in the first set. Example:

For L=6 & D=1

Set1 = {0, 1, 1, 2, 3, ..., 98, 99}
Set2 = {100001, 101101,102201,103301, ..., 198891,199991}
Prime in Set1 = 25
Primes in Set2 = 30

Huen says that apparently the first set should contain more primes than the second, because the members of the first set are - member by member-  lower than the members of the second set. But the real situation is on the contrary: there are more primes in the set of the palindromes than in the set of the natural numbers.

Why is this?

***

Again we must also remind that the elements of the first set runs over numbers even and odds ending in 5 while the elements of the second set even after divided by 11 are always odd and not ending in 5. This explain qualitatively why things got reversed against the immediate expectative. At the end the set of palindrome numbers, despite of being larger than the natural numbers, collect more primes just for the force of persist over odd (but not 5) numbers .

But we may make more precise calculations of the primes in both sets, for each L & D, using the prime counting function, the following way.

Primes in Set1 = 10^(L/2-1)/Ln(10^(L/2-1))

Primes in Set2 [10^(L/2-1)]*[p(Z)] [10^(L/2-1)]*[2.5/Ln(((D+1/2)*10^(L-1))/11)]

You may verify that these approximations to the real primes in both sets confirm the Huen's observation about the relative quantity of primes in Sets 1 & 2, and explain it in detail.

Primes in Set2/Primes in Set1 goes to the value 1.25 as L goes to infinite for any D. This quotient is not comparable to the quotient calculated by Jud Enoch and myself because Primes in Set2/Primes in Set1 is dividing different things than p(R)/p(Z).

***

After reading the Jud's contributions, Huen wrote this:

"I have read Jud McCranie's contribution which is interesting and by and large confirms my observations. Any doubt of the efficacy of the shortcut could arise from the method of comparing prime hits between the natural and the palindrome sequences.  I think that a standardized method of comparison needs to be formulated.  For example, if in the palindrome sequence we know where the primes concentrate whereas in the natural number sequence we do not have this knowledge, then this would bias prime hits in favor of the former. This aspect has not been considered yet by anyone. I would need to study in detail over the next few days to be able to offer my response to some points raised by him by including my latest findings."

***

Enoch Haga sent the following lines:

"After a care reading of paragraph 2, I note that Huen does not define the "random numbers of the same length (as) the cofactors" in detail. To me it makes sense that no one looking for primes in random numbers would select those ending in 2, 4, 5, 6, or 8. Accordingly, I have removed these from the random runs.

Now the palindromes and the randoms are selected on the same basis, except that the palindromes were 10-digit odd, while the randoms were 1000 8-digit odds and 39000 9-digit odds. As I see it, now we are comparing apples to apples.

To find a "stable" number, I have found the mean of 10 runs for each of the 8- and 9-digit randoms. What I have now is:

PALINDROMIC COFACTORS:

132/1000 = 13.2% 8-digit
5094/39000 = 13.1% 9-digit
Total - 5226/40000 = 13.1%
132/5226 = 2.5% of total palindromic cofactors
5094/5226 = 97.5% of total palindromic cofactors

RANDOMS:

141/1000 = 14.1% 8-digit
4812/39000 = 12.3% 9-digit
Total - 4953/40000 = 12.4%
141/4953 = 2.85% of total random primes
4812/4953 = 97.15 of total random primes

So now, I will answer the questions:

1) p(R) / P(z) = .131 / .124 = 105.6%
2) Huen's claim is validated minimally at the level of 10-digit odd
palindromes (5's not counted).
3) Unless the ratio improves for larger odd palindromes, I don't see much advantage to using Huen's method.

***

Felice Russo made an interesting exploration of the Huen's shortcut for L=10, 12, ...60 generating 1000 odd palindromes with L digits at random for each L, counting the primes after dividing the palindromes by 11, in order to calculate an approximation to p(R). Then he compared this p(R) against the theorical p(Z) provided by the prime counting function. Here are his results and conclusions for one run:

 
L primes p(R)/p/(Z)
10 136 0.136/0.120=1.133
12 119 0.119/0.098=1.214
14
85
0.085/0.083=1.024
16
73
0.073/0.072=1.013
18
87
0.087/0.064=1.359
20
46
0.046/0.057=0.807
22
44
0.044/0.052=0.846
24
63
0.063/0.047=1.340
26
33
0.033/0.043=0.767
28
43
0.043/0.040=1.075
30
34
0.034/0.037=0.918
32
40
0.040/0.035=1.143
34
31
0.031/0.033=0.939
36
28
0.028/0.031=0.903
38
33
0.033/0.029=1.138
40
29
0.029/0.028=1.036
42
33
0.033/0.026=1.269
44
22
0.022/0.025=0.880
46
20
0.020/0.024=0.833
48
24
0.024/0.023=1.043
50
21
0.021/0.022=0.954
52
17
0.017/0.021=0.809
54
16
0.016/0.020=0.800
56
19
0.019/0.019=1.000
58
19
0.019/0.019=1.000
60
18
0.018/0.018=1.000

"...About P(Z) I calculated it using the well known formula P(R)=2.5*1/(d*ln10) where d is the number of digits of the random number R [d=L-1]. The factor 2.5 take in account the fact that R is not divisible by 2 and by 5... If we calculate the median value and the mean of all the ratios between 10 and 60 we obtain: Mean=1.009 Median=1.0 . According to those experimental results looks like that for big palindrome numbers the Huen's shortcut doesn't give any advantage".

While certainly the Russo's result are the results for one run, and different runs can provide different absolute values of the second column, and eventually different absolute values of the last column, it's hard to expect great variations in these last values, and much less probable is to expect great variations in the mean & median statistical values for the p(R)/p(Z) of any entire defined table. In any case the Russo's approach shows a simple route to test statistically the Huen's shortcut for larger L values.

***

 

 


Records   |  Conjectures  |  Problems  |  Puzzles