%I #21 May 31 2024 22:10:26

%S 1,3,4,6,10,12,15,18,20,21,30,42,60,70,105,210,385,770,1155,2310,4620,

%T 5005,10010,15015,30030,60060,90090,120120,150150,180180,210210,

%U 240240,255255,510510

%N 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).

%C 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.

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

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

%H Paul Erdős, <a href="https://projecteuclid.org/euclid.dmj/1077491914">The difference of consecutive primes</a>, Duke Mathematical Journal, Vol. 6, No. 2 (1940), pp. 438-441, <a href="https://users.renyi.hu/~p_erdos/1940-10.pdf">alternative link</a>.

%H Paul Erdős, <a href="http://www.jstor.org/stable/24489279">On the integers relatively prime to n and on a number-theoretic function considered by Jacobsthal</a>, Mathematica Scandinavica, Vol. 10 (1962), pp. 163-170, <a href="http://www.mscand.dk/article/viewFile/10523/8544">alternative link</a>.

%H H. L. Montgomery & R. C. Vaughan, <a href="http://www.jstor.org/stable/1971274">On the distribution of reduced residues</a>, Annals of Mathematics, Vol. 123, No. 2 (1986), pp. 311-333.

%e 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..., ...

%t 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

%o (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

%o 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

%Y Cf. A000010, A038566, A132952, A322144.

%K nonn,more

%O 1,2

%A _Amiram Eldar_, Nov 29 2018