OFFSET
0,3
COMMENTS
Partial sums of A000244. Values of base 3 strings of 1's.
a(n) = (3^n-1)/2 is also the number of different nonparallel lines determined by pair of vertices in the n dimensional hypercube. Example: when n = 2 the square has 4 vertices and then the relevant lines are: x = 0, y = 0, x = 1, y = 1, y = x, y = 1-x and when we identify parallel lines only 4 remain: x = 0, y = 0, y = x, y = 1 - x so a(2) = 4. - Noam Katz (noamkj(AT)hotmail.com), Feb 11 2001
Also number of 3-block bicoverings of an n-set (if offset is 1, cf. A059443). - Vladeta Jovovic, Feb 14 2001
3^a(n) is the highest power of 3 dividing (3^n)!. - Benoit Cloitre, Feb 04 2002
Apart from the a(0) and a(1) terms, maximum number of coins among which a lighter or heavier counterfeit coin can be identified (but not necessarily labeled as heavier or lighter) by n weighings. - Tom Verhoeff, Jun 22 2002, updated Mar 23 2017
n such that A001764(n) is not divisible by 3. - Benoit Cloitre, Jan 14 2003
Consider the mapping f(a/b) = (a + 2b)/(2a + b). Taking a = 1, b = 2 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the sequence 1/2, 4/5, 13/14, 40/41, ... converging to 1. Sequence contains the numerators = (3^n-1)/2. The same mapping for N, i.e., f(a/b) = (a + Nb)/(a+b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003
Binomial transform of A000079 (with leading zero). - Paul Barry, Apr 11 2003
With leading zero, inverse binomial transform of A006095. - Paul Barry, Aug 19 2003
Number of walks of length 2*n + 2 in the path graph P_5 from one end to the other one. Example: a(2) = 4 because in the path ABCDE we have ABABCDE, ABCBCDE, ABCDCDE and ABCDEDE. - Emeric Deutsch, Apr 02 2004
The number of triangles of all sizes (not counting holes) in Sierpiński's triangle after n inscriptions. - Lee Reeves (leereeves(AT)fastmail.fm), May 10 2004
Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2*n + 1, s(0) = 1, s(2n+1) = 4. - Herbert Kociemba, Jun 10 2004
Number of non-degenerate right-angled incongruent integer-edged Heron triangles whose circumdiameter is the product of n distinct primes of shape 4k + 1. - Alex Fink and R. K. Guy, Aug 18 2005
Also numerator of the sum of the reciprocals of the first n powers of 3, with A000244 being the sequence of denominators. With the exception of n < 2, the base 10 digital root of a(n) is always 4. In base 3 the digital root of a(n) is the same as the digital root of n. - Alonso del Arte, Jan 24 2006
The sequence 3*a(n), n >= 1, gives the number of edges of the Hanoi graph H_3^{n} with 3 pegs and n >= 1 discs. - Daniele Parisse, Jul 28 2006
Numbers n such that a(n) is prime are listed in A028491 = {3, 7, 13, 71, 103, 541, 1091, ...}. 2^(m+1) divides a(2^m*k) for m > 0. 5 divides a(4k). 5^2 divides a(20k). 7 divides a(6k). 7^2 divides a(42k). 11^2 divides a(5k). 13 divides a(3k). 17 divides a(16k). 19 divides a(18k). 1093 divides a(7k). 41 divides a(8k). p divides a((p-1)/5) for prime p = {41, 431, 491, 661, 761, 1021, 1051, 1091, 1171, ...}. p divides a((p-1)/4) for prime p = {13, 109, 181, 193, 229, 277, 313, 421, 433, 541, ...}. p divides a((p-1)/3) for prime p = {61, 67, 73, 103, 151, 193, 271, 307, 367, ...} = A014753, 3 and -3 are both cubes (one implies other) mod these primes p = 1 mod 6. p divides a((p-1)/2) for prime p = {11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, ...} = A097933(n). p divides a(p-1) for prime p > 7. p^2 divides a(p*(p-1)k) for all prime p except p = 3. p^3 divides a(p*(p-1)*(p-2)k) for prime p = 11. - Alexander Adamchuk, Jan 22 2007
Let P(A) be the power set of an n-element set A. Then a(n) = the number of [unordered] pairs of elements {x,y} of P(A) for which x and y are disjoint [and both nonempty]. Wieder calls these "disjoint usual 2-combinations". - Ross La Haye, Jan 10 2008 [This is because each of the elements of {1, 2, ..., n} can be in the first subset, in the second or in neither. Because there are three options for each, the total number of options is 3^n. However, since the sets being empty is not an option we subtract 1 and since the subsets are unordered we then divide by 2! (The number of ways two objects can be arranged.) Thus we obtain (3^n-1)/2 = a(n). - Chayim Lowen, Mar 03 2015]
Also, still with P(A) being the power set of a n-element set A, a(n) is the number of 2-element subsets {x,y} of P(A) such that the union of x and y is equal to A. Cf. A341590. - Fabio Visonà, Feb 20 2021
Starting with offset 1 = binomial transform of A003945: (1, 3, 6, 12, 24, ...) and double bt of (1, 2, 1, 2, 1, 2, ...); equals polcoeff inverse of (1, -4, 3, 0, 0, 0, ...). - Gary W. Adamson, May 28 2009
Also the constant of the polynomials C(x) = 3x + 1 that form a sequence by performing this operation repeatedly and taking the result at each step as the input at the next. - Nishant Shukla (n.shukla722(AT)gmail.com), Jul 11 2009
It appears that this is A120444(3^n-1) = A004125(3^n) - A004125(3^n-1), where A004125 is the sum of remainders of n mod k for k = 1, 2, 3, ..., n. - John W. Layman, Jul 29 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = 1, A[i, i] := 3, (i > 1), A[i, i-1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = det(A). - Milan Janjic, Jan 27 2010
This is the sequence A(0, 1; 2, 3; 2) = A(0, 1; 4, -3; 0) of the family of sequences [a, b:c, d:k] considered by Gary Detlefs, and treated as A(a, b; c, d; k) in the Wolfdieter Lang link given below. - Wolfdieter Lang, Oct 18 2010
It appears that if s(n) is a first order rational sequence of the form s(0) = 0, s(n) = (2*s(n-1)+1)/(s(n-1)+2), n > 0, then s(n)= a(n)/(a(n)+1). - Gary Detlefs, Nov 16 2010
This sequence also describes the total number of moves to solve the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Towers of Hanoi puzzle (cf. A183111 - A183125).
From Adi Dani, Jun 08 2011: (Start)
a(n) is number of compositions of odd numbers into n parts less than 3. For example, a(3) = 13 and there are 13 compositions odd numbers into 3 parts < 3:
1: (0, 0, 1), (0, 1, 0), (1, 0, 0);
3: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0), (1, 1, 1);
5: (1, 2, 2), (2, 1, 2), (2, 2, 1).
(End)
Pisano period lengths: 1, 2, 1, 2, 4, 2, 6, 4, 1, 4, 5, 2, 3, 6, 4, 8, 16, 2, 18, 4, ... . - R. J. Mathar, Aug 10 2012
a(n) is the total number of holes (triangles removed) after the n-th step of a Sierpiński triangle production. - Ivan N. Ianakiev, Oct 29 2013
a(n) solves Sum_{j = a(n) + 1 .. a(n+1)} j = k^2 for some integer k, given a(0) = 0 and requiring smallest a(n+1) > a(n). Corresponding k = 3^n. - Richard R. Forberg, Mar 11 2015
a(n+1) equals the number of words of length n over {0, 1, 2, 3} avoiding 01, 02 and 03. - Milan Janjic, Dec 17 2015
For n >= 1, a(n) is also the total number of words of length n, over an alphabet of three letters, such that one of the letters appears an odd number of times (See A006516 for 4 letter words, and the Balakrishnan reference there). - Wolfdieter Lang, Jul 16 2017
Also, the number of maximal cliques, maximum cliques, and cliques of size 4 in the n-Apollonian network. - Andrew Howroyd, Sep 02 2017
For n > 1, the number of triangles (cliques of size 3) in the (n-1)-Apollonian network. - Andrew Howroyd, Sep 02 2017
a(n) is the largest number that can be represented with n trits in balanced ternary. Correspondingly, -a(n) is the smallest number that can be represented with n trits in balanced ternary. - Thomas König, Apr 26 2020
These form Sierpinski nesting-stars, which alternate pattern on 3^n+1/2 star numbers A003154, based on the square configurations of 9^n. The partial sums of 3^n are delineated according to the geometry of a hexagram, see illustrations in links. (3*a(n-1) + 1) create Sierpinski-anti-triangles, representing the number of holes in a (n+1) Sierpinski triangle (see illustrations). - John Elias, Oct 18 2021
For n > 1, a(n) is the number of iterations necessary to calculate the hyperbolic functions with CORDIC. - Mathias Zechmeister, Jul 26 2022
a(n) is the least number k such that A065363(k) = n. - Amiram Eldar, Sep 03 2022
For all n >= 0, Sum_{k=a(n)+1..a(n+1)} 1/k < Sum_{j=a(n+1)+1..a(n+2)} 1/j. These are the minimal points which partition the infinite harmonic series into a monotonically increasing sequence. Each partition approximates log(3) from below as n tends to infinity. - Joseph Wheat, Apr 15 2023
a(n) is also the number of 3-cycles in the n-Dorogovtsev-Goltsev-Mendes graph (using the convention the 0-Dorogovtsev-Goltsev-Mendes graph is P_2). - Eric W. Weisstein, Dec 06 2023
REFERENCES
J. G. Mauldon, Strong solutions for the counterfeit coin problem, IBM Research Report RC 7476 (#31437) 9/15/78, IBM Thomas J. Watson Research Center, P. O. Box 218, Yorktown Heights, N. Y. 10598.
Paulo Ribenboim, The Book of Prime Number Records, Springer-Verlag, NY, 2nd ed., 1989, p. 60.
Paulo Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.
Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case three-in-a row, sequence a(n).
Robert Sedgewick, Algorithms, 1992, pp. 109.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..2000 (terms 0..200 from T. D. Noe)
A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.
Max A. Alekseyev and Toby Berger, Solving the Tower of Hanoi with Random Moves. In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2016, pp. 65-79. ISBN 978-0-691-16403-8
Arcytech, The Sierpinski Triangle Fractal.
Andrei Asinowski and Michaela A. Polley, Patterns in rectangulations. Part I: T-like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths, arXiv:2501.11781 [math.CO], 2025. See p. 26.
Jean-Luc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Beáta Bényi and Toshiki Matsusaka, Extensions of the combinatorics of poly-Bernoulli numbers, arXiv:2106.05585 [math.CO], 2021.
Göksal Bilgici and Tuncay Deniz Şentürk, Some Addition Formulas for Fibonacci, Pell and Jacobsthal Numbers, Annales Mathematicae Silesianae (2019) Vol. 33, 55-65.
Carlos M. da Fonseca and Anthony G. Shannon, A formal operator involving Fermatian numbers, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 491-498.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From N. J. A. Sloane, Dec 24 2012
Shaoshi Chen, Hanqian Fang, Sergey Kitaev, and Candice X.T. Zhang, Patterns in Multi-dimensional Permutations, arXiv:2411.02897 [math.CO], 2024. See pp. 17, 26.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Roger B. Eggleton, Maximal Midpoint-Free Subsets of Integers, International Journal of Combinatorics Volume 2015, Article ID 216475, 14 pages.
John Elias, Sierpinski Nesting Stars, Stars of 3*9^n-1/2, Stars of 9^n-1/2, Sierpinski Anti-Triangles.
Graham Everest, Shaun Stevens, Duncan Tamsett and Tom Ward, Primes generated by recurrence sequences, Amer. Math. Monthly, Vol. 114, No. 5 (2007), pp. 417-431.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 372.
Takao Komatsu, Some recurrence relations of poly-Cauchy numbers, J. Nonlinear Sci. Appl., (2019) Vol. 12, Issue 12, 829-845.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
H. V. Krishna and N. J. A. Sloane, Correspondence, 1975.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
László Németh, The trinomial transform triangle, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also arXiv:1807.07109 [math.NT], 2018.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
A. G. Shannon, Letter to N. J. A. Sloane, Dec 06 1974.
Morgan Ward, Note on divisibility sequences, Bull. Amer. Math. Soc., 42 (1936), 843-845.
Eric Weisstein's World of Mathematics, Apollonian Network.
Eric Weisstein's World of Mathematics, Dorogovtsev-Goltsev-Mendes Graph.
Eric Weisstein's World of Mathematics, Graph Cycle.
Eric Weisstein's World of Mathematics, Maximal Clique.
Eric Weisstein's World of Mathematics, Maximum Clique.
Eric Weisstein's World of Mathematics, Mephisto Waltz Sequence.
Eric Weisstein's World of Mathematics, Repunit.
Eric Weisstein's World of Mathematics, Weighing.
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, Vol. 8 (2008).
K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math., Vol. 3 (1892), 265-284.
Index entries for linear recurrences with constant coefficients, signature (4,-3)
FORMULA
G.f.: x/((1-x)*(1-3*x)).
a(n) = 4*a(n-1) - 3*a(n-2), n > 1. a(0) = 0, a(1) = 1.
a(n) = 3*a(n-1) + 1, a(0) = 0.
E.g.f.: (exp(3*x) - exp(x))/2. - Paul Barry, Apr 11 2003
a(n+1) = Sum_{k = 0..n} binomial(n+1, k+1)*2^k. - Paul Barry, Aug 20 2004
a(n) = Sum_{i = 0..n-1} 3^i, for n > 0; a(0) = 0.
a(n) = A125118(n, 2) for n > 1. - Reinhard Zumkeller, Nov 21 2006
a(n) = StirlingS2(n+1, 3) + StirlingS2(n+1, 2). - Ross La Haye, Jan 10 2008
a(n) = 2*a(n-1) + 3*a(n-2) + 2, n > 1. - Gary Detlefs, Jun 21 2010
a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) = 5*a(n-1) - 7*a(n-2) + 3*a(n-3), a(0) = 0, a(1) = 1, a(2) = 4. Observation by G. Detlefs. See the W. Lang comment and link. - Wolfdieter Lang, Oct 18 2010
A008344(a(n)) = 0, for n > 1. - Reinhard Zumkeller, May 09 2012
A085059(a(n)) = 1 for n > 0. - Reinhard Zumkeller, Jan 31 2013
G.f.: Q(0)/2 where Q(k) = 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 - 1/(3*9^k - 27*x*81^k/(9*x*9^k - 1/Q(k+1)))))); (continued fraction ). - Sergei N. Gladkovskii, Apr 12 2013
a(n) = A001065(3^n) where A001065(m) is the sum of the proper divisors of m for positive integer m. - Chayim Lowen, Mar 03 2015
Sum_{n>=1} 1/a(n) = A321872. - Amiram Eldar, Nov 18 2020
EXAMPLE
There are 4 3-block bicoverings of a 3-set: {{1, 2, 3}, {1, 2}, {3}}, {{1, 2, 3}, {1, 3}, {2}}, {{1, 2, 3}, {1}, {2, 3}} and {{1, 2}, {1, 3}, {2, 3}}.
Ternary........Decimal
0.................0
1.................1
11................4
111..............13
1111.............40 etc. - Zerinvary Lajos, Jan 14 2007
There are altogether a(3) = 13 three letter words over {A,B,C} with say, A, appearing an odd number of times: AAA; ABC, ACB, ABB, ACC; BAC, CAB, BAB, CAC; BCA, CBA, BBA, CCA. - Wolfdieter Lang, Jul 16 2017
MAPLE
A003462:=1/(3*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation
MATHEMATICA
(3^Range[0, 30] - 1)/2 (* Harvey P. Dale, Jul 13 2011 *)
LinearRecurrence[{4, -3}, {0, 1}, 30] (* Harvey P. Dale, Jul 13 2011 *)
Accumulate[3^Range[0, 30]] (* Alonso del Arte, Sep 10 2017 *)
CoefficientList[Series[x/(1 - 4x + 3x^2), {x, 0, 30}], x] (* Eric W. Weisstein, Sep 28 2017 *)
Table[FromDigits[PadRight[{}, n, 1], 3], {n, 0, 30}] (* Harvey P. Dale, Jun 01 2022 *)
PROG
(PARI) a(n)=(3^n-1)/2
(Sage) [(3^n - 1)/2 for n in range(0, 30)] # Zerinvary Lajos, Jun 05 2009
(Haskell)
a003462 = (`div` 2) . (subtract 1) . (3 ^)
a003462_list = iterate ((+ 1) . (* 3)) 0 -- Reinhard Zumkeller, May 09 2012
(Maxima) A003462(n):=(3^n - 1)/2$
makelist(A003462(n), n, 0, 30); /* Martin Ettl, Nov 05 2012 */
(Magma) [(3^n-1)/2: n in [0..30]]; // Vincenzo Librandi, Feb 21 2015
(PARI) concat(0, Vec(x/((1-x)*(1-3*x)) + O(x^30))) \\ Altug Alkan, Nov 01 2015
(GAP)
A003462:=List([0..30], n->(3^n-1)/2); # Muniru A Asiru, Sep 27 2017
CROSSREFS
Cf. A000225, A000392, A004125, A014753, A028491 (indices of primes), A059443 (column k = 3), A065363, A097933, A120444, A321872 (sum reciprocals).
Cf. A064099 (minimal number of weightings to detect lighter or heavier coin among n coins).
Cf. A039755 (column k = 1).
Cf. A006516 (binomial transform, and special 4 letter words).
Cf. A341590.
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Michael Somos
Corrected my comment of Jan 10 2008. - Ross La Haye, Oct 29 2008
Removed comment that duplicated a formula. - Joerg Arndt, Mar 11 2010
STATUS
approved