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

Author

N. J. A. Sloane, May 13 2002

Keywords

• nonn
• nice
• easy

Comments

Maximal gap in reduced residue system mod n.

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

Examples

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

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

Crossrefs

Cf. A000010.

Cf. A038566.

Programs

Haskell

a070194 n = maximum $ zipWith (-) (tail ts) ts where ts = a038566_row n
-- Reinhard Zumkeller, Oct 01 2012

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}]

PARI

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

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

Extensions

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