This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A048669 The Jacobsthal function g(n): maximal gap in a list of all the integers relatively prime to n. 15
 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, 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, 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS 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. The definition refers to all integers, not just those in the range 1..n-1. Differs from A070194 by 1 at the primes. - T. D. Noe, Mar 21 2007 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 REFERENCES 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. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Pages 33-34. E. Westzynthius, Uber die Verteilung der Zahlen, die zu der n ersten Primzahlen teilerfremd sind, Comm. Phys. Math. Helsingfors 25 (1931), 1-37. LINKS T. D. Noe, Table of n, a(n) for n = 1..10000 Fintan Costello, and Paul Watts, A short note on Jacobsthal's function, arXiv preprint arXiv:1306.1064 [math.NT], 2013. P. Erdős, On the integers relatively prime to n and on a number theoretic function considered by Jacobsthal. Math. Scand., 10, 1962, 163-170. H. Iwaniec, On the problem of Jacobsthal, Demonstratio Math. 11 (1978), pp. 225-231. Hans-Joachim Kanold, Über eine zahlentheoretische Funktion von Jacobsthal, Mathematische Annalen 170.4 (1967): 314-326. Gerhard R. Paseman, Updating an upper bound of Erik Westzynthius, arXiv preprint arXiv:1311.5944 [math.NT], 2013-2014. Carl Pomerance, A note on the least prime in an arithmetic progression, Journal of Number Theory 12.2 (1980): 218-223. Harlan Stevens, On Jacobsthal's g(n)-function, Mathematische Annalen 226.1 (1977): 95-97. Mario Ziller, John F. Morack, Algorithmic concepts for the computation of Jacobsthal's function, arXiv:1611.03310 [math.NT], 2016. FORMULA From N. J. A. Sloane, Apr 19 2017 (Start): 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. g(n) <= 2^w for all w [Kanold]. g(n) <= 2^(1/w) for all w >= e^50 [Kanold]. For some unknown X, g(n) <= X*(w*log(w))^2 for all w [Iwaniec]. (End) g(n) << (log(n))^2, as proved by Iwaniec. - Charles R Greathouse IV, Sep 08 2012. EXAMPLE g(6)=4 because the gap between 1 and 5, both being relatively prime to 6, is maximal and 5-1 = 4. 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 MATHEMATICA 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 *) PROG (PARI) A048669(n)=my(L=1, m=1); for(k=2, n+1, gcd(k, n)>1 && next; L+m

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 21 08:47 EDT 2019. Contains 328292 sequences. (Running on oeis4.)