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
KEYWORD
nonn
AUTHOR
Michel Marcus, Nov 13 2015
EXTENSIONS
a(29)-a(55) from Charles R Greathouse IV, Nov 13 2015
STATUS
approved