A055465 Composite numbers k for which phi(k) + sigma(k) is an integer multiple of the number of divisors of k.

4, 15, 21, 25, 30, 33, 35, 39, 45, 48, 49, 51, 55, 56, 57, 65, 69, 70, 77, 78, 81, 85, 87, 91, 93, 95, 99, 102, 105, 110, 111, 115, 119, 121, 123, 125, 126, 129, 133, 135, 140, 141, 143, 145, 147, 153, 155, 159, 161, 165, 168, 169, 174, 177, 180, 182, 183, 184

Offset

1,1

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). In this more general case the right hand side is instead m*d(k), and this equation holds for all primes.

This sequence is infinite: if p == 1 (mod 3) is prime then p^2 is a term. - Amiram Eldar, Mar 25 2024

References

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

Links

Charles R Greathouse IV, 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

Composite integer solutions of phi(x) + sigma(x) = m * d(x) or A000010(x) + A000203(x) = m * A000005(x), 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 = 24 * 8.

Mathematica

Select[Range[184], CompositeQ[#] && Divisible[(DivisorSigma[1, #] + EulerPhi[#]), DivisorSigma[0, #]] &] (* Jayanta Basu, Jul 12 2013 *)

Prog

(PARI) is(n)=my(f=factor(n)); (eulerphi(f)+sigma(f))%numdiv(f)==0 && !isprime(n) && n>1 \\ Charles R Greathouse IV, Mar 01 2017

Crossrefs

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

Sequence in context: A100783 A170850 A297711 * A209870 A167293 A376693

Adjacent sequences: A055462 A055463 A055464 * A055466 A055467 A055468

Keyword

nonn

Author

Labos Elemer, Jun 27 2000

Status

approved