login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003462 (3^n - 1)/2.
(Formerly M3463)
229
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 (list; graph; refs; listen; history; text; internal format)
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 a(0) term, maximum number of coins among which a lighter or heavier counterfeit coin can be detected by n weighings. - Tom Verhoeff (Tom.Verhoeff(AT)acm.org), Jun 22 2002

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 (daniele.parisse(AT)eads.com), 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 pairs of elements {x,y} of P(A) for which x and y are disjoint. Wieder calls these "disjoint usual 2-combinations". - Ross La Haye, Jan 10 2008

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 G. Detlefs, and treated as A(a,b;c,d;k) in the W. 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 solving the [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Tower 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 <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)

It appears that a(n) is the number of unordered pairs of disjoint subsets of {1,2,...,n}. - John W. Layman, Mar 07 2012

For n > 1: A008344(a(n)) = 0. - Reinhard Zumkeller, May 09 2012

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

A085059(a(n)) = 1 for n > 0. - Reinhard Zumkeller, Jan 31 2013

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

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

P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 60.

P. Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.

R. Sedgewick, Algorithms, 1992, pp. 109.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

K. Zsigmondy, Zur Theorie der Potenreste, Monatsh. Math., 3 (1892), 265-284.

LINKS

T. D. Noe, Table of n, a(n) for n=0..200

Arcytech, The Sierpinski Triangle Fractal

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

G. Everest et al., Primes generated by recurrence sequences, Amer. Math. Monthly, 114 (No. 5, 2007), 417-431.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 372

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.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

Eric Weisstein's World of Mathematics, Repunit, Mephisto Waltz Sequence

Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).

M. A. Alekseyev and T. Berger, Solving the Tower of Hanoi with Random Moves, arXiv:1304.3780 [math.CO], 2013-2014.

Index entries for sequences related to sorting

Index entries for sequences related to 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) = sum(0<=k<=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

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

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

Ternery........Decimal

0.................0

1.................1

11................4

111..............13

1111.............40 etc. - Zerinvary Lajos, Jan 14 2007

MAPLE

A003462 := n-> (3^n - 1)/2;

A003462:=1/(3*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+3*a[n-2]+2 od: seq(a[n], n=0..33); # Zerinvary Lajos, Dec 14 2008

MATHEMATICA

lst={}; Do[p=(3^n-1)/2; AppendTo[lst, p], {n, 0, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Sep 29 2008 *)

a=0; lst={a}; Do[a=a*3+1; AppendTo[lst, a], {n, 0, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Dec 25 2008 *)

(3^Range[0, 30]-1)/2 (* or *) LinearRecurrence[{4, -3}, {0, 1}, 30] (* Harvey P. Dale, Jul 13 2011 *)

PROG

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

(Sage) [(3^n - 1)/2 for n in xrange(0, 27)] # 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 */

CROSSREFS

Sequences used for Shell sort: A003462, A033622, A036562, A036564, A036569, A055875.

Cf. A002718, A059443, A059945-A059951.

Cf. A064099 (minimal number of weighings to detect lighter or heavier coin among n coins).

Cf. A028491, A014753, A097933.

Cf. A000225, A000392.

Cf. A004125, A120444.

Range of A179526.

Sequence in context: A238846 A025567 * A076040 A091141 A098183 A171556

Adjacent sequences:  A003459 A003460 A003461 * A003463 A003464 A003465

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 21 15:07 EST 2014. Contains 252322 sequences.