Three raised to an integer power
81 (34 ) combinations of weights of 1 (30 ), 3 (31 ), 9 (32 ) and 27 (33 ) 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 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]
Graph theory
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
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
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
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
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
References
^ 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
λ
=
1
{\displaystyle \lambda =1}
",
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
Possessing a specific set of other numbers
Expressible via specific sums
Examples in numerical order Expression methods
Related articles (alphabetical order)