A373531 a(n) is the maximum number of divisors of n with an equal value of the Euler totient function (A000010).

1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1

Offset: 1

Author

Amiram Eldar, Jun 08 2024

Keywords

• nonn
• easy

Comments

The sums of the first 10^k terms, for k = 1, 2, ..., are 15, 161, 1641, 16554, 166029, 1662306, 16630535, 166335597, 1663473941, 16635216306, ... . Apparently, this sequence has an asymptotic mean 1.663... .

Examples

			a(2) = 2 since 2 has 2 divisors, 1 and 2, and phi(1) = phi(2) = 1.
a(12) = 3 since 3 of the divisors of 12 (3, 4 and 6) have the same value of phi: phi(3) = phi(4) = phi(6) = 2.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A102190, A319696, A326835, A359563, A359565, A373532.

Programs

Mathematica

a[n_] := Max[Tally[EulerPhi[Divisors[n]]][[;; , 2]]]; Array[a, 100]

PARI

a(n) = vecmax(matreduce(apply(x->eulerphi(x), divisors(n)))[ , 2]);

Python

from collections import Counter
from sympy import divisors, totient
def a(n):
    c = Counter(totient(d) for d in divisors(n, generator=True))
    return c.most_common(1)[0][1]
print([a(n) for n in range(1, 88)]) # Michael S. Branicky, Jun 08 2024

Formula

a(A326835(n)) = 1.

a(A359563(n)) >= 2.

a(A359565(n)) >= 3.

a(2*n) >= 2.

a(p) = 2 for an odd prime p.

a(m*n) >= a(n) for all m > 1.