[seqfan] Hopping for primes

[Peter Luschny]

Hopping for primes.

Given n >= 1, find the first prime that lies on the grid
[n] + (n), [n+n] + (n+1), [n+n+n+1] + (n+2), [n+n+n+1+n+2] + (n+3), ...

One might regard it as a hopping from stone to stone, with
the step length always increased by one if no prime was found.
The path starts at n, but n is not part of the search.

n   path                           [no. of steps]
-------------------------------------------------
2 -> 4 -> 7                              [2 step]
5 -> 10 -> 16 -> 23                     [3 steps]
8 -> 16 -> 25 -> 35 -> 46 -> 58 -> 71   [6 steps]
105 -> 210 -> ... -> 6121              [47 steps]

Starting from 153 the prime 10891 is reached after 59 steps.
It could also be reached in 59 steps with fixed step length 182.

The first number which needs
... more than 100 steps to reach a prime is 633;
... more than 1000 steps is 10178808 when after 1130 steps
    11512869733 is found.

A research program could include:
(1) The sequence of the primes found.
(2) Number of steps needed to reach a prime.
(3) The length of the path.
(4) Numbers where the length is prime.
(5) Primes where the length is prime.
(6) Numbers where the number of steps rise to a new maximum.
(7) Numbers n that divide the length of the path.
(8) Primes that can never be found by this method.

One of these questions leads you to Max Alekseyev's A130800.

Anyhow, enough to keep my grandson busy for an afternoon.
The game went like this: alternately one of us determined a
number between 1 and 20. Whoever found the first prime number
on the grid had won. Arithmetic training without school smell.

My grandson quickly found a mystery, that he could not solve,
despite great effort. Can you guess what it was?

The next day he wanted to play the game again. But this time
he wrote down the primes on a list. More precisely on two lists.
One for the primes he found and one for the ones I found.
I think he did not trust my numbers as much as his. Maybe he
should become a cryptographer. When we later studied the list,
I said that I know more prime numbers than the list says.
We dubbed them the 'hidden primes'. They start:

    3, 5, 11, 17, 29, 41, ...

These primes can never be found by the rules of the game.
I will put them in the database.

Is it guaranteed that one can always find a prime number on
the grid starting at n? How long one has to search on average,
depending on n?

Cheers, Peter