Community Hub0 Subscribers
Community hub
Power of three
View on Wikipediafrom Wikipedia
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. The first ten non-negative powers of three are:
1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, etc. (sequence A000244 in OEIS)
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
| Integer sequences |
|  | ||||
|---|---|---|---|---|---|---|
| Properties of sequences | ||||||
| Properties of series |
| |||||
| Explicit series | ||||||
| Kinds of series | ||||||
| Hypergeometric series | ||||||
Classes of natural numbers | |||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
Power of three
View on Grokipediafrom Grokipedia
Definition and Fundamentals
Definition
In mathematics, a power of three is defined as a number of the form , where is an integer and the base 3 is raised to the exponent through exponentiation.[5] Exponentiation in this context represents the process of multiplying the base by itself times when is positive; for instance, .[6] This sequence, known as the powers of 3, is cataloged in the Online Encyclopedia of Integer Sequences (OEIS) as A000244.[3] The first ten terms of the sequence are:,
,
,
,
,
,
[729](/page/729),
[2187](/page/21-87),
,
.[3] For completeness, powers of three extend to negative exponents, where for positive integer , resulting in fractions like and .[5] However, the concept primarily emphasizes non-negative exponents in integer contexts. Powers of three form the basis for place values in the ternary numeral system.[7]
Notation and Sequence
In mathematics, powers of three are denoted using exponential notation as , where is an integer and the exponent appears as a superscript to the right of the base 3.[8] This compact form represents the product of factors of 3 when is positive, with by convention.[9] In computational and programming contexts, such as in C++ or Python, the operation is commonly expressed using the power function pow(3, n).[10] The infinite sequence of powers of three, given by for , is cataloged as A000244 in the On-Line Encyclopedia of Integer Sequences (OEIS).[3] This sequence is strictly increasing for , as each term is precisely three times the preceding one, resulting in exponential growth.[3] Relative to the sequence of powers of two (), powers of three grow more rapidly owing to the larger base, yielding values that surpass those of for sufficiently large .[11] Higher powers of three can be computed through iterative multiplication, initializing with and successively multiplying by 3 for each increment in the exponent: .[12] For approximating large exponents without exact computation, the properties of logarithms provide a useful tool; specifically, , which estimates the number of digits and magnitude as .[8] The table below lists exact values of for from 0 to 20, beyond which scientific notation is practical for representation.[3]| 0 | 1 |
| 1 | 3 |
| 2 | 9 |
| 3 | 27 |
| 4 | 81 |
| 5 | 243 |
| 6 | 729 |
| 7 | 2,187 |
| 8 | 6,561 |
| 9 | 19,683 |
| 10 | 59,049 |
| 11 | 177,147 |
| 12 | 531,441 |
| 13 | 1,594,323 |
| 14 | 4,782,969 |
| 15 | 14,348,907 |
| 16 | 43,046,721 |
| 17 | 129,140,163 |
| 18 | 387,420,489 |
| 19 | 1,162,261,467 |
| 20 | 3,486,784,401 |
Mathematical Properties
Arithmetic and Algebraic Properties
The powers of three, expressed as for non-negative integers , follow the standard laws of exponents in arithmetic operations involving multiplication and division. The product of two such powers is given by , reflecting the additive property of exponents when bases are identical. Similarly, division yields provided , as this simplifies the repeated multiplication inherent in the definition of exponents.[13] Addition and subtraction of distinct powers of three do not admit simple closed-form expressions analogous to those for multiplication and division. However, the sum of consecutive powers starting from up to constitutes a finite geometric series, with the formula . This summation leverages the common ratio of 3 and derives from multiplying the series by the ratio and subtracting to isolate the result.[14] Key algebraic identities further characterize powers of three. The difference factors as , where the parenthetical sum is the geometric series up to . Additionally, expressing as allows expansion via the binomial theorem:
which decomposes the power into terms weighted by binomial coefficients.[15][16]
The sequence demonstrates exponential growth, with base 3 exceeding , corresponding to a natural logarithm . This rapid expansion outpaces polynomial growth rates, such as linear or quadratic , as the function scales multiplicatively with each increment in .[17]
Number-Theoretic Properties
Powers of three, expressed as for non-negative integers , possess distinct number-theoretic characteristics rooted in their prime base. Excluding , all powers of three are odd integers, as the base 3 is odd and odd numbers raised to positive integer powers remain odd.[3] In terms of primality, is prime, while higher powers for are composite, factoring as .[3] For example, . Regarding divisibility, is divisible by whenever , since . Additionally, the relation to cyclotomic polynomials arises in the factorization of , where denotes the -th cyclotomic polynomial. Powers of three also belong to special classes of integers. For , every is a perfect totient number, satisfying , where is Euler's totient function, , and is the smallest integer such that . This holds because the iterated totients form the sequence , and their sum is .[18] The powers of three further form the basis for a Stanley sequence, where the sequence consists of all possible sums of distinct powers of three, which is 3-free (containing no three-term arithmetic progression).[19] No power of three is a perfect number, as the sum of divisors function gives , and setting this equal to yields , or , implying , which is impossible for non-negative integer . Similarly, the only Mersenne prime among powers of three is ; for , no is a Mersenne prime, as the equation with has no solutions by Mihăilescu's theorem on consecutive powers.Applications in Discrete Mathematics
In Numeral Systems
In the ternary numeral system, also known as base-3, numbers are represented using the digits 0, 1, and 2, with each positional place value corresponding to successive powers of three: for the units place, for the threes place, for the nines place, and so forth. This system allows any non-negative integer to be expressed as a sum of these weighted digits, where the coefficient for each power of three is between 0 and 2. For instance, the ternary representation denotes in decimal notation.[20][4] A notable variant is balanced ternary, which employs the digits -1, 0, and 1 (commonly symbolized as $ \overline{1} $, 0, and 1 or -, 0, +) to achieve a unique and unambiguous representation for every integer, including negatives, without the need for a separate sign bit or leading zeros. Here, the place values remain powers of three, functioning as weights for the coefficients -1, 0, or 1, enabling compact encoding of both positive and negative values. For example, the balanced ternary number equals in decimal. This structure ensures that every integer can be uniquely converted to a sum of distinct powers of three multiplied by these coefficients, facilitating efficient arithmetic operations like addition and subtraction directly on the digits.[21][4] The historical roots of numeral representations trace back to ancient Chinese counting rods, used from the Warring States period (circa 5th century BCE) through the 17th century CE, where rods arranged on a board allowed positional notation.[22] In modern computing, balanced ternary finds application in error detection mechanisms, such as ternary Berger codes, which enable self-checking circuits to detect faults in data storage and transmission by leveraging the three-state logic for improved reliability over binary equivalents.[23]In Combinatorics and Graph Theory
In combinatorics, the expression enumerates the signed subsets of an -element set, where each element may be included with a positive sign (+1), included with a negative sign (-1), or omitted (assigned 0). This count arises from the three choices available for each of the elements, corresponding to the cardinality of the set of all functions from the -element set to [0](/page/0), 1\}.[24] Similarly, Hanner polytopes, a family of convex polytopes constructed recursively via Cartesian products and polar duals starting from line segments, possess exactly faces in dimension , achieving the minimum number of faces among unconditional polytopes of that dimension.[25] The expression also appears in basic enumerative problems, such as counting the total number of ternary strings of length , where each position can be one of three symbols (e.g., 0, 1, or 2). This follows directly from the possible assignments, one for each position.[24] In the context of lattice paths, counts the unrestricted walks of length on the plane (or higher dimensions) using a step set of three directions, such as east (1,0), north (0,1), and northeast (1,1), since each step offers three independent choices without constraints on the endpoint.[26] In graph theory, provides the Moon–Moser bound on the maximum number of maximal cliques in an -vertex graph, achieved when is divisible by 3 by the complete multipartite graph with parts of size 3 each; in this Turán graph , the maximal cliques are precisely the transversals selecting one vertex from each part, yielding such cliques.[27] For example, when , this construction on 12 vertices produces exactly maximal cliques. The Bron–Kerbosch algorithm, a backtracking procedure for enumerating all maximal cliques in an undirected graph, has a worst-case time complexity of in its version with pivoting, matching the Moon–Moser bound on the output size and thus optimal up to polynomial factors for graphs achieving the maximum number of maximal cliques.[28]Applications in Geometry and Large-Scale Structures
In Fractal Geometry
In fractal geometry, powers of three frequently appear in the iterative construction of self-similar fractals, where scaling factors of $ \frac{1}{3} $ or removal of middle thirds dictate the geometry at each stage. For instance, the Cantor set is generated by starting with the unit interval [0,1] and iteratively removing the open middle third of each remaining subinterval; after $ n $ iterations, this leaves $ 2^n $ closed subintervals, each of length $ \frac{1}{3^n} $. The Hausdorff dimension of the Cantor set is $ \frac{\log 2}{\log 3} $, reflecting the scaling ratio of 3 and multiplicity of 2 per iteration. Similarly, the Koch snowflake begins with an equilateral triangle and replaces each side with four segments of length one-third the original in each iteration, adding protrusions scaled by $ \frac{1}{3} $; this process increases the perimeter while bounding an area that converges to a finite value. The curve's Hausdorff dimension is $ \frac{\log 4}{\log 3} $, arising from the factor of 4 in segment multiplication against the linear scaling of $ \frac{1}{3} $. The Sierpinski triangle is constructed by subdividing an equilateral triangle into four smaller congruent triangles using midpoints and removing the central one, repeating on the remaining three; at iteration $ n $, this yields $ 3^n $ smallest upward-pointing triangles, each with side length $ \left( \frac{1}{2} \right)^n $.[29] Its Hausdorff dimension is $ \frac{\log 3}{\log 2} $, determined by the triplication of substructures at half-scale.[29] In three dimensions, the Menger sponge starts with a cube divided into 27 smaller cubes of side $ \frac{1}{3} $ and removes the central cube and the six face centers, leaving 20 subcubes; after $ n $ iterations, it consists of $ 20^n $ cubes, each of side length $ \frac{1}{3^n} $.[30] The sponge's Hausdorff dimension is $ \frac{\log 20}{\log 3} $, capturing the 20-fold replication at one-third scale.[30] These iterative processes highlight the role of powers of three in defining fractal scaling, where inverse powers $ \frac{1}{3^n} $ govern size reduction and positive powers like $ 3^n $ or $ 20^n $ count the proliferating substructures.In Hyperbolic and Large Numbers
In hyperbolic geometry, structures involving powers of three arise in tilings and packings that leverage three-fold symmetry to model the exponential expansion of space. The order-3 apeirogonal tiling, denoted by the Schläfli symbol , is a regular paracompact tiling of the hyperbolic plane in which three apeirogons (infinite-sided polygons) meet at each vertex. This configuration reflects the negative curvature of hyperbolic space, where the number of elements—such as vertices or edge segments—at geodesic distance from a central vertex grows exponentially, with the growth rate governed by the tiling's adjacency structure rooted in the vertex degree of 3. Such tilings provide a framework for understanding large-scale geometric arrangements, where the iterative replication of triangular vertex figures leads to hierarchical expansions analogous to powers of three in discrete models. Horoball packings in hyperbolic 3-space further illustrate this connection, as they represent optimal density arrangements in ideal cell decompositions derived from regular honeycombs with triangular facets. For instance, packings associated with certain Coxeter groups achieve high densities through symmetric distributions involving three-way branching at vertices, resulting in layered structures where the number of horoballs scales exponentially with depth, effectively incorporating factors of in the cardinality of successive layers for certain group actions. These packings highlight how powers of three contribute to bounding volumes and covering efficiencies in unbounded hyperbolic domains. Powers of three also underpin some of the largest finite numbers in mathematics, particularly through iterated exponentiation in Ramsey theory. Graham's number , named after Ronald Graham, serves as an upper bound for the smallest dimension such that any 2-coloring of the edges of the complete graph on the vertices of an n-dimensional hypercube guarantees a monochromatic consisting of four coplanar vertices with all six connecting edges the same color. This problem, a specific instance of multidimensional Ramsey theory, ensures the existence of ordered substructures in large combinatorial systems. The bound vastly exceeds simple exponential growth, illustrating the scale required for such guarantees in high dimensions.[31] The construction of Graham's number employs Knuth's up-arrow notation, introduced by Donald Knuth to compactly denote hyperoperations beyond exponentiation. The notation defines , with , and extends to more arrows for higher iterations:
Tetration already surpasses dramatically for , as it stacks exponents iteratively. Graham's number is then , where (three up-arrows between three 3's, equivalent to a power tower of 3's of immense height), and for , with the superscript indicating the number of up-arrows. This 64-fold iteration yields a number incomprehensible in scale, where even the number of digits defies standard computation. Tetration and higher operations with base 3 thus provide the explosive growth needed to bound multicolored Ramsey numbers like in higher dimensions.[32]
This construction originated in the context of a 1971 paper by Graham and Bruce Rothschild, which proved a generalized Ramsey theorem for -parameter sets, establishing that sufficiently large sets partitioned into finitely many classes contain monochromatic combinatorial lines. Applying this to hypercube edge colorings yields the theoretical foundation for the bound, with the iterated powers of three ensuring the result holds across escalating dimensional complexities. The paper's insights into parameter words and partitions directly inform the hypercube problem, marking a seminal contribution to combinatorial bounds on large-scale structures.