## 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:

## Hint 1

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

Let be its prime factorization. Rewrite as . For now, it seems hard to control both the left and right side if we consider varying . Can we restrict the search space to make it easier?## Hint 3

For now, consider such that every prime factor occurs only once (i.e. ).## Hint 4

We need . Intuitively, the left side is almost always larger than the right side, especially since we cannot use . How should the prime factors of relate to each other if we want to keep small?## Hint 5

We should consider using primes such that only contains small prime factors, e.g. only and .## Hint 6

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

Write a recursive backtracking program that tries all under where 's prime factors are all distinct and only contains small prime factors. This should quickly find many large solutions for . If we search for smaller , we should be able to find two values of with digits beginning with , which gets of the points.## Hint 8

The key intuition needed is that we should consider using primes such that only contains small prime factors. Recall that we restricted ourselves to using only earlier. Modify the recursive backtracking program to consider where some prime factors occur more than once (). We should be able to find a value of with digits beginning with , which gets of the points.## Answer

Two intended for of the points are and .The intended for full points is .

## 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