login
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}.
4

%I #35 Jul 05 2022 15:05:55

%S 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 101,89,103,127,107,113,137,131,139,109,149,151,163,157,167,173,193,

%U 211,179,191,181,223,199,197,233,227,229,239,241,251,257,307,281,269,271,293

%N 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 By Euclid's argument, the a(i) are distinct.

%C One can ask whether all primes occur in this sequence.

%H Max Alekseyev, <a href="/A167604/b167604.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.

%F 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 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 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 a :=n->if n = 1 then 2 else p(mul(a(i),i = 1 .. n-1)) fi :

%p seq(a(n), n=1..15);

%p # _Robert FERREOL_, Oct 01 2019

%o (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 A167605 lists such n that the first n terms of a(n) is a permutation of the first n primes.

%Y A000945 is the original Euclid-Mullin sequence (where I is restricted to the empty set).

%Y Cf. A344020.

%K nonn

%O 1,1

%A Kok Seng Chua (chuakokseng(AT)hotmail.com), Nov 07 2009

%E Edited and extended by _Max Alekseyev_, Nov 11 2009