# Power of three

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Power_of_three
> Markdown URL: https://mediated.wiki/source/Power_of_three.md
> Source: https://en.wikipedia.org/wiki/Power_of_three
> Source revision: 1310322792
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Three raised to an integer power}}
{{Other uses|Power of Three (disambiguation){{!}}Power of Three}}
thumb|81&nbsp;(3<sup>4</sup>) combinations of weights of 1&nbsp;(3<sup>0</sup>), 3&nbsp;(3<sup>1</sup>), 9&nbsp;(3<sup>2</sup>) and 27&nbsp;(3<sup>3</sup>)&nbsp;kg &ndash; each weight on the left pan, right pan or unused &ndash; allow integer weights from &minus;40 to +40&nbsp;kg to be balanced; the figure shows the positive values
In [mathematics](/source/mathematics), a '''power of three''' is a number of the form {{math|3<sup>''n''</sup>}} where {{mvar|n}} is an [integer](/source/integer), that is, the result of [exponentiation](/source/exponentiation) with number [three](/source/3) as the [base](/source/Base_(exponentiation)) and integer&nbsp;{{mvar|n}} as the [exponent](/source/exponent).  The first ten non-negative powers of three are: 

[1](/source/1), [3](/source/3), [9](/source/9), [27](/source/27_(number)), [81](/source/81_(number)), [243](/source/243_(number)), [729](/source/729_(number)), 2187, 6561, 19683, etc. (sequence [A000244](/source/oeis%3AA000244) in [OEIS](/source/OEIS))

==Applications==
The powers of three give the place values in the [ternary numeral system](/source/ternary_numeral_system).<ref>{{citation
 | last = Ranucci | first = Ernest R.
 | date = December 1968
 | issue = 8
 | journal = The Arithmetic Teacher
 | jstor = 41185884
 | pages = 718–722
 | title = Tantalizing ternary
 | volume = 15| doi = 10.5951/AT.15.8.0718
 }}</ref>

=== Graph theory ===
In [graph theory](/source/graph_theory), powers of three appear in the Moon–Moser bound {{math|3<sup>''n''/3</sup>}} on the number of [maximal independent set](/source/maximal_independent_set)s of an {{mvar|n}}-vertex [graph](/source/graph_(discrete_mathematics)),<ref>{{citation | last1 = Moon | first1 = J. W. | author2-link = Leo Moser | last2 = Moser | first2 = L. | title = On cliques in graphs | journal = [Israel Journal of Mathematics](/source/Israel_Journal_of_Mathematics) | volume = 3 | year = 1965 | pages = 23–28 |mr=0182577 | doi = 10.1007/BF02760024 | doi-access= | s2cid = 9855414 }}</ref> and in the time analysis of the [Bron–Kerbosch algorithm](/source/Bron%E2%80%93Kerbosch_algorithm) for finding these sets.<ref>{{citation |first1=Etsuji |last1=Tomita |first2=Akira |last2=Tanaka |first3=Haruhisa |last3=Takahashi |title=The worst-case time complexity for generating all maximal cliques and computational experiments |journal=Theoretical Computer Science |volume=363 |issue=1 |pages=28–42 |year=2006 |doi=10.1016/j.tcs.2006.06.015|doi-access= }}</ref> Several important [strongly regular graph](/source/strongly_regular_graph)s also have a number of vertices that is a power of three, including the [Brouwer–Haemers graph](/source/Brouwer%E2%80%93Haemers_graph) (81 vertices), [Berlekamp–van Lint–Seidel graph](/source/Berlekamp%E2%80%93van_Lint%E2%80%93Seidel_graph) (243 vertices), and [Games graph](/source/Games_graph) (729 vertices).<ref>For the Brouwer–Haemers and Games graphs, see {{citation
 | last1 = Bondarenko | first1 = Andriy V.
 | last2 = Radchenko | first2 = Danylo V.
 | arxiv = 1201.0383 
 | doi = 10.1016/j.jctb.2013.05.005 | doi-access=free
 | issue = 4
 | journal = [Journal of Combinatorial Theory](/source/Journal_of_Combinatorial_Theory)
 | mr = 3071380
 | pages = 521–531
 | series = Series B
 | title = On a family of strongly regular graphs with <math>\lambda=1</math>
 | volume = 103
 | year = 2013}}. For the Berlekamp–van Lint–Seidel and Games graphs, see {{citation
 | last1 = van Lint | first1 = J. H. | author1-link = J. H. van Lint
 | last2 = Brouwer | first2 = A. E. | author2-link = Andries Brouwer
 | editor1-last = Jackson | editor1-first = David M. | editor1-link = David M. Jackson
 | editor2-last = Vanstone | editor2-first = Scott A. | editor2-link = Scott Vanstone
 | contribution = Strongly regular graphs and partial geometries
 | contribution-url = https://pure.tue.nl/ws/files/2394798/595248.pdf
 | location = London
 | mr = 782310
 | pages = 85–122
 | publisher = Academic Press
 | title = Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982
 | year = 1984}}</ref>

