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


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

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


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

      wagwan