A322165 Numbers k that give record values for s(k)*phi(k)/k^2, where s(k) is the sum of squares of the differences between consecutive totatives of k (A322144).

1, 3, 4, 6, 10, 12, 15, 18, 20, 21, 30, 42, 60, 70, 105, 210, 385, 770, 1155, 2310, 4620, 5005, 10010, 15015, 30030, 60060, 90090, 120120, 150150, 180180, 210210, 240240, 255255, 510510

Offset: 1

Author

Amiram Eldar, Nov 29 2018

Keywords

• nonn
• more

Comments

Erdős conjectured that this ratio is bounded and offered $500 for a proof. The conjecture was proved by Montgomery and Vaughan, who won the prize.

Is this sequence infinite? If yes, what is lim_{n->oo} s(a(n))*phi(a(n))/a(n)^2?

Examples

			The values of the ratio at the first terms of the sequence are 0, 0.222..., 0.5, 0.888..., 0.96, 1, 1.031..., ...
		

References

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer, 2004, Chapter B40, Gaps between totatives, p. 146.

Links

• Paul Erdős, The difference of consecutive primes, Duke Mathematical Journal, Vol. 6, No. 2 (1940), pp. 438-441, alternative link.
• Paul Erdős, On the integers relatively prime to n and on a number-theoretic function considered by Jacobsthal, Mathematica Scandinavica, Vol. 10 (1962), pp. 163-170, alternative link.
• H. L. Montgomery & R. C. Vaughan, On the distribution of reduced residues, Annals of Mathematics, Vol. 123, No. 2 (1986), pp. 311-333.

Crossrefs

Cf. A000010, A038566, A132952, A322144.

Programs

Mathematica

ratio[n_] := Module[{v=Differences[Select[Range[n], GCD[n, #] == 1 &]]^2}, Total[v] * (Length[v]+1) / n^2]; seq={}; rm=-1; Do[r=ratio[n]; If[r>rm, rm=r; AppendTo[seq, n]], {n, 1, 1000}]; seq

PARI

s(n) = {v = select(x->gcd(x, n)==1, vector(n, k, k)); sum(i=1, #v-1, (v[i+1] - v[i])^2); } \\ A322144
lista(nn) = {my(m = -1); for (n=1, nn, newm = s(n)*eulerphi(n)/n^2; if (newm > m, print1(n, ", "); m = newm););} \\ Michel Marcus, Nov 29 2018