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,1

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).

Formula

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

Prog

(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

Crossrefs

Cf. A000010, A057826, A066412.

Sequence in context: A345165 A062405 A368180 * A213675 A321185 A320322

Adjacent sequences: A071178 A071179 A071180 * A071182 A071183 A071184

Keyword

easy,nonn

Author

Benoit Cloitre, Jun 10 2002

Status

approved