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 (C.R.) got results in the same trend of the McCranie's ones. These are summarized in the following table.

* 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:

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