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,1

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")

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)

a(n) = A014197(A000010(n)).

For all n, a(n) <= A071181(n).

(End)

Example

invphi(6) = [7, 9, 14, 18], thus a(7) = a(9) = a(14) = a(18) = 4.

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 *)

Prog

(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

Crossrefs

Cf. A000010, A001055, A014197, A032447, A036913, A057826, A071181.

Cf. A070305 (positions where coincides with A000005).

Sequence in context: A105096 A157790 A070241 * A196048 A176075 A256555

Adjacent sequences: A066409 A066410 A066411 * A066413 A066414 A066415

Keyword

nonn

Author

Vladeta Jovovic, Dec 25 2001

Status

approved