A032447 -id:A032447 - cp's OEIS frontend

A206292 Numbers k such that cyclotomic polynomial Phi(k,-m) < Phi(j,-m) for any j > k and m >= 2.

1, 2, 3, 4, 6, 12, 18, 30, 42, 48, 60, 66, 70, 78, 90, 102, 120, 126, 150, 180, 210, 240, 270, 300, 330, 420, 450, 462, 480, 510, 540, 630, 660, 690, 780, 840, 870, 924, 1050, 1092, 1140, 1260, 1320, 1470, 1560, 1680, 1890, 2310, 2730, 2940, 3150, 3570, 3990

Offset: 1

Lei Zhou, Feb 13 2012

nonn

			For k such that A000010(k) = 1:
  Phi(1, -m) = -1 - m,
  Phi(2, -m) = 1 - m,
  Phi(1, -m) <  Phi(2, -m),
  so a(1) = 1, a(2) = 2.
For k > 2 such that A000010(k) = 2:
  Phi(3, -m) = 1 - m + m^2,
  Phi(4, -m) = 1 + m^2,
  Phi(6, -m) = 1 + m + m^2.
When integer m > 1, Phi(3, -m) < Phi(4, -m) < Phi(6, -m), so a(3) = 3, a(4) = 4, and a(5) = 6.
For k > 6 such that A000010(k) = 4:
  Phi(8, -m) = 1 + m^4,
  Phi(10, -m) = 1 + m + m^2 + m^3 + m^4,
  Phi(12, -m) = 1 - m^2 + m^4.
When integer m > 1, Phi(12, -m) < Phi(8, -m) < Phi(10, -m), so a(6) = 12.

Wikipedia, Cyclotomic polynomial

Cf. A194712, A206225, A000010, A002202, A032447.

