Problems & Puzzles: Puzzles

Puzzle 680 The largest palindrome prime-proof odd integer race “Prime-proof odd integers” are odd composite numbers not ending in 5 that remain composite even when a single decimal digit of the number is changed. For the origins of these numbers see: 1 & 2 For our Puzzle 679 J. K. Andersen sent one large example of a palindrome case: A 2013-digit example: (10^2013-1)/9 + 65161816156*10^1001. Q1. Send your largest palindrome prime-proof odd integer example. Q2. What is the population law for these kind of integers? It's easier or harder to get larger examples? Please send your comments for both issues.

---

Contributions came from Emmanuel Vantieghem and J. K. Andersen.

***

Emmanuel wrote

I  only made a small research on palindromic prime-proof numbers less than  10^15.

The number  k_n  of such numbers in the intervals  [10^n, 10^(n+1)]  for  n = 0, 1, 2, ... , 14  is :

     0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 17, 7, 163, 58, 1831.

So, I think the value of  k_n  increases with  n.  However, the time to find them grows in such a way that the chance of finding them decreases.  I was able to find a 400-digit example in a reasonable time (= a few hours) :
 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999422566522499999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999

However, a 1000-digit example did not came out after more than 10 hours. Therefore, I think Andersen's record will stand for a while.

***

Andersen wrote:

Q1. A solution with 10001 digits:
(10^10001-1)/9 + 8822446442288*10^4994.
Tested with PrimeForm/GW after a C program identified promising palindromes
with many small factors in the numbers. The chance was above 1% for each
tested palindrome.
Without the palindromic condition, it should be possible to generate
arbitrarily large solutions with a covering set of prime factors.
This strategy, even for a partially covering set, seems hard to combine
with a palindrome.

Q2. Suppose a large odd palindrome has n digits and doesn't end in 5.
For simplicity, let's ignore the initial number must be composite and assume
there are 9n independent numbers around 10^n which are not divisible by 2 or 5
(inaccurate for some changes of the last digit).
A rough estimate of the chance all 9n numbers are composite, based on
the prime number theorem with adjustment for indivisibility by 2 and 5:
(1 - (2 * 5/4)/log(10^n))^(9n) ~= ((1-1.086/n)^n)^9

If the palindrome has an even number of digits then it's always divisible by
11, and none of the 9n changes are. This gives a further adjustment:
(1 - (2 * 5/4 * 11/10)/log(10^n))^(9n) ~= ((1-1.194/n)^n)^9

(1+x/n)^n tends to e^x when n tends to infinite. Then the odd and even
estimates tend to respectively
(e^(-1.086))^9 ~= 1/18000, and (e^(-1.194))^9 ~= 1/47000.

So we expect an approximately constant ratio of solutions, with more for an
odd number of digits. Below are actual counts of solutions for 9 to 16 digits
out of all odd palindromes not ending in 5. The estimates from the above
formulas are shown in parentheses.
As expected, there are no solutions for 1-8 and 10 digits.

digits: count (estimate)
9: 2 out of 40000 = 1 in 20000 (1 in 33296)
10: 0 out of 40000             (1 in 93604)
11: 17 out of 400000 = 1 in 23529 (1 in 29383)
12: 7 out of 400000 = 1 in 57143 (1 in 82623)
13: 163 out of 4000000 = 1 in 24540 (1 in 27009)
14: 58 out of 4000000 = 1 in 68966 (1 in 75745)
15: 1831 out of 40000000 = 1 in 21846 (1 in 25421)
16: 596 out of 40000000 = 1 in 67114 (1 in 71048)

The counts are not that far from the estimates. Simplifying assumptions
were made so precise estimates were not expected.

***