Unknown bias in a distribution related to prime numbers

Question

If $n$ is composite then $\phi(n) < n-1$, hence there is at least one divisor $d$ of $n-1$ which does not divide $\phi(n)$. We call $d$ as the totient divisor of $n$. Trvially, if $n$ is prime then it has no totient divisor and if $n-1$ is prime then $n$ has exactly 1 totient divisor. The number of such integers $\le x$ is $\pi(x)$.

I counted how many integers $\le x$ have exactly $2,3,4,5, ...$ totient divisors. I observed nothing interesting. Then I counted how many even integers $\le x$ have exactly $2,3,4,5, ...$ totient divisors. I observed nothing interesting either. Finally I counted how many odd integers $\le x$ have exactly $2,3,4,5, ...$ totient divisors. I found something which looked interesting.

Let $T_{o}(n,x)$ be the number of odd integers $\le x$ which have $n$ totient divisors. I plotted the graph of $T_{o}(n,x)$ vs. $x$ for different values of $x$ and found a consistent pattern in them as shown below.

The red dots are the spikes and the green dots are the crests or local minima. We observe that every primes $>2$ appears on a green dot i.e. odd primes seem to appear only at the crests. This suggests odd numbers prefer to have a composite number of totient divisors i.e.somehow odd numbers do not like having a prime number of totient divisors.

Question: In the observed data why is $T_{o}(p,x) < T_{o}(p \pm 1,x)$, for a prime $p >2$. What is the phenomenon that is driving primes to appear on the local minimas?

If this observation is true then we can claim that

Odd numbers prefer not to have a prime number of totient divisors.

Note: Every prime $> 2$ is green but the converse is not true. We have a crest at 25.

Answer 1

The number of totient divisors of $n$ is $d(n-1)-d((n-1, \varphi(n))$. As $n$ gets large, then almost all $n$ have the property that $\varphi(n)$ is divisble by all small primes. The average number of prime divisors $p<y$ of $n-1$ is of magnitude $\log\log y$, hence, for almost all $n$ we have that the number of prime divisors of $(n-1, \varphi(n-1))$ tends to infinity. On the other hand the powerful part of $n-1$ is bounded, thus both $n-1$ and $(n-1, \varphi(n-1))$ are divisible by a large number of primes with exponent 1. Hence for almost all $n$ both $d(n-1)$ and $d((n-1, \varphi(n-1))$ are divisible by a growing power of 2, in particular, the number of totient divisors tends not to be prime.

Answer 2

First, consider the number of divisors of a given number $m$. This is a product of numbers derived from the exponents of the prime factorization of $m$. The only way this is a prime is if $m$ is itself a prime to a power one less than some (likely different) prime. In general, think of the divisor lattice of $m$ as a parallelpiped of grid points, with the total number almost always composite.

Now consider throwing away a part of this block of divisors. Divisors $d$ of $m$ do not divide some other integer $f$ if and only if they do not divide a special divisor of $m$ which is $d'=\gcd(m,f)$. So out of our divisor block, we carve out a smaller block out of a corner, and consider how many are left.

If $d'$ and $m$ contain all the powers of a prime $p$ that divides $m$ (i.e. $p$ divides $m$ and $p$ does not divide $m/d'$), then the number of remaining divisors is composite. One way to see this is if $d$ divides $m$, $d$ does not divide $d'$ and $p$ does not divide $d$, then $dp^i$ also does not divide $d'$ for $i$ from 0 up to the appropriate power of $p$. (A situation where this fails and such a number is prime is if $m=q^jp^i$ for a prime $q$, and $i+1$ is prime, and then $d'$ has to be $m/q$. But the end point is to consider what usually happens, so this is like a measure 0 exception.)

Now to your situation. If $n$ is even, $n-1$ is odd and $\phi(n)$ has an odd divisor which may or may not relate to a divisor of $n-1$, and in general we do not expect $(n-1)/\gcd(n-1,\phi(n))$ to be coprime to any prime divisors of $n-1$. Not much to say without further analysis.

If $n$ is odd however, then both $n-1$ and $\phi(n-1)$ share some powers of $2$. I believe the effect you are seeing is when $\phi(n-1)$ has as many or more powers of $2$ than does $n-1$, which leads to the number of selected non-divisors of $\phi(n)$ being composite. $\phi(n)$ is divisible by 4 more often than $n$ is, for example.

Interesting data, but I don't see how much further you can take it, especially if you are looking at the conjecture $\phi(n)$ divides $n-1$ implies $n$ is prime.

Gerhard "But Enjoy The Journey Anyway" Paseman, 2016.08.25.