Is this iteration involving primes known?

Im a math learner so this may seem obvious.

Consider the following iteration (the $x$ on the RHS is the new iterate, and value of x and the LHS contains the old value of x)

$x+y+1:=x$

where $y>x$ and $x,y$ are primes and the output (which is the new value of $x$) iterate is prime. Note $y$ is not unique. So only the value $x$ is known to begin with and its assumed $y$ exists such that $x+y+1$ (which becomes the new value of $x$) is prime.

Does this sequence have an infinite number of terms ?-that question if true assumes a $y$ can be always found each time in every iteration.

Is there a known proof for this result (i.e. is this iteration known)? It maybe easier to look at a simplified version of this iteration, to prove this result, which is where the sequence starts at the first odd prime and y is considered minimal in each iteration.

It seems like something easy to prove with this simple iteration.

Example

$3+7+1=3+7+1=11$ (since $7>3$)

$x=3, y=7$ and new value of x=11 here

$11+17+1=11+17+1=29$ (since $17>11$)

$x=11, y=17$ and new value of x=29 here

$29+31+1=61$ (since $31>29$)

$x=29, y=31$ and new value of x=61 here

$61+89+1=151$ (since $89>61$)

$x=61, y=89$ and new value of x=151 here

and so on.

This quite clearly illustrates the iteration is correct (numerically).

So for these particular choices of $y$ used in the numerical example above , we have the sequence

3, 11,29,61,151 and so on.

Informally the question is asking if can we build an infinitely long "bridge" across the set of natural numbers where the difference between two consecutive "steps" (i.e. terms of the iteration) across the bridge is always a prime number+1. In other words the difference is never a composite number+1. Or describing the question in another way informally it asks if we can walk forever along the natural number line by stepping on primes only and taking steps which are very nearly of prime length.

Another question is what can be said about an upperbound minimal "step" length as you walk further along the "bridge"?

And considering the analogy to Gaussian primes- can we walk to some direction further and further away from the centre of the complex plane by stepping on Gaussian primes (considering both if the steps are bounded above or not) such that the step value is nearly a Gaussian prime?-we replace the constant 1 by some fixed Gaussian prime to get the version of the iteration for Gaussian primes,and again numerical examples suggest this is true for the unbounded case.

I'd love to see the proofs to any of these questions.

Solution 1:

This doesn't answer your question, but you may find it helpful.

Here's some more Python 2 code to calculate terms of your sequence. It uses a deterministic form of the Miller-Rabin primality test, so it's a little slower than my earlier 5 minute hack at producing the small terms of the sequence, but it can go much higher, and because it doesn't build a huge table of primes it's much more RAM-friendly.

In theory it could go even higher, given an appropriate set of witnesses.

#!/usr/bin/env python
''' Prime sequence maker

    See http://math.stackexchange.com/q/1635263/207316

    Written by PM 2Ring 2016.02.03
    miller-rabin primality test written 2015.04.29
'''

# miller-rabin primality test.
def is_prime_mr(n,
    #This set of witnesses is sufficient to prove primality
    #for all n < 3317044064679887385961981
    witnesses=(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41),
    range=range, pow=pow):

    #Test small prime factors. 
    for p in witnesses:
        if n % p == 0: 
            return n == p

    m = n - 1
    s, d = -1, m
    while d % 2 == 0:
        s, d = s + 1, d // 2
    srange = range(s)
    for a in witnesses:
        x = pow(a, d, n)
        if x == 1 or x == m:
            #Looks good, check next witness
            continue
        for _ in srange:
            x = x * x % n
            if x == 1:
                #previous (x+1)(x-1) == 0 mod n 
                return False
            if x == m: 
                #Looks good, check next witness
                #but previous x may be a fake root of -1 mod n
                break
        else: 
            #x**m != 1
            return False
    return True

hi = 3317044064679887385961981

x = 3
lst = [x]
i = 1
print 'i: x + y + 1 = s, y-x'
while True:
    y = x
    while True:
        y += 2
        if not is_prime_mr(y):
            continue
        s = x + y + 1
        if is_prime_mr(s):
            break
    if s >= hi: 
        break
    print '%2d: %d + %d + 1 = %d, %d' % (i, x, y, s, y-x)
    x = s
    lst.append(x)
    i += 1

