login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A260653 Phi-practical numbers: integers n such that x^n - 1 has divisors of every degree up to n. 10
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

There are 431320394 terms up to 10^10. - Charles R Greathouse IV, Sep 19 2017

LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Carl Pomerance, Lola Thompson, Andreas Weingartner, On integers n for which X^n-1 has a divisor of every degree, 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.

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 0.98. - Charles R Greathouse IV, Nov 13 2015

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.

Cf. A005153, A102190.

Sequence in context: A331088 A336506 A336508 * A232711 A178751 A309353

Adjacent sequences:  A260650 A260651 A260652 * A260654 A260655 A260656

KEYWORD

nonn

AUTHOR

Michel Marcus, Nov 13 2015

EXTENSIONS

a(29)-a(55) from Charles R Greathouse IV, Nov 13 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 19 07:24 EDT 2020. Contains 337178 sequences. (Running on oeis4.)