OFFSET
1,3
COMMENTS
Let j(n) be the Jacobsthal function (A048669): maximal distance between consecutive integers coprime to n. Then a(n) is the least k>0 such that k+1,k+2,...k+j(n)-1 are not coprime to n. If n is prime and e>0, then j(n^e)=2 and a(n^e)=n-1. If n>2 is prime, then a(2n)=n-2. If m is the squarefree kernel of n (A007947), then j(n)=j(m) and a(n)=a(m). For composite n, a(n)<n/2. Note that a(n)=1 iff n is in sequence A055932. When n is the product of the first r primes (A002110), then a(n)+1 begins (or is inside) a prime gap of size at least A048670(r).
LINKS
T. D. Noe, Table of n, a(n) for n=1..10000
EXAMPLE
The numbers coprime to 10 are 1,3,7,9,11,13,17,19,... Observe that the differences are periodic: 2,4,2,2,2,4,2,... The largest distance between the coprime numbers is 4, which first occurs between 3 and 7. Hence j(10)=4 and a(10)=3.
MATHEMATICA
JacobsthalPos[n_] := Module[{g, d, mx, pos}, g=Select[Range[n+1], GCD[n, # ]==1&]; d=Rest[g]-Most[g]; mx=Max@@d; pos=Position[d, mx, 1, 1][[1, 1]]; g[[pos]]]; Table[JacobsthalPos[n], {n, 100}]
CROSSREFS
KEYWORD
nonn
AUTHOR
T. D. Noe, Mar 24 2007
STATUS
approved