login
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.
7
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
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
KEYWORD
nonn
AUTHOR
Lei Zhou, Feb 13 2012
STATUS
approved