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