I became interested in mathematics through solving programming challenges, particularly those on https://projecteuler.net. The problems I enjoyed solving the most were the problems that required in-depth analysis of a mathematical nature. I liked investigating how these problems worked, especially when some mathematical structure became apparent which could be exploited by a clever algorithm.
One I recently solved was https://projecteuler.net/problem=516. The aim is to find the sum of all numbers n less than or equal to L=〖10〗^12 such that Euler’s totient function φ(n) is a 5-smooth number.
A 5-smooth is a number whose largest prime factor does not exceed 5, which means it’s a number of the form a=2^(k_1 ) 3^(k_2 ) 5^(k_3 ), where k_1,k_2 and k_3 are non-negative integers.
Euler’s totient function is a function that counts the number of positive integers less than or equal to n, that have no common divisors other than 1 with n.
Unfortunately, iterating through all numbers n≤〖10〗^12 and calculating φ(n) for each of them, and confirming that φ(n) is 5-smooth, is not possible. So instead we find out what these numbers n look like, and instead of finding them we can just generate them.
Euler’s totient function is defined as a product over the number n’s district prime factors:
Let’s see what φ(n) looks like for n=p_1^(a_1 ) p_2^(a_2 ) p_3^(a_3 ) p_4^(a_4 ) p_5^(a_5 ), for example, where p_i is a distinct prime factor of n and a_i is the exponent for p_i.
We want to have no prime factors larger than 5.
We note that (2-1)=1, (3-2)=2 and (5-1)=4 are clearly 5-smooth numbers as they have no prime factors over 5.
We also note that a 5-smooth number multiplied by another 5-smooth number is also 5-smooth. A non-5-smooth number multiplied by either a 5-smooth number or another non-5-smooth number is not 5-smooth.
Therefore for φ(n) to be 5-smooth we require p_1^(a_1-1) p_2^(a_2-1) p_3^(a_3-1) p_4^(a_4-1) p_5^(a_5-1) to be 5-smooth and
(p_1-1)(p_2-1)(p_3-1)(p_4-1)(p_5-1) to be 5-smooth.
The number (p_1-1)(p_2-1)(p_3-1)(p_4-1)(p_5-1) will be 5-smooth when for all i, (p_i-1) is 5-smooth. Which is true for p_i=2,3 or 5, but is also true for primes such as 11 as 11-1=10=2^1 5^1 and 13 as 13-1=12=2^2 3^1, meaning our number n can include any of these primes.
The number p_1^(a_1-1) p_2^(a_2-1) p_3^(a_3-1) p_4^(a_4-1) p_5^(a_5-1) will be 5-smooth when for all p_i>5, p_i^(a_1-1)=1→a_i-1=0→a_i=1. As this will leave us a 5-smooth number as only the prime factors 2, 3, and 5 will survive.
From the above analysis we get two conditions on the number n: firstly that it’s prime factors can only be primes p, where (p-1) is 5-smooth, and secondly that all of its prime factors p>5, must have multiplicity 1. Therefore we can see that all 5-smooth numbers will have the form:
where k_1,k_2 and k_3 are any non-negative integer and for all i, p_i-1=2^(j_1 ) 3^(j_2 ) 5^(j_3 ), where j_1,j_2 and j_3 are some non-negative integers.
Now that we know what the numbers n look like, all we need to do is generate all of them up to L=〖10〗^12, which can be done very quickly.
Thomas Miller was a recipient of a 2018/19 AMSI Vacation Research Scholarship.