login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A055466
Numbers k such that d(k)^2 divides phi(k) + sigma(k).
4
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
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
KEYWORD
nonn
AUTHOR
Labos Elemer, Jun 27 2000
STATUS
approved