A394433 Numbers k such that gcd(k, phi(k)) is prime.

4, 6, 9, 10, 14, 21, 22, 25, 26, 30, 34, 38, 39, 45, 46, 49, 55, 57, 58, 62, 66, 70, 74, 75, 82, 86, 93, 94, 99, 102, 105, 106, 111, 118, 121, 122, 129, 130, 134, 138, 142, 146, 153, 154, 155, 158, 165, 166, 169, 170, 174, 175, 178, 182, 183, 190, 194, 195

Offset

1,1

Comments

No prime k belongs to the sequence, because for prime k, phi(k) = k-1 and consecutive numbers are coprime, i.e. gcd(k, k-1) = 1, which is not prime.

All squares of primes (p^2) belong to the sequence, because phi(p^2) = p^2 - p and gcd(p^2, p^2 - p) = p, which is prime.

Squarefree terms are A350586. - Robert Israel, Mar 20 2026

Links

Table of n, a(n) for n=1..58.

Example

For k = 9: phi(9) = 6 and gcd(9, 6) = 3, which is prime, so 9 is a term.
For k = 8: phi(8) = 4 and gcd(8, 4) = 4, which is not prime, so 8 is not a term.

Maple

filter:= k -> isprime(igcd(k, NumberTheory:-phi(k))):
select(filter, [$1..300]); # Robert Israel, Mar 20 2026

Mathematica

Select[Range[210], PrimeQ[GCD[#, EulerPhi[#]]] &] (* Amiram Eldar, Mar 20 2026 *)

Prog

(Python)
from sympy import totient, gcd, isprime
def ok(k): return isprime(gcd(k, totient(k)))
print([k for k in range(1, 300) if ok(k)])
(PARI) isok(k) = isprime(gcd(k, eulerphi(k))); \\ Michel Marcus, Mar 20 2026

Crossrefs

Cf. A000010, A003277, A054395, A392199.

A001248 and A350586 are subsequences.

Sequence in context: A236026 A193305 A084759 * A054395 A142863 A318990

Adjacent sequences: A394430 A394431 A394432 * A394434 A394435 A394436

Keyword

nonn,easy

Author

Aied Sulaiman, Mar 20 2026

Status

approved