Editorial for DMOPC '21 Contest 10 P5 - Number Theory - Olympiads Online Judge

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 (φ (n)) = φ (d (n))

d ((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}) = φ ((e_{1} + 1) (e_{2} + 1) \dots (e_{k} + 1))

. 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)) = φ (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))$ $ϕ (d (n)) = d (ϕ (n))$ ?

-4

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

wagwan