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

%I #43 Feb 23 2023 10:40:27

%S 7,9,11,13,14,18,19,21,22,23,25,26,27,28,29,31,33,35,36,37,38,39,41,

%T 42,43,44,45,46,47,49,50,52,53,54,55,56,57,58,59,61,62,63,65,66,67,69,

%U 70,71,72,73,74,75,76,77,78,79,81,82,83,84,86,87,88,89,90,91

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

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

%C Numbers m for which A295660(m) > 1. - _Lorenzo Sauras Altuzarra_, Nov 04 2018

%D A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 183.

%D B. L. van der Waerden, Modern Algebra. Unger, NY, 2nd ed., Vols. 1-2, 1953, Vol. 1, p. 187.

%H T. D. Noe, <a href="/A004169/b004169.txt">Table of n, a(n) for n = 1..1000</a>

%H Claudi Alsina and Roger B. Nelson, <a href="https://bookstore.ams.org/view?ProductCode=DOL/58">A Panoply of Polygons</a>, Dolciani Math. Expeditions Vol. 58, AMS/MAA (2023), see page 16.

%H C. F. Gauss, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k994003">Disquisitiones Arithmeticae</a>, Lipsiae, 1801. Reprinted in C. F. Gauss, <a href="https://archive.org/details/carlfriedrichga01gausgoog">Werke</a>, 1863.

%H C. F. Gauss, <a href="https://doi.org/10.1007/978-1-4939-7560-0">Disquisitiones Arithmeticae</a>, 1801. English translation: Yale University Press, New Haven, CT, 1966, p. 460.

%F a(n) = n + O(log^2 n). - _Charles R Greathouse IV_, Oct 23 2015

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

%o (Haskell)

%o a004169 n = a004169_list !! (n-1)

%o a004169_list = map (+ 1) $ elemIndices 0 $ map a209229 a000010_list

%o -- _Reinhard Zumkeller_, Jul 31 2012

%o (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

%Y Cf. A003401 (complement).

%Y Cf. A000010, A209229.

%Y 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).

%K nonn,nice

%O 1,1

%A _N. J. A. Sloane_, Branislav Kisacanin (bkisacan(AT)eecs.uic.edu)