cp's OEIS Frontend

A132468 Longest gap between numbers relatively prime to n.

%I A132468 #40 Feb 14 2019 12:36:19
%S A132468 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,
%T A132468 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,
%U A132468 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
%N A132468 Longest gap between numbers relatively prime to n.
%C A132468 Here "gap" does not include the endpoints.
%C A132468 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
%H A132468 N. J. A. Sloane, <a href="/A132468/b132468.txt">Table of n, a(n) for n = 1..20000</a>
%H A132468 Mario Ziller, John F. Morack, <a href="https://arxiv.org/abs/1611.03310">Algorithmic concepts for the computation of Jacobsthal's function</a>, arXiv:1611.03310 [math.NT], 2016.
%F A132468 a(n) = 1 at every prime power.
%e A132468 E.g. n=3: the longest gap in 1, 2, 4, 5, 7, ... is 1, between 2 and 4, so a(3) = 1.
%p A132468 a:=[];
%p A132468 for n from 1 to 120 do
%p A132468 s:=[seq(j,j=1..4*n)];
%p A132468 rec:=0;
%p A132468    for st from 1 to n do
%p A132468    len:=0;
%p A132468     for i from 1 to n while gcd(s[st+i-1],n)>1 do len:=len+1; od:
%p A132468     if len>rec then rec:=len; fi;
%p A132468    od:
%p A132468 a:=[op(a),rec];
%p A132468 od:
%p A132468 a; # _N. J. A. Sloane_, Apr 18 2017
%t A132468 a[ n_ ] := (Max[ Drop[ #,1 ]-Drop[ #,-1 ] ]-1&)[ Select[ Range[ n+1 ],GCD[ #,n ]==1& ] ]
%t A132468 Do[Print[n, " ", a[n]],{n,20000}]
%Y A132468 Equals A048669(n) - 1.
%Y A132468 See also A048670, A049298, A070791, A070194.
%K A132468 nonn
%O A132468 1,6
%A A132468 _Michael Kleber_, Nov 16 2007
%E A132468 Incorrect formula removed by _Thomas Anton_, Dec 30 2018