A058277 -id:A058277 - cp's OEIS frontend

A035113 Numbers != 2 (mod 4) listed in order of increasing totient function phi (A000010).

1, 3, 4, 5, 8, 12, 7, 9, 15, 16, 20, 24, 11, 13, 21, 28, 36, 17, 32, 40, 48, 60, 19, 27, 25, 33, 44, 23, 35, 39, 45, 52, 56, 72, 84, 29, 31, 51, 64, 68, 80, 96, 120, 37, 57, 63, 76, 108, 41, 55, 75, 88, 100, 132, 43, 49, 69, 92, 47, 65, 104, 105, 112, 140, 144

Offset: 1

N. J. A. Sloane

			phi(1)=1, phi(3)=2, phi(4)=2, phi(5)=4, ...

Dumitru Damian, Table of n, a(n) for n = 1..10000
L. C. Washington, The Main Conjecture and Annihilation of Class Groups, In: Introduction to Cyclotomic Fields, Graduate Texts in Mathematics, vol 83 (1997) Springer, New York, NY.

Cf. A000010, A035114.

Cf. A002181, A002202, A007614, A014197, A016825, A032447, A058277.

from sympy import totient as A000010
def lov(n): return sorted([[A000010(n), n] for n in range(1,n) if n%4 != 2])
print([x[1] for x in lov(200)][:100]) # Dumitru Damian, Feb 01 2022

More terms from James Sellers

a(43) onward corrected by Sean A. Irvine, Sep 26 2020

A035114 Values of phi(n) corresponding to A035113.

Original entry on oeis.org

1, 2, 2, 4, 4, 4, 6, 6, 8, 8, 8, 8, 10, 12, 12, 12, 12, 16, 16, 16, 16, 16, 18, 18, 20, 20, 20, 22, 24, 24, 24, 24, 24, 24, 24, 28, 30, 32, 32, 32, 32, 32, 32, 36, 36, 36, 36, 36, 40, 40, 40, 40, 40, 40, 42, 42, 44, 44, 46, 48, 48, 48, 48, 48, 48, 48, 48, 48

Offset: 1

N. J. A. Sloane

			phi(1)=1, phi(3)=2, phi(4)=2, phi(5)=4, ...

Dumitru Damian, Table of n, a(n) for n = 1..10000
L. C. Washington, The Main Conjecture and Annihilation of Class Groups, In: Introduction to Cyclotomic Fields, Graduate Texts in Mathematics, vol 83 (1997) Springer, New York, NY.

Cf. A000010, A035113.

Cf. A002181, A002202, A007614, A014197, A016825, A032447, A058277.

from sympy import totient as A000010
def lov(n): return sorted([[A000010(n), n] for n in range(1,n) if n%4 != 2])
print([x[0] for x in lov(200)][:100]) # Dumitru Damian, Feb 03 2022

a(n) = A000010(A035113(n)). - Michel Marcus, Feb 07 2022

More terms from James Sellers

a(43) onward corrected by Sean A. Irvine, Sep 26 2020

A071387 Smallest number k for which the set of solutions to phi(x) = k has 2n-1 entries.

Original entry on oeis.org

0, 2, 8, 32, 40, 48, 396, 704, 72, 216, 144, 1056, 360, 384, 1320, 240, 9000, 7128, 480, 1296, 15936, 3072, 864, 7344, 720, 4992, 2016, 6000, 4752, 3024, 9984, 1920, 7560, 22848, 29160, 3360, 13248, 27720, 9072, 9360, 4032, 4800, 16896, 3840, 9504, 23520, 5040

Offset: 1

Labos Elemer, May 23 2002

nonn

			For n = 7: 2n-1 = 13, a(7) = Min(InvPhi(13)) = Min({396,400,420,552,560,660}) = 396.

Amiram Eldar, Table of n, a(n) for n = 1..1000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (see invphi.gp there).

Cf. A000010 (phi), A014197, A058277, A063512, A071386, A071388, A071389.

