A132468 -id:A132468 - cp's OEIS frontend

A285182 L = A132468(n) = A048669(n)-1 is the length of the longest run of consecutive numbers that have a common factor with n; a(n) = smallest k >= 0 which starts such a run.

0, 0, 0, 0, 2, 0, 0, 0, 4, 0, 2, 0, 6, 5, 0, 0, 2, 0, 4, 6, 10, 0, 2, 0, 12, 0, 6, 0, 2, 0, 0, 11, 16, 14, 2, 0, 18, 12, 4, 0, 6, 0, 10, 5, 22, 0, 2, 0, 4, 17, 12, 0, 2, 10, 6, 18, 28, 0, 2, 0, 30, 6, 0, 25, 8, 0, 16, 23, 4, 0, 2, 0, 36, 5, 18, 21, 12, 0, 4, 0, 40, 0, 6, 34, 42, 29, 10, 0, 2, 13, 22, 30

Offset: 2

N. J. A. Sloane, Apr 19 2017

nonn

Related to the Jacobsthal function A048669.

a(n) depends only on the radical A007947(n).

			If n = 6, among the numbers k = 0,1,2,3,4,5,6,7,... there is a run of L = 3 consecutive numbers, 2,3,4, all with gcd(k,6)>1, starting at k=2, so a(6) = 2.
If n is a prime (or prime power), a(n)=0.

Rémy Sigrist, Table of n, a(n) for n = 2..20000

Cf. A132468, A048669, A007947.

acf:=[]; wcf:=[];
for n from 2 to 120 do
s:=[seq(j,j=0..4*n)];
rec:=0;
   for st from 0 to n do
   len:=0;
      for i from 1 to n while gcd(s[st+i],n)>1 do len:=len+1; od:
      if len>rec then rec:=len; w:=st; fi;
   od:
acf:=[op(acf),rec];
wcf:=[op(wcf),w];
od:
acf; # A132468
wcf; # A285182

A132724 Number of occurrences through n^2 of the longest gap between numbers relatively prime to n (A132468).

Original entry on oeis.org

0, 1, 2, 7, 4, 6, 6, 31, 26, 10, 10, 24, 12, 14, 30, 127, 16, 54, 18, 40, 42, 22, 22, 96, 124, 26, 242, 56, 28, 60, 30, 511, 66, 34, 70, 216, 36, 38, 78, 160, 40, 84, 42, 88, 270, 46, 46, 384, 342, 250, 102, 104, 52, 486, 110, 224, 114, 58, 58, 240, 60, 62, 378, 2047, 130

Offset: 1

Jonathan Vos Post, Nov 16 2007

			For n=3, the longest gap in 1, 2, 4, 5, 7, 8 is 1, between 2 and 4 and again between 5 and 7, so a(3) = 2.
For n=4, the longest gap in 1, 3, 5, 7, 9, 11, 13, 15 is 1, at (1,3), (3,5), (5,7), (7,9), (9,11), (11,13) and (13,15), so a(4) = 7.
The numbers coprime to 6 and smaller than 36 are {1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35}, the largest distance between two consecutive terms is 4; 4 appears as a distance in the cases (1,5),(7,11),(13,17),(19,23),(25,29) and (31,35) - it appears 6 times. Therefore a(6)=6.

Cf. A132468.

a = {}; For[n = 1, n < 70, n++, b = Select[Range[1, n^2], GCD[ #, n] == 1 &]; m = 0; For[j = 1, j < Length[b], j++, If[b[[j + 1]] - b[[j]] > m, m = b[[j + 1]] - b[[j]]]]; c = 0; For[j = 1, j < Length[b], j++, If[b[[j + 1]] - b[[j]] == m, c++ ]]; AppendTo[a, c]]; a (* Stefan Steinerberger, Nov 20 2007 *)

Corrected and extended by Stefan Steinerberger, Nov 20 2007

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

Original entry on oeis.org

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

Offset: 1

Jan Kristian Haugland

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

			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

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.

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.

Essentially same as A049298. See A132468 for another version.

Cf. A048670, A070971, A007947, A038566, A192224, A285183.

a048669 n = maximum $ zipWith (-) (tail ts) ts where
   ts = a038566_row n ++ [n + 1]
-- Reinhard Zumkeller, Oct 01 2012

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 *)
Table[Max[Differences[Select[Range[110],CoprimeQ[#,n]&]]],{n,110}] (* Harvey P. Dale, Jan 10 2022 *)

A048669(n)=my(L=1,m=1);for(k=2,n+1,gcd(k,n)>1 && next;L+mM. F. Hasler, Sep 08 2012

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.

Edited, changed symbol to g(n), added references pertaining to bounds. - N. J. A. Sloane, Apr 19 2017

cp's OEIS Frontend

A285182 L = A132468(n) = A048669(n)-1 is the length of the longest run of consecutive numbers that have a common factor with n; a(n) = smallest k >= 0 which starts such a run.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A132724 Number of occurrences through n^2 of the longest gap between numbers relatively prime to n (A132468).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions