login
Numbers n such that tau(n) (or sigma_0(n)) = phi(n).
32

%I #57 Sep 24 2022 13:43:09

%S 1,3,8,10,18,24,30

%N Numbers n such that tau(n) (or sigma_0(n)) = phi(n).

%C Numbers satisfying A000005(n) = A000010(n).

%C This sequence is complete because tau(n) < n^(2/3) for all n except a few small numbers, whereas phi(n) > n/(exp(gamma) * log(log(n)) + 3/(log(log(n))) for n > 2. log(log(n)) grows slowly, so phi(n) > tau(n) for all n greater than some relatively small constant. - _Jud McCranie_, Jun 17 2005

%C Subset of A112587. - _Reinhard Zumkeller_, Sep 14 2005

%C A. P. Minin proved in 1894 that these are the only terms. - _Amiram Eldar_, May 14 2017

%D L. E. Dickson, History of the Theory of Numbers, Vol. 1, (1919), Chapter X, p. 313.

%D Jean-Marie De Koninck, Those Fascinating Numbers, translated by the author. Providence, Rhode Island (2009) American Mathematical Society, p. 3.

%D G. Pólya and G. Szegő, Problems and Theorems in Analysis II, Springer, 1976, Part VIII, Problem 45.

%H A. P. Minin, <a href="http://www.mathnet.ru/php/archive.phtml?wshow=paper&amp;jrnid=sm&amp;paperid=7282&amp;option_lang=eng">On integers N such that the number of divisors of N equals the number of integers less than N and prime to it</a>, Math. Soc. Moscow, Vol. 17, (1894), pp. 537-544 (some front matter is in English and German, article is in Russian)

%e 10 has four divisors: 1, 2, 5, 10, so tau(10) = 4. And four numbers less than 10 are coprime to 10: 1, 3, 7, 9, so phi(10) = 4. Since tau(10) = phi(10), 10 is in the sequence.

%e phi(12) = 4 also, but 12 has more than four divisors: 1, 2, 3, 4, 6, 12. So 12 is not in the sequence.

%p select(k->tau(k)=phi(k),[$1..1000]); # _Peter Luschny_, Aug 26 2011

%t k = 1; s = Select[Range[100000], Equal[Sign[DivisorSigma[k - 1, #] - EulerPhi[#]^k ], 0 ] &]

%t Select[Range[1000], DivisorSigma[0, #] == EulerPhi[#] &] (* _Alonso del Arte_, Jan 15 2019 *)

%o (PARI) isok(n) = numdiv(n) == eulerphi(n); \\ _Michel Marcus_, May 14 2017

%o (Magma) [n: n in [1..1000] | EulerPhi(n) eq NumberOfDivisors(n)]; // _Marius A. Burtea_, Dec 20 2018

%o (GAP) Filtered([1..1000],n->Tau(n)=Phi(n)); # _Muniru A Asiru_, Dec 20 2018

%Y Cf. A064374, A064375, A064376, A064377, A000005, A000010.

%Y Cf. A112954, A062516, A063469, A063470.

%K nonn,fini,full

%O 1,2

%A _David W. Wilson_