|
%I #122 Sep 08 2022 08:44:39
%S 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 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 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 Number of numbers m with Euler phi(m) = n.
%C Carmichael conjectured that there are no 1's in this sequence. - _Jud McCranie_, Oct 10 2000
%C Number of cyclotomic polynomials of degree n. - _T. D. Noe_, Aug 15 2003
%C 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 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 R. K. Guy, Unsolved Problems in Number Theory, section B39.
%D J. Roberts, Lure of The Integers, entry 32, page 182.
%H T. D. Noe, <a href="/A014197/b014197.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 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 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 K. 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 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 Primefan, <a href="http://primefan.tripod.com/TotientAnswers1000.html">Totient Answers For The First 1000 Integers</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotientFunction.html">Totient Function</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotientValenceFunction.html">Totient Valence Function</a>
%F 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 Lim_{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 From _Christopher J. Smyth_, Jan 08 2017: (Start)
%F Euler transform = Product_{n>=1} (1-x^n)^(-a(n)) = g.f. of A120963.
%F Product_{n>=1} (1+x^n)^a(n)
%F = Product_{n>=1} ((1-x^(2n))/(1-x^n))^a(n)
%F = Product_{n>=1} (1-x^n)^(-A280712(n))
%F = Euler transform of A280712 = g.f. of A280611.
%F (End)
%F a(A000010(n)) = A066412(n). - _Antti Karttunen_, Jul 18 2017
%F From _Antti Karttunen_, Dec 04 2018: (Start)
%F a(A000079(n)) = A058321(n).
%F a(A000142(n)) = A055506(n).
%F a(A017545(n)) = A063667(n).
%F a(n) = Sum_{d|n} A008683(n/d)*A070633(d).
%F a(n) = A056239(A322310(n)).
%F (End)
%p with(numtheory): A014197:=n-> nops(invphi(n)): seq(A014197(n), n=1..200);
%t 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 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 (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 (Python)
%o from sympy import totient, divisors, isprime, prod
%o def a(m):
%o if m == 1: return 2
%o if m % 2: return 0
%o X = (x + 1 for x in divisors(m))
%o nmax=m*prod(i/(i - 1) for i in X if isprime(i))
%o n=m
%o k=0
%o while n<=nmax:
%o if totient(n)==m:k+=1
%o n+=1
%o return k
%o print([a(n) for n in range(1, 51)]) # _Indranil Ghosh_, Jul 18 2017, after Mathematica code
%o (Magma) [#EulerPhiInverse(n): n in [1..100]]; // _Marius A. Burtea_, Sep 08 2019
%Y 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 For records see A131934.
%Y Column 1 of array A320000.
%K nonn,nice,easy
%O 1,1
%A _N. J. A. Sloane_
|
