A070194 List the phi(n) numbers from 1 to n-1 which are relatively prime to n; sequence gives size of maximal gap.

1, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 3, 2, 1, 4, 1, 4, 3, 4, 1, 4, 2, 4, 2, 4, 1, 6, 1, 2, 3, 4, 3, 4, 1, 4, 3, 4, 1, 6, 1, 4, 3, 4, 1, 4, 2, 4, 3, 4, 1, 4, 3, 4, 3, 4, 1, 6, 1, 4, 3, 2, 3, 6, 1, 4, 3, 6, 1, 4, 1, 4, 3, 4, 3, 6, 1, 4, 2, 4, 1, 6, 3, 4, 3, 4, 1, 6, 3, 4, 3, 4, 3, 4, 1, 4, 3, 4, 1, 6, 1, 4, 5, 4, 1

Offset

3,2

Comments

Maximal gap in reduced residue system mod n.

It is an unsolved problem to determine the rate of growth of this sequence.

References

H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 200.

Links

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

Formula

a(n) = max(A048669(n),2) for all n>2. Indeed A048669 is obtained when going up to n+1 instead of only n-1 (because after n+1, the gaps among numbers coprime to n repeat). Since n-1 and n+1 are both coprime to n, this means that A048669(n)=2 whenever a(n)=1, but in all other cases, there is equality. - M. F. Hasler, Sep 08 2012

Example

For n = 10 the reduced residues are 1, 3, 7, 9; the maximal gap is a(10) = 7-3 = 4.

Mathematica

f[n_] := Block[{a = Select[ Table[i, {i, n - 1}], GCD[ #, n] == 1 & ], b = {}, k = 1, l = EulerPhi[n]}, While[k < l, b = Append[b, Abs[a[[k]] - a[[k + 1]]]]; k++ ]; Max[b]]; Table[ f[n], {n, 3, 100}]

Prog

(PARI) A070194(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)
a070194 n = maximum $ zipWith (-) (tail ts) ts where ts = a038566_row n
-- Reinhard Zumkeller, Oct 01 2012

Crossrefs

Cf. A000010.

Cf. A038566.

Sequence in context: A091891 A258127 A181982 * A323300 A349128 A366450

Adjacent sequences: A070191 A070192 A070193 * A070195 A070196 A070197

Keyword

nonn,nice,easy

Author

N. J. A. Sloane, May 13 2002

Extensions

More terms from Robert G. Wilson v and John W. Layman, May 13 2002

Status

approved