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
Keywords
Examples
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.
Links
- Antti Karttunen, Table of n, a(n) for n = 1..16384
Programs
-
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 *) -
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
Formula
a(n) = Card[Intersection[D[n], D[A000010(n)]]].
a(n) = Sum_{d|n, d|A000010(n)} 1. - Antti Karttunen, Oct 21 2017
Comments