Euler Phi Chowla and Mersenne primes

Jon Maiga, 2018-12-13

I encountered the following interesting sequence it while tinkering with the last article, “Efficient computation of ratios between divisor sum”. It only has 7 known terms that are generated under the condition

A132794 Numbers n such that sigma(phi(n))-phi(n)-1=phi(sigma(n)-n-1).

8, 16, 64, 256, 16384, 262144, 1048576, ?

Let’s start by looking at the components of this sequence.

The number of relative primes up to $n$, is denoted by phi, $\phi(n)$ also referred to as Euler’s totient function:

$\phi(1)= 1$ (1)
$\phi(2)= 1$ (1)
$\phi(3)= 2$ (1,2)
$\phi(4)= 2$ (1,3)
$\phi(5)= 4$ (1,2,3,4)
$\phi(6)= 2$ (1,5)
$\phi(7)= 6$ (1,2,3,4,5,6)
$\phi(8)= 4$ (1,3,5,7)

And sigma, $\sigma(n)$ is the sum of all divisors of n
$\sigma(1)=1=1$
$\sigma(2)=2+1=3$
$\sigma(3)=3+1=4$
$\sigma(4)=4+2+1=7$
$\sigma(5)=5+1=6$
$\sigma(6)=6+3+2+1=12$
$\sigma(7)=7+1=8$
$\sigma(8)=8+4+2+1=15$

Now that we know what $\phi(n)$ and $\sigma(n)$ do we can start pondering about what this condition mean and what numbers fulfill it, I will flip left and right side just because it’s easier to start that way

$\phi(\sigma(n)-n-1)=\sigma(\phi(n))-\phi(n)-1$

Left side

$\phi(\sigma(n)-n-1)$

Let’s examine the left side that represent the number of relative primes to $\sigma(n)-n-1$. If you look on the $\sigma$ table above you notice that one and the number itself is included in the summing the divisors. In the condition $n$ and $1$ is removed so we get another sum of divisors that is

A048050 Chowla’s function: sum of divisors of n except 1 and n.

0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21, 10, 13, 0,

Lets call it $ch(n)=\sigma(n)-n-1$.

Now applying $\phi(ch(n))$ give us the unrecognized sequence

? $\phi(c(n))$

1, 0, 0, 1, 0, 4, 0, 2, 2, 6, 0, 8, 0, 6, 4, 6, 0, 8, 0, 12, 4, 12, 0, 24,

Substituting with $ch$ on the lhs we get

$\phi(ch(n))$

Right side

$\sigma(\phi(n))-\phi(n)-1$

Similar to the left side, we take take $\sigma(\phi(n))$ and remove $\phi(n)$ and 1, just like with with Chowla’s function. We already know how $\phi(n)$ behaves so lets consider $\sigma(\phi(n))$.

A062402 a(n) = sigma(phi(n)).

1, 1, 3, 3, 7, 3, 12, 7, 12, 7, 18, 7, 28, 12, 15, 15, 31, 12, 39, 15, 28,

Hmm not to helpful, lets keep going, now subtracting $\phi(n)$ we get to an unrecognized sequence, as far as oeis.org concerns

? $\sigma(\phi(n))-\phi(n)$

0, 0, 1, 1, 3, 1, 6, 3, 6, 3, 8, 3, 16, 6, 7, 7, 15, 6, 21, 7, 16, 8, 14, 7

Finally remove 1 from the divisor sum leaves us at

? $\sigma(\phi(n))-\phi(n)-1$

-1, -1, 0, 0, 2, 0, 5, 2, 5, 2, 7, 2, 15, 5, 6, 6, 14, 5, 20, 6, 15, 7, 13, 6,

Well, we shall not despair, we can simplify it a bit by recognizing that the right side is also Chowlas function but with $\phi(n)$ as argument

$ch(\phi(n))$

Wilderness to the left, wilderness to the right

Our left sequence
1, 0, 0, 1, 0, 4, 0, 2, 2, 6, 0, 8, 0, 6, 4, 6, 0, 8, 0, 12, 4, 12, 0, 24,

Our right sequence
-1, -1, 0, 0, 2, 0, 5, 2, 5, 2, 7, 2, 15, 5, 6, 6, 14, 5, 20, 6, 15, 7, 13, 6,

The actual sequence are the $n$ that fulfills the condition (bolded terms above)

$ch(\phi(n))=\phi(ch(n))$

3?, 8, 16, 64, 256, 16384, 262144, 1048576, ?

First, we note that $\phi(ch(3))=ch(\phi(3))$ so either we have made a miscalculation or maybe $\phi(0)$ is undefined. Mathematica eats it but let’s ignore that for now. EDIT: (Looking in the history of the entry shows that $\phi(0)$ is avoided).

So we have

$ch(\phi(n))=\phi(\ch(n))$

Proof that every Mersenne prime is hidden in there

Here is a proof that every Mersenne prime $p_m$ appears in this sequence on the form $2^{m_e+1}$ where $m_e$ is a mersenne exponent.

We only need to know a few properties of $ch$ and $phi$ to prove this, most are understandable and you can find them on Wikipedia.

