login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A048669 Jacobsthal function: maximal gap in a list of all the integers relatively prime to n. 11
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

The definition refers to all integers, not just those in the range 1..n-1.

Equivalently, a(n) is the least integer such that among any a(n) consecutive integers i, i+1, ..., i+a(n)-1 there is at least one which is relatively prime to n.

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

H. Iwaniec, On the problem of Jacobsthal, Demonstratio Math. 11 (1978), pp. 225-231.

E. Jacobsthal, Uber Sequenzen ganzer Zahlen, von denen keine zu n teilerfremd ist, I, II, III. Norske Videnskabsselskab Forhdl., 33, 1960, 117-139

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

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.

FORMULA

a(n) << log^2 n, as proved by Iwaniec. - Charles R Greathouse IV, Sep 08 2012

EXAMPLE

a(6)=4 because the gap between 1 and 5, both being relatively prime to 6, is maximal and 5-1 = 4.

a(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

a[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[a[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<k&m=k-L; L=k); m} \\ M. F. Hasler, Sep 08 2012

(Haskell)

a048669 n = maximum $ zipWith (-) (tail ts) ts where

   ts = a038566_row n ++ [n + 1]

-- Reinhard Zumkeller, Oct 01 2012

CROSSREFS

Cf. A048670, A070971. Essentially same as A049298. See A132468 for another version.

Cf. A038566, A192224.

Sequence in context: A216321 A058263 A232398 * A158522 A034444 A073180

Adjacent sequences:  A048666 A048667 A048668 * A048670 A048671 A048672

KEYWORD

nonn,easy,nice

AUTHOR

Jan Kristian Haugland (jankrihau(AT)hotmail.com)

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified March 22 22:17 EDT 2017. Contains 283901 sequences.