A014197 Number of numbers m with Euler phi(m) = n.
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, 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, 0, 2, 0, 17, 0, 0, 0, 0, 0, 2, 0, 10, 0, 2, 0, 6, 0, 0, 0, 6, 0, 0, 0, 3
Offset: 1
References
- Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B39, pp. 144-146.
- Joe Roberts, Lure of The Integers, The Mathematical Association of America, 1992, entry 32, page 182.
Links
- T. D. Noe, Table of n, a(n) for n = 1..10000
- Max A. Alekseyev, Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions, Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.2.
- Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
- R. D. Carmichael, On Euler’s phi-function, Bull. Amer. Math. Soc. 13 (1907), 241-243.
- R. D. Carmichael, Note on Euler’s phi-function, Bull. Amer. Math. Soc. 28 (1922), 109-110.
- Kevin Ford, The number of solutions of phi(x)=m, arXiv:math/9907204 [math.NT], 1999.
- S. Sivasankaranarayana Pillai, On some functions connected with phi(n), Bull. Amer. Math. Soc. 35 (1929), 832-836.
- Primefan, Totient Answers For The First 1000 Integers.
- Eric Weisstein's World of Mathematics, Totient Function.
- Eric Weisstein's World of Mathematics, Totient Valence Function.
Crossrefs
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.
For records see A131934.
Column 1 of array A320000.
Programs
-
GAP
a := function(n) local S, T, R, max, i, k, r; S:=[]; for i in DivisorsInt(n)+1 do if IsPrime(i)=true then S:=Concatenation(S,[i]); fi; od; T:=[]; for k in [1..Size(S)] do T:=Concatenation(T,[S[k]/(S[k]-1)]); od; max := n*Product(T); R:=[]; for r in [1..Int(max)] do if Phi(r)=n then R:=Concatenation(R,[r]); fi; od; return Size(R); end; # Miles Englezou, Oct 22 2024 -
Magma
[#EulerPhiInverse(n): n in [1..100]]; // Marius A. Burtea, Sep 08 2019
-
Maple
with(numtheory): A014197:=n-> nops(invphi(n)): seq(A014197(n), n=1..200);
-
Mathematica
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 *) 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 *) -
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
-
PARI
a(n) = invphiNum(n); \\ Amiram Eldar, Nov 15 2024 using Max Alekseyev's invphi.gp
-
Python
from sympy import totient, divisors, isprime, prod def a(m): if m == 1: return 2 if m % 2: return 0 X = (x + 1 for x in divisors(m)) nmax=m*prod(i/(i - 1) for i in X if isprime(i)) n=m k=0 while n<=nmax: if totient(n)==m:k+=1 n+=1 return k print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 18 2017, after Mathematica code
Formula
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
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
From Christopher J. Smyth, Jan 08 2017: (Start)
Euler transform = Product_{n>=1} (1-x^n)^(-a(n)) = g.f. of A120963.
Product_{n>=1} (1+x^n)^a(n)
= Product_{n>=1} ((1-x^(2n))/(1-x^n))^a(n)
= Product_{n>=1} (1-x^n)^(-A280712(n))
(End)
From Antti Karttunen, Dec 04 2018: (Start)
(End)
Comments