|
%I #42 Jun 30 2021 02:34:26
%S 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,
%T 90,96,100,105,108,112,120,126,128,132,140,144,150,156,160,162,165,
%U 168,176,180,192,195,198,200,208,210,216,220,224,234
%N Phi-practical numbers: integers n such that x^n - 1 has divisors of every degree up to n.
%C 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).
%C 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
%C There are 431320394 terms up to 10^10. - _Charles R Greathouse IV_, Sep 19 2017
%C 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
%H Charles R Greathouse IV, <a href="/A260653/b260653.txt">Table of n, a(n) for n = 1..10000</a>
%H Carl Pomerance, Lola Thompson, and Andreas Weingartner, <a href="https://www.impan.pl/en/publishing-house/journals-and-series/acta-arithmetica/all/175/3/91743/on-integers-n-for-which-x-n-1-has-a-divisor-of-every-degree">On integers n for which X^n-1 has a divisor of every degree</a>, Acta Arithmetica 175 (2016), 225-243; <a href="https://arxiv.org/abs/1511.03357">arXiv preprint</a>, arXiv:1511.03357 [math.NT], 2015.
%H Lola Thompson, <a href="http://arxiv.org/abs/1111.5401">Polynomials with divisors of every degree</a>, arXiv:1111.5401 [math.NT], 2011.
%H Lola Thompson, <a href="http://dx.doi.org/10.1016/j.jnt.2011.10.005">Polynomials with divisors of every degree</a>, Journal of Number Theory 132 (2012), pp. 1038-1053.
%H Lola Thompson, <a href="http://arxiv.org/abs/1206.4355">Variations on a question concerning the degrees of divisors of x^n-1</a>, arXiv:1206.4355 [math.NT], 2012.
%H Andreas Weingartner, <a href="https://doi.org/10.1090/mcom/3402">On the constant factor in several related asymptotic estimates</a>, Math. Comp., Vol. 88, No. 318 (2019), pp. 1883-1902; <a href="https://arxiv.org/abs/1705.06349">arXiv preprint</a>, arXiv:1705.06349 [math.NT], 2017-2018.
%F 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
%F 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
%e 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.
%e 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.
%t 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 *)
%o (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;
%o (PARI) is(n)=#Set(apply(poldegree, divisors('x^n-1)))==n+1 \\ _Charles R Greathouse IV_, Nov 13 2015
%o (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
%Y Subsequence of A171581.
%Y Cf. A005153, A102190.
%K nonn
%O 1,2
%A _Michel Marcus_, Nov 13 2015
%E a(29)-a(55) from _Charles R Greathouse IV_, Nov 13 2015
|
