Power of three: Difference between revisions
m Consistency with power of 2 article. |
Antepenultimate digit of powers of three. |
||
(22 intermediate revisions by 16 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Three raised to an integer power}} |
{{Short description|Three raised to an integer power}} |
||
{{Original research|date=April 2023}} |
|||
{{Other uses|Power of Three (disambiguation){{!}}Power of Three}} |
{{Other uses|Power of Three (disambiguation){{!}}Power of Three}} |
||
[[File:fewest_weights_balance_puzzle.svg|thumb|81 (3<sup>4</sup>) combinations of weights of 1 (3<sup>0</sup>), 3 (3<sup>1</sup>), 9 (3<sup>2</sup>) and 27 (3<sup>3</sup>) kg – each weight on the left pan, right pan or unused – allow integer weights from −40 to +40 kg to be balanced; the figure shows the positive values]] |
[[File:fewest_weights_balance_puzzle.svg|thumb|81 (3<sup>4</sup>) combinations of weights of 1 (3<sup>0</sup>), 3 (3<sup>1</sup>), 9 (3<sup>2</sup>) and 27 (3<sup>3</sup>) kg – each weight on the left pan, right pan or unused – allow integer weights from −40 to +40 kg to be balanced; the figure shows the positive values]] |
||
In [[mathematics]], a '''power of three''' is a number of the form {{math|3<sup>''n''</sup>}} where {{mvar|n}} is an [[integer]], that is, the result of [[exponentiation]] with number [[3|three]] as the [[Base (exponentiation)|base]] and integer {{mvar|n}} as the [[exponent]]. |
In [[mathematics]], a '''power of three''' is a number of the form {{math|3<sup>''n''</sup>}} where {{mvar|n}} is an [[integer]], that is, the result of [[exponentiation]] with number [[3|three]] as the [[Base (exponentiation)|base]] and integer {{mvar|n}} as the [[exponent]]. |
||
In base 10, every power of 3 has an even number as its second-last digit. |
|||
==Applications== |
==Applications== |
||
Line 18: | Line 19: | ||
=== Graph theory === |
=== Graph theory === |
||
In [[graph theory]], powers of three appear in the Moon–Moser bound {{math|3<sup>''n''/3</sup>}} on the number of [[maximal independent set]]s of an {{mvar|n}}-vertex [[graph (discrete mathematics)|graph]],<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]] | volume = 3 | year = 1965 | pages = 23–28 |mr=0182577 | doi = 10.1007/BF02760024 | doi-access= |
In [[graph theory]], powers of three appear in the Moon–Moser bound {{math|3<sup>''n''/3</sup>}} on the number of [[maximal independent set]]s of an {{mvar|n}}-vertex [[graph (discrete mathematics)|graph]],<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]] | 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]] 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]]s 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).<ref>For the Brouwer–Haemers and Games graphs, see {{citation |
||
| last1 = Bondarenko | first1 = Andriy V. |
| last1 = Bondarenko | first1 = Andriy V. |
||
| last2 = Radchenko | first2 = Danylo V. |
| last2 = Radchenko | first2 = Danylo V. |
||
Line 123: | Line 124: | ||
=== Graham's number === |
=== Graham's number === |
||
[[Graham's number]], an enormous number arising from a [[mathematical proof|proof]] in [[Ramsey theory]], is (in the version popularized by [[Martin Gardner]]) a power of three. |
[[Graham's number]], an enormous number arising from a [[mathematical proof|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.<ref>{{citation |
However, the actual publication of the proof by [[Ronald Graham]] used a different number which is a [[power of two]] and much smaller.<ref>{{citation |
||
| last = Gardner | first = Martin | author-link = Martin Gardner |
| last = Gardner | first = Martin | author-link = Martin Gardner |
||
| date = November 1977 |
| date = November 1977 |
||
Line 131: | Line 132: | ||
| title = In which joining sets of points leads into diverse (and diverting) paths |
| 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> |
| volume = 237| doi = 10.1038/scientificamerican1177-18 | bibcode = 1977SciAm.237e..18G }}</ref> |
||
== Table of values == |
|||
{{Anchor|List of powers of three}} |
|||
{{OEIS|id=A000244}} |
|||
<div style="overflow:auto"> |
|||
{| style="text-align:center" |
|||
|+ |
|||
|- style="background:#e9e9e9;" |
|||
|'''3<sup>0</sup>''' || '''=''' || align="right" | '''[[1 (number)|1]]''' |
|||
| rowspan="16" style="background:white;" | |
|||
|'''3<sup>16</sup>''' || '''=''' || align="right" | '''43,046,721''' |
|||
| rowspan="16" style="background:white;" | |
|||
|'''3<sup>32</sup>''' || '''=''' || align="right" | '''1,853,020,188,851,841''' |
|||
| rowspan="16" style="background:white;" | |
|||
|'''3<sup>48</sup>''' || '''=''' || align="right" | '''79,766,443,076,872,509,863,361''' |
|||
|- |
|||
|3<sup>1</sup> || = || align="right" | [[3 (number)|3]] |
|||
|3<sup>17</sup> || = || align="right" | 129,140,163 |
|||
|3<sup>33</sup> || = || align="right" | 5,559,060,566,555,523 |
|||
|3<sup>49</sup> || = || align="right" | 239,299,329,230,617,529,590,083 |
|||
|- |
|||
|3<sup>2</sup> || = || align="right" | [[9 (number)|9]] |
|||
|3<sup>18</sup> || = || align="right" | 387,420,489 |
|||
|3<sup>34</sup> || = || align="right" | 16,677,181,699,666,569 |
|||
|3<sup>50</sup> || = || align="right" | 717,897,987,691,852,588,770,249 |
|||
|- |
|||
|3<sup>3</sup> || = || align="right" | [[27 (number)|27]] |
|||
|3<sup>19</sup> || = || align="right" | 1,162,261,467 |
|||
|3<sup>35</sup> || = || align="right" | 50,031,545,098,999,707 |
|||
|3<sup>51</sup> || = || align="right" | 2,153,693,963,075,557,766,310,747 |
|||
|- |
|||
|'''3<sup>4</sup>''' || '''=''' || align="right" | '''[[81 (number)|81]]''' |
|||
|'''3<sup>20</sup>''' || '''=''' || align="right" | '''3,486,784,401''' |
|||
|'''3<sup>36</sup>''' || '''=''' || align="right" | '''150,094,635,296,999,121''' |
|||
|'''3<sup>52</sup>''' || '''=''' || align="right" | '''6,461,081,889,226,673,298,932,241''' |
|||
|- |
|||
|3<sup>5</sup> || = || align="right" | [[243 (number)|243]] |
|||
|3<sup>21</sup> || = || align="right" | 10,460,353,203 |
|||
|3<sup>37</sup> || = || align="right" | 450,283,905,890,997,363 |
|||
|3<sup>53</sup> || = || align="right" | 19,383,245,667,680,019,896,796,723 |
|||
|- |
|||
|3<sup>6</sup> || = || align="right" | 729 |
|||
|3<sup>22</sup> || = || align="right" | 31,381,059,609 |
|||
|3<sup>38</sup> || = || align="right" | 1,350,851,717,672,992,089 |
|||
|3<sup>54</sup> || = || align="right" | 58,149,737,003,040,059,690,390,169 |
|||
|- |
|||
|3<sup>7</sup> || = || align="right" | 2,187 |
|||
|3<sup>23</sup> || = || align="right" | 94,143,178,827 |
|||
|3<sup>39</sup> || = || align="right" | 4,052,555,153,018,976,267 |
|||
|3<sup>55</sup> || = || align="right" | 174,449,211,009,120,179,071,170,507 |
|||
|- style="background:#e9e9e9;" |
|||
|'''3<sup>8</sup>''' || '''=''' || align="right" | '''6,561''' |
|||
|'''3<sup>24</sup>''' || '''=''' || align="right" | '''282,429,536,481''' |
|||
|'''3<sup>40</sup>''' || '''=''' || align="right" | '''12,157,665,459,056,928,801''' |
|||
|'''3<sup>56</sup>''' || '''=''' || align="right" | '''523,347,633,027,360,537,213,511,521''' |
|||
|- |
|||
|3<sup>9</sup> || = || align="right" | 19,683 |
|||
|3<sup>25</sup> || = || align="right" | 847,288,609,443 |
|||
|3<sup>41</sup> || = || align="right" | 36,472,996,377,170,786,403 |
|||
|3<sup>57</sup> || = || align="right" | 1,570,042,899,082,081,611,640,534,563 |
|||
|- |
|||
|3<sup>10</sup> || = || align="right" | 59,049 |
|||
|3<sup>26</sup> || = || align="right" | 2,541,865,828,329 |
|||
|3<sup>42</sup> || = || align="right" | 109,418,989,131,512,359,209 |
|||
|3<sup>58</sup> || = || align="right" | 4,710,128,697,246,244,834,921,603,689 |
|||
|- |
|||
|3<sup>11</sup> || = || align="right" | 177,147 |
|||
|3<sup>27</sup> || = || align="right" | 7,625,597,484,987 |
|||
|3<sup>43</sup> || = || align="right" | 328,256,967,394,537,077,627 |
|||
|3<sup>59</sup> || = || align="right" | 14,130,386,091,738,734,504,764,811,067 |
|||
|- |
|||
|'''3<sup>12</sup>''' || '''=''' || align="right" | '''531,441''' |
|||
|'''3<sup>28</sup>''' || '''=''' || align="right" | '''22,876,792,454,961''' |
|||
|'''3<sup>44</sup>''' || '''=''' || align="right" | '''984,770,902,183,611,232,881''' |
|||
|'''3<sup>60</sup>''' || '''=''' || align="right" | '''42,391,158,275,216,203,514,294,433,201''' |
|||
|- |
|||
|3<sup>13</sup> || = || align="right" | 1,594,323 |
|||
|3<sup>29</sup> || = || align="right" | 68,630,377,364,883 |
|||
|3<sup>45</sup> || = || align="right" | 2,954,312,706,550,833,698,643 |
|||
|3<sup>61</sup> || = || align="right" | 127,173,474,825,648,610,542,883,299,603 |
|||
|- |
|||
|3<sup>14</sup> || = || align="right" | 4,782,969 |
|||
|3<sup>30</sup> || = || align="right" | 205,891,132,094,649 |
|||
|3<sup>46</sup> || = || align="right" | 8,862,938,119,652,501,095,929 |
|||
|3<sup>62</sup> || = || align="right" | 381,520,424,476,945,831,628,649,898,809 |
|||
|- |
|||
|3<sup>15</sup> || = || align="right" | 14,348,907 |
|||
|3<sup>31</sup> || = || align="right" | 617,673,396,283,947 |
|||
|3<sup>47</sup> || = || align="right" | 26,588,814,358,957,503,287,787 |
|||
|3<sup>63</sup> || = || align="right" | 1,144,561,273,430,837,494,885,949,696,427 |
|||
|} |
|||
</div>All of these numbers above represent exponents in [[base-3]], as mentioned above. |
|||
== Powers of three whose exponents are powers of three == |
|||
{{OEIS|id=A055777}} |
|||
<div style="overflow:auto"> |
|||
{| style="text-align:center" |
|||
|+ |
|||
|- style="background:#e9e9e9;" |
|||
|'''3<sup>1</sup>''' || '''=''' || align="right" | '''[[3 (number)|3]]''' |
|||
|- |
|||
|3<sup>3</sup> || = || align="right" | [[27 (number)|27]] |
|||
|- |
|||
|3<sup>9</sup> || = || align="right" | 19,683 |
|||
|- |
|||
|3<sup>27</sup> || = || align="right" | {{replace|7,625,597,484,987|,|,{{wbr}}}} (13 digits) |
|||
|- |
|||
|'''3<sup>81</sup>''' || '''=''' || align="right" | '''{{replace|443,426,488,243,037,769,948,249,630,619,149,892,803|,|,{{wbr}}}} (39 digits)''' |
|||
|- |
|||
|3<sup>243</sup> || = || align="right" | {{replace|87,189,642,485,960,958,202,911,0...,831,683,116,791,055,225,665,627|,|,{{wbr}}}} (116 digits) |
|||
|- |
|||
|3<sup>729</sup> || = || align="right" | {{replace|662,818,605,424,187,176,105,172,...,205,437,212,700,131,838,846,883|,|,{{wbr}}}} (347 digits) |
|||
|- |
|||
|3<sup>2187</sup> || = || align="right" | {{replace|291,195,106,143,185,347,895,545,...,152,086,037,206,066,369 147,387|,|,{{wbr}}}} (1,044 digits) |
|||
|- style="background:#e9e9e9;" |
|||
|'''3<sup>6561</sup>''' || '''=''' || align="right" | '''{{replace|24,691,769,589,333,631,072,790,0...,504,694,982,343,979,438,089,603|,|,{{wbr}}}} (3,131 digits)''' |
|||
|- |
|||
|3<sup>19683</sup> || = || align="right" | {{replace|15,054,164,145,220,926,243,143,2...,800,510,818,762,686,617,859,227|,|,{{wbr}}}} (9,392 digits) |
|||
|- |
|||
|3<sup>59049</sup> || = || align="right" | {{replace|3,411,692,975,886,675,012,755,34...,240,649,572,770,556,941,930,083|,|,{{wbr}}}} (28,174 digits) |
|||
|- |
|||
|3<sup>177147</sup> || = || align="right" |{{replace|39,710,908,604,467,909,151,990,5...,219,060,890,796,418,967,881,787|,|,{{wbr}}}} (84,521 digits) |
|||
|} |
|||
</div>All of these numbers above end in 3 or 7.{{cn}} |
|||
The numbers <math>3^{3^n}</math> form an [[irrationality sequence]]: for every sequence <math>x_i</math> of [[positive integer]]s, the [[series (mathematics)|series]] |
|||
:<math>\sum_{i=0}^{\infty} \frac{1}{3^{3^i} x_i} = \frac{1}{3x_0}+\frac{1}{27x_1}+\frac{1}{19683x_2}+\cdots</math> |
|||
converges to an [[irrational number]]. Despite the rapid growth of this sequence, it is a slow-growing irrationality sequence.{{cn}} |
|||
== Selected powers of three == |
|||
'''3<sup>3</sup> = 27''' |
|||
The number that is the [[cube number|cube]] of three. |
|||
'''3<sup>9</sup> = 19,683''' |
|||
The largest power of three with distinct digits in [[base-10]]. |
|||
'''3<sup>27</sup> = 7,625,597,484,987''' |
|||
The number that is the first power of three [[tetration]] of three. |
|||
'''3<sup>39</sup> = 4,052,555,153,018,976,267''' |
|||
The first power of 3 to contain all decimal digits. |
|||
'''3<sup>68</sup> = {{Nowrap|278,128,389,443,693,511,257,285,776,231,761}}''' |
|||
The number that is conjectured to be the last power of 3 not containing a 0 in decimal. |
|||
'''3<sup>209</sup> = {{Nowrap|5,228,080,143,043,843,084,895,232,761,630,250,394,879,802,048,576,763,864,267,558,971,910,557,498,410,330,867,878,474,031,283,071,683}}''' |
|||
The largest power of 3 smaller than a [[googol]] (10<sup>100</sup>). |
|||
'''3<sup>210</sup> = {{Nowrap|15,684,240,429,131,529,254,685,6...,992,603,635,422,093,849,215,049}}''' |
|||
The smallest power of 3 greater than a [[googol]] (10<sup>100</sup>). |
|||
== See also == |
== See also == |
||
* [[Graham's Number]] |
|||
* [[Power of 10]] |
* [[Power of 10]] |
||
* [[Power of two]] |
* [[Power of two]] |
||
* [[Square root of 3]] |
|||
==References== |
==References== |
||
Line 303: | Line 148: | ||
{{DEFAULTSORT:Power Of Three}} |
{{DEFAULTSORT:Power Of Three}} |
||
[[Category:Integers]] |
[[Category:Integers]] |
||
[[Category:3 (number)]] |
Latest revision as of 07:05, 26 August 2024
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.
In base 10, every power of 3 has an even number as its second-last digit.
Applications
[edit]The powers of three give the place values in the ternary numeral system.[1]
Graph theory
[edit]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]
Enumerative combinatorics
[edit]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]
Inverse power of three lengths
[edit]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]
Perfect totient numbers
[edit]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
[edit]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 which is a power of two and much smaller.[13]
See also
[edit]References
[edit]- ^ Ranucci, Ernest R. (December 1968), "Tantalizing ternary", The Arithmetic Teacher, 15 (8): 718–722, doi:10.5951/AT.15.8.0718, JSTOR 41185884
- ^ Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics, 3: 23–28, doi:10.1007/BF02760024, MR 0182577, S2CID 9855414
- ^ 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
- ^ 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
- ^ Kalai, Gil (1989), "The number of faces of centrally-symmetric polytopes", Graphs and Combinatorics, 5 (1): 389–391, doi:10.1007/BF01788696, MR 1554357, S2CID 8917264
- ^ 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
- ^ See, e.g., Mihăilă, Ioana (2004), "The rationals of the Cantor set", The College Mathematics Journal, 35 (4): 251–255, doi:10.2307/4146907, JSTOR 4146907, MR 2076132
- ^ 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
- ^ 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
- ^ Iannucci, Douglas E.; Deng, Moujie; Cohen, Graeme L. (2003), "On perfect totient numbers", Journal of Integer Sequences, 6 (4), Article 03.4.5, Bibcode:2003JIntS...6...45I, MR 2051959
- ^ Sloane, N. J. A. (ed.), "Sequence A005836", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
- ^ 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
- ^ Gardner, Martin (November 1977), "In which joining sets of points leads into diverse (and diverting) paths", Scientific American, 237 (5): 18–28, Bibcode:1977SciAm.237e..18G, doi:10.1038/scientificamerican1177-18