A344020 A sequence of prime numbers: a(1)=2, a(n+1) is the least prime dividing Product_{i in S} a(i)^2 + Product_{i not in S} a(i)^2, minimized over all subsets S of {1..n}.

2, 5, 29, 17, 41, 13, 37, 53, 61, 97, 101, 73, 89, 109, 149, 137, 113, 173, 181, 157, 229, 197, 241, 257, 233, 193, 277, 269, 349, 317, 337, 293, 281, 313, 353, 373, 389, 409, 421, 397, 457, 461, 401, 433, 521, 509, 449, 541, 569, 557, 701, 593, 613, 653, 641, 617, 577, 661, 673, 709, 677, 601, 761, 733, 757, 769, 773, 797

Offset: 1

Author

Lucas Hoogendijk, May 06 2021

Keywords

• nonn

Comments

A variant of Euclid-Mullin (A000945) and Chua's adaptation (A167604).

All a(i) must be unique and, apart from 2, must be congruent to 1 (mod 4) as p only divides Product_{i in S} a(i)^2 + Product_{i not in S} a(i)^2 if -1 is a quadratic residue modulo p.

Whether all primes congruent to 1 (mod 4) occur in this sequence is unknown.

For n > 1, a(n) >= p, where p is the smallest prime p such that p == 1 (mod 4) and a(2)*a(3)*...*a(n-1) is a nonzero square modulo p. Conjecture: a(n) = p. - Jinyuan Wang and Max Alekseyev, Jul 04 2022

Examples

			For n=4 we obtain the 4 partitions with their products: 1 + 2^2 * 5^2 * 29^2 = 84101 = 37 * 2273, 2^2 + 5^2 * 29^2 = 21029 = 17*1237, 5^2 + 2^2 * 29^2 = 3389 and 2^2 * 5^2 + 29^2 = 941. The minimum of the primes dividing these is 17, thus a(4)=17.
		

Links

• Max Alekseyev, Table of n, a(n) for n = 1..2500
• Andrew R. Booker, A variant of the Euclid-Mullin sequence containing every prime, arXiv preprint arXiv:1605.08929 [math.NT], 2016.
• Lucas M. H. Hoogendijk, Prime Generators, UU bachelor thesis, 2020.
• Lucas Hoogendijk, Python code used to compute the first 27 terms (all known terms at the time of upload).

Crossrefs

Cf. A000945, A167604.

Programs

Mathematica

a = {2}; leastPrimeDivisor[n_Integer] := First[Select[FactorInteger[n][[All, 1]], PrimeQ]]; SequenceRange[start_Integer, end_Integer] := Module[{n, subsets, products, minPrime}, While[Length[a] < end, n = Length[a];subsets = Subsets[Range[n]]; products = Table[With[{S = subsets[[i]]}, Times @@ (a[[#]]^2 & /@ S) + Times @@ (a[[#]]^2 & /@ Complement[Range[n], S])], {i, Length[subsets]}]; minPrime = Min[leastPrimeDivisor /@ products]; AppendTo[a, minPrime];]; a[[start ;; end]]]; SequenceRange[1, 15] (* Hilko Koning, Nov 01 2024 *)

PARI

{ A344020_list() = my(a, A, m, p, b, q, z); print1(2,", "); a = [2]; A=1; while(1, p=5; while( kronecker(A, p)!=1 || p%4!=1, p=nextprime(p+1) ); b=lift(sqrt(A+O(p))*(1+sqrt(-1+O(p)))); z=znprimroot(p); m = nextprime(random(10^6)); q=lift(prod(i=1, #a, Mod(1+x^znlog(Mod(a[i], p), z, p-1), (1-x^(p-1))*Mod(1,m)) )); if( polcoeff(q, znlog(Mod(b, p), z, p-1), x)==0 && polcoeff(q, znlog(Mod(-b, p), z, p-1), x)==0, error("conjecture failed mod",m) ); a=concat(a, [p]); A*=p; print1(p, ", ") ); } \\ Max Alekseyev, Jul 04 2022

Extensions

More terms from Max Alekseyev, Jul 03 2022