A341088 - OEIS

%I #15 Feb 18 2022 20:45:55

%S 2,7,67,673,8389

%N a(n) is the least prime p such that there is a set of n primes <= p such that every concatenation of two distinct members of the set is prime.

%C a(6) > 400000 if it exists.

%C Consider the graph whose vertices are primes, with an edge {p,q} if both concatenations pq and qp are prime. a(n) is the least p such that there is an n-clique in this graph with largest vertex p.

%e For n=1 there are no concatenations to consider, so a(1) is the first prime 2.

%e a(2) = 7 with the set {3,7}, where both concatenations 37 and 73 are both prime.

%e a(3) = 67 with the set {3, 37, 67}, where all concatenations 337, 373, 367, 673, 3767 and 6737 are prime.

%e a(4) = 673 with the set {3, 7, 109, 673} and 12 prime concatenations.

%e a(5) = 8389 with the set {13, 5197, 5701, 6733, 8389} and 20 prime concatenations.

%p dcat:= proc(x,y) 10^(1+ilog10(y))*x+y end proc:

%p Primes:= select(isprime, [seq(i,i=3..10^5,2)]):

%p nP:= nops(Primes):

%p V:= Vector(5):

%p V[1]:= 2: count:= 1:

%p for i from 1 while count < 5 do

%p   p:= Primes[i];

%p   S[p]:= select(t -> isprime(dcat(p,t)) and isprime(dcat(t,p)), Primes[1..i-1]);

%p   E:= map(convert,select(t -> member(t[1],S[t[2]]), {seq(seq([S[p][i],S[p][j]],i=1..j-1),j=1..nops(S[p]))}),set);

%p   G:= GraphTheory:-Graph(S[p],E);

%p   c:= GraphTheory:-CliqueNumber(G)+1;

%p   if V[c] = 0 then V[c]:= p; count:= count+1 fi

%p od:

%p convert(V,list);

%K nonn,base,more

%O 5,1

%A _J. M. Bergot_ and _Robert Israel_, Feb 13 2022