A073811 Number of common divisors of n and phi(n).

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 1, 4, 1, 4, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 2, 1, 5, 1, 2, 1, 6, 1, 2, 2, 4, 1, 4, 1, 3, 2, 2, 1, 5, 2, 4, 1, 3, 1, 6, 2, 4, 2, 2, 1, 3, 1, 2, 3, 6, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 2, 3, 1, 4, 1, 5, 4, 2, 1, 6, 1, 2, 1, 4, 1, 4, 1, 3, 2, 2, 1, 6, 1, 4, 2, 6, 1, 2, 1, 4, 2

Offset

1,4

Comments

Where records occur: 1, 4, 8, 16, 32, 36, 72, 108, 144, 216, 432, 648, 864, ... - David A. Corneth, Oct 21 2017

Links

Antti Karttunen, Table of n, a(n) for n = 1..16384

Formula

a(n) = Card[Intersection[D[n], D[A000010(n)]]].

a(n) = Sum_{d|n, d|A000010(n)} 1. - Antti Karttunen, Oct 21 2017

a(n) = A000005(A009195(n)). - Antti Karttunen, Oct 21 2017, after David A. Corneth's PARI-program.

Example

For n = 24: phi(n) = 8, Intersection[{1,2,3,4,6,8,12,24},{1,2,4,8}] = {1,2,4,8}, so a(24) = 4.

Mathematica

g1[x_] := Divisors[x] g2[x_] := Divisors[EulerPhi[x]] ncd[x_] := Length[Intersection[g1[x], g2[x]]] Table[ncd[w], {w, 1, 128}]
Table[Length[Intersection[Divisors[n], Divisors[EulerPhi[n]]]], {n, 110}] (* Harvey P. Dale, Oct 03 2013 *)
a[n_] := DivisorSigma[0, GCD[n, EulerPhi[n]]]; Array[a, 100] (* Amiram Eldar, Jul 01 2022 *)

Prog

(PARI) A073811(n) = sumdiv(eulerphi(n), d, !(n%d)); \\ Antti Karttunen, Oct 21 2017
(PARI) a(n) = numdiv(gcd(eulerphi(n), n)) \\ David A. Corneth, Oct 21 2017
(Scheme)
;; Implemented literally (naively) after the description. Either:
(define (A073811 n) (length (filter (lambda (d) (zero? (modulo n d))) (divisors (A000010 n)))))
;; Or:
(define (A073811 n) (let ((phn (A000010 n))) (length (filter (lambda (d) (zero? (modulo phn d))) (divisors n)))))
(define (divisors n) (cons 1 (proper-divisors n))) ;; This can be also memoized with definec.
(define (proper-divisors n) (let loop ((k n) (divs (list))) (cond ((= 1 k) divs) ((zero? (modulo n k)) (loop (- k 1) (cons k divs))) (else (loop (- k 1) divs)))))
;; Antti Karttunen, Oct 21 2017

Crossrefs

Cf. A000005, A000010, A009195, A073802, A073808, A073809, A073810.

Sequence in context: A380654 A325568 A326195 * A125030 A116479 A366989

Adjacent sequences: A073808 A073809 A073810 * A073812 A073813 A073814

Keyword

nonn

Author

Labos Elemer, Aug 13 2002

Status

approved