A260653 Phi-practical numbers: integers n such that x^n - 1 has divisors of every degree up to n.
1, 2, 3, 4, 6, 8, 12, 15, 16, 18, 20, 24, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 72, 80, 84, 90, 96, 100, 105, 108, 112, 120, 126, 128, 132, 140, 144, 150, 156, 160, 162, 165, 168, 176, 180, 192, 195, 198, 200, 208, 210, 216, 220, 224, 234
Offset: 1
Keywords
Examples
For n = 3, the divisors of x^3 - 1 are 1, x - 1, x^2 + x + 1, x^3 - 1, so 3 is a term. For n = 5, the divisors of x^5 - 1 are 1, x - 1, x^4 + x^3 + x^2 + x + 1, x^5 - 1, so 5 is not a term.
Links
- Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
- Carl Pomerance, Lola Thompson, and Andreas Weingartner, On integers n for which X^n-1 has a divisor of every degree, Acta Arithmetica 175 (2016), 225-243; arXiv preprint, arXiv:1511.03357 [math.NT], 2015.
- Lola Thompson, Polynomials with divisors of every degree, arXiv:1111.5401 [math.NT], 2011.
- Lola Thompson, Polynomials with divisors of every degree, Journal of Number Theory 132 (2012), pp. 1038-1053.
- Lola Thompson, Variations on a question concerning the degrees of divisors of x^n-1, arXiv:1206.4355 [math.NT], 2012.
- Andreas Weingartner, On the constant factor in several related asymptotic estimates, Math. Comp., Vol. 88, No. 318 (2019), pp. 1883-1902; arXiv preprint, arXiv:1705.06349 [math.NT], 2017-2018.
Programs
-
Mathematica
PhiPracticalQ[n_] := If[n<1, False, If[n==1, True, (lst=Sort@EulerPhi[Divisors[n]]; ok=True; Do[If[lst[[m]]>Sum[lst[[l]], {l, 1, m-1}]+1, (ok=False; Break[])], {m, 1, Length[lst]}]; ok)]]; Select[Range[1000], PhiPracticalQ] (* Frank M Jackson, Jan 21 2016 *) -
PARI
isok(n)=vd = divisors(x^n-1); for (k=1, n, ok = 0; for (j=1, #vd, if (poldegree(vd[j])==k, ok = 1; break);); if (!ok, break);); ok;
-
PARI
is(n)=#Set(apply(poldegree, divisors('x^n-1)))==n+1 \\ Charles R Greathouse IV, Nov 13 2015 -
PARI
is(n)=my(u=List(),f=factor(n),t,s=1); forvec(v=vector(#f~,i,[0,f[i,2]]), t=prod(i=1,#v, if(v[i],(f[i,1]-1)*f[i,1]^(v[i]-1),1)); listput(u,t)); listsort(u); for(i=1,#u, if(u[i]>s, return(0)); s+=u[i]); 1 \\ Charles R Greathouse IV, Nov 13 2015
Formula
Pomerance, Thompson, & Weingartner show that a(n) ~ kn log n for some constant k, strengthening an earlier result of Thompson. The former give a heuristic suggesting that k is about 1/0.96. - Charles R Greathouse IV, Nov 13 2015
More precisely, a(n) = k*n*log(n*log(n)) + O(n), where 1.034 < k < 1.059 (See comments). - Andreas Weingartner, Jun 29 2021
Extensions
a(29)-a(55) from Charles R Greathouse IV, Nov 13 2015
Comments