OFFSET
1,2
COMMENTS
The terms 1 and 2 correspond to degenerate polygons.
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
From Stanislav Sykora, May 02 2016: (Start)
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.
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).
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)
If x,y are terms, and gcd(x,y) is a power of 2 then x*y is also a term. - David James Sycamore, Aug 24 2024
REFERENCES
A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 183.
Allan Clark, Elements of Abstract Algebra, Chapter 4, Galois Theory, Dover Publications, NY 1984, page 124.
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
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
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..2000
Laura Anderson, Jasbir S. Chahal and Jaap Top, The last chapter of the Disquisitiones of Gauss, arXiv:2110.01355 [math.HO], 2021.
Wayne Bishop, How to construct a regular polygon, Amer. Math. Monthly 85(3) (1978), 186-188.
Alessandro Chiodo, A note on the construction of the Śrī Yantra, Sorbonne Université (Paris, France, 2020).
T. Chomette, Construction des polygones réguliers (in French).
Duane W. DeTemple, Carlyle circles and the Lemoine simplicity of polygon constructions, Amer. Math. Monthly 98(2) (1991), 97-108.
Bruce Director, Measurement and Divisibility.
David Eisenbud and Brady Haran, Heptadecagon and Fermat Primes (the math bit), Numberphile video (2015).
Mauro Fiorentini, Construibili (numeri).
C. F. Gauss, Disquisitiones Arithmeticae, 1801. English translation: Yale University Press, New Haven, CT, 1966, p. 463. Original (in Latin).
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag. 63(1) (1990), 3-20. [Annotated scanned copy] [DOI]
R. K. Guy and N. J. A. Sloane, Correspondence, 1988.
Johann Gustav Hermes, Über die Teilung des Kreises in 65537 gleiche Teile (About the division of the circle into 65537 equal pieces), Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse, Vol. 3 (1894), 170-186.
Friedrich Julius Richelot, 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 ...), Journal für die reine und angewandte Mathematik 9 (1832), 1-26.
Pierre Wantzel, 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), Journal de Mathématiques Pures et Appliquées 2 (1837), 366-372.
Eric Weisstein's World of Mathematics, Constructible Number.
Eric Weisstein's World of Mathematics, Constructible Polygon.
Eric Weisstein's World of Mathematics, Regular Polygon.
Eric Weisstein's World of Mathematics, Trigonometry.
Eric Weisstein's World of Mathematics, Trigonometry Angles.
Wikipedia, Constructible polygon.
Wikipedia, Johann Gustav Hermes.
Wikipedia, Friedrich Julius Richelot.
Wikipedia, Mohr-Mascheroni theorem.
Wikipedia, Pierre Wantzel.
Wikipedia, Poncelet-Steiner theorem.
Robert G. Wilson v, Letter to N. J. A. Sloane, Aug. 1993.
FORMULA
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
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
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
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
EXAMPLE
34 is a term of this sequence because a circle can be divided into exactly parts. 7 is not.
MATHEMATICA
Select[ Range[ 1300 ], IntegerQ[ Log[ 2, EulerPhi[ # ] ] ]& ] (* Olivier Gérard Feb 15 1999 *)
(* 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 *)
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]]]
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 *)
PROG
(Haskell)
a003401 n = a003401_list !! (n-1)
a003401_list = map (+ 1) $ elemIndices 1 $ map a209229 a000010_list
-- Reinhard Zumkeller, Jul 31 2012
(PARI) for(n=1, 10^4, my(t=eulerphi(n)); if(t/2^valuation(t, 2)==1, print1(n, ", "))); \\ Joerg Arndt, Jul 29 2014
(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
(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
(Python)
from sympy import totient
A003401_list = [n for n in range(1, 10**4) if format(totient(n), 'b').count('1') == 1]
# Chai Wah Wu, Jan 12 2015
CROSSREFS
Subsequence of A295298. - Antti Karttunen, Nov 27 2017
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).
Positions of zeros in A293516 (apart from two initial -1's), and in A336469, positions of ones in A295660 and in A336477 (characteristic function).
Cf. also A046528.
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
Definition clarified by Bill Gosper. - N. J. A. Sloane, Jun 14 2020
STATUS
editing