|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
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
|
|
|
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)=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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|