A132468 Longest gap between numbers relatively prime to n.

0, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 1, 3, 2, 1, 1, 3, 1, 3, 2, 3, 1, 3, 1, 3, 1, 3, 1, 5, 1, 1, 2, 3, 2, 3, 1, 3, 2, 3, 1, 5, 1, 3, 2, 3, 1, 3, 1, 3, 2, 3, 1, 3, 2, 3, 2, 3, 1, 5, 1, 3, 2, 1, 2, 5, 1, 3, 2, 5, 1, 3, 1, 3, 2, 3, 2, 5, 1, 3, 1, 3, 1, 5, 2, 3, 2, 3, 1, 5, 2, 3, 2, 3, 2, 3, 1, 3, 2, 3, 1, 5, 1, 3, 4

Offset: 1

Author

Michael Kleber, Nov 16 2007

Keywords

• nonn

Comments

Here "gap" does not include the endpoints.

a(n) is given by the maximum length of a run of numbers satisfying one congruence modulo each of n's distinct prime factors. It follows that if m is the number of distinct prime factors of n and each of n's prime factors is greater than m then a(n) = m. - Thomas Anton, Dec 30 2018

Examples

			E.g. n=3: the longest gap in 1, 2, 4, 5, 7, ... is 1, between 2 and 4, so a(3) = 1.
		

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..20000
• Mario Ziller, John F. Morack, Algorithmic concepts for the computation of Jacobsthal's function, arXiv:1611.03310 [math.NT], 2016.

Crossrefs

Equals A048669(n) - 1.

See also A048670, A049298, A070791, A070194.

Programs

Maple

a:=[];
for n from 1 to 120 do
s:=[seq(j,j=1..4*n)];
rec:=0;
   for st from 1 to n do
   len:=0;
    for i from 1 to n while gcd(s[st+i-1],n)>1 do len:=len+1; od:
    if len>rec then rec:=len; fi;
   od:
a:=[op(a),rec];
od:
a; # N. J. A. Sloane, Apr 18 2017

Mathematica

a[ n_ ] := (Max[ Drop[ #,1 ]-Drop[ #,-1 ] ]-1&)[ Select[ Range[ n+1 ],GCD[ #,n ]==1& ] ]
Do[Print[n, " ", a[n]],{n,20000}]

Formula

a(n) = 1 at every prime power.

Extensions

Incorrect formula removed by Thomas Anton, Dec 30 2018