OFFSET
1,1
COMMENTS
Related to Linnik's theorem; main sequence is A085420. - Charles R Greathouse IV, Apr 16 2010
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
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
FORMULA
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
EXAMPLE
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
PROG
(PARI) a(n)={
my(todo=(1<<n)-1, r=2, q=2);
if(n==1, return(2));
for(a=0, n-1,
if(gcd(a, n)>1, todo=bitnegimply(todo, 1<<a))
);
todo=bitnegimply(todo, 1<<2);
forprime(p=3, default(primelimit),
r+=p-q;
r=r%n;
todo=bitnegimply(todo, 1<<r);
if(!todo, return(p));
q=p;
);
error("Not enough precomputed primes")
}; \\ Charles R Greathouse IV, Feb 14 2011
(PARI) p(n, b)=while(!isprime(b), b+= n); b
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
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved