cp's OEIS Frontend

A167604 A variant of Euclid-Mullin (A000945): a(1)=2, a(n+1) is the least prime dividing [Product_{i in I} a(i) + Product_{i not in I} a(i)], minimized over all subsets I of {1..n}.

%I A167604 #41 Nov 17 2024 07:03:04
%S A167604 2,3,5,11,37,13,7,29,17,19,43,23,47,41,53,31,61,59,67,79,83,73,97,71,
%T A167604 101,89,103,127,107,113,137,131,139,109,149,151,163,157,167,173,193,
%U A167604 211,179,191,181,223,199,197,233,227,229,239,241,251,257,307,281,269,271,293
%N A167604 A variant of Euclid-Mullin (A000945): a(1)=2, a(n+1) is the least prime dividing [Product_{i in I} a(i) + Product_{i not in I} a(i)], minimized over all subsets I of {1..n}.
%C A167604 By Euclid's argument, the a(i) are distinct.
%C A167604 One can ask whether all primes occur in this sequence.
%H A167604 Max Alekseyev, <a href="/A167604/b167604.txt">Table of n, a(n) for n = 1..2500</a>
%H A167604 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.
%F A167604 For any n, we have Legendre symbol (-a(1)*a(2)*...*a(n-1) / a(n)) = 1. If p is the smallest prime such that (-a(1)*a(2)*...*a(n-1) / p) = 1, then a(n) >= p. Conjecture: For all n, a(n) = p. Note that if b is such that b^2 == -a(1)*a(2)*...*a(n-1) (mod p) and for some I, b == prod_{i in I} a(i) (mod p), then a(n) = p. Heuristically, I must exist for large enough n, since the number of possible subsets I is much larger than p. - _Max Alekseyev_, Nov 11 2009, May 20 2015
%e A167604 a(4)=11 which is the smallest prime dividing the 4 partitions 2+3*5=17, 3+2*5=13, 5+2*3=11, 1+2*3*5=31.
%p A167604 with(numtheory):p:=proc(N) local S, d : S:=NULL:for d  in divisors(N) while d^2<=N  do S:=S,divisors(d+N/d)[2] od : return(min(S)) end:
%p A167604 a :=n->if n = 1 then 2 else p(mul(a(i),i = 1 .. n-1)) fi :
%p A167604 seq(a(n), n=1..15);
%p A167604 # _Robert FERREOL_, Oct 01 2019
%t A167604 p[N_Integer] := Module[{S = {}, d, divisorsList},
%t A167604 For[d = 1, d^2 <= N, d++, If[Divisible[N, d], divisorsList = Divisors[d + N/d];
%t A167604 If[Length[divisorsList] >= 2, AppendTo[S, divisorsList[[2]]]];]]; Min[S]];
%t A167604 a[n_Integer] := If[n == 1, 2, p[Times @@ Table[a[i], {i, 1, n - 1}]]];
%t A167604 Table[a[n], {n, 1, 14}] (* _Hilko Koning_, Oct 30 2024 *)
%o A167604 (PARI) { A167604_list() = my(a,A,p,b,q,z,m); a = []; A=1; while(1, p=2; while( kronecker(-A,p)!=1, p=nextprime(p+1) ); b=lift(sqrt(-A+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, error("conjecture failed mod",m)); a=concat(a,[p]); A*=p; print1(p,", ") ) } /* _Max Alekseyev_, May 20 2015 */
%Y A167604 A167605 lists such n that the first n terms of a(n) is a permutation of the first n primes.
%Y A167604 A000945 is the original Euclid-Mullin sequence (where I is restricted to the empty set).
%Y A167604 Cf. A344020.
%K A167604 nonn
%O A167604 1,1
%A A167604 Kok Seng Chua (chuakokseng(AT)hotmail.com), Nov 07 2009
%E A167604 Edited and extended by _Max Alekseyev_, Nov 11 2009