cp's OEIS Frontend

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

%I A070194 #17 Oct 01 2012 16:12:34
%S A070194 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,
%T A070194 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,
%U A070194 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
%N A070194 List the phi(n) numbers from 1 to n-1 which are relatively prime to n; sequence gives size of maximal gap.
%C A070194 Maximal gap in reduced residue system mod n.
%C A070194 It is an unsolved problem to determine the rate of growth of this sequence.
%D A070194 H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 200.
%H A070194 T. D. Noe, <a href="/A070194/b070194.txt">Table of n, a(n) for n=3..10000</a>
%F A070194 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
%e A070194 For n = 10 the reduced residues are 1, 3, 7, 9; the maximal gap is a(10) = 7-3 = 4.
%t A070194 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}]
%o A070194 (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
%o A070194 (Haskell)
%o A070194 a070194 n = maximum $ zipWith (-) (tail ts) ts where ts = a038566_row n
%o A070194 -- _Reinhard Zumkeller_, Oct 01 2012
%Y A070194 Cf. A000010.
%Y A070194 Cf. A038566.
%K A070194 nonn,nice,easy
%O A070194 3,2
%A A070194 _N. J. A. Sloane_, May 13 2002
%E A070194 More terms from _Robert G. Wilson v_ and _John W. Layman_, May 13 2002