Power of three

From HandWiki
Short description: 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.

In a context where only integers are considered, n is restricted to non-negative values, so there are 1, 3, and 3 multiplied by itself a certain number of times.

The first ten powers of 3 for non-negative values of n are:

1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, ... (sequence A000244 in the OEIS)

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.[13]

Table of values

(sequence A000244 in the OEIS)

30 = 1 316 = 43,046,721 332 = 1,853,020,188,851,841 348 = 79,766,443,076,872,509,863,361
31 = 3 317 = 129,140,163 333 = 5,559,060,566,555,523 349 = 239,299,329,230,617,529,590,083
32 = 9 318 = 387,420,489 334 = 16,677,181,699,666,569 350 = 717,897,987,691,852,588,770,249
33 = 27 319 = 1,162,261,467 335 = 50,031,545,098,999,707 351 = 2,153,693,963,075,557,766,310,747
34 = 81 320 = 3,486,784,401 336 = 150,094,635,296,999,121 352 = 6,461,081,889,226,673,298,932,241
35 = 243 321 = 10,460,353,203 337 = 450,283,905,890,997,363 353 = 19,383,245,667,680,019,896,796,723
36 = 729 322 = 31,381,059,609 338 = 1,350,851,717,672,992,089 354 = 58,149,737,003,040,059,690,390,169
37 = 2,187 323 = 94,143,178,827 339 = 4,052,555,153,018,976,267 355 = 174,449,211,009,120,179,071,170,507
38 = 6,561 324 = 282,429,536,481 340 = 12,157,665,459,056,928,801 356 = 523,347,633,027,360,537,213,511,521
39 = 19,683 325 = 847,288,609,443 341 = 36,472,996,377,170,786,403 357 = 1,570,042,899,082,081,611,640,534,563
310 = 59,049 326 = 2,541,865,828,329 342 = 109,418,989,131,512,359,209 358 = 4,710,128,697,246,244,834,921,603,689
311 = 177,147 327 = 7,625,597,484,987 343 = 328,256,967,394,537,077,627 359 = 14,130,386,091,738,734,504,764,811,067
312 = 531,441 328 = 22,876,792,454,961 344 = 984,770,902,183,611,232,881 360 = 42,391,158,275,216,203,514,294,433,201
313 = 1,594,323 329 = 68,630,377,364,883 345 = 2,954,312,706,550,833,698,643 361 = 127,173,474,825,648,610,542,883,299,603
314 = 4,782,969 330 = 205,891,132,094,649 346 = 8,862,938,119,652,501,095,929 362 = 381,520,424,476,945,831,628,649,898,809
315 = 14,348,907 331 = 617,673,396,283,947 347 = 26,588,814,358,957,503,287,787 363 = 1,144,561,273,430,837,494,885,949,696,427

All of these numbers above represent exponents in base-3, as mentioned above.

Powers of three whose exponents are powers of three

(sequence A055777 in the OEIS)

31 = 3 1 digit
33 = 27 2 digits
39 = 19,683 5 digits
327 = 7,​625,​597,​484,​987 13 digits
381 = 443,​426,​488,​243,​037,​769,​948,​249,​630,​619,​149,​892,​803 39 digits
3243 = 87,​189,​642,​485,​960,​958,​202,​911,​0...,​831,​683,​116,​791,​055,​225,​665,​627 116 digits
3729 = 662,​818,​605,​424,​187,​176,​105,​172,​...,​205,​437,​212,​700,​131,​838,​846,​883 347 digits
32187 = 291,​195,​106,​143,​185,​347,​895,​545,​...,​152,​086,​037,​206,​066,​369 147,​387 1,044 digits
36561 = 24,​691,​769,​589,​333,​631,​072,​790,​0...,​504,​694,​982,​343,​979,​438,​089,​603 3,131 digits
319683 = 15,​054,​164,​145,​220,​926,​243,​143,​2...,​800,​510,​818,​762,​686,​617,​859,​227 9,392 digits
359049 = 3,​411,​692,​975,​886,​675,​012,​755,​34...,​240,​649,​572,​770,​556,​941,​930,​083 28,174 digits
3177147 = 39,​710,​908,​604,​467,​909,​151,​990,​5...,​219,​060,​890,​796,​418,​967,​881,​787 84,521 digits

All of these numbers above end in 3 or 7.[citation needed]

The numbers [math]\displaystyle{ 3^{3^n} }[/math] form an irrationality sequence: for every sequence [math]\displaystyle{ x_i }[/math] of positive integers, the series

[math]\displaystyle{ \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.[citation needed]

Selected powers of three

33 = 27

The number that is the cube of three.

39 = 19,683

The largest power of three with distinct digits in base-10.

327 = 7,625,597,484,987

The number that is the first power of three tetration of three.

339 = 4,052,555,153,018,976,267

The first power of 3 to contain all decimal digits.

368 = 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.

3209 = 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 (10100).

3210 = 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 (10100).

See also

References

  1. Ranucci, Ernest R. (December 1968), "Tantalizing ternary", The Arithmetic Teacher 15 (8): 718–722, doi:10.5951/AT.15.8.0718 
  2. Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics 3: 23–28, doi:10.1007/BF02760024 
  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 [math]\displaystyle{ \lambda=1 }[/math]", Journal of Combinatorial Theory, Series B 103 (4): 521–531, doi:10.1016/j.jctb.2013.05.005 . For the Berlekamp–van Lint–Seidel and Games graphs, see "Strongly regular graphs and partial geometries", 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, 1984, pp. 85–122, https://pure.tue.nl/ws/files/2394798/595248.pdf 
  5. "The number of faces of centrally-symmetric polytopes", Graphs and Combinatorics 5 (1): 389–391, 1989, doi:10.1007/BF01788696 
  6. "Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire" (in fr), Arkiv för Matematik 1: 681–704, 1904, https://babel.hathitrust.org/cgi/pt?id=inu.30000100114564;view=1up;seq=673 
  7. 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 
  8. Hinz, Andreas M. (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 
  9. "Optimal denominations for coins and currency", Economics Letters 49 (4): 425–427, October 1995, 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, Bibcode2003JIntS...6...45I, https://cs.uwaterloo.ca/journals/JIS/VOL6/Cohen2/cohen50.html 
  11. Sloane, N. J. A., ed. "Sequence A005836". OEIS Foundation. https://oeis.org/A005836. 
  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) 
  13. "In which joining sets of points leads into diverse (and diverting) paths", Scientific American 237 (5): 18–28, November 1977, doi:10.1038/scientificamerican1177-18, Bibcode1977SciAm.237e..18G