a(n) = {if (n==1, return (0)); my(k=1); while(#invphi(k) != 2*n-1, k++); k;} \\ Michel Marcus, May 13 2020

a(n) = Min({x; Card(InvPhi(x)) = 2n-1}); a(1)=0 because of Carmichael conjecture.

a(12)-a(47) from Donovan Johnson, Jul 27 2011

A071388 Numbers k such that the cardinality of the set of solutions to phi(x) = k is a prime.

Original entry on oeis.org

1, 2, 8, 10, 20, 22, 28, 30, 32, 44, 46, 48, 52, 54, 56, 58, 66, 70, 72, 78, 82, 92, 96, 102, 104, 106, 110, 116, 120, 126, 130, 132, 136, 138, 140, 148, 150, 156, 164, 166, 172, 178, 190, 196, 198, 204, 210, 212, 216, 220, 222, 226, 228, 238, 240, 250, 260, 262

Offset: 1

Labos Elemer, May 23 2002

nonn

All terms except 1 are even. - Robert Israel, Mar 29 2020

			InvPhi(48) = {65,104,105,112,130,140,144,156,168,180,210} has 11 terms, so 48 is a term.

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

Cf. A000010, A007366, A007367, A014197, A058277, A060668, A060670, A060674, A063512, A071386-A071389.

filter:= n -> isprime(nops(numtheory:-invphi(n))):
select(filter, [$1..400]); # Robert Israel, Mar 29 2020

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

A071389 Least number m such that cardinality of InvPhi(m) = prime(n).

Original entry on oeis.org

1, 2, 8, 32, 48, 396, 72, 216, 1056, 1320, 240, 480, 15936, 3072, 7344, 2016, 3024, 9984, 22848, 3360, 13248, 9360, 4800, 9504, 9216, 23328, 7680, 53280, 12480, 29376, 91200, 159744, 22464, 228960, 29952, 179200, 47040, 68544, 15840, 20736, 61440

Offset: 1

Labos Elemer, May 23 2002

nonn

			For n = 11: prime(11) = 31, Card(InvPhi(x)) = 31 for {240, 672, ...}; the smallest is 240 = a(11).

Amiram Eldar, Table of n, a(n) for n = 1..1000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A014197, A058277, A063512, A071386, A071387, A071388.

lista(len) = {my(p = prime(len), v = vector(p, i, -!isprime(i)), c = 0, k = 1, i); while(c < len, i = invphiNum(k); if(i > 0 && i <= p && v[i] == 0, c++; v[i] = k); k++); select(x -> x > 0, v);} \\ Amiram Eldar, Nov 11 2024, using Max Alekseyev's invphi.gp

a(n) = Min{x; Card(InvPhi(x)) = prime(n), n-th prime}

4 more terms from Emeric Deutsch, Jul 25 2005

More terms from Max Alekseyev, Apr 24 2010

A058341 Primes p such that phi(x) = p - 1 has more than 2 solutions.

Original entry on oeis.org

3, 5, 7, 13, 17, 19, 37, 41, 43, 61, 73, 89, 97, 101, 109, 113, 157, 163, 181, 193, 233, 241, 257, 277, 281, 313, 337, 349, 353, 397, 401, 409, 421, 433, 449, 457, 461, 487, 521, 541, 577, 593, 601, 613, 617, 641, 661, 673, 701, 733, 757, 761, 769, 821, 829

Offset: 1

Labos Elemer, Dec 14 2000

nonn

There are always at least 2 such values: p and 2p. - Franklin T. Adams-Watters, May 17 2010

			3 is a term since phi(x) = 3 - 1 = 2 has more than 2 solutions: 3, 4 and 6.
5 is a term since phi(x) = 5 - 1 = 4 has more than 2 solutions: 5, 8, 10 and 12.

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

Cf. A000010, A006093.

Cf. A014197, A058277, A005277. - Franklin T. Adams-Watters, May 17 2010

isok(p) = isprime(p) && #invphi(p-1) > 2; \\ Amiram Eldar, Mar 08 2025, using Max Alekseyev's invphi.gp (see links).

A143422 Number of even numbers k such that phi(k) = n, where n runs through the values (A002202) taken by phi.

Original entry on oeis.org

1, 2, 3, 2, 4, 1, 4, 5, 2, 3, 1, 7, 1, 1, 6, 5, 6, 2, 2, 1, 9, 1, 1, 2, 1, 5, 7, 1, 1, 11, 1, 8, 1, 4, 4, 2, 13, 2, 1, 2, 1, 5, 1, 4, 2, 11, 1, 8, 1, 4, 1, 1, 2, 16, 1, 1, 4, 10, 2, 2, 1, 8, 1, 6, 1, 5, 3, 1, 17, 1, 1, 5, 2, 3, 1, 2, 12, 3, 1, 6, 1, 1, 4, 1, 21, 1, 5, 9, 2, 1, 7, 1, 1, 3, 5, 5, 1

Offset: 1

T. D. Noe, Aug 14 2008

nonn

All terms are positive.

T. D. Noe, Table of n, a(n) for n=1..10000

Cf. A207335.

A058277(n) = A143421(n) + a(n).

A143421 Number of odd numbers k such that phi(k) = n, where n runs through the values (A002202) taken by phi.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 3, 1, 1, 1, 3, 3, 2, 1, 1, 2, 1, 1, 1, 1, 4, 1, 1, 1, 6, 1, 2, 1, 2, 2, 1, 4, 2, 1, 1, 1, 4, 1, 2, 1, 6, 1, 1, 1, 3, 1, 1, 1, 5, 1, 1, 3, 2, 2, 1, 1, 4, 1, 2, 1, 5, 1, 1, 4, 1, 1, 3, 1, 1, 1, 1, 7, 2, 1, 2, 1, 1, 2, 1, 10, 1, 4, 1, 1, 1, 3, 1, 1, 2, 4, 3, 1, 6, 1, 1, 1, 2, 1, 1, 6

Offset: 1

T. D. Noe, Aug 14 2008

nonn

The first zero term is for n = 16842752 = 257*2^16. If there are only five Fermat primes, then terms will be zero for n=2^r for all r>31. This is discussed in problem E3361.

a(2698482) = 0. That is, the 2698482nd term of A002202 is 16842752. - T. D. Noe, Aug 19 2008

R. K. Guy, Unsolved problems in number theory, B39.

T. D. Noe, Table of n, a(n) for n=1..10000
T. D. Noe, Numbers Like 16842752
William P. Wardlaw, L. L. Foster and R. J. Simpson, Problem E3361, Amer. Math. Monthly, Vol. 98, No. 5 (May, 1991), 443-444.

A058277(n) = A143421(n) + A143422(n).

A305656 Integers m that satisfy tau(m) + omega(m) = #({phi(x) = m}).

Original entry on oeis.org

2, 4, 8, 16, 24, 32, 64, 128, 256, 320, 512, 1024, 2048, 3712, 4096, 7168, 8192, 10512, 16192, 16384, 32768, 33024, 37888, 41728, 49280, 51552, 54528, 57280, 62592, 65536, 66432, 67968, 68832, 69792, 81600, 84352, 87696, 91968, 92016, 93888, 94720, 124128, 129888, 131072

Offset: 1

Torlach Rush, Jun 07 2018

nonn

All even terms of A000079 are contained in this sequence.

a(5) = 24 is the first term not a term of A000079, a(10) = 320 is the second.

			2 is a term because tau(2) = 2, omega(2) = 1, and #({phi(x) = 2}) = 3.
24 is a term because tau(24) = 8, omega(24) = 2, and #({phi(x) = 24}) = 10.

Robert Israel, Table of n, a(n) for n = 1..1000
Max Alekseyev, PARI scripts for various problems (see invphi.gp there).

Cf. A000005, A001222, A163523.
Cf. A000010, A058277, A014197.
Cf. A000079.

filter:= proc(n) uses numtheory; tau(n)+nops(factorset(n)) = nops(invphi(n)) end proc:
select(filter, [seq(i,i=2..10^5,2)]); # Robert Israel, Oct 28 2021

Block[{nn = 10^5, s}, s = 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]; Select[Range@ nn, DivisorSigma[0, #] + PrimeNu[#] == s[[#]] &] ] (* Michael De Vlieger, Jul 21 2018 *)

isok(m) = numdiv(m) + omega(m) == #invphi(m); \\ Michel Marcus, Jun 08 2018

tau(m) + omega(m) = #({phi(x) = m}).

Integers m such that A163523(m) = A014197(m).

More terms from Michel Marcus, Jun 08 2018

A306882 Even numbers k such that phi(m) = k^2 has no solution.

Original entry on oeis.org

22, 34, 38, 46, 58, 62, 76, 78, 82, 86, 92, 98, 102, 106, 118, 122, 138, 142, 152, 154, 158, 164, 166, 172, 178, 182, 190, 194, 202, 212, 214, 218, 226, 238, 244, 254, 258, 262, 266, 274, 278, 282, 298, 302, 304, 310, 316, 318, 322, 328, 332, 334, 338, 344, 346, 356, 358, 362

Offset: 1

Bernard Schott, Mar 15 2019

nonn

In the link, P. Pollack and C. Pomerance "show that almost all squares are missing from the range of Euler's phi-function".
Except for m=1 and m=2, phi(m) is always even, so, the odd numbers >= 3 are not included in the data for clarity.
Includes 2*p if p is a prime not in A052291. - Robert Israel, Apr 10 2019

			phi(489) = 18^2, phi(401) = 20^2, phi(577) = 24^2, phi(677) = 26^2, but there is no integer m such that phi(m) = 22^2 = 484.

Robert Israel, Table of n, a(n) for n = 1..10000
P. Pollack and C. Pomerance, Square values of Euler's function, preprint (2013); Bulletin of the London Mathematical Society, Volume 46, Issue 2, 1 April 2014, Pages 403-414.

Cf. A000010, A002202, A052291, A058277, A062732, A221284, A221285.

select(t -> numtheory:-invphi(t^2)=[], [seq(i,i=2..400,2)]);  # Robert Israel, Apr 10 2019

isok(n) = !(n%2) && !istotient(n^2); \\ Michel Marcus, Mar 15 2019

cp's OEIS Frontend

A035113 Numbers != 2 (mod 4) listed in order of increasing totient function phi (A000010).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Extensions

A035114 Values of phi(n) corresponding to A035113.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A071387 Smallest number k for which the set of solutions to phi(x) = k has 2n-1 entries.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A071388 Numbers k such that the cardinality of the set of solutions to phi(x) = k is a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

A071389 Least number m such that cardinality of InvPhi(m) = prime(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A058341 Primes p such that phi(x) = p - 1 has more than 2 solutions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A143422 Number of even numbers k such that phi(k) = n, where n runs through the values (A002202) taken by phi.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A143421 Number of odd numbers k such that phi(k) = n, where n runs through the values (A002202) taken by phi.

Views

Author

Keywords

Comments

References

Links