A071181 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

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

(list; graph; refs; listen; history; text; internal format)

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