Power of three

In mathematics, a power of three is a number of the form 3n where n is an integer, that is, the result of exponentiation with number three as the base and integer n as the exponent.

Applications

The powers of three give the place values in the ternary numeral system.[1]

In graph theory, powers of three appear in the Moon–Moser bound 3n/3 on the number of maximal independent sets of an n-vertex graph,[2] and in the time analysis of the Bron–Kerbosch algorithm for finding these sets.[3] Several important strongly regular graphs also have a number of vertices that is a power of three, including the Brouwer–Haemers graph (81 vertices), Berlekamp–van Lint–Seidel graph (243 vertices), and Games graph (729 vertices).[4]

In enumerative combinatorics, there are 3n signed subsets of a set of n elements. In polyhedral combinatorics, the hypercube and all other Hanner polytopes have a number of faces (not counting the empty set as a face) that is a power of three. For example, a 2-cube, or square, has 4 vertices, 4 edges and 1 face, and 4 + 4 + 1 = 32. Kalai's 3d conjecture states that this is the minimum possible number of faces for a centrally symmetric polytope.[5]

In recreational mathematics and fractal geometry, inverse power-of-three lengths occur in the constructions leading to the Koch snowflake,[6] Cantor set,[7] Sierpinski carpet and Menger sponge, in the number of elements in the construction steps for a Sierpinski triangle, and in many formulas related to these sets. There are 3n possible states in an n-disk Tower of Hanoi puzzle or vertices in its associated Hanoi graph.[8] In a balance puzzle with w weighing steps, there are 3w possible outcomes (sequences where the scale tilts left or right or stays balanced); powers of three often arise in the solutions to these puzzles, and it has been suggested that (for similar reasons) the powers of three would make an ideal system of coins.[9]

In number theory, all powers of three are perfect totient numbers.[10] The sums of distinct powers of three form a Stanley sequence, the lexicographically smallest sequence that does not contain an arithmetic progression of three elements.[11] A conjecture of Paul Erdős states that this sequence contains no powers of two other than 1, 4, and 256.[12]

Graham's number, an enormous number arising from a proof in Ramsey theory, is (in the version popularized by Martin Gardner) a power of three. However, the actual publication of the proof by Ronald Graham used a different number.[13]

The 0th to 63rd powers of three

(sequence A000244 in the OEIS)

30=1 316=43046721 332=1853020188851841 348=79766443076872509863361
31=3 317=129140163 333=5559060566555523 349=239299329230617529590083
32=9 318=387,420,489 334=16677181699666569 350=717897987691852588770249
33=27 319=1162261467 335=50031545098999707 351=2153693963075557766310747
34=81 320=3486784401 336=150094635296999121 352=6461081889226673298932241
35=243 321=10460353203 337=450283905890997363 353=19383245667680019896796723
36=729 322=31381059609 338=1350851717672992089 354=58149737003040059690390169
37=2187 323=94143178827 339=4052555153018976267 355=174449211009120179071170507
38=6561 324=282429536481 340=12157665459056928801 356=523347633027360537213511521
39=19683 325=847288609443 341=36472996377170786403 357=1570042899082081611640534563
310=59049 326=2541865828329 342=109418989131512359209 358=4710128697246244834921603689
311=177147 327=7625597484987 343=328256967394537077627 359=14130386091738734504764811067
312=531441 328=22876792454961 344=984770902183611232881 360=42391158275216203514294433201
313=1594323 329=68630377364883 345=2954312706550833698643 361=127173474825648610542883299603
314=4782969 330=205891132094649 346=8862938119652501095929 362=381520424476945831628649898809
315=14348907 331=617673396283947 347=26588814358957503287787 363=1144561273430837494885949696427
gollark: That would be a very weird law.
gollark: Why?
gollark: Well, guessing is hard, so I wanted to see if I could do automatic stylometric analysis.
gollark: <@!293066066605768714> Do you have the early code guessing rounds' data in a conveniently machine-readable format somewhere?
gollark: That's one for each publicly disclosed letter of the English alphabet!

See also

References
  1. Ranucci, Ernest R. (December 1968), "Tantalizing ternary", The Arithmetic Teacher, 15 (8): 718–722, JSTOR 41185884
  2. Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics, 3: 23–28, doi:10.1007/BF02760024, MR 0182577
  3. Tomita, Etsuji; Tanaka, Akira; Takahashi, Haruhisa (2006), "The worst-case time complexity for generating all maximal cliques and computational experiments", Theoretical Computer Science, 363 (1): 28–42, doi:10.1016/j.tcs.2006.06.015
  4. For the Brouwer–Haemers and Games graphs, see Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "On a family of strongly regular graphs with ", Journal of Combinatorial Theory, Series B, 103 (4): 521–531, arXiv:1201.0383, doi:10.1016/j.jctb.2013.05.005, MR 3071380. For the Berlekamp–van Lint–Seidel and Games graphs, see van Lint, J. H.; Brouwer, A. E. (1984), "Strongly regular graphs and partial geometries" (PDF), in Jackson, David M.; Vanstone, Scott A. (eds.), Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982, London: Academic Press, pp. 85–122, MR 0782310
  5. Kalai, Gil (1989), "The number of faces of centrally-symmetric polytopes", Graphs and Combinatorics, 5 (1): 389–391, doi:10.1007/BF01788696, MR 1554357
  6. von Koch, Helge (1904), "Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire", Arkiv för Matematik (in French), 1: 681–704, JFM 35.0387.02
  7. See, e.g., Mihaila, Ioana (2004), "The rationals of the Cantor set", The College Mathematics Journal, 35 (4): 251–255, doi:10.2307/4146907, MR 2076132
  8. Hinz, Andreas M.; Klavžar, Sandi; Milutinović, Uroš; Petr, Ciril (2013), "2.3 Hanoi graphs", The tower of Hanoi—myths and maths, Basel: Birkhäuser, pp. 120–134, doi:10.1007/978-3-0348-0237-6, ISBN 978-3-0348-0236-9, MR 3026271
  9. Telser, L. G. (October 1995), "Optimal denominations for coins and currency", Economics Letters, 49 (4): 425–427, doi:10.1016/0165-1765(95)00691-8
  10. Iannucci, Douglas E.; Deng, Moujie; Cohen, Graeme L. (2003), "On perfect totient numbers", Journal of Integer Sequences, 6 (4), Article 03.4.5, MR 2051959
  11. Sloane, N. J. A. (ed.). "Sequence A005836". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  12. Gupta, Hansraj (1978), "Powers of 2 and sums of distinct powers of 3", Univerzitet u Beogradu Publikacije Elektrotehničkog Fakulteta, Serija Matematika i Fizika (602–633): 151–158 (1979), MR 0580438
  13. Gardner, Martin (November 1977), "In which joining sets of points leads into diverse (and diverting) paths", Scientific American, 237 (5): 18–28
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.