login
Last position reached by winner of n-th Littlewood Frog Race.
10

%I #21 Jan 21 2022 23:28:47

%S 2,3,7,5,19,7,29,17,19,19,43,13,103,29,31,41,103,19,191,41,67,43,137,

%T 73,149,103,109,83,317,31,311,97,181,103,191,71,439,191,233,89,379,67,

%U 463,113,181,137,967,97,613,149,197,181,607,109,331,233

%N Last position reached by winner of n-th Littlewood Frog Race.

%C Related to Linnik's theorem; main sequence is A085420. - _Charles R Greathouse IV_, Apr 16 2010

%C a(n) is the smallest prime such that some subset of primes <= a(n) is a reduced residue system modulo n. - _Vladimir Shevelev_, Feb 19 2013

%H Charles R Greathouse IV, <a href="/A038026/b038026.txt">Table of n, a(n) for n = 1..10000</a>

%F Let p(n,b) be the smallest prime in the arithmetic progression k*n+b, with k >= 0. Then a(n) = max(p(n,b)) with 0 < b < n and gcd(b,n) = 1. - _Charles R Greathouse IV_, Sep 08 2012

%e a(6) = 7 since the primes less than or equal to 7, {2, 3, 5, 7}, reduced modulo 6 are {2, 3, 5, 1}. This contains the reduced residue system modulo 6, which is {1, 5}, and 7 is clearly the smallest such prime. - _Vladimir Shevelev_, Feb 19 2013

%o (PARI) a(n)={

%o my(todo=(1<<n)-1,r=2,q=2);

%o if(n==1, return(2));

%o for(a=0,n-1,

%o if(gcd(a,n)>1,todo=bitnegimply(todo,1<<a))

%o );

%o todo=bitnegimply(todo,1<<2);

%o forprime(p=3,default(primelimit),

%o r+=p-q;

%o r=r%n;

%o todo=bitnegimply(todo,1<<r);

%o if(!todo, return(p));

%o q=p;

%o );

%o error("Not enough precomputed primes")

%o }; \\ _Charles R Greathouse IV_, Feb 14 2011

%o (PARI) p(n,b)=while(!isprime(b), b+= n); b

%o a(n)=my(t=p(n,1));for(b=2,n-1,if(gcd(n,b)==1,t=max(t,p(n,b))));t \\ _Charles R Greathouse IV_, Sep 08 2012

%Y This sequence is a lower bound for the related sequence A085420.

%Y Cf. A038025.

%K nonn

%O 1,1

%A _Christian G. Bower_