|
     
|
Question: Squares and primes Let t(n) denote the number of positive divisors of the positive integer. Then t(1) = 1, t(2) = 2, t(3) = 2, t(4) = 3, t(5) = 2, ... The subject of this problem is the family of sequences n, t(n), t(t(n)), t(t(t(n))), ... in which each term after the first is the number of divisors of the preceding term. For example, 540, 24, 8, 4, ... Prove that the sequence n, t(n), t(t(n)), t(t(t(n))), ... does not contain a perfect square if and only if n is prime. Answer: TO PROVE ONE SIDE OF THE IMPLICATION
Conjecture 1: if n is prime, the sequence n, t(n), t(t(n)), t(t(t(n))), ...
does not contain a perfect square.
Proof:
Suppose that n is prime, say p. Then t(n) = 2 and thus the series is: p, 2,
2, 2, 2, 2, ....
Indeed, the sequence n, t(n), t(t(n)), t(t(t(n))), ... does not contain a
perfect square.
TO PROVE THE OTHER SIDE OF THE IMPLICATION
Prove conjecture 2: if n is non-prime, the sequence n, t(n), t(t(n)),
t(t(t(n))), ... contains a perfect square.
Proof:
Suppose that n is non-prime, say p_1 ^ n_1 + p_2 ^ n_2 + ... + p_k ^ n_k;
where k is a non-negative integer; p_i are primes for i=1, 2, ..., k and n_i
are non-negative integers for i=1, 2, ..., k. Because n is non-prime, if k =
1 then n_1 has to be greater than 1.
Fact 1: t(n) = (n_1 + 1) * (n_2 + 1) * (n_k + 1) for all positive n; this
can be deduced from basic mathematics.
Fact 2: t(n) is a prime if and only if k=1 and n_1 + 1 is prime (for all
positive n).
Fact 3a: If k=1 and n_1 + 1 = 2; then n = p_1 => contradiction with the
assumption that n is non-prime (for all positive n).
Fact 3b: If k=1 and n_1 + 1 is prime greater than 2; then n_1 is even and
thus n = p_1 ^ n_1 is a perfect square (for all positive n).
Fact 4: Combining facts 2 & 3: If t(n) is a prime, then n is a perfect
square and the sequence contains a perfect square (for all positive n).
Now, what is left is a proof "uit het ongerijmde" (sorry, this is the Dutch
name of the method.)
a) Conjecture 2 holds for n = 1, 4.
b) Let's assume that conjecture 2 holds for all values of n < k. If t(k) is
prime, then (see fact 4), conjecture 2 holds for n = k.
If t(k) is non-prime, then t(k) is less than k (a number cannot be divisible
by all the numbers 1, 2, 3, ..., k if k > 2). Conjecture 2 holds for all
values less than k, so the sequence for t(k) contains a perfect square.
Since this sequence is the tail of the sequence for k, the sequence k, t(k),
t(t(k)), ... also contains a perfect square.
Combining a and b proves that conjecture 2 holds for all values of n.
CONCLUSION
Combining the proofs of conjecture 1 and conjecture 2 proofs the question.
-Ron L.J. van den Burg
|