The divisor sum of power of twos is $\sigma(2^k)=2^{k+1}-1$. We use this to find the $ch$ eqvivalence $\ch(2^k)=\sigma(2^k) -2^k-1=2^{k+1}-1-2^k-1=2^k-2$

Further, we know that if $p$ is a prime then $\phi(p)=p-1$ and that $\phi(2^k)=2^{k-1}$ we also know that $\phi$ is multiplicative for relative primes.

Now we are equipped with the following relations

$\ch(2^k)=2^k-2$
$\phi(2^k)=2^{k-1}$
$\phi(p)=p-1$
$\phi(pq)=\phi(p)\phi(q)$ if $gcd(p,q) = 1$

Noting that the known terms in the sequence are on the form of $2^k$ (8,16,64…) we can check exactly which $2^k$ fulfills the condition

$ch(\phi(n))=\phi(\ch(n))$

Let $n=2^k$ then

$ch(\phi(2^k))=\phi(\ch(2^k))$

Lhs: substituting $\phi(2^k)=2^{k-1}$. Rhs: $ch(2^k)=2^k-2$ we get

$ch(2^{k-1})=\phi(2^k-2)$

Lhs: substituting $\ch(2^{k-1})$ with $2^{k-1}-2$. Rhs: factoring out a $2$

$2^{k-1}-2=\phi(2(2^{k-1}-1))$

Rhs: Since $\phi$ is multiplicative ($2^{k-1}-1$ is odd) we can move out the factor of 2.

$2^{k-1}-2=\phi(2)\phi(2^{k-1}-1)$

Rhs: $\phi(2)=1$

$2^{k-1}-2=\phi(2^{k-1}-1)$

Note that the lhs is 1 less than what’s inside $\phi$ on the rhs. We know that $\phi(n)=n-1$ iff n is a prime. Primes on the form $2^k-1$ are the Mersenne primes

A000668 Mersenne primes (of form 2^p - 1 where p is a prime).
3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, …

Our condition in terms of Mersenne primes seems very true

$p_m-1=\phi(p_m)$

Let’s try it, in the table below I have bolded those that pass the test. Note that the rows that pass the test are associated with a $p_m-1$.

k	$n=2^k$	$2^{k-1}-2$	$\phi(2^{k-1}-1)$
1	2	-1	0
2	4	0	1
3	8	2	2
4	16	6	6
5	32	14	8
6	64	30	30
7	128	62	36
8	256	126	126
14	16384	8190	8190
18	262144	131070	131070
20	1048576	524286	524286

8, 16, 64, 256, 16384, 262144, 1048576, ?

Those are the known terms of the sequence, A132794, the entry says that the next term has to be larger than $10^8$. If our proof is correct we will be able to find large terms of this sequence quickly (because large Mersenne primes are known).

Let’s proceed, the last known term is $1048576$ with the associated Mersenne prime $524287$. The next Mersenne prime is $2147483647$, which is $2^{31}-1$

To work out $n$ from the Mersenne prime we inverse $ch$ which is straightforward, we just add one and multiply by two.

$a(9)=2(2^{31}-1+1)=2^{32}=4294967296$

It’s larger than $10^8$ and plugging it into the our equation it passes the test.

The Mersenne exponent, $m_e$ can be used directly as

A000043 Mersenne exponents: primes p such that $2^p - 1$ is prime. Then $2^p - 1$ is called a Mersenne prime.

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423,…

$2^{m_e+1} \in \text {A132794}$

A small observation is that the first terms is $2^3=8$ and not $3$ (as we encountered in the beginning).

Now that we have proven that every Mersenne prime is hidden in this sequence we still not know for sure that no other numbers are in it. Maybe the millionth term is on another form?

Next step

By looking on the parity of the functions, we can do some pruning, mind you, this is just a sketch:

$\phi(n)$ is always even for $n>2$ this means that whatever goes into $ch$ on the left side will be even on the form, $2n$.

$ch(\phi(n))=\phi(\ch(n))$

$ch$ will be larger than $2$ for $n>4$ with the exception of primes which will make it $0$. So for large $n$ the rhs is even, this forces the lhs to be even for numbers that satisfy the condition.

With reasoning along those lines I think it’s possible to conclude that $n$ has to be on the form $2n^2$ and $4n^2$. As a sanity check $2^k$ is a subsequence of those (easy to prove).

A088827 Even numbers with odd abundance: even squares or two times squares. Sigma(n)-2n=odd means that sigma(n) is also odd.
2,4,8,16,18,32,36,50,64,72,98,100,128,144,162,196,200,242,256,288,324,338,392,400,450,484

I am not sure how to prove/disprove that the sequence only has terms on the form ${2^{m_e+1}}$, maybe it’s trivial or super hard?

Conjecture

However, if I had to guess I would guess that this sequence is exclusively the numbers

$a(n)={2^{m_e(n)+1}}$

If this conjecture is true the next terms will be

n	a(n)
8	4294967296
9	4611686018427387904
10	1237940039285380274899124224
11	324518553658426726783156020576256
12	340282366920938463463374607431768211456
13	13729595320261219429963801598162786434538870600286610818788926918371086366795312104245119281322909109954592622782961716074243975999433287625148056582230114304

Written with StackEdit.