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,6

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

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.

Formula

a(n) = 1 at every prime power.

Example

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

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}]

Crossrefs

Equals A048669(n) - 1.

See also A048670, A049298, A070791, A070194.

Sequence in context: A348953 A095345 A342671 * A353235 A243915 A367482

Adjacent sequences: A132465 A132466 A132467 * A132469 A132470 A132471

Keyword

nonn

Author

Michael Kleber, Nov 16 2007

Extensions

Incorrect formula removed by Thomas Anton, Dec 30 2018

Status

approved