A055465 - OEIS

%I #24 Mar 25 2024 06:45:33

%S 4,15,21,25,30,33,35,39,45,48,49,51,55,56,57,65,69,70,77,78,81,85,87,

%T 91,93,95,99,102,105,110,111,115,119,121,123,125,126,129,133,135,140,

%U 141,143,145,147,153,155,159,161,165,168,169,174,177,180,182,183,184

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

%C 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.

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

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

%H Charles R Greathouse IV, <a href="/A055465/b055465.txt">Table of n, a(n) for n = 1..10000</a>

%H A. Makowski, <a href="https://gdz.sub.uni-goettingen.de/id/PPN378850199_0013?tify=%7B%22pages%22%3A%5B119%5D%2C%22view%22%3A%22info%22%7D">Problem 339</a>, Elemente der Mathematik, Vol. 13 (1958), p. 115; <a href="https://www.e-periodica.ch/digbib/view?pid=edm-001%3A1958%3A13%3A%3A121">alternative link</a>.

%H C. A. Nicol, <a href="http://www.jstor.org/stable/2312203">Problem E 1674</a>, The American Mathematical Monthly, Vol. 71, No. 3 (1964), p. 317; <a href="http://www.jstor.org/stable/2310997">Another characterization of prime number</a>, Solutions to Problem E 1674 by Martin J. Cohen and J. A. Fridy, ibid., Vol. 72, No. 2 (1965), pp. 186-187.

%F Composite integer solutions of phi(x) + sigma(x) = m * d(x) or A000010(x) + A000203(x) = m * A000005(x), where m is an integer.

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

%t Select[Range[184], CompositeQ[#] && Divisible[(DivisorSigma[1, #] + EulerPhi[#]), DivisorSigma[0, #]] &] (* _Jayanta Basu_, Jul 12 2013 *)

%o (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

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

%K nonn

%O 1,1

%A _Labos Elemer_, Jun 27 2000