A070633 -id:A070633 - cp's OEIS frontend

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

N. J. A. Sloane

Carmichael conjectured that there are no 1's in this sequence. - Jud McCranie, Oct 10 2000
Number of cyclotomic polynomials of degree n. - T. D. Noe, Aug 15 2003
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
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

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.

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.

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.

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

[#EulerPhiInverse(n): n in [1..100]]; // Marius A. Burtea, Sep 08 2019

with(numtheory): A014197:=n-> nops(invphi(n)): seq(A014197(n), n=1..200);

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

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

a(n) = invphiNum(n); \\ Amiram Eldar, Nov 15 2024 using Max Alekseyev's invphi.gp

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

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))
= Euler transform of A280712 = g.f. of A280611.
(End)
a(A000010(n)) = A066412(n). - Antti Karttunen, Jul 18 2017
From Antti Karttunen, Dec 04 2018: (Start)
a(A000079(n)) = A058321(n).
a(A000142(n)) = A055506(n).
a(A017545(n)) = A063667(n).
a(n) = Sum_{d|n} A008683(n/d)*A070633(d).
a(n) = A056239(A322310(n)).
(End)

A069932 Number of k, 1<=k<=n, such that phi(k) divides n.

Original entry on oeis.org

1, 2, 2, 4, 2, 5, 2, 7, 2, 5, 2, 11, 2, 5, 2, 11, 2, 9, 2, 10, 2, 5, 2, 19, 2, 5, 2, 9, 2, 11, 2, 16, 2, 5, 2, 20, 2, 5, 2, 18, 2, 9, 2, 10, 2, 5, 2, 32, 2, 7, 2, 9, 2, 13, 2, 15, 2, 5, 2, 26, 2, 5, 2, 22, 2, 11, 2, 9, 2, 7, 2, 38, 2, 5, 2, 9, 2, 9, 2, 30, 2, 5, 2, 23, 2, 5, 2, 17, 2, 17, 2, 10, 2, 5

Offset: 1

Benoit Cloitre, May 05 2002

Unlike A070633, this sequence does not give the number of all integers of the form phi(k) dividing n (for some n and some m > n, phi(m) divides n).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Vaclav Kotesovec, Plot of Sum_{k=1..n} a(k)/(n*log(n)) for n = 2..65537 (based on b-file).

Cf. A000010, A070633, A378642.

Row lengths of A378636.

a[n_] := Boole[ Divisible[n, EulerPhi[#]]] & /@ Range[n] // Total; Table[a[n], {n, 1, 94}] (* Jean-François Alcover, May 23 2013 *)

for(n=1,150,print1(sum(i=1,n,if(n%eulerphi(i),0,1)),","))

a(n)=if(n<1,0,polcoeff(sum(k=1,n,1/(1-x^eulerphi(k)),x*O(x^n)),n))

A069932(n) = sum(k=1, n, !(n%eulerphi(k))); \\ Antti Karttunen, Sep 10 2018

a(n) = sumdiv(n, d, #select(x -> x<=n, invphi(d))); \\ Amiram Eldar, Nov 29 2024, using Max Alekseyev's invphi.gp

Asymptotically (still conjectured): Sum_{k=1..n} a(k) = C*n*log(n) + o(n*log(n)) with C = 1.5...
G.f.: Sum_{k>=1} 1/(1-x^phi(k)).
a(n) <= A070633(n). - Antti Karttunen, Sep 10 2018
a(n) = Sum_{k=1..n} (1 - ceiling(n/phi(k)) + floor(n/phi(k))). - Wesley Ivan Hurt, Apr 21 2023
a(n) = n - A378642(n). - Paolo Xausa, Dec 06 2024

A319048 a(n) is the greatest k such that A000010(k) divides n where A000010 is the Euler totient function.

Original entry on oeis.org

2, 6, 2, 12, 2, 18, 2, 30, 2, 22, 2, 42, 2, 6, 2, 60, 2, 54, 2, 66, 2, 46, 2, 90, 2, 6, 2, 58, 2, 62, 2, 120, 2, 6, 2, 126, 2, 6, 2, 150, 2, 98, 2, 138, 2, 94, 2, 210, 2, 22, 2, 106, 2, 162, 2, 174, 2, 118, 2, 198, 2, 6, 2, 240, 2, 134, 2, 12, 2, 142, 2, 270, 2, 6, 2, 12, 2, 158, 2, 330

Offset: 1

Michel Marcus, Sep 09 2018

nonn

Sándor calls this function the totient maximum function and remarks that this function is well-defined, since a(n) can be at least 2, and cannot be greater than n^2 (when n > 6).

Antti Karttunen, Table of n, a(n) for n = 1..16384
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
József Sándor, On the Euler minimum and maximum functions, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, Pages 1—8.

Cf. A000010 (Euler totient), A061026 (the totient minimum function).
Cf. A319068 (the analog for the sum of divisors).
Cf. A070633, also A057635, A057826, A069932, A071181.
Right border of A378638.

a[n_] := Module[{kmax = If[n <= 6, 10 n, n^2]}, For[k = kmax, True, k--, If[Divisible[n, EulerPhi[k]], Return[k]]]];
Array[a, 80] (* Jean-François Alcover, Sep 17 2018, from PARI *)

a(n) = {my(kmax = if (n<=6, 10*n, n^2)); forstep (k=kmax, 1, -1, if ((n % eulerphi(k)) == 0, return (k)););}

\\ (The first two functions could probably be combined in a smarter way):
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))))} \\ From A014197 by M. F. Hasler
A057635(n) = if(1==n,2,if((n%2),0,my(k=A014197(n),i=n); if(!k, 0, while(k, i++; if(eulerphi(i)==n, k--)); (i))));
A319048(n) = { my(m=0); fordiv(n,d, m = max(m,A057635(d))); (m); }; \\ Antti Karttunen, Sep 09 2018

