A055466 Numbers k such that d(k)^2 divides phi(k) + sigma(k).

1, 2, 4, 15, 39, 49, 55, 78, 81, 87, 95, 99, 110, 111, 119, 121, 125, 143, 159, 183, 184, 215, 247, 287, 295, 303, 319, 327, 335, 350, 357, 391, 407, 415, 423, 430, 447, 455, 471, 507, 511, 519, 527, 535, 543, 551, 559, 583, 591, 620, 623, 654, 655, 671, 679

Offset

1,2

Comments

Makowski proved that phi(k) + sigma(k) = k*d(k) if and only if k is a prime (see in Sivaramakrishnan, Chapter I, page 8, Theorem 3).

2 is the only prime term of this sequence.

Contains p^2 if p is a prime == 2 or 7 (mod 9), and p*q if p and q are distinct primes with p*q == 7 (mod 8). - Robert Israel, Jan 18 2018

References

R. Sivaramakrishnan, Classical Theory of Arithmetic Functions, Marcel Dekker, Inc., New York and Basel, 1989.

Links

Robert Israel, Table of n, a(n) for n = 1..10000

A. Makowski, Problem 339, Elemente der Mathematik, Vol. 13 (1958), p. 115; alternative link.

C. A. Nicol, Problem E 1674, The American Mathematical Monthly, Vol. 71, No. 3 (1964), p. 317; Another characterization of prime number, Solutions to Problem E 1674 by Martin J. Cohen and J. A. Fridy, ibid., Vol. 72, No. 2 (1965), pp. 186-187.

Formula

Integer solutions of phi(x) + sigma(x) = m * d(x) or A000010(x) + A000203(x) = m * A000005(x)^2, where m is an integer.

Example

78 is a term since it has 8 divisors, phi(78) = 24, sigma(78) = 168, and 24 + 168 = 192 = 3 * 8^2.

Maple

filter:= proc(n) uses numtheory;
  phi(n)+sigma(n) mod tau(n)^2 = 0
end proc:
select(filter, [$1..1000]); # Robert Israel, Jan 18 2018

Mathematica

okQ[n_] := Divisible[EulerPhi[n] + DivisorSigma[1, n], DivisorSigma[0, n]^2];
Select[Range[1000], okQ] (* Jean-François Alcover, May 11 2023 *)

Prog

(PARI) is(n) = {my(f = factor(n)); (eulerphi(f) + sigma(f)) % numdiv(f)^2 == 0; } \\ Amiram Eldar, Mar 25 2024

Crossrefs

Cf. A000005, A000010, A000203, A055465, A055467, A055468.

Sequence in context: A005219 A153945 A153942 * A342957 A148267 A148268

Adjacent sequences: A055463 A055464 A055465 * A055467 A055468 A055469

Keyword

nonn

Author

Labos Elemer, Jun 27 2000

Status

approved