A066412 Number of elements in the set phi_inverse(phi(n)).
2, 2, 3, 3, 4, 3, 4, 4, 4, 4, 2, 4, 6, 4, 5, 5, 6, 4, 4, 5, 6, 2, 2, 5, 5, 6, 4, 6, 2, 5, 2, 6, 5, 6, 10, 6, 8, 4, 10, 6, 9, 6, 4, 5, 10, 2, 2, 6, 4, 5, 7, 10, 2, 4, 9, 10, 8, 2, 2, 6, 9, 2, 8, 7, 11, 5, 2, 7, 3, 10, 2, 10, 17, 8, 9, 8, 9, 10, 2, 7, 2, 9, 2, 10, 8, 4, 3, 9, 6, 10, 17, 3, 9, 2, 17, 7
Offset: 1
Keywords
Examples
invphi(6) = [7, 9, 14, 18], thus a(7) = a(9) = a(14) = a(18) = 4.
Links
- Antti Karttunen, Table of n, a(n) for n = 1..10000
- Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
- Wikipedia, Euler's totient function (see the last paragraph in section "Some values of the function")
Crossrefs
Programs
-
Maple
nops(invphi(phi(n)));
-
Mathematica
With[{nn = 120}, Function[s, Take[#, nn] &@ Values@ KeySort@ Flatten@ Map[Function[{k, m}, Map[# -> m &, k]] @@ {#, Length@ #} &@ Lookup[s, #] &, Keys@ s]]@ KeySort@ PositionIndex@ Array[EulerPhi, nn^2 + 10]] (* Michael De Vlieger, Jul 18 2017 *) -
PARI
for(n=1,150,print1(sum(i=1,10*n,if(n-eulerphi(n)-i+eulerphi(i),0,1)),",")) \\ By the original author(s). Note: the upper limit 10*n for the search range is quite ad hoc, and is guaranteed to miss some cases when n is large enough. Cf. Wikipedia-article. - Antti Karttunen, Jul 19 2017
-
PARI
\\ Here is an implementation not using arbitrary limits: A014197(n, m=1) = { n==1 && return(1+(m<2)); my(p, q); sumdiv(n, d, if( d>=m && isprime(d+1), sum( i=0, valuation(q=n\d, p=d+1), A014197(q\p^i, p))))} \\ M. F. Hasler, Oct 05 2009 A066412(n) = A014197(eulerphi(n)); \\ Antti Karttunen, Jul 19 2017
-
PARI
a(n) = invphiNum(eulerphi(n)); \\ Amiram Eldar, Nov 14 2024, using Max Alekseyev's invphi.gp
-
Scheme
;; A naive implementation requiring precomputed A057826: (define (A066412 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 (= ph (A000010 k)) 1 0)))))))) ;; Antti Karttunen, Jul 18 2017
Formula
a(n) = Card( k>0 : cototient(k)=cototient(n) ) where cototient(x) = x - phi(x). - Benoit Cloitre, May 09 2002
From Antti Karttunen, Jul 18 2017: (Start)
For all n, a(n) <= A071181(n).
(End)