|
%I #48 Jul 04 2018 20:22:51
%S 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,
%T 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,
%U 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
%N Number of elements in the set phi_inverse(phi(n)).
%H Antti Karttunen, <a href="/A066412/b066412.txt">Table of n, a(n) for n = 1..10000</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Euler's_totient_function">Euler's totient function</a> (see the last paragraph in section "Some values of the function")
%F a(n) = Card( k>0 : cototient(k)=cototient(n) ) where cototient(x) = x - phi(x). - _Benoit Cloitre_, May 09 2002
%F From _Antti Karttunen_, Jul 18 2017: (Start)
%F a(n) = A014197(A000010(n)).
%F For all n, a(n) <= A071181(n).
%F (End)
%e invphi(6) = [7, 9, 14, 18], thus a(7) = a(9) = a(14) = a(18) = 4.
%p nops(invphi(phi(n)));
%t 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 *)
%o (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
%o (PARI)
%o ;; Here is an implementation not using arbitrary limits:
%o 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
%o A066412(n) = A014197(eulerphi(n)); \\ _Antti Karttunen_, Jul 19 2017
%o (Scheme)
%o ;; A naive implementation requiring precomputed A057826:
%o (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
%Y Cf. A000010, A001055, A014197, A032447, A036913, A057826, A071181.
%Y Cf. A070305 (positions where coincides with A000005).
%K nonn
%O 1,1
%A _Vladeta Jovovic_, Dec 25 2001
|
