cp's OEIS Frontend

A014197 Number of numbers m with Euler phi(m) = n.

%I A014197 #136 Mar 27 2025 07:39:24
%S A014197 2,3,0,4,0,4,0,5,0,2,0,6,0,0,0,6,0,4,0,5,0,2,0,10,0,0,0,2,0,2,0,7,0,0,
%T A014197 0,8,0,0,0,9,0,4,0,3,0,2,0,11,0,0,0,2,0,2,0,3,0,2,0,9,0,0,0,8,0,2,0,0,
%U A014197 0,2,0,17,0,0,0,0,0,2,0,10,0,2,0,6,0,0,0,6,0,0,0,3
%N A014197 Number of numbers m with Euler phi(m) = n.
%C A014197 Carmichael conjectured that there are no 1's in this sequence. - _Jud McCranie_, Oct 10 2000
%C A014197 Number of cyclotomic polynomials of degree n. - _T. D. Noe_, Aug 15 2003
%C A014197 Let v == 0 (mod 24), w = v + 24, and v < k < q < w, where k and q are integer. It seems that, for most values of v, there is no b such that b = a(k) + a(q) and b > a(v) + a(w). The first case where b > a(v) + a(w) occurs at v = 888: b = a(896) + a(900) = 15 + 4, b > a(888) + a(912), or 19 > 8 + 7. The first case where v < n < w and a(n) > a(v) + a(w) occurs at v = 2232: a(2240) > a(2232) + a(2256), or 27 > 7 + 8. - _Sergey Pavlov_, Feb 05 2017
%C A014197 One elementary result relating to phi(m) is that if m is odd, then phi(m)=phi(2m) because 1 and 2 both have phi value 1 and phi is multiplicative. - _Roderick MacPhee_, Jun 03 2017
%D A014197 Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B39, pp. 144-146.
%D A014197 Joe Roberts, Lure of The Integers, The Mathematical Association of America, 1992, entry 32, page 182.
%H A014197 T. D. Noe, <a href="/A014197/b014197.txt">Table of n, a(n) for n = 1..10000</a>
%H A014197 Max A. Alekseyev, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Alekseyev/alek5.html">Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.2.
%H A014197 Max Alekseyev, <a href="https://oeis.org/wiki/User:Max_Alekseyev/gpscripts">PARI/GP Scripts for Miscellaneous Math Problems</a> (invphi.gp).
%H A014197 R. D. Carmichael, <a href="https://doi.org/10.1090/S0002-9904-1907-01453-2">On Euler’s phi-function</a>, Bull. Amer. Math. Soc. 13 (1907), 241-243.
%H A014197 R. D. Carmichael, <a href="https://doi.org/10.1090/S0002-9904-1922-03504-5">Note on Euler’s phi-function</a>, Bull. Amer. Math. Soc. 28 (1922), 109-110.
%H A014197 Kevin Ford, <a href="http://arxiv.org/abs/math/9907204">The number of solutions of phi(x)=m</a>, arXiv:math/9907204 [math.NT], 1999.
%H A014197 S. Sivasankaranarayana Pillai, <a href="http://dx.doi.org/10.1090/S0002-9904-1929-04799-2">On some functions connected with phi(n)</a>, Bull. Amer. Math. Soc. 35 (1929), 832-836.
%H A014197 Primefan, <a href="http://primefan.tripod.com/TotientAnswers1000.html">Totient Answers For The First 1000 Integers</a>.
%H A014197 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TotientFunction.html">Totient Function</a>.
%H A014197 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TotientValenceFunction.html">Totient Valence Function</a>.
%F A014197 Dirichlet g.f.: Sum_{n>=1} a(n)*n^-s = zeta(s)*Product_(1+1/(p-1)^s-1/p^s). - _Benoit Cloitre_, Apr 12 2003
%F A014197 Limit_{n->infinity} (1/n) * Sum_{k=1..n} a(k) = zeta(2)*zeta(3)/zeta(6) = 1.94359643682075920505707036... (see A082695). - _Benoit Cloitre_, Apr 12 2003
%F A014197 From _Christopher J. Smyth_, Jan 08 2017: (Start)
%F A014197 Euler transform = Product_{n>=1} (1-x^n)^(-a(n)) = g.f. of A120963.
%F A014197 Product_{n>=1} (1+x^n)^a(n)
%F A014197 = Product_{n>=1} ((1-x^(2n))/(1-x^n))^a(n)
%F A014197 = Product_{n>=1} (1-x^n)^(-A280712(n))
%F A014197 = Euler transform of A280712 = g.f. of A280611.
%F A014197 (End)
%F A014197 a(A000010(n)) = A066412(n). - _Antti Karttunen_, Jul 18 2017
%F A014197 From _Antti Karttunen_, Dec 04 2018: (Start)
%F A014197 a(A000079(n)) = A058321(n).
%F A014197 a(A000142(n)) = A055506(n).
%F A014197 a(A017545(n)) = A063667(n).
%F A014197 a(n) = Sum_{d|n} A008683(n/d)*A070633(d).
%F A014197 a(n) = A056239(A322310(n)).
%F A014197 (End)
%p A014197 with(numtheory): A014197:=n-> nops(invphi(n)): seq(A014197(n), n=1..200);
%t A014197 a[1] = 2; a[m_?OddQ] = 0; a[m_] := Module[{p, nmax, n, k}, p = Select[ Divisors[m]+1, PrimeQ]; nmax = m*Times @@ (p/(p - 1)); n = m; k = 0; While[n <= nmax, If[EulerPhi[n] == m, k++]; n++]; k]; Array[a, 92] (* _Jean-François Alcover_, Dec 09 2011, updated Apr 25 2016 *)
%t A014197 With[{nn = 116}, Function[s, Function[t, Take[#, nn] &@ ReplacePart[t, Map[# -> Length@ Lookup[s, #] &, Keys@ s]]]@ ConstantArray[0, Max@ Keys@ s]]@ KeySort@ PositionIndex@ Array[EulerPhi, Floor[nn^(3/2)] + 10]] (* _Michael De Vlieger_, Jul 19 2017 *)
%o A014197 (PARI) 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 A014197 (PARI) a(n) = invphiNum(n); \\ _Amiram Eldar_, Nov 15 2024 using _Max Alekseyev_'s invphi.gp
%o A014197 (Python)
%o A014197 from sympy import totient, divisors, isprime, prod
%o A014197 def a(m):
%o A014197     if m == 1: return 2
%o A014197     if m % 2: return 0
%o A014197     X = (x + 1 for x in divisors(m))
%o A014197     nmax=m*prod(i/(i - 1) for i in X if isprime(i))
%o A014197     n=m
%o A014197     k=0
%o A014197     while n<=nmax:
%o A014197         if totient(n)==m:k+=1
%o A014197         n+=1
%o A014197     return k
%o A014197 print([a(n) for n in range(1, 51)]) # _Indranil Ghosh_, Jul 18 2017, after Mathematica code
%o A014197 (Magma) [#EulerPhiInverse(n): n in [1..100]]; // _Marius A. Burtea_, Sep 08 2019
%o A014197 (GAP)
%o A014197 a := function(n)
%o A014197 local S, T, R, max, i, k, r;
%o A014197 S:=[];
%o A014197 for i in DivisorsInt(n)+1 do
%o A014197     if IsPrime(i)=true then
%o A014197         S:=Concatenation(S,[i]);
%o A014197     fi;
%o A014197 od;
%o A014197 T:=[];
%o A014197 for k in [1..Size(S)] do
%o A014197     T:=Concatenation(T,[S[k]/(S[k]-1)]);
%o A014197 od;
%o A014197 max := n*Product(T);
%o A014197 R:=[];
%o A014197 for r in [1..Int(max)] do
%o A014197     if Phi(r)=n then
%o A014197         R:=Concatenation(R,[r]);
%o A014197     fi;
%o A014197 od;
%o A014197 return Size(R);
%o A014197 end; # _Miles Englezou_, Oct 22 2024
%Y A014197 Cf. A000010, A002202, A032446 (bisection), A049283, A051894, A055506, A057635, A057826, A058277 (nonzero terms), A058341, A063439, A066412, A070243 (partial sums), A070633, A071386 (positions of odd terms), A071387, A071388 (positions of primes), A071389 (where prime(n) occurs for the first time), A082695, A097942 (positions of records), A097946, A120963, A134269, A219930, A280611, A280709, A280712, A296655 (positions of positive even terms), A305353, A305656, A319048, A322019.
%Y A014197 For records see A131934.
%Y A014197 Column 1 of array A320000.
%K A014197 nonn,nice,easy
%O A014197 1,1
%A A014197 _N. J. A. Sloane_