|
%I M0505 #156 Aug 26 2022 11:59:44
%S 1,2,3,4,5,6,8,10,12,15,16,17,20,24,30,32,34,40,48,51,60,64,68,80,85,
%T 96,102,120,128,136,160,170,192,204,240,255,256,257,272,320,340,384,
%U 408,480,510,512,514,544,640,680,768,771,816,960,1020,1024,1028,1088,1280,1285
%N Numbers of edges of regular polygons constructible with ruler (or, more precisely, an unmarked straightedge) and compass.
%C The terms 1 and 2 correspond to degenerate polygons.
%C These are also the numbers for which phi(n) is a power of 2: A209229(A000010(a(n)) = 1. - _Olivier Gérard_ Feb 15 1999
%C From _Stanislav Sykora_, May 02 2016: (Start)
%C The sequence can be also defined as follows: (i) 1 is a member. (ii) Double of any member is also a member. (iii) If a member is not divisible by a Fermat prime F_k then its product with F_k is also a member. In particular, the powers of 2 (A000079) are a subset and so are the Fermat primes (A019434), which are the only odd prime members.
%C The definition is too restrictive (though correct): The Georg Mohr - Lorenzo Mascheroni theorem shows that constructibility using a straightedge and a compass is equivalent to using compass only. Moreover, Jean Victor Poncelet has shown that it is also equivalent to using straightedge and a fixed ('rusty') compass. With the work of Jakob Steiner, this became part of the Poncelet-Steiner theorem establishing the equivalence to using straightedge and a fixed circle (with a known center). A further extension by Francesco Severi replaced the availability of a circle with that of a fixed arc, no matter how small (but still with a known center).
%C Constructibility implies that when m is a member of this sequence, the edge length 2*sin(Pi/m) of an m-gon with circumradius 1 can be written as a finite expression involving only integer numbers, the four basic arithmetic operations, and the square root. (End)
%D A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 183.
%D Allan Clark, Elements of Abstract Algebra, Chapter 4, Galois Theory, Dover Publications, NY 1984, page 124.
%D DeTemple, Duane W. "Carlyle circles and the Lemoine simplicity of polygon constructions." The American Mathematical Monthly 98.2 (1991): 97-108. - _N. J. A. Sloane_, Aug 05 2021
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%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="/A003401/b003401.txt">Table of n, a(n) for n = 1..2000</a>
%H Laura Anderson, Jasbir S. Chahal and Jaap Top, <a href="https://arxiv.org/abs/2110.01355">The last chapter of the Disquisitiones of Gauss</a>, arXiv:2110.01355 [math.HO], 2021.
%H Wayne Bishop, <a href="https://dx.doi.org/10.2307/2321061">How to construct a regular polygon</a>, Amer. Math. Monthly 85(3) (1978), 186-188.
%H Alessandro Chiodo, <a href="https://webusers.imj-prg.fr/~alessandro.chiodo/sriyantra.pdf">A note on the construction of the Śrī Yantra</a>, Sorbonne Université (Paris, France, 2020).
%H T. Chomette, <a href="http://www.dma.ens.fr/culturemath/maths/pdf/geometrie/polygones.pdf">Construction des polygones réguliers</a> (in French).
%H Duane W. DeTemple, <a href="https://dx.doi/10.2307/2323939">Carlyle circles and the Lemoine simplicity of polygon constructions</a>, Amer. Math. Monthly 98(2) (1991), 97-108.
%H Bruce Director, <a href="http://lymcanada.org/measurement-and-divisibility/">Measurement and Divisibility</a>.
%H David Eisenbud and Brady Haran, <a href="https://www.youtube.com/watch?v=oYlB5lUGlbw">Heptadecagon and Fermat Primes (the math bit)</a>, Numberphile video (2015).
%H Mauro Fiorentini, <a href="http://www.bitman.name/math/article/264">Construibili (numeri)</a>.
%H C. F. Gauss, Disquisitiones Arithmeticae, 1801. English translation: Yale University Press, New Haven, CT, 1966, p. 463. <a href="http://archive.org/stream/werkecarlf01gausrich#page/n471/mode/2up">Original</a> (in Latin).
%H R. K. Guy, <a href="/A005347/a005347.pdf">The Second Strong Law of Small Numbers</a>, Math. Mag. 63(1) (1990), 3-20. [Annotated scanned copy] <a href="https://dx.doi/10.2307/2691503">[DOI]</a>
%H R. K. Guy and N. J. A. Sloane, <a href="/A005180/a005180.pdf">Correspondence</a>, 1988.
%H Johann Gustav Hermes, <a href="http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN002496585">Über die Teilung des Kreises in 65537 gleiche Teile (About the division of the circle into 65537 equal pieces)</a>, Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse, Vol. 3 (1894), 170-186.
%H Friedrich Julius Richelot, <a href="https://eudml.org/doc/146780">De resolutione algebraica aequationis X^257 = 1, sive de divisione circuli per bisectionem anguli septies repetitam in partes 257 inter se aequales commentatio coronata (On the resolution of the algebraic equation X^257 = 1, or ...)</a>, Journal für die reine und angewandte Mathematik 9 (1832), 1-26.
%H Pierre Wantzel, <a href="http://visualiseur.bnf.fr/ConsulterElementNum?O=NUMM-16381&Deb=374&Fin=380&E=PDF">Recherches sur les moyens de reconnaître si un Problème de Géométrie peut se résoudre avec la règle et le compas (Investigations into means of knowing if a problem of geometry can be solved with a straightedge and compass)</a>, Journal de Mathématiques Pures et Appliquées 2 (1837), 366-372.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConstructibleNumber.html">Constructible Number</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConstructiblePolygon.html">Constructible Polygon</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RegularPolygon.html">Regular Polygon</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Trigonometry.html">Trigonometry</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TrigonometryAngles.html">Trigonometry Angles</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Constructible_polygon">Constructible polygon</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Johann_Gustav_Hermes">Johann Gustav Hermes</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Friedrich_Julius_Richelot">Friedrich Julius Richelot</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Mohr%E2%80%93Mascheroni_theorem">Mohr-Mascheroni theorem</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Pierre_Wantzel">Pierre Wantzel</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Poncelet%E2%80%93Steiner_theorem">Poncelet-Steiner theorem</a>.
%H Robert G. Wilson v, <a href="/A007117/a007117.pdf">Letter to N. J. A. Sloane, Aug. 1993</a>.
%F Terms from 3 onward are computable as numbers such that cototient-of-totient equals the totient-of-totient: Flatten[Position[Table[co[eu[n]]-eu[eu[n]], {n, 1, 10000}], 0]] eu[m]=EulerPhi[m], co[m]=m-eu[m]. - _Labos Elemer_, Oct 19 2001, clarified by _Antti Karttunen_, Nov 27 2017
%F Any product of 2^k and distinct Fermat primes (primes of the form 2^(2^m)+1). - _Sergio Pimentel_, Apr 30 2004, edited by _Franklin T. Adams-Watters_, Jun 16 2006
%F If the well-known conjecture that there are only five prime Fermat numbers F_k=2^{2^k}+1, k=0,1,2,3,4 is true, then we have exactly: Sum_{n>=1} 1/a(n)= 2*Product_{k=0..4} (1+1/F_k) = 4869735552/1431655765 = 3.40147098978.... - _Vladimir Shevelev_ and _T. D. Noe_, Dec 01 2010
%F log a(n) >> sqrt(n); if there are finitely many Fermat primes, then log a(n) ~ k log n for some k. - _Charles R Greathouse IV_, Oct 23 2015
%e 34 is a term of this sequence because a circle can be divided into exactly parts. 7 is not.
%t Select[ Range[ 1300 ], IntegerQ[ Log[ 2, EulerPhi[ # ] ] ]& ] (* _Olivier Gérard_ Feb 15 1999 *)
%t (* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) Take[ Union[ Flatten[ NestList[2# &, Times @@@ Table[ UnrankSubset[n, Join[{1}, Table[2^2^i + 1, {i, 0, 4}]]], {n, 63}], 11]]], 60] (* _Robert G. Wilson v_, Jun 11 2005 *)
%t nn=10; logs=Log[2,{2,3,5,17,257,65537}]; lim2=Floor[nn/logs[[1]]]; Sort[Reap[Do[z={i,j,k,l,m,n}.logs; If[z<=nn, Sow[2^z]], {i,0,lim2}, {j,0,1}, {k,0,1}, {l,0,1}, {m,0,1}, {n,0,1}]][[2,1]]]
%t A092506 = {2, 3, 5, 17, 257, 65537}; s = Sort[Times @@@ Subsets@ A092506]; mx = 1300; Union@ Flatten@ Table[(2^n)*s[[i]], {i, 64}, {n, 0, Log2[mx/s[[i]]]}] (* _Robert G. Wilson v_, Jul 28 2014 *)
%o (Haskell)
%o a003401 n = a003401_list !! (n-1)
%o a003401_list = map (+ 1) $ elemIndices 1 $ map a209229 a000010_list
%o -- _Reinhard Zumkeller_, Jul 31 2012
%o (PARI) for(n=1,10^4,my(t=eulerphi(n));if(t/2^valuation(t,2)==1,print1(n,", "))); \\ _Joerg Arndt_, Jul 29 2014
%o (PARI) is(n)=n>>=valuation(n,2); if(n<7, return(n>0)); my(k=logint(logint(n,2),2)); if(k>32, my(p=2^2^k+1); if(n%p, return(0)); n/=p; unknown=1; if(n%p==0, return(0)); p=0; if(is(n)==0, 0, "unknown [has large Fermat number in factorization]"), 4294967295%n==0) \\ _Charles R Greathouse IV_, Jan 09 2022
%o (PARI) is(n)=n>>=valuation(n,2); 4294967295%n==0 \\ valid for n <= 2^2^33, conjecturally valid for all n; _Charles R Greathouse IV_, Jan 09 2022
%o (Python)
%o from sympy import totient
%o A003401_list = [n for n in range(1,10**4) if format(totient(n),'b').count('1') == 1]
%o # _Chai Wah Wu_, Jan 12 2015
%Y Subsequence of A295298. - _Antti Karttunen_, Nov 27 2017
%Y A004729 and A051916 are subsequences. - _Reinhard Zumkeller_, Mar 20 2010
%Y Cf. A000079, A004169, A000215, A099884, A019434 (Fermat primes).
%Y Edge lengths of other constructible m-gons: A002194 (m=3), A002193 (4), A182007 (5), A101464 (8), A094214 (10), A101263 (12), A272534 (15), A272535 (16), A228787 (17), A272536 (20).
%Y Positions of zeros in A293516 (apart from two initial -1's), and in A336469, positions of ones in A295660 and in A336477 (characteristic function).
%Y Cf. also A046528.
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_, _R. K. Guy_
%E Definition clarified by _Bill Gosper_. - _N. J. A. Sloane_, Jun 14 2020
|
