Problems & Puzzles: Puzzles

Puzzle 217. n in pn

Recently a reader asked a question that I have transformed in a more general one:

Find these primes pn such that n is in pn

Here are a few of them:

 n pn Position of n in pn 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' pn (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 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:

 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 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.

***

____
* Please notice the beast number inside...

 Records   |  Conjectures  |  Problems  |  Puzzles