=== Enumerative combinatorics ===
In [enumerative combinatorics](/source/enumerative_combinatorics), there are {{math|3<sup>''n''</sup>}} [signed subset](/source/signed_set)s of a set of {{mvar|n}} elements. In [polyhedral combinatorics](/source/polyhedral_combinatorics), the [hypercube](/source/hypercube) and all other [Hanner polytope](/source/Hanner_polytope)s have a number of faces (not counting the [empty set](/source/empty_set) as a face) that is a power of three. For example, a {{nowrap|2-cube}}, or [square](/source/square), has 4 vertices, 4 edges and 1 face, and {{math|1=4 + 4 + 1 = 3<sup>2</sup>}}. [Kalai's {{math|3<sup>''d''</sup>}} conjecture](/source/Kalai's_3%5Ed_conjecture) states that this is the minimum possible number of faces for a [centrally symmetric](/source/Point_reflection) polytope.<ref>{{citation
 | last = Kalai | first = Gil | author-link = Gil Kalai
 | doi = 10.1007/BF01788696
 | issue = 1
 | journal = [Graphs and Combinatorics](/source/Graphs_and_Combinatorics)
 | mr = 1554357
 | pages = 389–391
 | title = The number of faces of centrally-symmetric polytopes
 | volume = 5
 | year = 1989| s2cid = 8917264 }}</ref>

=== Inverse power of three lengths ===
In [recreational mathematics](/source/recreational_mathematics) and [fractal geometry](/source/fractal_geometry), inverse power-of-three lengths occur in the constructions leading to the [Koch snowflake](/source/Koch_snowflake),<ref>{{citation
 | last = von Koch | first = Helge | author-link = Helge von Koch
 | jfm = 35.0387.02
 | journal = [Arkiv för Matematik](/source/Arkiv_f%C3%B6r_Matematik)
 | language = fr
 | pages = 681–704
 | title = Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire
 | url = https://babel.hathitrust.org/cgi/pt?id=inu.30000100114564;view=1up;seq=673
 | volume = 1
 | year = 1904}}</ref> [Cantor set](/source/Cantor_set),<ref>See, e.g., {{citation
 | last = Mihăilă | first = Ioana
 | doi = 10.2307/4146907
 | issue = 4
 | journal = The College Mathematics Journal
 | mr = 2076132
 | pages = 251–255
 | title = The rationals of the Cantor set
 | volume = 35
 | year = 2004| jstor = 4146907
 }}</ref> [Sierpinski carpet](/source/Sierpinski_carpet) and [Menger sponge](/source/Menger_sponge), in the number of elements in the construction steps for a [Sierpinski triangle](/source/Sierpinski_triangle), and in many formulas related to these sets. There are {{math|3<sup>''n''</sup>}} possible states in an {{mvar|n}}-disk [Tower of Hanoi](/source/Tower_of_Hanoi) puzzle or vertices in its associated [Hanoi graph](/source/Hanoi_graph).<ref>{{citation
 | last1 = Hinz | first1 = Andreas M.
 | last2 = Klavžar | first2 = Sandi | author2-link = Sandi Klavžar
 | last3 = Milutinović | first3 = Uroš
 | last4 = Petr | first4 = Ciril
 | contribution = 2.3 Hanoi graphs
 | doi = 10.1007/978-3-0348-0237-6
 | isbn = 978-3-0348-0236-9
 | mr = 3026271
 | pages = 120–134
 | publisher = Birkhäuser | location = Basel
 | title = The tower of Hanoi—myths and maths
 | title-link = The Tower of Hanoi – Myths and Maths
 | year = 2013}}</ref> In a [balance puzzle](/source/balance_puzzle) with {{mvar|w}} weighing steps, there are {{math|3<sup>''w''</sup>}} 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 [coin](/source/coin)s.<ref>{{citation
 | last = Telser | first = L. G. | author-link = Lester G. Telser
 | date = October 1995
 | doi = 10.1016/0165-1765(95)00691-8
 | issue = 4
 | journal = Economics Letters
 | pages = 425–427
 | title = Optimal denominations for coins and currency
 | volume = 49}}</ref>

