A206225 Numbers j such that the numbers Phi(j, m) are in sorted order for any integer m >= 2, where Phi(k, x) is the k-th cyclotomic polynomial.

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

Offset

1,2

Comments

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

Note that (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))) >= 0 since k^3 > k^2+k+1 when k >= 2.

This means that this sequence can be segmented into sets in which Phi(k,m) shares the same degree of polynomial and it can be generated in this way.

Links

Table of n, a(n) for n=1..63.

S. P. Glasby, Cyclotomic ordering conjecture, arXiv:1903.02951 [math.NT], 2019.

Carl Pomerance and Simon Rubinstein-Salzedo, Cyclotomic Coincidences, arXiv:1903.01962 [math.NT], 2019.

Example

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.
For m > 1, Phi(6,m) < Phi(4,m) < Phi(3,m), so a(3)=6, a(4)=4, and a(5)=3 (noting that Phi(6,m) > Phi(2,m) when m > 2, and Phi(6,2) = Phi(2,2)).
For k such that 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.
For m > 1, Phi(10,m) < Phi(12,m) < Phi(8,m) < Phi(5,m), so a(6) = 10, a(7) = 12, a(8) = 8, and a(9) = 5 (noting Phi(10,m) - Phi(3,m) = m((m^2 + m + 2)(m - 2) + 2) >= 4 > 0 when m >= 2).

Mathematica

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

Crossrefs

Cf. A194712, A000010, A002202, A032447.

Sequence in context: A299402 A286451 A102510 * A208507 A216153 A100115

Adjacent sequences: A206222 A206223 A206224 * A206226 A206227 A206228

Keyword

nonn

Author

Lei Zhou, Feb 13 2012

Status

approved