A066412 -id:A066412 - 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)

A015126 Least k such that phi(k) = phi(n).

Original entry on oeis.org

1, 1, 3, 3, 5, 3, 7, 5, 7, 5, 11, 5, 13, 7, 15, 15, 17, 7, 19, 15, 13, 11, 23, 15, 25, 13, 19, 13, 29, 15, 31, 17, 25, 17, 35, 13, 37, 19, 35, 17, 41, 13, 43, 25, 35, 23, 47, 17, 43, 25, 51, 35, 53, 19, 41, 35, 37, 29, 59, 17, 61, 31, 37, 51, 65, 25, 67, 51, 69, 35, 71, 35, 73

Offset: 1

Vladeta Jovovic, Jan 12 2002

From Jianing Song, Nov 11 2022: (Start)
The first even term is a(33817088) = 16842752 (see A002181 and A143510).
Conjecture: a(n) is always odd for odd n. (End)

Antti Karttunen, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A028476, A066412, A066659.

Cf. A002181, A143510.

a(n) = {my(en = eulerphi(n)); k = 1; while (eulerphi(k) != en, k++); return (k);} \\ Michel Marcus, Jun 17 2013

a(n) = vecmin(select(x -> x<=n, invphi(eulerphi(n)))); \\ Amiram Eldar, Nov 14 2024, using Max Alekseyev's invphi.gp

A028476 Greatest k such that phi(k) = phi(n), where phi is Euler's totient function.

Original entry on oeis.org

2, 2, 6, 6, 12, 6, 18, 12, 18, 12, 22, 12, 42, 18, 30, 30, 60, 18, 54, 30, 42, 22, 46, 30, 66, 42, 54, 42, 58, 30, 62, 60, 66, 60, 90, 42, 126, 54, 90, 60, 150, 42, 98, 66, 90, 46, 94, 60, 98, 66, 120, 90, 106, 54, 150, 90, 126, 58, 118, 60, 198, 62, 126, 120, 210, 66, 134

Offset: 1

Vladeta Jovovic, Jan 12 2002

nonn

Every number in this sequence occurs at least twice. For all n > 6, a(n) > phi(n)^2 is impossible. - Alonso del Arte, Dec 31 2016

			phi(1) = 1 and phi(2) = 1 also. There is no greater k such that phi(k) = 1, so therefore a(1) = a(2) = 2.
phi(3) = phi(4) = phi(6) = 2, and there is no greater k such that phi(k) = 6, hence a(3) = a(4) = a(6) = 6.

Antti Karttunen, Table of n, a(n) for n = 1..10000 (computed from the b-file of A057826 provided by T. D. Noe)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A015126, A057826, A066412, A066659, A071181.

Table[Module[{k = (2 Boole[n <= 6]) + #^2}, While[EulerPhi@ k != #, k--]; k] &@ EulerPhi@ n, {n, 120}] (* Michael De Vlieger, Dec 31 2016 *)

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

a(1) = a(2) = 2, for n > 2, a(n) = A057826(A000010(n)/2). - Antti Karttunen, Aug 07 2017

A071181 Number of numbers k such that phi(k) divides phi(n).

Original entry on oeis.org

2, 2, 5, 5, 9, 5, 9, 9, 9, 9, 7, 9, 19, 9, 14, 14, 20, 9, 13, 14, 19, 7, 7, 14, 16, 19, 13, 19, 11, 14, 13, 20, 16, 20, 34, 19, 31, 13, 34, 20, 30, 19, 13, 16, 34, 7, 7, 20, 13, 16, 27, 34, 11, 13, 30, 34, 31, 11, 7, 20, 37, 13, 31, 27, 51, 16, 13, 27, 14, 34, 9, 34, 63, 31, 30, 31

Offset: 1

Benoit Cloitre, Jun 10 2002

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..2048 from Antti Karttunen computed with the help of b-file of A057826 provided by T. D. Noe)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A057826, A066412.

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

a(n) = {my(v = 0); fordiv(eulerphi(n), d, v += invphiNum(d)); v;}  \\ Amiram Eldar, Nov 12 2024, using Max Alekseyev's invphi.gp; edited by Max Alekseyev, Nov 16 2024

;; A naive implementation requiring precomputed A057826:
(define (A071181 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 (zero? (modulo ph (A000010 k))) 1 0)))))))) ;; Antti Karttunen, Jul 18 2017

For all n, a(n) >= A066412(n). - Antti Karttunen, Jul 17 2017

A070242 a(n) = Card( k>0 : sigma(k)=sigma(n) ).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 3, 3, 2, 2, 1, 1, 3, 2, 1, 3, 3, 2, 3, 1, 2, 1, 5, 2, 1, 3, 2, 3, 1, 1, 3, 2, 3, 3, 4, 1, 3, 1, 5, 3, 2, 1, 1, 5, 2, 2, 4, 5, 4, 2, 3, 3, 6, 1, 4, 2, 1, 3, 5, 1, 2, 4, 5, 5, 1, 1, 2, 2, 2, 4, 6, 2, 2, 1, 2, 3, 3, 2, 2, 4, 4, 3, 3, 1, 6, 2, 5, 4, 6, 2, 1, 2, 1, 1, 5, 2, 2, 5

