|
|
A073811
|
|
Number of common divisors of n and phi(n).
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
a(n) = Card[Intersection[D[n], D[A000010(n)]]].
|
|
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
|
(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)))))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|