|
| |
|
|
A070194
|
|
List the phi(n) numbers from 1 to n-1 which are relatively prime to n; sequence gives size of maximal gap.
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
