A359059 Numbers k such that phi(k) + rad(k) + psi(k) is a multiple of 3.

1, 2, 3, 5, 7, 8, 9, 11, 13, 17, 18, 19, 20, 23, 27, 29, 31, 32, 36, 37, 41, 42, 43, 44, 45, 47, 49, 50, 53, 54, 59, 61, 63, 67, 68, 71, 72, 73, 78, 79, 80, 81, 83, 84, 89, 90, 92, 97, 99, 101, 103, 105, 107, 108, 109, 110, 113, 114, 116, 117, 125, 126, 127, 128, 131, 135, 137, 139

Offset: 1

Author

Torlach Rush, Dec 14 2022

Keywords

• nonn

Comments

When k is prime (denote as p), phi(p) = p - 1, rad(p) = p, and psi(p) = p + 1, so phi(p) + rad(p) + psi(p) = 3*p. Therefore, A000040 is a subsequence.

When k = p^m (m>=1) with p prime, phi(p^m) = (p-1)*p^(m-1), rad(p^m) = p, and psi(p^m) = (p+1)*p^(m-1), so phi(p^m) + rad(p^m) + psi(p^m) = 2*p^m + p = p * (1+2*p^(m-1)). Then, this expression is a multiple of 3 iff p == 0 or 1 (mod 3), equivalently iff p is a generalized cuban prime of A007645. Therefore, as 1 is also a term, every sequence {p^m, p in A007645, m>=0} is a subsequence. See crossrefs section. - Bernard Schott, Jan 25 2023 after an observation of Alois P. Heinz

Examples

			8 is a term because 4+2+12 is divisible by 3.
		

Crossrefs

Cf. A000010 (phi), A000040, A001615 (psi), A007645, A007947 (rad), A001748 (3*p), A000244.

Subsequences of the form {p^n, n>=0}: A000244 (p=3), A000420 (p=7), A001022 (p=13), A001029 (p=19), A009975 (p=31), A009981 (p=37), A009987 (p=43).

Programs

Mathematica

q[n_] := Module[{f = FactorInteger[n], p, e}, p = f[[;; , 1]]; e = f[[;; , 2]]; Divisible[Times @@ ((p - 1)*p^(e - 1)) + Times @@ p + Times @@ ((p + 1)*p^(e - 1)), 3]]; Select[Range[170], q] (* Amiram Eldar, Dec 15 2022 *)

PARI

isok(m) = ((eulerphi(m) + factorback(factorint(m)[, 1]) + m*sumdiv(m, d, moebius(d)^2/d)) % 3) == 0; \\ Michel Marcus, Dec 27 2022

Python

from sympy.ntheory.factor_ import totient
from sympy import primefactors, prod
def rad(n): return 1 if n < 2 else prod(primefactors(n))
def psi(n):
    plist = primefactors(n)
    return n*prod(p+1 for p in plist)//prod(plist)
# Output display terms.
for n in range(1,170):
    if(0 == (totient(n) + rad(n) + psi(n)) % 3):
        print(n, end = ", ")