Totient and Non-Totient Numbers

I've written about Euler's Totient Function in an eponymously titled post on March 12th 2019. Today however, my diurnal age number count of 26248 alerted me to the fact that this number was a member of OEIS A333020:

A333020

Starts of runs of 3 consecutive even numbers that are all totient numbers    (A002202).

This begged the question as to what a totient number was and as it turns out that:

A totient number is a value of Euler's totient function: that is, an \(m\) for which there is at least one \(n\) for which \( \phi(n) = m\). The valency or multiplicity of a totient number \(m\) is the number of solutions to this equation. A non-totient is a natural number which is not a totient number. Source.

Apart from 1, every totient number is even. This follows from the fact that every natural number is either prime or a product of primes and the totient of a prime number is one less than the number itself. For example, \( \phi(7)=6\) because 1, 2, 3, 4, 5 and 6 are coprime to it. All primes except 2 are odd and so the totient of all odd primes is even. Let's look at the totient numbers between 1 and 100:

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100 

There are 38 totient numbers between 1 and 100, thus 38%. Between 1 and 1000, there are 291 or about 29% and, between 1 and 10000, there are 2374 or about 24% and so. The percentage decreases as the range is extended. The Wikipedia article provides a formula for approximating this but I won't go into that here.

In my post from June of 2019, I looked at OEIS A001274:

A001274

Numbers \(k\) such that \( \phi(k) = \phi(k+1) \).

Such numbers are relatively infrequent as the following list shows:

1, 3, 15, 104, 164, 194, 255, 495, 584, 975, 2204, 2625, 2834, 3255, 3705, 5186, 5187, 10604, 11715, 13365, 18315, 22935, 25545, 32864, 38804, 39524, 46215, 48704, 49215, 49335, 56864, 57584, 57645, 64004, 65535, 73124, 105524, 107864, 123824, 131144, 164175, 184635, ...

 Apparently, in 1999, the following was proved that:

for every integer \(k \geq 2 \) there is a totient number \(m\) of multiplicity \(k\): that is, for which the equation \( \phi(n) = m\) has exactly \(k\) solutions. However, no number \(m\) is known with multiplicity \(k = 1\). Source.

It's interesting to look at the distribution of these \(k\)s. For values of \(m\) up to one million, we find that \(m\)=241920 has a \(k\) value of 937. Figure 1 shows the distribution:

Figure 1: permalink

As can be seen, \(k\)=937 is quite an outlier. The next highest \(k\) value is 750. This means that up to the one million mark, there are no \(k\) values between 751 to 936 inclusive.

There are many sequences in the OEIS that relate to totient numbers. Here is one example:

A050495

Numbers that are the first term of at least one arithmetic progression with 4 or more terms all having the same value of Euler's totient function \( \phi(x) \).

The example is given of \( \phi(x) \)72 = \( \phi(x) \)(78) = \( \phi(x) \)(84) = \( \phi(x) \)(90) = 24, so 72 is a member of the sequence.

Figure 2 shows the totient numbers between 1 and 72, along with the numbers that produce these totient values:

Figure 2: source