login
A260653
Phi-practical numbers: integers n such that x^n - 1 has divisors of every degree up to n.
14
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,2
COMMENTS
n is phi-practical if and only if each natural number up to n is a subsum of the multiset {phi(d) : d | n} (see Pomerance link p. 2).
There are 6 terms up to 10, 28 up to 10^2, 174 up to 10^3, 1198 up to 10^4, 9301 up to 10^5, 74461 up to 10^6, 635528 up to 10^7, 5525973 up to 10^8, and 48386047 up to 10^9. - Charles R Greathouse IV, Nov 13 2015
There are 431320394 terms up to 10^10. - Charles R Greathouse IV, Sep 19 2017
Let F(x) denote the number of phi-practical numbers up to x. F(x) has order of magnitude x/log(x) (See Thompson 2012). Moreover, we have F(x) = c*x/log(x) + O(x/(log(x))^2), where 0.945 < c < 0.967 (See Pomerance, Thompson & Weingartner 2016 and Weingartner 2019). As a result, a(n) = k*n*log(n*log(n)) + O(n), where k = 1/c and 1.034 < k < 1.059. - Andreas Weingartner, Jun 29 2021
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.
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
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
Subsequence of A171581.
Sequence in context: A331088 A336506 A336508 * A232711 A178751 A309353
KEYWORD
nonn
AUTHOR
Michel Marcus, Nov 13 2015
EXTENSIONS
a(29)-a(55) from Charles R Greathouse IV, Nov 13 2015
STATUS
approved