(*)

Based on heuristics, I would guess the table is infinite. Proving that would probably be next to impossible. Consider a d-digit value of n. If n is positioned in the right of p(n) then d digits must all match. If the digits are considered random then the probability is 1/10^d. There are 0.9*10^d numbers with d digits, so the expected number of d-digit solutions is 0.9*10^d/10^d = 0.9. Then there are 0.9*d expected solutions with at most d digits. The known small solutions seem consistent with this. This was only for right position and alone gives an infinite number of expected solutions. If p(n) has k digits more than n then there are k+1 possible positions. The left position solutions are likely to come in clusters, when p(n)/n is slightly above a power of 10. This ratio is near 10 for n around 6455 and gave 6 solutions in the table. The next time to expect left solutions is when the ratio reaches 100, around n=10^41.

***

A few minutes before updating this page with the solutions of the week two more contributions arrived:

a) Johann Wiesenbauer also reported 27737957, 527737957, right.

b) Jon Perry made an interesting extension of this puzzle as follows:

Regarding Puzzle 217, I have examined the results if we perform the comparison operation in binary rather than base 10.

Here are my results, for n to 1million.

1(2):[1] -> [1, 0]

5(11):[1, 0, 1] -> [1, 0, 1, 1]

6(13):[1, 1, 0] -> [1, 1, 0, 1]

31(127):[1, 1, 1, 1, 1] -> [1, 1, 1, 1, 1, 1, 1]

32(131):[1, 0, 0, 0, 0, 0] -> [1, 0, 0, 0, 0, 0, 1, 1] 34(139):[1, 0, 0, 0, 1, 0] -> [1, 0, 0, 0, 1, 0, 1, 1] 49(227):[1, 1, 0, 0, 0, 1] -> [1, 1, 1, 0, 0, 0, 1, 1] 50(229):[1, 1, 0, 0, 1, 0] -> [1, 1, 1, 0, 0, 1, 0, 1] 81(419):[1, 0, 1, 0, 0, 0, 1] -> [1, 1, 0, 1, 0, 0, 0, 1, 1] 82(421):[1, 0, 1, 0, 0, 1, 0] -> [1, 1, 0, 1, 0, 0, 1, 0, 1] 1052(8419):[1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0] -> [1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1] 1799(15391):[1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1] -> [1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 3378(31333):[1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0] -> [1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1] 61870(771769):[1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0] -> [1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1] 95752(1240081):[1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0] -> [1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1] 213547(2951341):[1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1] -> [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1] 644695(9677999):[1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1] -> [1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1] 750550(11390809):[1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0] -> [1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1]

The argument as to the finiteness of these sequences seems clearer in binary - as there is no reason why the property should not hold, we can assume with a reasonable confidence that the property holds an infinite number of times, although with decreasing frequency.

An extra question, which I think is probably easier to answer in binary, when do n and n+1 have this property? As 81,82 is the last such pair in my list, is it the last ever pair?

Note that most binary numbers with the property are 'middlers', with the first 'middlers' at 49, in fact all after 1052 are 'middlers', can this be proved?

There are also no 'righters', with the exception of the ambidextrous 31, can this be proved (obviously false for p(2n))?

***

Bill Murphy has found (May, 2003) one more result and the largest (13 digitsd) by now:

He found this "playing around with the "Nth Prime Page" (I have asked him details about how he did this play), and later he confirmed it "with my own calculations"

This is his answer to my question about his method to consult the N-th page:

I was able to confirm this result using a "chunking sieve", but I can explain how to use the Nth prime page to search...

First, I'd checked through P(10,000,000,000) : 252,097,800,623. The next place to hope for a number to satisfy the condition must be a prime above 310,000,000,000. ("3" + "10,000,000,000"). So, into the pi of x page, I entered 310,000,000,000. This then indicated the next digit must be 312,000,000,000. Each further lookup indicated another digit until I narrowed the search to a single possibility and eliminated it.

Then I repeated with "4" + "10,000,000,000" and so on... till I found the one extra result I have reported.

Brute force, and not too elegant...

***

Bill Murphy remains producing more results, so he keeps the record results for this sequence. Congratulations Bill!

On October 6, 2004 he sent two more results (both of the right type):

There are 426,836,115,943 primes less than or equal to 12,426,836,115,943.
There are 732,382,677,641 primes less than or equal to 21,732,382,677,641.

I'm still working to be certain there are no other such primes below 3*10^13, but the nth prime page supports me in the correctness of these, even if others can be found.
 

***