t = Select[Range[4000], EulerPhi[#] <= 1000 &]; t =  SortBy[t, Cyclotomic[#, -2] &]; DeleteDuplicates[Table[Max[Take[t, n]], {n, 1, Length[t]}]]

A207334 Array of indices N for which the minimal polynomial C(N,x) of 2*cos(Pi/N) has allowed degree A207335(n).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 8, 10, 12, 15, 11, 13, 14, 18, 21, 16, 17, 20, 24, 30, 19, 27, 22, 25, 33, 23, 26, 28, 35, 36, 39, 42, 45, 29, 31, 32, 34, 40, 48, 51, 60, 37, 38, 54, 57, 63, 41, 44, 50, 55, 66, 75, 43, 49, 46, 69, 47, 52, 56, 65, 70, 72, 78, 84, 90, 105, 53, 81, 58, 87, 59, 61, 62, 77, 93, 99

Offset: 1

Wolfdieter Lang, Feb 19 2012

For the minimal polynomial C(N,x) and its degree delta(N) see A207333.

The row length sequence l(n) of this array is A207335(n). The allowed values for the degree delta(N) are v(n):=A207333(n).

			Row length l(n), degree values v(n).
l(n):=A207335(n): 3, 3, 2, 4, 1, 4, 5, 2, 3, 1, ...
v(n):=A207333(n): 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, ...
n,  v(n)\m 1  2  3  4  5 ...
1,   1:    1  2  3
2,   2:    4  5  6
3,   3:    7  9
4,   4:    8 10 12 15
5,   5:   11
6,   6:   13 14 18 21
7,   8:   16 17 20 24 30
8,   9:   19 27
9,  10:   22 25 33
10, 11:   23
...
a(4,2)=10 because C(10,x) has degree A207333(4)=4. In fact, C(10,x) = x^4-5*x^2+5.
The set {N:delta(N)=v(4)=4} = {8,10,12,15} (ordered increasingly). Exactly these N indices lead to degree 4
  polynomials C.

Cf. A032447 (array for cyclotomic polynomials with Euler's phi function as degree).

a(n,m), m=1..l(n):=A207335(n), n>=1, gives the m-th member of the set {N positive integer: delta(N)= v(n):= A207333(n)}, when read as ordered list with increasing numbers.

A217842 Product of the numbers p such that phi(p) = n, where phi is Euler's totient function.

Original entry on oeis.org

2, 72, 1, 4800, 1, 15876, 1, 3456000, 1, 242, 1, 300500928, 1, 1, 1, 2130739200, 1, 1052676, 1, 119790000, 1, 1058, 1, 531598161669120000, 1, 1, 1, 1682, 1, 1922, 1, 20864198246400, 1, 1, 1, 1159208596538496, 1, 1, 1, 265804426800000000, 1, 17757796, 1

Offset: 1

T. D. Noe, Oct 12 2012

nonn

It appears that all terms greater than 1 are distinct. This is true for all n <= 10^6.

T. D. Noe, Table of n, a(n) for n = 1..1000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
David M. Bressoud, A Course in Computational Number Theory (web page), CNT.m, Computational Number Theory Mathematica package.

Cf. A002181 (smallest inverse), A006511 (largest inverse), A215240 (sum of inverses).

Cf. A032447 (inverse of phi).

Needs["CNT`"]; Table[Times @@ PhiInverse[n], {n, 100}]

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

A253215 a(n) is the greatest positive integer m such that phi(m) <= n where phi is Euler's totient function.

Original entry on oeis.org

2, 6, 6, 12, 12, 18, 18, 30, 30, 30, 30, 42, 42, 42, 42, 60, 60, 60, 60, 66, 66, 66, 66, 90, 90, 90, 90, 90, 90, 90, 90, 120, 120, 120, 120, 126, 126, 126, 126, 150, 150, 150, 150, 150, 150, 150, 150, 210, 210, 210, 210, 210, 210, 210, 210

Offset: 1

Jean-François Alcover, Jan 08 2015

nonn

If all duplicates are removed the result is A036913. The indices where a(n) takes a new value are A036912. - Jeppe Stig Nielsen, Sep 28 2021

Jean-François Alcover, Table of n, a(n) for n = 1..1000
MathOverflow, The maximum of the preimage of [1,x] through Euler's totient function
Eric Weisstein's World of Mathematics, Totient Function
Wikipedia, Euler's totient function

Cf. A000010, A007614, A032447, A036912, A036913, A057635.

inversePhi[m_?EvenQ] := Module[{p, nmax, n, nn}, p = Select[Divisors[m]+1, PrimeQ]; nmax = m*Times @@ (p/(p-1)); n = m; nn = {}; While[n <= nmax, If[EulerPhi[n] == m, AppendTo[nn, n]]; n++]; nn]; a[1] = 2; a[n_?OddQ] := a[n-1]; a[n_] := a[n] = Module[{m}, m = inversePhi[n] // Max; If[m > a[n-1], m, a[n-1]]]; Table[a[n], {n, 1, 100}]

A297475 Numbers n such that phi(x) = n for more than one value of x, and the smallest such x divides the largest.

Original entry on oeis.org

1, 2, 8, 10, 22, 28, 30, 44, 46, 52, 54, 56, 58, 66, 70, 78, 82, 92, 102, 104, 106, 110, 116, 126, 128, 130, 136, 138, 140, 148, 150, 164, 166, 172, 178, 190, 196, 198, 204, 210, 212, 222, 226, 228, 238, 250, 260, 262, 268, 270, 282, 292, 294, 296, 306, 310, 316, 330, 332, 342, 344, 346, 356, 358, 366, 368, 372

Offset: 1

Torlach Rush, Dec 30 2017

nonn

The larger endpoint is always twice the value of the smaller endpoint.
Conjecture 1: The number of solutions, excluding endpoints is always 0, or an odd number. (known to n = 2 * 10^5)
Conjecture 2: If both endpoints are divisible by 5, then the number of solutions (excluding terms of A007366) is of the form 4k + 1. (known to n = 2 * 10^5)
A007366 is contained in this sequence and the number of solutions, excluding endpoints is always 0.
Terms of this sequence are totients with a single odd totient inverse.

			2 is in the sequence because {phi^-1(2)} = {3,4,6}, and 2 = 6 / 3.
8 is in the sequence because {phi^-1(8)} = {15,...,30}, and 2 = 30 / 15.
10 is in the sequence because {phi^-1(10)} = {11,22}, and 2 = 22 / 11.

Michel Marcus, Table of n, a(n) for n = 1..2441
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A002181, A002202, A006511, A007366, A032447.

With[{nn = 67}, Take[#, nn] &@ Keys@ Select[KeySort@ PositionIndex@ Array[EulerPhi, nn^2], IntegerQ[#2/#1] & @@ {First@ #, Last@ #} &]] (* Michael De Vlieger, Dec 31 2017 *)

isok(n) = my(vx = invphi(n)); (#vx > 1) && ((vecmax(vx) % vecmin(vx)) == 0); \\ Michel Marcus, Jul 18 2018

2 = max({phi^-1(n)}) / min({phi^-1(n)}).

0 = A006511(n) mod A002181(n).

A206710 This irregular table contains indices j, k, l,... in each row such that the values Phi(j,-m) < Phi(k,-m)< Phi(l,-m)< ... of cyclotomic polynomials Phi(.,.) are sorted given any constant integer argument m >= 2.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 12, 8, 10, 7, 9, 18, 14, 30, 20, 24, 16, 15, 11, 22, 42, 13, 28, 36, 21, 26, 17, 40, 48, 32, 60, 34, 19, 27, 54, 38, 66, 44, 25, 50, 33, 23, 46, 70, 78, 52, 90, 56, 72, 45, 84, 39, 35, 29, 58, 31, 62, 102, 68, 80, 96, 64, 120

Offset: 1

Lei Zhou, Feb 13 2012

Based on A002202 "Values taken by totient function phi(m)", A000010 can only take certain even numbers. So for the worst case, the largest Phi(k,m) with degree d (even positive integer) will be (1-k^(d+1))/(1-k) (or smaller)and the smallest Phi(k,m) with degree d+2 will be (1+k^(d+3))/(1+k) (or larger).
(1+k^(d+3))/(1+k)-(1-k^(d+1))/(1-k)=(k/(k^2-1))*(2+k^d*(k^3-(k^2+k+1)))
k^3>k^2+k+1 when k>=2.
This means that this sequence can be segmented to sets in which Cyclotomic(k,m) shares the same degree of Polynomial and it can be generated in this way.

			For those k's that make A000010(k) = 1
Phi(1,-m) = -1-m
Phi(2,-m) = 1-m
Phi(1,-m) < Phi(2,-m)
So, a(1) = 1, a(2) = 2;
For those k's (k > 2) that make A000010(k) = 2
Phi(3,-m) = 1 - m + m^2
Phi(4,-m) = 1 + m^2
Phi(6,-m) = 1 + m + m^2
Obviously when integer m > 1, Phi(3,m) < Phi(4,m) < Phi(6,m)
So a(3)=3, a(4)=4, and a(5)=6
For those k's that make A000010(k) = 4
  Phi(5,-m) = 1 - m + m^2 - m^3 + m^4
  Phi(8,-m) = 1 + m^4
Phi(10,-m) = 1 + m + m^2 + m^3 + m^4
Phi(12,-m) = 1 - m^2 + m^4
Obviously when integer m > 1, Phi(5,m) < Phi(12,m) < Phi(8,m) < Phi(10,m),
So a(6) = 5, a(7) = 12, a(8) = 8, and a(9) = 10.
The table starts
1,2;
3,4,6;
5,12,8,10;

Cf. A206292, A194712, A206225, A000010, A032447.

t = Select[Range[400], EulerPhi[#] <= 40 &]; SortBy[t, Cyclotomic[#, -2] &]

A219793 Least k such that phi(n) = lambda(k), or 0 if there is no such k.

Original entry on oeis.org

1, 1, 3, 3, 5, 3, 7, 5, 7, 5, 11, 5, 13, 7, 32, 32, 17, 7, 19, 32, 13, 11, 23, 32, 25, 13, 19, 13, 29, 32, 31, 17, 25, 17, 224, 13, 37, 19, 224, 17, 41, 13, 43, 25, 224, 23, 47, 17, 43, 25, 128, 224, 53, 19, 41, 224, 37, 29, 59, 17, 61, 31, 37, 128, 119, 25

Offset: 1

Michel Lagneau, Nov 28 2012

nonn

lambda(n) is the Carmichael lambda function A002322. For n <10000, it appears that a(n) = 0 for n = 2047, 4094, 6141, 6533, 8119, 8188, 9637. if a(n) = p is a prime greater than 2, then n belongs to the finite set {p, p1, p2, ...., pk} that is a subsequence of A032447 (see the array with characteristic rows in the example of A032447), for example : a(n) = 3 for n = 3, 4, 6; a(n) = 5 for n = 5, 8, 10, 12; a(n) = 7 for n = 7, 9, 14, 18, 15, 16, 20, 24, 30; a(n) = 11 for n = 11, 22; a(n) = 13 for n = 13, 21, 26, 28, 36, 42; a(n) = 17 for n = 17, 32, 34, 40, 48, 60.

			a(6) = 3 because phi(6) = lambda(3) = 2.

Michel Lagneau, Table of n, a(n) for n = 1..10000

Cf. A002322, A032447, A141162, A143407.

with(numtheory): for n from 1 to 100 do: ii:=0:for k from 1 to 10^6 while(ii=0) do:if phi(n)=lambda(k) then ii:=1: printf(`%d, `,k):else fi:od:if ii=0 then printf(`%d, `,0): else fi:od:

Table[k=0; While[!EulerPhi[n] == CarmichaelLambda[k], k++]; k, {n, 100}] (* program will go into an infinite loop at n = 2047 *)

A376927 Totients whose inverses can be separated into ordered pairs (x, 2*x) with no remainder.

Original entry on oeis.org

1, 6, 10, 18, 22, 28, 30, 42, 46, 52, 54, 58, 66, 70, 78, 82, 100, 102, 106, 110, 126, 130, 136, 138, 148, 150, 162, 166, 172, 178, 180, 190, 196, 198, 210, 222, 226, 228, 238, 250, 262, 268, 270, 282, 292, 294, 306, 310, 316, 330, 342, 346, 348, 358, 366, 372

Offset: 1

Torlach Rush, Oct 11 2024

nonn

Conjecture: Numbers having an even number of totient inverses, the odd inverses being confined to the lower half of the list.

			1 is a totient and has totient inverses 1 and 2, giving an ordered pair (1, 2*1)
6 is a totient and has totient inverses 7, 9, 14, 18 giving ordered pairs (7,2*7) and (9, 2*9).
18 is a totient and has totient inverses 19, 27, 38, 54 giving ordered pairs (19,2*19) and (27, 2*27).
348 is a totient and has totient inverses 349, 413, 531, 698, 826, 1062 giving ordered pairs (349, 2*349), (413, 2*413), and (531, 2*531).

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

Subset of A002202.

Cf. A000010, A007617, A032447.

q:= n-> (s-> s<>{} and ((x, y)-> x = map(t->t/2, y))(
    selectremove(x-> x::odd, s)))({numtheory[invphi](n)[]}):
select(q, [$1..543])[];  # Alois P. Heinz, Nov 21 2024

okQ[k_] := With[{s = Sort[invphi[k]]}, s != {} && Select[s, EvenQ]/2 == Select[s, OddQ]];
Reap[For[k = 1, k <= 1000, k++, If[okQ[k], Print[k]; Sow[k]]]][[2, 1]] (* Jean-François Alcover, Apr 04 2025, using Maxim Rytin's 'invphi' program (see A007617) *)

evencardinality(list)={e=0;o=0;if(0 < #list,if(0 == Mod(#list, 2),for(i=1,#list,if(1==Mod(list[i],2),o++,e++)),o++), o++);return(if(o==e, 1, 0))}
for(n = 1, 372, if(1 == evencardinality(invphi(n)), print1(n, ", ")));

A294618 a(n) is the number of solutions of x^2 = eulerphi(x * m) where x is A293928(n).

Original entry on oeis.org

2, 2, 3, 1, 4, 2, 5, 1, 1, 4, 6, 3, 3, 5, 1, 7, 6, 4, 1, 7, 1, 3, 1, 8, 10, 5, 1, 1, 9, 3, 8, 4, 1, 9, 1, 13, 1, 7, 4, 3, 1, 12, 5, 14, 1, 7, 1, 1, 2, 10, 2, 18, 1, 1, 1, 9, 9, 3, 1, 5, 1, 14, 7, 22, 3, 1

Offset: 1

Torlach Rush, Nov 05 2017

The valid values of m in the equation are the terms of the sequence A151999 in order.
m is a solution if all squarefree divisors of x also divide m.
The formula is recursive. For example, taking A151999(68) we get the following: 11664=phi(108*324), 1259712=phi(11664*324), 136048896=phi(1259712*324), ...
If a solution exists then x^(k+1) = phi(x^k * m) for a fixed m, and the smallest value of k must be 1. This follows from a|b implies phi(a)|phi(b), and for k >= 1 a^(k-1)|a^k.
The smallest solution where solutions exist are the terms of the sequence A055744 not in order.
The values of phi(m) are the terms of the sequence A068997 not in order.

			The first 1 is a term since there is only 1 solution when phi(m)=6. The solution is m=18.
The first 5 is a term since there are 5 solutions when phi(m)=16. These are 32, 34, 40, 48, and 60.
From _Michel Marcus_, Nov 08 2017: (Start)
Illustration of first few terms:
   1: [1, 2],
   2: [4, 6],
   4: [8, 10, 12],
   6: [18],
   8: [16, 20, 24, 30],
  12: [36, 42],
  16: [32, 34, 40, 48, 60],
  18: [54],
  20: [50],
  24: [72, 78, 84, 90],
  32: [64, 68, 80, 96, 102, 120],
  ... (End)

Max Alekseyev, PARI scripts for various problems

Cf. A000010, A006511, A032447, A151999, A055744, A068997, A293928.

isok(n) = {iv = invphi(n); if (#iv, return (sum(m=1, #iv, n^2 == eulerphi(n*iv[m])))); return (0);}
lista(nn) = {for (n=1, nn, if (v = isok(n), print1(v, ", ")););} \\ \\ using the invphi script by Max Alekseyev; Michel Marcus, Nov 07 2017

0 < (phi(m)^(k+1) = phi(phi(m)^k*m)), k >= 1, m >= 1.

A317013 For successive terms of A002202, totient values t, lcm({x: phi(x)=t})/gcd({x: phi(x)=t}).

Original entry on oeis.org

2, 12, 120, 126, 240, 2, 3276, 8160, 1026, 3300, 2, 32760, 2, 2, 16320, 531468, 270600, 4214, 12, 2, 65520, 2, 2, 12, 2, 5241852, 32640, 2, 2, 5043631320, 2, 541200, 2, 25284, 245640, 12, 216084960, 25250, 2, 12, 2, 4697028, 2, 393240, 12, 3407203800, 2, 65280, 2, 388332

Offset: 1

Michel Marcus, Jul 19 2018

nonn

From Torlach Rush, Jul 03 2018: (Start)
Consider the quotients q(t) = lcm({x: phi(x)=t})/gcd({x: phi(x)=t}).
When the number of solutions is 2, q(t) must be 2. For example invphi(10) = [11, 22], and q(10)=2.
When the number of solutions is 3, the solutions are x1 < x2 < (2 * x1) and the only observed value of q(t) is 12. For example, invphi(44) = [69, 92, 138], and q(44)=12.
When the number of solutions is greater than 3, multiple values of q(t) are observed. (End)

			invphi(1) = [1, 2] and lcm(1, 2) / gcd(1, 2) is 2.

Max Alekseyev, PARI scripts for various problems

Cf. A000010, A002202, A032447.

Map[LCM[##]/GCD[##] & @@ # &, Take[Values@ KeySort@ PositionIndex@ Array[EulerPhi, 10^6], 50]] (* Michael De Vlieger, Jul 20 2018 *)

lista(nn) = {for (n=1, nn, my(v = invphi(n)); if (#v, print1(lcm(v)/gcd(v), ", ")););}

cp's OEIS Frontend

A206292 Numbers k such that cyclotomic polynomial Phi(k,-m) < Phi(j,-m) for any j > k and m >= 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A207334 Array of indices N for which the minimal polynomial C(N,x) of 2*cos(Pi/N) has allowed degree A207335(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A217842 Product of the numbers p such that phi(p) = n, where phi is Euler's totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A253215 a(n) is the greatest positive integer m such that phi(m) <= n where phi is Euler's totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A297475 Numbers n such that phi(x) = n for more than one value of x, and the smallest such x divides the largest.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A206710 This irregular table contains indices j, k, l,... in each row such that the values Phi(j,-m) < Phi(k,-m)< Phi(l,-m)< ... of cyclotomic polynomials Phi(.,.) are sorted given any constant integer argument m >= 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A219793 Least k such that phi(n) = lambda(k), or 0 if there is no such k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A376927 Totients whose inverses can be separated into ordered pairs (x, 2*x) with no remainder.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica