A362951 a(n) is the Hamming distance between the binary expansions of n and phi(n) where phi is the Euler totient function (A000010).

0, 2, 1, 2, 1, 1, 1, 2, 4, 3, 1, 1, 1, 1, 3, 2, 1, 2, 1, 3, 3, 3, 1, 1, 3, 3, 2, 1, 1, 3, 1, 2, 4, 3, 5, 2, 1, 3, 6, 3, 1, 3, 1, 3, 4, 3, 1, 1, 4, 3, 3, 3, 1, 2, 5, 1, 4, 3, 1, 3, 1, 1, 4, 2, 4, 4, 1, 3, 4, 5, 1, 2, 1, 5, 4, 3, 4, 4, 1, 3, 5, 5, 1, 3, 3, 5, 6

Offset: 1

Author

Darío Clavijo, Jul 05 2023

Keywords

• nonn
• base
• less

Comments

a(2^k) = 2 for k >= 1.

a(p) = 1 for each odd prime p because phi(p) = p-1 and (p-1 xor p) = 1.

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A000120, A065091, A101080, A169814.

Programs

Mathematica

A362951[n_] := DigitCount[BitXor[n, EulerPhi[n]], 2, 1];
Array[A362951, 100] (* Paolo Xausa, Feb 20 2024 *)

Python

from gmpy2 import mpz, hamdist
from sympy import totient
a = lambda n: hamdist(mpz(n), mpz(totient(n)))
print([a(n) for n in range(1, 87)])

Python

from sympy import totient
def A362951(n): return (n^totient(n)).bit_count() # Chai Wah Wu, Jul 07 2023

Formula

a(n) = A101080(n,A000010(n)).

a(n) = A000120(A169814(n)).