a(n) = {my(d = divisors(n)); vecmax(vector(#d, i, invphiMax(d[i])));} \\ Amiram Eldar, Nov 29 2024, using Max Alekseyev's invphi.gp

a(n) = Max_{d|n} A057635(d). - Antti Karttunen, Sep 09 2018

A378638 Irregular triangle read by rows: row n lists all m such that phi(m) divides n, where phi is the Euler totient function (A000010).

Original entry on oeis.org

1, 2, 1, 2, 3, 4, 6, 1, 2, 1, 2, 3, 4, 5, 6, 8, 10, 12, 1, 2, 1, 2, 3, 4, 6, 7, 9, 14, 18, 1, 2, 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 1, 2, 1, 2, 3, 4, 6, 11, 22, 1, 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 18, 21, 26, 28, 36, 42, 1, 2, 1, 2, 3, 4, 6, 1, 2

Offset: 1

Paolo Xausa, Dec 03 2024

If n is odd, row n is {1, 2}.

If n is even, row n begins with {1, 2, 3, 4}.

			Triangle begins:
  n\k| 1  2  3  4  5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20 ...
  ----------------------------------------------------------------------------------
   1 | 1, 2;
   2 | 1, 2, 3, 4, 6;
   3 | 1, 2;
   4 | 1, 2, 3, 4, 5,  6,  8, 10, 12;
   5 | 1, 2;
   6 | 1, 2, 3, 4, 6,  7,  9, 14, 18;
   7 | 1, 2;
   8 | 1, 2, 3, 4, 5,  6,  8, 10, 12, 15, 16, 20, 24, 30;
   9 | 1, 2;
  10 | 1, 2, 3, 4, 6, 11, 22;
  11 | 1, 2;
  12 | 1, 2, 3, 4, 5,  6,  7,  8,  9, 10, 12, 13, 14, 18, 21, 26, 28, 36, 42;
  13 | 1, 2;
  14 | 1, 2, 3, 4, 6;
  15 | 1, 2;
  16 | 1, 2, 3, 4, 5,  6,  8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, 48, 60;
  17 | 1, 2;
  18 | 1, 2, 3, 4, 6,  7,  9, 14, 18, 19, 27, 38, 54;
  19 | 1, 2;
  20 | 1, 2, 3, 4, 5,  6,  8, 10, 11, 12, 22, 25, 33, 44, 50, 66;
  ...

Paolo Xausa, Table of n, a(n) for n = 1..13988 (rows 1..1000 of triangle, flattened).

Cf. A070633 (row lengths), A319048 (right border), A378639 (row sums).
Supersequence of A378636.
Cf. A000010.

With[{nmax = 25}, Table[If[OddQ[n], {1, 2}, PositionIndex[Divisible[n, #[[;; Max[n^2, 6]]]]][True]], {n, nmax}] & [EulerPhi[Range[nmax^2]]]]

row(n) = select(x->!(n % eulerphi(x)), [1..max(n^2, 6)]); \\ Michel Marcus, Dec 05 2024

T(n,k) <= n^2, for n > 2 (see A319048).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A069932 Number of k, 1<=k<=n, such that phi(k) divides n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

A319048 a(n) is the greatest k such that A000010(k) divides n where A000010 is the Euler totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A378638 Irregular triangle read by rows: row n lists all m such that phi(m) divides n, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula