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 (31101) 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 12digit 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 14digit 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 16digit 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/21) 
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^(L1))/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 counterthesis 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/21) 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/21)/Ln(10^(L/21))
Primes in Set2 »
[10^(L/21)]*[p(Z)] »
[10^(L/21)]*[2.5/Ln(((D+1/2)*10^(L1))/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 10digit odd, while the randoms
were 1000 8digit odds and 39000 9digit 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 9digit randoms. What I have now is:
PALINDROMIC COFACTORS:
132/1000 = 13.2% 8digit
5094/39000 = 13.1% 9digit
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% 8digit
4812/39000 = 12.3% 9digit
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 10digit
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=L1]. 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.
***
