cp's OEIS Frontend

A048669 The Jacobsthal function g(n): maximal gap in a list of all the integers relatively prime to n.

%I A048669 #85 Aug 11 2025 09:09:52
%S A048669 1,2,2,2,2,4,2,2,2,4,2,4,2,4,3,2,2,4,2,4,3,4,2,4,2,4,2,4,2,6,2,2,3,4,
%T A048669 3,4,2,4,3,4,2,6,2,4,3,4,2,4,2,4,3,4,2,4,3,4,3,4,2,6,2,4,3,2,3,6,2,4,
%U A048669 3,6,2,4,2,4,3,4,3,6,2,4,2,4,2,6,3,4,3,4,2,6,3,4,3,4,3,4,2,4,3,4,2,6,2,4,5
%N A048669 The Jacobsthal function g(n): maximal gap in a list of all the integers relatively prime to n.
%C A048669 Equivalently, g(n) is the least integer such that among any g(n) consecutive integers i, i+1, ..., i+g(n)-1 there is at least one which is relatively prime to n.
%C A048669 The definition refers to all integers, not just those in the range 1..n-1.
%C A048669 Differs from A070194 by 1 at the primes. - _T. D. Noe_, Mar 21 2007
%C A048669 Jacobsthal's function is used in the proofs of Recamán's and Pomerance's conjectures on P-integers--see A192224. - _Jonathan Sondow_, Jun 14 2014
%D A048669 E. Jacobsthal, Uber Sequenzen ganzer Zahlen, von denen keine zu n teilerfremd ist, I, II, III. Norske Vid. Selsk. Forh., 33, 1960, 117-139.
%D A048669 D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Pages 33-34.
%D A048669 E. Westzynthius, Uber die Verteilung der Zahlen, die zu der n ersten Primzahlen teilerfremd sind, Comm. Phys. Math. Helsingfors 25 (1931), 1-37.
%H A048669 T. D. Noe, <a href="/A048669/b048669.txt">Table of n, a(n) for n = 1..10000</a>
%H A048669 Fintan Costello, and Paul Watts, <a href="https://arxiv.org/abs/1306.1064">A short note on Jacobsthal's function</a>, arXiv preprint arXiv:1306.1064 [math.NT], 2013.
%H A048669 P. Erdős, <a href="https://dx.doi.org/10.7146/math.scand.a-10523">On the integers relatively prime to n and on a number theoretic function considered by Jacobsthal</a>. Math. Scand., 10, 1962, 163-170.
%H A048669 H. Iwaniec, <a href="https://doi.org/10.1515/dema-1978-0121">On the problem of Jacobsthal</a>, Demonstratio Math. 11 (1978), pp. 225-231.
%H A048669 Hans-Joachim Kanold, <a href="https://eudml.org/doc/161543">Über eine zahlentheoretische Funktion von Jacobsthal</a>, Mathematische Annalen 170.4 (1967): 314-326.
%H A048669 Gerhard R. Paseman, <a href="https://arxiv.org/abs/1311.5944">Updating an upper bound of Erik Westzynthius</a>, arXiv preprint arXiv:1311.5944 [math.NT], 2013-2014.
%H A048669 Carl Pomerance, <a href="https://doi.org/10.1016/0022-314X(80)90056-6">A note on the least prime in an arithmetic progression</a>, Journal of Number Theory 12.2 (1980): 218-223.
%H A048669 Harlan Stevens, <a href="https://eudml.org/doc/162943">On Jacobsthal's g(n)-function</a>, Mathematische Annalen 226.1 (1977): 95-97.
%H A048669 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 A048669 From _N. J. A. Sloane_, Apr 19 2017 (Start):
%F A048669 g(n) = g(Rad(n)) (cf. A007947). So in studying g(n) we may focus on the case when n is a product of w (say) distinct primes.
%F A048669 g(n) <= 2^w for all w [Kanold].
%F A048669 g(n) <= 2^(1/w) for all w >= e^50 [Kanold].
%F A048669 For some unknown X, g(n) <= X*(w*log(w))^2 for all w [Iwaniec].
%F A048669 (End)
%F A048669 g(n) << (log(n))^2, as proved by Iwaniec. - _Charles R Greathouse IV_, Sep 08 2012.
%e A048669 g(6)=4 because the gap between 1 and 5, both being relatively prime to 6, is maximal and 5-1 = 4.
%e A048669 g(7)=2, because the numbers relatively prime to 7 are 1,2,3,4,5,6,8,9,10,..., and the biggest gap is 2. Similarly a(p) = 2 for any prime p. - _N. J. A. Sloane_, Sep 08 2012
%t A048669 g[n_] := Module[{L = 1, m = 1}, For[k = 2, k <= n+1, k++, If[GCD[k, n] == 1, If[L+m < k, m = k-L]; L = k]]; m]; Table[g[n], {n, 1, 105}] (* _Jean-François Alcover_, Sep 03 2013, after _M. F. Hasler_ *)
%t A048669 Table[Max[Differences[Select[Range[110],CoprimeQ[#,n]&]]],{n,110}] (* _Harvey P. Dale_, Jan 10 2022 *)
%o A048669 (PARI) A048669(n)=my(L=1,m=1);for(k=2,n+1,gcd(k,n)>1 && next;L+m<k && m=k-L;L=k);m \\ _M. F. Hasler_, Sep 08 2012
%o A048669 (Haskell)
%o A048669 a048669 n = maximum $ zipWith (-) (tail ts) ts where
%o A048669    ts = a038566_row n ++ [n + 1]
%o A048669 -- _Reinhard Zumkeller_, Oct 01 2012
%Y A048669 Essentially same as A049298. See A132468 for another version.
%Y A048669 Cf. A048670, A070971, A007947, A038566, A192224, A285183.
%K A048669 nonn,easy,nice
%O A048669 1,2
%A A048669 _Jan Kristian Haugland_
%E A048669 Edited, changed symbol to g(n), added references pertaining to bounds. - _N. J. A. Sloane_, Apr 19 2017