print
print ', '.join([str(u) for u in lst])

output

i: x + y + 1 = s, y-x
 1: 3 + 7 + 1 = 11, 4
 2: 11 + 17 + 1 = 29, 6
 3: 29 + 31 + 1 = 61, 2
 4: 61 + 89 + 1 = 151, 28
 5: 151 + 179 + 1 = 331, 28
 6: 331 + 359 + 1 = 691, 28
 7: 691 + 761 + 1 = 1453, 70
 8: 1453 + 1499 + 1 = 2953, 46
 9: 2953 + 2969 + 1 = 5923, 16
10: 5923 + 5939 + 1 = 11863, 16
11: 11863 + 11897 + 1 = 23761, 34
12: 23761 + 23801 + 1 = 47563, 40
13: 47563 + 47639 + 1 = 95203, 76
14: 95203 + 95267 + 1 = 190471, 64
15: 190471 + 190529 + 1 = 381001, 58
16: 381001 + 381047 + 1 = 762049, 46
17: 762049 + 762227 + 1 = 1524277, 178
18: 1524277 + 1524401 + 1 = 3048679, 124
19: 3048679 + 3048737 + 1 = 6097417, 58
20: 6097417 + 6097439 + 1 = 12194857, 22
21: 12194857 + 12194909 + 1 = 24389767, 52
22: 24389767 + 24389861 + 1 = 48779629, 94
23: 48779629 + 48779903 + 1 = 97559533, 274
24: 97559533 + 97559597 + 1 = 195119131, 64
25: 195119131 + 195119207 + 1 = 390238339, 76
26: 390238339 + 390238367 + 1 = 780476707, 28
27: 780476707 + 780477179 + 1 = 1560953887, 472
28: 1560953887 + 1560954053 + 1 = 3121907941, 166
29: 3121907941 + 3121908089 + 1 = 6243816031, 148
30: 6243816031 + 6243816911 + 1 = 12487632943, 880
31: 12487632943 + 12487633439 + 1 = 24975266383, 496
32: 24975266383 + 24975266753 + 1 = 49950533137, 370
33: 49950533137 + 49950534041 + 1 = 99901067179, 904
34: 99901067179 + 99901067291 + 1 = 199802134471, 112
35: 199802134471 + 199802134667 + 1 = 399604269139, 196
36: 399604269139 + 399604269587 + 1 = 799208538727, 448
37: 799208538727 + 799208539709 + 1 = 1598417078437, 982
38: 1598417078437 + 1598417082629 + 1 = 3196834161067, 4192
39: 3196834161067 + 3196834161293 + 1 = 6393668322361, 226
40: 6393668322361 + 6393668323331 + 1 = 12787336645693, 970
41: 12787336645693 + 12787336646477 + 1 = 25574673292171, 784
42: 25574673292171 + 25574673292991 + 1 = 51149346585163, 820
43: 51149346585163 + 51149346586409 + 1 = 102298693171573, 1246
44: 102298693171573 + 102298693172747 + 1 = 204597386344321, 1174
45: 204597386344321 + 204597386346407 + 1 = 409194772690729, 2086
46: 409194772690729 + 409194772691297 + 1 = 818389545382027, 568
47: 818389545382027 + 818389545382499 + 1 = 1636779090764527, 472
48: 1636779090764527 + 1636779090764621 + 1 = 3273558181529149, 94
49: 3273558181529149 + 3273558181529171 + 1 = 6547116363058321, 22
50: 6547116363058321 + 6547116363059369 + 1 = 13094232726117691, 1048
51: 13094232726117691 + 13094232726118211 + 1 = 26188465452235903, 520
52: 26188465452235903 + 26188465452236177 + 1 = 52376930904472081, 274
53: 52376930904472081 + 52376930904473327 + 1 = 104753861808945409, 1246
54: 104753861808945409 + 104753861808945467 + 1 = 209507723617890877, 58
55: 209507723617890877 + 209507723617890899 + 1 = 419015447235781777, 22
56: 419015447235781777 + 419015447235784361 + 1 = 838030894471566139, 2584
57: 838030894471566139 + 838030894471567241 + 1 = 1676061788943133381, 1102
58: 1676061788943133381 + 1676061788943136391 + 1 = 3352123577886269773, 3010
59: 3352123577886269773 + 3352123577886270323 + 1 = 6704247155772540097, 550
60: 6704247155772540097 + 6704247155772540173 + 1 = 13408494311545080271, 76
61: 13408494311545080271 + 13408494311545080659 + 1 = 26816988623090160931, 388
62: 26816988623090160931 + 26816988623090161187 + 1 = 53633977246180322119, 256
63: 53633977246180322119 + 53633977246180325303 + 1 = 107267954492360647423, 3184
64: 107267954492360647423 + 107267954492360651273 + 1 = 214535908984721298697, 3850
65: 214535908984721298697 + 214535908984721301833 + 1 = 429071817969442600531, 3136
66: 429071817969442600531 + 429071817969442602191 + 1 = 858143635938885202723, 1660
67: 858143635938885202723 + 858143635938885203273 + 1 = 1716287271877770405997, 550
68: 1716287271877770405997 + 1716287271877770406121 + 1 = 3432574543755540812119, 124
69: 3432574543755540812119 + 3432574543755540813821 + 1 = 6865149087511081625941, 1702
70: 6865149087511081625941 + 6865149087511081625987 + 1 = 13730298175022163251929, 46
71: 13730298175022163251929 + 13730298175022163252467 + 1 = 27460596350044326504397, 538
72: 27460596350044326504397 + 27460596350044326504983 + 1 = 54921192700088653009381, 586
73: 54921192700088653009381 + 54921192700088653009667 + 1 = 109842385400177306019049, 286
74: 109842385400177306019049 + 109842385400177306020187 + 1 = 219684770800354612039237, 1138
75: 219684770800354612039237 + 219684770800354612041011 + 1 = 439369541600709224080249, 1774
76: 439369541600709224080249 + 439369541600709224080463 + 1 = 878739083201418448160713, 214
77: 878739083201418448160713 + 878739083201418448165697 + 1 = 1757478166402836896326411, 4984