=== Perfect totient numbers ===
In [number theory](/source/number_theory), all powers of three are [perfect totient numbers](/source/Perfect_totient_number).<ref>{{citation
 | last1 = Iannucci | first1 = Douglas E.
 | last2 = Deng | first2 = Moujie
 | last3 = Cohen | first3 = Graeme L.
 | at = Article 03.4.5
 | issue = 4
 | journal = Journal of Integer Sequences
 | mr = 2051959
 | title = On perfect totient numbers
 | url = https://cs.uwaterloo.ca/journals/JIS/VOL6/Cohen2/cohen50.html
 | volume = 6
 | year = 2003| bibcode = 2003JIntS...6...45I
 }}</ref> The sums of distinct powers of three form a [Stanley sequence](/source/Stanley_sequence), the lexicographically smallest sequence that does not contain an [arithmetic progression](/source/arithmetic_progression) of three elements.<ref>{{cite OEIS|A005836|mode=cs2}}</ref> A [conjecture](/source/conjecture) of [Paul Erdős](/source/Paul_Erd%C5%91s) states that this sequence contains no [powers of two](/source/power_of_two) other than 1, 4, and 256.<ref>{{citation
 | last = Gupta | first = Hansraj
 | issue = 602–633
 | journal = Univerzitet u Beogradu Publikacije Elektrotehničkog Fakulteta, Serija Matematika i Fizika
 | mr = 580438
 | pages = 151–158 (1979)
 | title = Powers of 2 and sums of distinct powers of 3
 | year = 1978}}</ref>

=== Graham's number ===
[Graham's number](/source/Graham's_number), an enormous number arising from a [proof](/source/mathematical_proof) in [Ramsey theory](/source/Ramsey_theory), is (in the version popularized by [Martin Gardner](/source/Martin_Gardner)) a power of three.
However, the actual publication of the proof by [Ronald Graham](/source/Ronald_Graham) used a different number which is a [power of two](/source/power_of_two) and much smaller.<ref>{{citation
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | date = November 1977
 | issue = 5
 | journal = Scientific American
 | pages = 18–28
 | title = In which joining sets of points leads into diverse (and diverting) paths
 | volume = 237| doi = 10.1038/scientificamerican1177-18 | bibcode = 1977SciAm.237e..18G }}</ref>

== See also ==
* [Power of 10](/source/Power_of_10)
* [Power of two](/source/Power_of_two)
* [Square root of 3](/source/Square_root_of_3)

==References==
{{reflist}}

{{-}}
{{Series (mathematics)}}
{{Classes of natural numbers}}
{{Large numbers}}

{{DEFAULTSORT:Power Of Three}} 
Category:Integers
Category:3 (number)

---
Adapted from the Wikipedia article [Power of three](https://en.wikipedia.org/wiki/Power_of_three) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Power_of_three?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.