A004169 Values of m for which a regular polygon with m sides cannot be constructed with ruler and compass.

7, 9, 11, 13, 14, 18, 19, 21, 22, 23, 25, 26, 27, 28, 29, 31, 33, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 84, 86, 87, 88, 89, 90, 91

Offset: 1

Author

N. J. A. Sloane, Branislav Kisacanin (bkisacan(AT)eecs.uic.edu)

Keywords

• nonn
• nice

Comments

Numbers m for which phi(a(m)) is not a power of 2, phi = A000010, Euler's totient function. - Reinhard Zumkeller, Jul 31 2012

Numbers m for which A295660(m) > 1. - Lorenzo Sauras Altuzarra, Nov 04 2018

References

• A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 183.
• B. L. van der Waerden, Modern Algebra. Unger, NY, 2nd ed., Vols. 1-2, 1953, Vol. 1, p. 187.

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• Claudi Alsina and Roger B. Nelson, A Panoply of Polygons, Dolciani Math. Expeditions Vol. 58, AMS/MAA (2023), see page 16.
• C. F. Gauss, Disquisitiones Arithmeticae, Lipsiae, 1801. Reprinted in C. F. Gauss, Werke, 1863.
• C. F. Gauss, Disquisitiones Arithmeticae, 1801. English translation: Yale University Press, New Haven, CT, 1966, p. 460.

Crossrefs

Cf. A003401 (complement).

Cf. A000010, A209229.

Edge lengths of nonconstructible n-gons: A272487 (n=7), A272488 (n=9), A272489 (n=11), A272490 (n=13), A255241 (n=14), A130880 (n=18), A272491 (n=19).

Programs

Haskell

a004169 n = a004169_list !! (n-1)
a004169_list = map (+ 1) $ elemIndices 0 $ map a209229 a000010_list
-- Reinhard Zumkeller, Jul 31 2012

Mathematica

Select[ Range[75], !IntegerQ[ Log[2, EulerPhi[#] ] ]& ] (* Jean-François Alcover, Nov 24 2011, after A003401 *)

PARI

is(n)=my(t=4294967295); n>>=valuation(n,2); n/=gcd(n,t); if(gcd(n,t)>1, return(1)); if(n==1, return(0)); if(n<9e2585827972, return(1)); forprime(p=7,1e5, if(n%p==0, return(1))); warning("Result is conjectural on the nonexistence of Fermat primes >= F(33)."); 1 \\ Charles R Greathouse IV, Oct 23 2015

Formula

a(n) = n + O(log^2 n). - Charles R Greathouse IV, Oct 23 2015