A344020 - OEIS

%I #39 Nov 17 2024 07:03:55

%S 2,5,29,17,41,13,37,53,61,97,101,73,89,109,149,137,113,173,181,157,

%T 229,197,241,257,233,193,277,269,349,317,337,293,281,313,353,373,389,

%U 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

%N 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}.

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

%C 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.

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

%C 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

%H Max Alekseyev, <a href="/A344020/b344020.txt">Table of n, a(n) for n = 1..2500</a>

%H Andrew R. Booker, <a href="https://arxiv.org/abs/1605.08929">A variant of the Euclid-Mullin sequence containing every prime</a>, arXiv preprint arXiv:1605.08929 [math.NT], 2016.

%H Lucas M. H. Hoogendijk, <a href="https://dspace.library.uu.nl/bitstream/handle/1874/394848/Thesis_LucasH_Final.pdf">Prime Generators</a>, UU bachelor thesis, 2020.

%H Lucas Hoogendijk, <a href="/A344020/a344020.py.txt">Python code used to compute the first 27 terms</a> (all known terms at the time of upload).

%e 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.

%t 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 *)

%o (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

%Y Cf. A000945, A167604.

%K nonn

%O 1,1

%A _Lucas Hoogendijk_, May 06 2021

%E More terms from _Max Alekseyev_, Jul 03 2022