A008344 -id:A008344 - cp's OEIS frontend

A003462 a(n) = (3^n - 1)/2.

0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413, 141214768240, 423644304721, 1270932914164

Offset: 0

N. J. A. Sloane

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
Subsequence of A134025; A171960(a(n)) = a(n). - Reinhard Zumkeller, Jan 20 2010
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

			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

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).

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.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See p. 4.
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 sequences related to sorting
Index entries for linear recurrences with constant coefficients, signature (4,-3)

Sequences used for Shell sort: A033622, A003462, A036562, A036564, A036569, A055875.
Cf. A179526 (repeats), A113047 (characteristic function).
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.
Cf. A003462(n) (3-cycles), A367967(n) (5-cycles), A367968(n) (6-cycles).

A003462:=List([0..30],n->(3^n-1)/2); # Muniru A Asiru, Sep 27 2017

a003462 = (`div` 2) . (subtract 1) . (3 ^)
a003462_list = iterate ((+ 1) . (* 3)) 0  -- Reinhard Zumkeller, May 09 2012

[(3^n-1)/2: n in [0..30]]; // Vincenzo Librandi, Feb 21 2015

A003462 := n-> (3^n - 1)/2: seq(A003462(n), n=0..30);
A003462:=1/(3*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation

(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 *)

A003462(n):=(3^n - 1)/2$
makelist(A003462(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

PARI
```
a(n)=(3^n-1)/2
```

concat(0, Vec(x/((1-x)*(1-3*x)) + O(x^30))) \\ Altug Alkan, Nov 01 2015

[(3^n - 1)/2 for n in range(0,30)] # Zerinvary Lajos, Jun 05 2009

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) = Sum_{k = 0..n} A106566(n, k)*A106233(k). - Philippe Deléham, Oct 30 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
a(n) = A000244(n) - A007051(n) = A007051(n)-1. - Yuchun Ji, Oct 23 2018
Sum_{n>=1} 1/a(n) = A321872. - Amiram Eldar, Nov 18 2020

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

A029858 a(n) = (3^n - 3)/2.

Original entry on oeis.org

0, 3, 12, 39, 120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160, 2391483, 7174452, 21523359, 64570080, 193710243, 581130732, 1743392199, 5230176600, 15690529803, 47071589412, 141214768239

Offset: 1

Christian G. Bower

Also the number of 2-block covers of a labeled n-set. a(n) = A055154(n,2). Generally, number of k-block covers of a labeled n-set is T(n,k) = (1/k!)*Sum_{i = 1..k + 1} Stirling1(k + 1,i)*(2^(i - 1) - 1)^n. In particular, T(n,2) = (1/2!)*(3^n - 3), T(n,3) = (1/3!)*(7^n - 6*3^n + 11), T(n,4) = (1/4)!*(15^n - 10*7^n + 35*3^n - 50), ... - Vladeta Jovovic, Jan 19 2001
Conjectured to be the number of integers from 0 to 10^(n-1) - 1 that lack 0, 1, 2, 3, 4, 5 and 6 as a digit. - Alexandre Wajnberg, Apr 25 2005. This is easily verified to be true. - Renzo Benedetti, Sep 25 2008
Number of monic irreducible polynomials of degree 1 in GF(3)[x1,...,xn]. - Max Alekseyev, Jan 23 2006
Also, the greatest number of identical weights among which an odd one can be identified and it can be decided if the odd one is heavier or lighter, using n weighings with a comparing balance. If the odd one only needs to be identified, the sequence starts 4, 13, 40 and is A003462 (3^n - 1)/2, n > 1. - Tanya Khovanova, Dec 11 2006; corrected by Samuel E. Rhoads, Apr 18 2016
Binomial transform yields A134057. Inverse binomial transform yields A062510 with one additional 0 in front. - R. J. Mathar, Jun 18 2008
Numbers k where the recurrence s(0)=0, if s(k-1) >= k then s(k) = s(k-1) - k otherwise s(k) = s(k-1) + k produces s(k) = 0. - Hugo Pfoertner, Jan 05 2012
For n > 1: A008344(a(n)) = a(n). - Reinhard Zumkeller, May 09 2012
Also the number of edges in the (n-1)-Hanoi graph. - Eric W. Weisstein, Jun 18 2017
A level 1 Sierpiński triangle graph is a triangle. Level n+1 is formed from three copies of level n by identifying pairs of corner vertices of each pair of triangles.  a(n) is the number of degree 4 vertices in the level n Sierpinski triangle graph. - Allan Bickle, Jul 30 2020
Also the number of minimum vertex cuts in the n-Apollonian network. - Eric W. Weisstein, Dec 20 2020
Also the minimum number of turns in n-dimensional Euclidean space needed to visit all 3^n points of the grid {0, 1, 2}^n, moving in straight lines between turns (repeated visits and direction changes at non-grid points are allowed). - Marco Ripà, Aug 06 2025

			For the Sierpiński triangle, Level 1 is a triangle, so a(1) = 0.
Level 2 has three corners (degree 2) and three degree 4 vertices, so a(2) = 3.
The level 2 Hanoi graph has 3 triangles joined by 3 edges, so a(2+1) = 12.

Vincenzo Librandi, Table of n, a(n) for n = 1..300
Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
Natalia Agudelo Muñetón, Agustín Moreno Cañadas, Pedro Fernando Fernández Espinosa, and Isaías David Marín Gaviria, Brauer Configuration Algebras and Their Applications in Graph Energy Theory, Mathematics (2021) Vol. 9, 3042.
Alex Born, Cor A. J. Hukrnes, and Gerhard J. Woeginger, How to detect a counterfeit coin: adaptive versus non-adaptive solutions, Inf. Proc. Lett. 86 (2003) 137-141.
Gary Darby, The Counterfeit Coin
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 17.
Lorenz Halbeisen and Norbert Hungerbuhler, The general counterfeit coin problem, Discr. Math 147 (1-3) (1995) 139-150, Theorem 1 with b=1.
Andreas Hinz, Sandi Klavzar, and Sara Sabrina Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
Bennet Manvel, Counterfeit coin problems, Math. Mag. 50 (2) (1977) 90-92, theorem 2.
Marco Ripà, Solving the 106 years old 3^k points problem with the clockwise-algorithm, Journal of Fundamental Mathematics and Applications, 2020, 3(2), 84-97.
Allen Stenger and Jack Wert, The Twelve Coins (or Twelve bags of Gold)
Eric Weisstein's World of Mathematics, Apollonian Network
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Minimum Vertex Cut
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A055154, A003462, A007051, A034472, A024023.
Cf. A000203, A008776.
Cf. A007283, A029858, A067771, A233774, A233775, A246959 (Sierpiński triangle graphs).
Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

a029858 = (`div` 2) . (subtract 3) . (3 ^)
a029858_list = iterate ((+ 3) . (* 3)) 0
-- Reinhard Zumkeller, May 09 2012

[(3^n-3)/2: n in [1..30]]; // Vincenzo Librandi, Jun 05 2011

a:=n->sum(3^j,j=1..n): seq(a(n),n=0..23); # Zerinvary Lajos, Jun 27 2007

Table[(3^n - 3)/2, {n, 24}] (* Alonso del Arte, Dec 29 2014 *)

a(n)=(3^n-3)\2 \\ Charles R Greathouse IV, Apr 17 2012

a(n) = 3*a(n-1) + 3. - Alexandre Wajnberg, Apr 25 2005
O.g.f: 3*x^2/((1-x)*(1-3*x)). - R. J. Mathar, Jun 18 2008
a(n) = 3^(n-1) + a(n-1) (with a(1)=0). - Vincenzo Librandi, Nov 18 2010
a(n) = 3*A003462(n-1). - R. J. Mathar, Sep 10 2015
E.g.f.: 3*(-1 + exp(2*x))*exp(x)/2. - Ilya Gutkovskiy, Apr 19 2016
a(n) = A067771(n-1) - 3. - Allan Bickle, Jul 30 2020
a(n) = sigma(A008776(n-2)) for n>=2. - Flávio V. Fernandes, Apr 20 2021

Corrected by T. D. Noe, Nov 07 2006

A008348 a(0)=0; thereafter a(n) = a(n-1) + prime(n) if a(n-1) < prime(n), otherwise a(n) = a(n-1) - prime(n).

Original entry on oeis.org

0, 2, 5, 0, 7, 18, 5, 22, 3, 26, 55, 24, 61, 20, 63, 16, 69, 10, 71, 4, 75, 2, 81, 164, 75, 172, 71, 174, 67, 176, 63, 190, 59, 196, 57, 206, 55, 212, 49, 216, 43, 222, 41, 232, 39, 236, 37, 248, 25, 252, 23, 256, 17, 258, 7, 264, 1, 270, 541, 264, 545, 262, 555

Offset: 0

N. J. A. Sloane and J. H. Conway

a(n) < 2*prime(n). Conjecture: a(n) > 0 for n > 3. - Thomas Ordowski, Dec 03 2016 [This conjecture is false, because a(369019)=0. The next counterexample occurs at n = 22877145. - Dmitry Kamenetsky, Feb 14 2017. (Cf. A309225.)]

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A008344, A022831, A022837, A309225.

A008348 := proc(n) option remember; if n = 0 then 0 elif A008348(n-1)>=ithprime(n) then A008348(n-1)-ithprime(n); else A008348(n-1)+ithprime(n); fi; end;
# Maple from N. J. A. Sloane, Aug 31 2019 (Start)
# Riecaman transform
Riecaman := proc(a,s,M)
# Start with s, add or subtract a[n], get M terms. If a has w terms, can get M=w+1 terms.
local b,M2,n,t;
if whattype(a) <> list then ERROR("First argument should be a list"); fi;
if a[1]=0 then ERROR("a[1] should not be zero"); fi;
M2 := min(nops(a),M-1);
b:=[s]; t:=s;
for n from 1 to M2 do
   if a[n]>t then t:=t+a[n] else t:=t-a[n]; fi; b:=[op(b),t]; od:
b; end;
# Riecaman transform of primes, starting at s=0
p1:=[seq(ithprime(i),i=1..100)];
q0:=Riecaman(p1,0,99);
# End

a := {0}; For[n = 2, n < 100, n++, If[a[[n - 1]] >= Prime[n - 1], b := a[[n - 1]] - Prime[n - 1], b := a[[n - 1]] + Prime[n - 1];]; a = Append[a, b]]; a (* Stefan Steinerberger, May 02 2006 *)
nxt[{n_,a_}]:={n+1,If[aHarvey P. Dale, Sep 13 2024 *)

lista(nn) = {print1(a=0, ", "); for (n=1, nn, if (a < (p=prime(n)), a += p, a -= p); print1(a, ", "););} \\ Michel Marcus, Dec 04 2016

a(n) = c(1)p(1) + ... + c(n)p(n), where c(i) = 1 if a(i-1) > p(i) and c(i) = -1 if a(i-1) <= p(i) (p(i) = primes). - Clark Kimberling

More terms from Clark Kimberling

Name edited by Dmitry Kamenetsky, Feb 14 2017

A046901 a(n) = a(n-1) - n if a(n-1) > n, else a(n) = a(n-1) + n.

Original entry on oeis.org

1, 3, 6, 2, 7, 1, 8, 16, 7, 17, 6, 18, 5, 19, 4, 20, 3, 21, 2, 22, 1, 23, 46, 22, 47, 21, 48, 20, 49, 19, 50, 18, 51, 17, 52, 16, 53, 15, 54, 14, 55, 13, 56, 12, 57, 11, 58, 10, 59, 9, 60, 8, 61, 7, 62, 6, 63, 5, 64, 4, 65, 3, 66, 2, 67, 1, 68, 136, 67, 137

Offset: 1

N. J. A. Sloane

Variation (1) on Recamán's sequence A005132.

a(A134931(n-1)) = 1. - Reinhard Zumkeller, Jan 31 2013

N. J. A. Sloane, First 10000 terms
Nick Hobson, Python program for this sequence
Kival Ngaokrajang, scatter plot in log-log scale looks, for both this sequence and A211346.
Index entries for sequences related to Recamán's sequence

Cf. A008343, A008344, A005132.
Cf. A076039, A003462, A076041, A076042, A057198.
Cf. A085059.
Cf. A238324.

a046901 n = a046901_list !! (n-1)
a046901_list = scanl1 (\u v -> if u > v then u - v else u + v) [1..]
-- Reinhard Zumkeller, Dec 07 2015, Jan 31 2013

A046901 := proc(n) option remember; if n = 1 then 1 else if A046901(n-1)>n then A046901(n-1)-n else A046901(n-1)+n; fi; fi; end;

a[1]=1;a[n_]:=a[n]=If[a[n-1]>n,a[n-1]-n,a[n-1]+n]; Table[a[i],{i,70}]  (* Harvey P. Dale, Apr 01 2011 *)
nxt[{n_,a_}]:={n+1,If[a>n+1,a-n-1,a+n+1]}; NestList[nxt,{1,1},70][[All,2]] (* Harvey P. Dale, Jun 01 2019 *)

a(n)=if(n<2,1,a(n-1)-if(sign(n-a(n-1))+1,-1,1)*n);

This is a concatenation S_0, S_1, S_2, ... where S_i = [b_0, b_1, ..., b_{k-1}], k=5*3^i, with b_0 = 1, b_{2j} = k+j, b_{2j+1} = (k+1)/2-j. E.g., S_0 = [1, 3, 6, 2, 7].
For any m>=1, for k such that 5*3^k+3>12m, a((5*3^k+3-12*m)/6)= m. For example, for k>=1, a((5*3^k-9)/6) = 1. - Benoit Cloitre, Oct 31 2002
a(n) = A008343(n+1) + 1. - Jon Maiga, Jul 09 2021

A076042 a(0) = 0; thereafter a(n) = a(n-1) + n^2 if a(n-1) < n^2, otherwise a(n) = a(n-1) - n^2.

Original entry on oeis.org

0, 1, 5, 14, 30, 5, 41, 90, 26, 107, 7, 128, 272, 103, 299, 74, 330, 41, 365, 4, 404, 845, 361, 890, 314, 939, 263, 992, 208, 1049, 149, 1110, 86, 1175, 19, 1244, 2540, 1171, 2615, 1094, 2694, 1013, 2777, 928, 2864, 839, 2955, 746, 3050, 649, 3149

Offset: 0

Amarnath Murthy, Oct 29 2002

Does not return to zero within first 2^25000 =~ 10^7525 terms.  Define an epoch as an addition followed by a sequence of (addition, subtraction) pairs.  The first epoch has length 1 (+), the second 3 (++-), the third 5 (++-+-), and so forth (cf. A324792).  The epoch lengths increase geometrically by about the square root of 3, and the value at the end of each epoch is the low value in the epoch.  These observations lead to the Python program given. - Tomas Rokicki, Aug 31 2019
Using the Maple program in A324791, I confirmed that a(n) != 0 for 0 < n < 10^2394. See the a- and b-files in A325056 and A324791. - N. J. A. Sloane, Oct 03 2019
'Easy Recamán transform' of the squares. - Daniel Forgues, Oct 25 2019

Tomas Rokicki, Table of n, a(n) for n = 0..20000

Cf. A076039, A003462, A076041, A046901.
See also A325056, A324791, A324792.
Cf. A053461 ('Recamán transform' of the squares).
Cf. A000290, A008344, A008345.

a:= proc(n) option remember; `if`(n<0, 0,
      ((s, t)-> s+`if`(sAlois P. Heinz, Jan 11 2020

a[0] = 0;
a[n_] := a[n] = a[n-1] + If[a[n-1] < n^2, n^2, -n^2];
a /@ Range[0, 50] (* Jean-François Alcover, Apr 11 2020 *)

v=vector(50); v[1]=1; for(n=2,50,if(v[n-1]

More terms from Ralf Stephan, Mar 20 2003
a(0)=0 prepended, at the suggestion of Allan C. Wechsler, by N. J. A. Sloane, Aug 31 2019
Offset set to 0, to cohere with previous action of N. J. A. Sloane, by Allan C. Wechsler, Sep 08 2019

A084110 Let L(n) = ordered list of divisors of n = {d_1=1, d_2, ..., d_k=n}; set e_1=1, e_i = e_{i-1}/d_i if that is an integer otherwise e_i = e_{i-1}*d_i; then a(n) = e_k.

Original entry on oeis.org

1, 2, 3, 8, 5, 1, 7, 1, 27, 1, 11, 48, 13, 1, 1, 16, 17, 162, 19, 80, 1, 1, 23, 16, 125, 1, 1, 112, 29, 25, 31, 512, 1, 1, 1, 1944, 37, 1, 1, 25, 41, 49, 43, 176, 405, 1, 47, 48, 343, 1250, 1, 208, 53, 324, 1, 49, 1, 1, 59, 9, 61, 1, 567, 8, 1, 121, 67, 272, 1, 49, 71, 9, 73, 1

Offset: 1

Reinhard Zumkeller, May 12 2003

nonn

a(n) = r(n,tau(n)), where r is defined as follows:
let d(n,j) = j-th divisor of n, 1 <= j <= tau(n) = A000005(n), r(n,1)=d(n,1), r(n,j) = if d(n,j) divides r(n,j-1) then r(n,j-1)/d(n,j) else r(n,j-1)*d(n,j), 1 < j <= tau(n);
p prime: a(p)=p, a(p^2)=p^3, a(p^3)=1, a(p^k)=p^A008344(k+1);
a(m)=1 iff m multiplicatively perfect: a(A007422(k))=1.
a(A084111(n)) = A084111(n). - Reinhard Zumkeller, Jul 31 2014

			Divisors of 48 = {1,2,3,4,6,8,12,16,24,48}: 1*2*3 = 6 -> 6*4 = 24 -> 24/6 = 4 -> 4*8 = 32 -> 32*12 = 384 -> 384/16 = 24 -> 24/24 = 1 -> 1*48 = a(48);
divisors of 49 = {1,7,49}: 1*7 = 7 -> 7*49 = 343 = a(49);
divisors of 50 = {1,2,5,10,25,50}: 1*2*5 = 10 -> 10/10 = 1 -> 1*25 = 25 -> 25*50 = 1250 = a(50).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Divisor Product.
Eric Weisstein's World of Mathematics, Multiplicative Perfect Number.

Cf. A027750, A084111 (fixed points), A084113, A084114.

a084110 = foldl (/*) 1 . a027750_row where
   x /* y = if m == 0 then x' else x*y where (x',m) = divMod x y
-- Reinhard Zumkeller, Feb 21 2012, Oct 25 2010

a[n_] := Module[{d = Divisors[n], e}, e[i_] := e[i] = If[i == 1, 1, If[Divisible[e[i-1], d[[i]]], e[i-1]/d[[i]], e[i-1] d[[i]]]]; e[Length[d]]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Oct 10 2021 *)

Corrected and extended by David Wasserman, Dec 14 2004

A309226 Index of n-th low point in A008348 (see Comments for definition).

Original entry on oeis.org

0, 3, 8, 21, 56, 145, 366, 945, 2506, 6633, 17776, 48521, 133106, 369019, 1028404, 2880287, 8100948, 22877145, 64823568, 184274931, 525282740, 1501215193, 4299836186, 12340952049, 35486796312, 102220582465, 294917666854, 852123981581, 2465458792768

Offset: 0

N. J. A. Sloane, Sep 01 2019

A "low point" in a sequence is a term which is less than the previous term (this condition is skipped for the initial term) and which is followed by two or more increases.

This concept is useful for the analysis of sequences (such as A005132, A008344, A008348, A022837, A076042, A309222, etc.) which have long runs of terms which alternately rise and fall.

Cf. A005132, A008344, A008348, A022837, A076042, A135025, A309222, A324782, A324783.

blocks := proc(a,S) local b,c,d,M,L,n;
# Given a list a, whose leading term has index S, return [b,c,d], where b lists the indices of the low points in a, c lists the values of a at the low points, and d lists the length of runs between the low points.
b:=[]; c:=[]; d:=[]; L:=1;
# is a[1] a low point?
   n:=1;
   if( (a[n+1]>a[n]) and (a[n+2]>a[n+1]) ) then
   b:=[op(b),n+S-1]; c:=[op(c),a[n]]; d:=[op(d), n-L]; L:=n; fi;
for n from 2 to nops(a)-2 do
# is a[n] a low point?
   if( (a[n-1]>a[n]) and (a[n+1]>a[n]) and (a[n+2]>a[n+1]) ) then
   b:=[op(b),n+S-1]; c:=[op(c),a[n]]; d:=[op(d), n-L]; L:=n; fi; od;
[b,c,d]; end;
# Let a := [0, 2, 5, 0, 7, 18, 5, 22, 3, 26, 55, 24, ...]; be a list of the first terms in A008348
blocks(a,0)[1]; # the present sequence
blocks(a,0)[2]; # A324782
blocks(a,0)[3]; # A324783

a(n) = A135025(n-1)-1.

a(17)-a(28) from Giovanni Resta, Oct 02 2019

Modified definition to make offset 0. - N. J. A. Sloane, Oct 02 2019

A327442 a(0) = 0; thereafter a(n) = a(n-1) + phi(n) if phi(n) > a(n-1), otherwise a(n) = a(n-1) - phi(n), where phi is the Euler phi-function A000010.

Original entry on oeis.org

0, 1, 0, 2, 0, 4, 2, 8, 4, 10, 6, 16, 12, 0, 6, 14, 6, 22, 16, 34, 26, 14, 4, 26, 18, 38, 26, 8, 20, 48, 40, 10, 26, 6, 22, 46, 34, 70, 52, 28, 12, 52, 40, 82, 62, 38, 16, 62, 46, 4, 24, 56, 32, 84, 66, 26, 2, 38, 10, 68, 52, 112, 82, 46, 14, 62, 42, 108, 76, 32, 8, 78, 54, 126, 90

Offset: 0

N. J. A. Sloane, Sep 12 2019

nonn

N. J. A. Sloane, Table of n, a(n) for n = 0..9999

Cf. A000010, A008344.

a:= proc(n) option remember; `if`(n<1, 0, ((s, t)-> s+
     `if`(sAlois P. Heinz, Jan 11 2020

a[0] = 0; a[n_] := a[n] = With[{phi = EulerPhi[n], a1 = a[n-1]}, If[phi>a1, a1+phi, a1-phi]];
a /@ Range[0, 80] (* Jean-François Alcover, Nov 01 2020 *)
nxt[{n_,a_}]:=Module[{ph=EulerPhi[n+1]},{n+1,If[ph>a,a+ph,a-ph]}]; NestList[nxt,{0,0},80][[;;,2]] (* Harvey P. Dale, Jun 14 2023 *)

A008343 a(1)=1; thereafter a(n+1) = a(n)-n if a(n) >= n otherwise a(n+1) = a(n)+n.

Original entry on oeis.org

1, 0, 2, 5, 1, 6, 0, 7, 15, 6, 16, 5, 17, 4, 18, 3, 19, 2, 20, 1, 21, 0, 22, 45, 21, 46, 20, 47, 19, 48, 18, 49, 17, 50, 16, 51, 15, 52, 14, 53, 13, 54, 12, 55, 11, 56, 10, 57, 9, 58, 8, 59, 7, 60, 6, 61, 5, 62, 4, 63, 3

Offset: 1

N. J. A. Sloane and J. H. Conway

nonn

For n>0, a(A060816(n))=0. - Dmitry Kamenetsky, Feb 14 2017

T. D. Noe, Table of n, a(n) for n=1..1000

Cf. A008344, A060816.

A008343 := proc(n) option remember; if n = 1 then 1 elif A008343(n-1) >= (n-1) then A008343(n-1)-(n-1) else A008343(n-1)+(n-1); fi; end;

nxt[{n_,a_}]:={n+1,If[a>=n,a-n,a+n]}; Transpose[NestList[nxt,{1,1},60]][[2]] (* Harvey P. Dale, May 04 2014 *)

a(n) = (n-1+a(n-1)) mod (2*(n-1)). - Jon Maiga, Jul 09 2021

Name edited by Dmitry Kamenetsky, Feb 14 2017

A085059 a(1) = 1, a(n+1) = a(n)-n if a(n) > n else a(n+1) = a(n) + n.

Original entry on oeis.org

1, 2, 4, 1, 5, 10, 4, 11, 3, 12, 2, 13, 1, 14, 28, 13, 29, 12, 30, 11, 31, 10, 32, 9, 33, 8, 34, 7, 35, 6, 36, 5, 37, 4, 38, 3, 39, 2, 40, 1, 41, 82, 40, 83, 39, 84, 38, 85, 37, 86, 36, 87, 35, 88, 34, 89, 33, 90, 32, 91, 31, 92, 30, 93, 29, 94, 28, 95, 27, 96, 26, 97, 25, 98, 24, 99

Offset: 1

Amarnath Murthy and Meenakshi Srikanth (menakan_s(AT)yahoo.com), Jun 27 2003

Let (3^k-1)/2 = r then a((3^k-1)/2) = a(r) = 1 and a(r-1) = r. Geometrical interpretation. The sequence is obtained by the following rule: A point moves on the positive number line with the rule that in every step it has to move one unit more than the previous step and with the aim that it is to be as close to 0 as possible but on the positive side.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A005132.
Equals 1+A008344(n).
Cf. A046901.

a085059 n = a085059_list !! (n-1)
a085059_list = 1 : f 1 1 where
   f v w = y : f (v + 1) y where
     y = if w > v then w - v else w + v
-- Reinhard Zumkeller, Jan 31 2013

RecurrenceTable[{a[1]==1,a[n+1]==If[a[n]>n,a[n]-n , a[n]+n]}, a[n], {n,80}] (* Harvey P. Dale, May 11 2011 *)

a(A003462(n)) = 1. - Reinhard Zumkeller, Jan 31 2013

More terms from Sam Alexander, Oct 20 2003

cp's OEIS Frontend

A003462 a(n) = (3^n - 1)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

Sage

Formula

Extensions

A029858 a(n) = (3^n - 3)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

Extensions

A008348 a(0)=0; thereafter a(n) = a(n-1) + prime(n) if a(n-1) < prime(n), otherwise a(n) = a(n-1) - prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A046901 a(n) = a(n-1) - n if a(n-1) > n, else a(n) = a(n-1) + n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A076042 a(0) = 0; thereafter a(n) = a(n-1) + n^2 if a(n-1) < n^2, otherwise a(n) = a(n-1) - n^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A084110 Let L(n) = ordered list of divisors of n = {d_1=1, d_2, ..., d_k=n}; set e_1=1, e_i = e_{i-1}/d_i if that is an integer otherwise e_i = e_{i-1}*d_i; then a(n) = e_k.

Views

Author

Keywords