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
Is there another valid value for
that's smaller than
, and if there isn't, is there a proof that
is the lowest odd
that satisfies
?
wagwan