A071181 Number of numbers k such that phi(k) divides phi(n).

2, 2, 5, 5, 9, 5, 9, 9, 9, 9, 7, 9, 19, 9, 14, 14, 20, 9, 13, 14, 19, 7, 7, 14, 16, 19, 13, 19, 11, 14, 13, 20, 16, 20, 34, 19, 31, 13, 34, 20, 30, 19, 13, 16, 34, 7, 7, 20, 13, 16, 27, 34, 11, 13, 30, 34, 31, 11, 7, 20, 37, 13, 31, 27, 51, 16, 13, 27, 14, 34, 9, 34, 63, 31, 30, 31

Offset: 1

Author

Benoit Cloitre, Jun 10 2002

Keywords

• easy
• nonn

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..2048 from Antti Karttunen computed with the help of b-file of A057826 provided by T. D. Noe)
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Crossrefs

Cf. A000010, A057826, A066412.

Programs

PARI

for(n=1,100,print1(sum(i=1,1000,if(eulerphi(n)%eulerphi(i),0,1)),","))

PARI

a(n) = {my(v = 0); fordiv(eulerphi(n), d, v += invphiNum(d)); v;}  \\ Amiram Eldar, Nov 12 2024, using Max Alekseyev's invphi.gp; edited by Max Alekseyev, Nov 16 2024

Scheme

;; A naive implementation requiring precomputed A057826:
(define (A071181 n) (if (<= n 2) 2 (let ((ph (A000010 n))) (let loop ((k (A057826 (/ ph 2))) (s 0)) (if (zero? k) s (loop (- k 1) (+ s (if (zero? (modulo ph (A000010 k))) 1 0)))))))) ;; Antti Karttunen, Jul 18 2017

Formula

For all n, a(n) >= A066412(n). - Antti Karttunen, Jul 17 2017