Offset: 1

Benoit Cloitre, May 09 2002

Antti Karttunen, Table of n, a(n) for n = 1..16384
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000203, A054973, A066412.

for(n=1,150,print1(sum(i=1,10*n,if(sigma(n)-sigma(i),0,1)),","))

A070242(n) = { my(s=sigma(n)); length(select(i->sigma(i) == s, vector(s, i, i))); } \\ Antti Karttunen, Nov 07 2017

A070242(n) = { my(s=sigma(n)); sum(k=1, s, (sigma(k)==s)); }; \\ Antti Karttunen, Nov 07 2017

a(n) = invsigmaNum(sigma(n)); \\ Amiram Eldar, Dec 20 2024, using Max Alekseyev's invphi.gp

a(n) = A054973(A000203(n)). - Antti Karttunen, Nov 07 2017

A070305 Numbers m such that Card(k>0 : phi(k)=phi(m)) = tau(m).

Original entry on oeis.org

2, 4, 8, 10, 11, 14, 16, 23, 27, 28, 29, 31, 32, 38, 47, 53, 59, 64, 67, 71, 79, 83, 86, 100, 103, 107, 114, 125, 127, 128, 131, 136, 137, 139, 147, 149, 151, 167, 170, 172, 173, 176, 179, 191, 197, 199, 202, 211, 223, 227, 229, 235, 239, 251, 256, 263, 265, 269

Offset: 1

Benoit Cloitre, May 10 2002

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Antti Karttunen)
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").

Cf. A000005, A000010, A057826, A066412.

With[{nn = 300}, Function[s, DeleteCases[MapIndexed[If[DivisorSigma[0, First@ #2] == #1, First@ #2, 0] &, Take[#, nn]], 0] &@ Values@ KeySort@ Flatten@ Map[Function[{k, m}, Map[# -> m &, k]] @@ {#, Length@ #} &@ Lookup[s, #] &, Keys@ s]]@ KeySort@ PositionIndex@ Array[EulerPhi, Floor[nn^(4/3)] + 10]] (* Michael De Vlieger, Jul 18 2017 *)

for(n=1,350,if(sum(i=1,10*n,if(eulerphi(n)-eulerphi(i),0,1))==numdiv(n),print1(n,","))) \\ By the original author. 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

\\ 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));
isA070305(n) = (A066412(n) == numdiv(n));
n=0; k=1; while(k <= 1000, n=n+1; if(isA070305(n),write("b070305.txt", k, " ", n);k=k+1)); \\ Antti Karttunen, Jul 19 2017

is(m) = {my(f = factor(m)); invphiNum(eulerphi(f)) == numdiv(f);} \\ Amiram Eldar, Nov 19 2024, using Max Alekseyev's invphi.gp

;; With my IntSeq-library.
(define A070305 (MATCHING-POS 1 1 (lambda (n) (= (A066412 n) (A000005 n))))) ;; Antti Karttunen, Jul 18 2017

Numbers k such that A066412(k) = A000005(k).

A262599 Lexicographically earliest sequence of distinct terms such that, for any n > 0, phi(a(n)) = phi(n) (where phi denotes the Euler totient function), and a(n) > n if possible.

Original entry on oeis.org

2, 1, 4, 6, 8, 3, 9, 10, 14, 12, 22, 5, 21, 18, 16, 20, 32, 7, 27, 24, 26, 11, 46, 30, 33, 28, 38, 36, 58, 15, 62, 34, 44, 40, 39, 42, 57, 54, 45, 48, 55, 13, 49, 50, 52, 23, 94, 60, 86, 66, 64, 56, 106, 19, 75, 70, 63, 29, 118, 17, 77, 31, 74, 68, 104, 25

Offset: 1

Paul Tek, Sep 25 2015

nonn

This is a permutation of the positive integers, with inverse A262603.
If the Carmichael's totient function conjecture is true, then this sequence has no fixed point.
For any n > 0, the orbit of n is finite, with length A066412(n).

			phi(n) = 6 iff n is in { 7, 9, 14, 18 }.
Hence: a(7) = 9, a(9) = 14, a(14) = 18, a(18) = 7.

Paul Tek, Table of n, a(n) for n = 1..10000
Paul Tek, C program for this sequence
Index entries for sequences that are permutations of the natural numbers

Cf. A049283, A066412, A066659, A262603 (inverse).

C
```
// See Links section for C program.
```

a(n) = max(A066659(n), A049283(A000010(n))), for any n > 0.

cp's OEIS Frontend

A070241 Erroneous version of A066412.

Views

Author

Keywords

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

A015126 Least k such that phi(k) = phi(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

A028476 Greatest k such that phi(k) = phi(n), where phi is Euler's totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A071181 Number of numbers k such that phi(k) divides phi(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Scheme

Formula

A070242 a(n) = Card( k>0 : sigma(k)=sigma(n) ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

PARI

PARI

Formula

A070305 Numbers m such that Card(k>0 : phi(k)=phi(m)) = tau(m).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Scheme