3, 11, 29, 61, 151, 331, 691, 1453, 2953, 5923, 11863, 23761, 47563, 95203, 190471, 381001, 762049, 1524277, 3048679, 6097417, 12194857, 24389767, 48779629, 97559533, 195119131, 390238339, 780476707, 1560953887, 3121907941, 6243816031, 12487632943, 24975266383, 49950533137, 99901067179, 199802134471, 399604269139, 799208538727, 1598417078437, 3196834161067, 6393668322361, 12787336645693, 25574673292171, 51149346585163, 102298693171573, 204597386344321, 409194772690729, 818389545382027, 1636779090764527, 3273558181529149, 6547116363058321, 13094232726117691, 26188465452235903, 52376930904472081, 104753861808945409, 209507723617890877, 419015447235781777, 838030894471566139, 1676061788943133381, 3352123577886269773, 6704247155772540097, 13408494311545080271, 26816988623090160931, 53633977246180322119, 107267954492360647423, 214535908984721298697, 429071817969442600531, 858143635938885202723, 1716287271877770405997, 3432574543755540812119, 6865149087511081625941, 13730298175022163251929, 27460596350044326504397, 54921192700088653009381, 109842385400177306019049, 219684770800354612039237, 439369541600709224080249, 878739083201418448160713, 1757478166402836896326411

Note that $y-x$ appears to be less than $i^2$, and often much smaller, which makes me hopeful that it will always be easy to find a $y$ that works. But of course, relying on the behaviour of "small" numbers when making conjectures in number theory is not a Good Idea. :)

Solution 2:

It is only a conjecture that every even number is the difference of two primes. Your iteration can be rewritten $x' - y = x + 1$ (where $x'$ is the new value of $x$), and assuming that conjecture is true, it will go on forever, since $x+1$ is even there are primes $x'$ and $y$ whose difference is equal to it. It only needs to hold for even numbers that are one greater than primes, and technically only those that appear in the iteration, so I can't say for sure that the conjecture is required to prove it. Of course we can prove that there are arbitrarily large even numbers that are the difference of two primes, and I think the conjecture is probably true, but if there is a counterexample I can't think of any reason it wouldn't be present in this sequence.