A339055 Values taken by d(k^2)/d(k) where d(k) is the number of divisors of k and when this ratio is an integer.

1, 3, 3, 3, 3, 3, 3, 3, 3, 5, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 5, 3, 5, 3, 3, 3, 3, 3, 5, 5, 3, 3, 5, 5, 5, 3, 3, 3, 3, 5, 3, 3, 3, 5, 3, 3, 3, 5, 5, 5, 5, 3, 3, 3, 3, 3, 5, 5, 5, 5, 3, 3, 5, 3, 5, 5, 3, 3, 3, 3, 5, 3, 3, 3, 3, 5, 3, 5, 3, 5, 3, 5

Offset: 1

Author

Bernard Schott, Nov 22 2020

Keywords

• nonn

Comments

This sequence was the subject of the 3rd problem, proposed by Belarus during the 39th International Mathematical Olympiad in 1998 at Taipei (Taiwan) [see the link IMO].

If the prime signature of k is (u_1, u_2, ... , u_q) then d(k^2)/d(k) = Product_{i=1..q} (2*u_i+1)/(u_i+1); now, by a fine induction, we prove that every positive odd integer is a product of fractions of type (2u+1)/(u+1). Hence, the set of possible integer values of the data coincides with the set of all positive odd integers [see Marcin E. Kuczma reference]. The smallest integers k such that d(k^2)/d(k) = n-th odd integer are in A339056.

a(1) = 1 then from a(2) to a(234) the ratio takes only the values 3 and 5.

a(n) = 3 for numbers k whose prime signature is (4, 2) and the smallest such integer is 144 = 2^4 * 3^2 corresponding to a(2) = 3.

a(n) = 5 for numbers k whose prime signature is (4, 2, 2) and the smallest such integer is 3600 = 2^4 * 3^2 * 5^2 corresponding to a(10) = 5.

a(n) = 9 for numbers k whose prime signature is (4, 4, 2, 2) and the smallest such integer is 1587600 = 2^4 * 3^4 * 5^2 * 7^2 corresponding to a(235) = 9.

Examples

			The 4th number k such that d(k^2)/d(k) is an integer is A217584(4) = 400, 400 has 15 divisors and 400^2 = 160000 has 45 divisors, so, a(4) = 45/15 = 3.
		

References

• Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 134-135.

Links

• The IMO Compendium, Problem 3, 39th IMO 1998.
• Index to sequences related to Olympiads.

Crossrefs

Cf. A000005, A005408, A025487, A048691, A217584, A339056.

Programs

Maple

for n from 1 to 600 do
q:= tau(n^4)/tau(n^2);
if q = floor(q) then print(q); else fi; od:

Mathematica

Select[DivisorSigma[0, #^2]/DivisorSigma[0, #] & /@ Range[10^5], IntegerQ] (* Amiram Eldar, Nov 23 2020 *)

PARI

lista(nn) = {my(q); for (n=1, nn, if (denominator(q=numdiv(n^2)/numdiv(n)) == 1, print1(q, ", ")););}
lista(100000) \\ Michel Marcus, Nov 23 2020

Formula

a(n) = A000005(A217584(n)^2)/A000005(A217584(n)).