Editorial for DMOPC '21 Contest 10 P5 - Number Theory

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: zhouzixiang2004

Hint 1

Pure brute force should have a very hard time finding a solution. Try to get some intuition about what a valid $n$ would look like.

Hint 2

Let $n = p_1^{e_1}p_2^{e_2} \dots p_k^{e_k}$ be its prime factorization. Rewrite $d(\varphi(n)) = \varphi(d(n))$ as $d\left((p_1-1)(p_2-1) \dots (p_k-1)p_1^{e_1-1}p_2^{e_2-1} \dots p_k^{e_k-1}\right) = \varphi\left((e_1+1)(e_2+1) \dots (e_k+1)\right)$ . For now, it seems hard to control both the left and right side if we consider varying $e_i$ . Can we restrict the search space to make it easier?

Hint 3

For now, consider $n$ such that every prime factor occurs only once (i.e. $e_i = 1$ ).

Hint 4

We need $d((p_1-1)(p_2-1) \dots (p_k-1)) = \varphi(2^k) = 2^{k-1}$ . Intuitively, the left side is almost always larger than the right side, especially since we cannot use $p_i-1 = 1$ . How should the prime factors of $p_i-1$ relate to each other if we want to keep $d((p_1-1)(p_2-1) \dots (p_k-1))$ small?

Hint 5

We should consider using primes $p_i$ such that $p_i-1$ only contains small prime factors, e.g. only $2$ and $3$ .

Hint 6

Trying to find an $n$ by hand is tedious and prone to only finding a large $n$ . However, we are allowed to use computer assistance.

Hint 7

Write a recursive backtracking program that tries all $n$ under $10^{18}$ where $n$ 's prime factors $p_i$ are all distinct and $p_i-1$ only contains small prime factors. This should quickly find many large solutions for $n$ . If we search for smaller $n$ , we should be able to find two values of $n$ with $13$ digits beginning with $12???????????$ , which gets $80\%$ of the points.

Hint 8

The key intuition needed is that we should consider using primes $p_i$ such that $p_i-1$ only contains small prime factors. Recall that we restricted ourselves to using only $e_i = 1$ earlier. Modify the recursive backtracking program to consider $n$ where some prime factors occur more than once ( $e_i > 1$ ). We should be able to find a value of $n$ with $11$ digits beginning with $15?????????$ , which gets $100\%$ of the points.

Answer

Two intended $n$ for $80\%$ of the points are $1244586078645 = 3 \cdot 5 \cdot 7 \cdot 13 \cdot 19 \cdot 37 \cdot 73 \cdot 109 \cdot 163$ and $1294951381815 = 3 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 19 \cdot 37 \cdot 163 \cdot 487$ .

The intended $n$ for full points is $15230439315 = 3^6 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 37 \cdot 73$ .

Comments

5

X_Ray commented on June 28, 2022, 5:40 p.m.

Is there another valid value for $n$ ~n~ that's smaller than $4^{17}$ ~4^{17}~, and if there isn't, is there a proof that $15230439315$ ~15230439315~ is the lowest odd $n$ ~n~ that satisfies $\phi(d(n))=d(\phi(n))$ ~\phi(d(n))=d(\phi(n))~?

-4

fleac1 commented on Sept. 9, 2022, 3:49 p.m.

wagwan