Problems & Puzzles:
Puzzles
Puzzle 217.
n in p_{n}
Recently a reader asked a question that I
have transformed in a more general one:
Find these primes p_{n} such that n is
in p_{n}
Here are a few of them:
n 
p_{n} 
Position of n in p_{n} 
7 
17 
right 
6455 
64553 
left 
6456 
64567 
left 
6457 
64577 
left 
6459 
64591 
left 
6460 
64601 
left 
6466 
64661 
left 
9551 
99551 
right 
303027 
4303027 
right 
440999 
6440999 
right 
968819 
14968819 
right 
5517973 
95517973 
right 
Questions:
1. Is there a case
where n is 'inside' p_{n} (that is to say not to the right, not to the
left)? If so, can you find the least example?
2. Can you extend this
table?
3. Is this Table finite
or infinite?
Solution:
Bill Murphy and J. K. Andersen
found independently more and the same new entries for our table:
n 
p(n) 
Position of n in p(n) 
27737957 
527737957 
right 
93230839 
1893230839 
right 
96664044 
1966640443 
middle

(*)
Murphy adds:
"Checked all primes up to P(370110660): 8053063589
For the question 3, J. K Andersen
argued:
Based on heuristics, I would guess the table is
infinite. Proving that would probably be next to impossible. Consider a
ddigit 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 ddigit 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:
n 
p(n) 
Position of n in p(n) 
46492090901 
1246492090901 
right 
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 Nth 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.
***
____
* Please notice the beast number
inside...
