# It's getting harder and harder to be composite these days

Given a non-empty list L of integers greater than 1, we define d(L) as the smallest positive integer such that n + d(L) is composite for each n in L.

We define the sequence an as:

• a0 = 2
• ai+1 is the smallest integer greater than ai such that d(a0, ..., ai, ai+1) > d(a0, ..., ai)

You may either:

• Take an integer N and return the N-th term of the sequence (0-indexed or 1-indexed)
• Take an integer N and return the first N terms of the sequence
• Take no input and print the sequence forever

This is , so the shortest answer in bytes wins!

It's OK if your code is getting slow as N gets larger, but it should at least find the 20 first terms in less than 2 minutes.

## First terms

• a0 = 2 and d(2) = 2 (we need to add 2 so that 2+2 is composite)
• a1 = 3 because d(2, 3) = 6 (we need to add 6 so that 2+6 and 3+6 are composite)
• a2 = 5 because d(2, 3, 5) = 7 (we need to add 7 so that 2+7, 3+7 and 5+7 are all composite), whereas d(2, 3, 4) is still equal to 6
• etc.

Below are the 100 first terms of the sequence (unknown on OEIS at the time of posting).

  2,   3,   5,   6,  10,  15,  17,  19,  22,  24,
30,  34,  35,  39,  41,  47,  51,  54,  56,  57,
70,  79,  80,  82,  92,  98, 100, 103, 106, 111,
113, 116, 135, 151, 158, 162, 165, 179, 183, 186,
191, 192, 200, 210, 217, 223, 226, 228, 235, 240,
243, 260, 266, 274, 277, 284, 285, 289, 298, 307,
309, 317, 318, 329, 341, 349, 356, 361, 374, 377,
378, 382, 386, 394, 397, 405, 409, 414, 417, 425,
443, 454, 473, 492, 494, 502, 512, 514, 519, 527,
528, 560, 572, 577, 579, 598, 605, 621, 632, 642


# Pyth, 24 bytes

Pu+GfP_+Tf!fP_+ZYG)eGQ]2


Demonstration

Basically, we start with [2], then add elements 1 at a time by alternately finding d, then adding an element, and so forth. Outputs the first n elements of the sequence.

Contains a filter inside a first integer filter inside a first integer filter inside an apply repeatedly loop.

Explanation:

Pu+GfP_+Tf!fP_+ZYG)eGQ]2
u                   Q]2    Starting with [2], do the following as many times
as the input
f        )         Starting from 1 and counting upward, find d where
!f     G          None of the elements in the current list
P_+ZY           plus d give a prime.
f              eG       Starting from the end of the current list and counting
upward, find the first number which
P_+T                   plus d gives a prime.
+G                        Append the new number to the current list
P                           Trim the last element of the list


There's obvious repeated effort between the two "Add and check if prime" calls, but I'm not sure how to eliminate it.

# Jelly, 31 bytes

ṛ,;1+ÆPẸṆʋ1#ⱮẎ</
Ḷß€‘Ṫç1#ƊḢƲ2⁸?


Try it online!

Jelly sucks at recurrence sequences. :/

# Retina, 74 bytes

K__;
"$+"{/;(?!(__+)\1+\b)/+; ;_ .+$
$&¶$&
)/;(__+)\1+$/+.+$
_$&_ %\G_  Try it online! 0-indexed. Explanation: K__;  Each line i in the workarea contains two unary values, aᵢ;d+aᵢ. We start with a₀=2 and d+a₀=0 (because it's golfier). "$+"{
...
)


Repeat the loop N times.

/;(?!(__+)\1+\b)/+


Repeat while there is at least one non-composite number.

;
;_


Increment d.

.+&¶$&  Duplicate the last line, copying aᵢ₋₁ to aᵢ. /;(__+)\1+$/+


Repeat while d+aᵢ is composite.

.+$_$&_


Increment aᵢ.

%\G_


Convert the results to decimal.

# Clean, 138130 128 bytes

import StdEnv
$l=until(\v=all(\n=any((<)1o gcd(n+v))[2..n+v-1])l)inc 1  map hd(iterate(\l=hd[[n:l]\\n<-[hd l..]|$[n:l]> $l])[2])  Try it online! Expanded: $l=until(\v=all(\n=any((<)1o gcd(n+v))[2..n+v-1])l)inc 1
$l=until( )inc 1 // first value from 1 upwards where _ \v=all( )l // _ is true for everything in l \n=any( )[2..n+v-1] // any of [2,3..n+v-1] match _ gcd(n+v) // the gcd of (n+v) and ^ o // (composed) ^ is _ (<)1 // greater than 1  map hd(iterate(\l=hd[[n:l]\\n<-[hd l..]|$[n:l]> $l])[2]) map hd( ) // the first element of each list in _ iterate( )[2] // infinite repeated application of _ to [2] \l=hd[ ] // the head of _ [n:l] // n prepended to l \\n<-[hd l..] // for every integer n greater than the head of l |$[n:l]> \$l       // where d(n0..ni+1) > d(n0..ni)


# Julia 0.6, 145 130 bytes

~L=(x=1;while any(map(m->all(m%i>0 for i=2:m-1),L+x));x+=1;end;x)
!n=n<1?[2]:(P=!(n-1);t=P[end]+1;while ~[P;t]<=~P;t+=1;end;[P;t])


Try it online!

(-15 bytes using my new and improved golfing skills - operator overloads, replacing conditional by ternary and hence removing return keyword.)

Expanded:

function primecheck(m)
all(m%i>0 for i∈2:m-1)
end

function d(L)
x = 1
while any(map(primecheck, L+x))
x += 1
end
return x
end

function a(n)
n > 0 || return [2]
Prev = a(n-1)
term = Prev[end] + 1
while d([Prev;term]) ≤ d(Prev)
term += 1
end
return [Prev;term]
end