A008611 a(n) = a(n-3) + 1, with a(0)=a(2)=1, a(1)=0.

1, 0, 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 10, 9, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 14, 13, 14, 15, 14, 15, 16, 15, 16, 17, 16, 17, 18, 17, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 22, 21, 22, 23, 22, 23, 24, 23, 24, 25, 24, 25, 26, 25, 26, 27, 26, 27, 28

Offset: 0

Author

N. J. A. Sloane, Mar 15 1996

Keywords

• nonn
• easy
• nice

Comments

Molien series of 2-dimensional representation of cyclic group of order 3 over GF(2).

One step back, two steps forward.

The crossing number of the graph C(n, {1,3}), n >= 8, is [n/3] + n mod 3, which gives this sequence starting at the first 4. [Yang Yuansheng et al.]

A Chebyshev transform of A078008. The g.f. is the image of (1-x)/(1-x-2*x^2) (g.f. of A078008) under the Chebyshev transform A(x)-> (1/(1+x^2))*A(x/(1+x^2)). - Paul Barry, Oct 15 2004

A047878 is an essentially identical sequence. - Anton Chupin, Oct 24 2009

Rhyme scheme of Dante Alighieri's "Divine Comedy." - David Gaita, Feb 11 2011

A194960 results from deleting the first four terms of A008611. Note that deleting the first term or first four terms of A008611 leaves a concatenation of segments (n, n+1, n+2); for related concatenations, see

A008619, (n,n+1) after deletion of first term;

A053737, (n,n+1,n+2,n+3) beginning with n=0;

A053824, (n to n+4) beginning with n=0. - Clark Kimberling, Sep 07 2011

It appears that a(n) is the number of roots of x^(n+1) + x + 1 inside the unit circle. - Michel Lagneau, Nov 02 2012

Also apparently for n >= 2: a(n) is the largest remainder r that results from dividing n+2 by 1..n+2 more than once, i.e., a(n) = max(i, A072528(n+2,i)>1). - Ralf Stephan, Oct 21 2013

Number of n-element subsets of [n+1] whose sum is a multiple of 3. a(4) = 1: {1,2,4,5}. - Alois P. Heinz, Feb 06 2017

It appears that a(n) is the number of roots of the Fibonacci polynomial F(n+2,x) strictly inside the unit circle of the complex plane. - Michel Lagneau, Apr 07 2017

For the proof of the preceding conjecture see my comments under A008615 and A049310. Chebyshev S(n,x) = i^n*F(n+1,-i*x), with i = sqrt(-1). - Wolfdieter Lang, May 06 2017

The sequence is the interleaving of three sequences: the positive integers (A000027), the nonnegative integers (A001477), and the positive integers, in that order. - Guenther Schrack, Nov 07 2020

a(n) is the number of multiples of 3 between n and 2n. - Christian Barrientos, Dec 20 2021

a(n) is the least number of football games a team has to play to be able to get n-1 points, where a win is 3 points, a draw is 1 point, and a loss is 0 points. - Sigurd Kittilsen, Dec 01 2022

Examples

			G.f. = 1 + x^2 + 2*x^3 + x^4 + 2*x^5 + 3*x^6 + 2*x^7 + 3*x^8 + 4*x^9 + ...
		

References

• D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 103.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..10000
• Cristian Cobeli, Aaditya Raghavan, and Alexandru Zaharescu, On the central ball in a translation invariant involutive field, arXiv:2408.01864 [math.NT], 2024. See p. 7.
• Frederik Glitzner and David Manlove, Perspectives on Unsolvability in Roommates Markets, arXiv:2505.06717 [cs.GT], 2025. See p. 13.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 447.
• Gerard P. Michon, Counting Polyhedra.
• Yang Yuansheng et al., The crossing number of C(n; {1,3}), Discr. Math. 289 (2004), 107-118.
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).
• Index entries for Molien series.

Crossrefs

Cf. A000027, A001477, A008619, A047878, A049310, A049347, A053737, A053824, A058207, A058788, A072528, A078008, A194960, A257075, A330396.

Programs

Haskell

a008611 n = n' + mod r 2 where (n', r) = divMod (n + 1) 3
a008611_list = f [1,0,1] where f xs = xs ++ f (map (+ 1) xs)
-- Reinhard Zumkeller, Nov 25 2013

Magma

[(n-1)-2*Floor((n-1)/3): n in [0..90]]; // Vincenzo Librandi, Aug 21 2011

Maple

with(numtheory): for n from 1 to 70 do:it:=0:
y:=[fsolve(x^n+x+1, x, complex)] : for m from 1 to nops(y) do : if abs(y[m])< 1 then it:=it+1:else fi:od: printf(`%d, `,it):od:
A008611:=n->(n-1)-2*floor((n-1)/3); seq(A008611(n), n=0..50); # Wesley Ivan Hurt, May 18 2014

Mathematica

With[{nn=30},Riffle[Riffle[Range[nn],Range[0,nn-1]],Range[nn],3]] (* or *) RecurrenceTable[{a[0]==a[2]==1,a[1]==0,a[n]==a[n-3]+1},a,{n,90}] (* Harvey P. Dale, Nov 06 2011 *)
LinearRecurrence[{1, 0, 1, -1}, {1, 0, 1, 2}, 100] (* Vladimir Joseph Stephan Orlovsky, Feb 23 2012 *)
a[ n_] := Quotient[n - 1, 3] + Mod[n + 2, 3]; (* Michael Somos, Jan 23 2014 *)

PARI

{a(n) = (n-1) \ 3 + (n+2) % 3}; /* Michael Somos, Jan 23 2014 */

Formula

a(n) = a(n-3) + 1.

a(n) = (n-1) - 2*floor((n-1)/3).

G.f.: (1 + x^2 + x^4)/(1 - x^3)^2.

After the initial term, has form {n, n+1, n+2} for n=0, 1, 2, ...

From Paul Barry, Mar 18 2004: (Start)

a(n) = Sum_{k=0..n} (-1)^floor(2*(k-2)/3);

a(n) = 4*sqrt(3)*cos(2*Pi*n/3 + Pi/6)/9 + (n+1)/3. (End)

From Paul Barry, Oct 15 2004: (Start)

G.f.: (1 - x + x^2)/((1 + x + x^2)*(x-1)^2);

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*A078008(n-2k)*(-1)^k. (End)

a(n) = -a(-2-n) for all n in Z.

Euler transform of length 6 sequence [0, 1, 2, 0, 0, -1]. - Michael Somos, Jan 23 2014

a(n) = ((n-1) mod 3) + floor((n-1)/3). - Wesley Ivan Hurt, May 18 2014

PSUM transform of A257075. - Michael Somos, Apr 15 2015

a(n) = A194960(n-3), n >= 0, with extended A194960. See the a(n) formula two lines above. - Wolfdieter Lang, May 06 2017

From Guenther Schrack, Nov 07 2020: (Start)

a(n) = (3*n + 3 + 2*(w^(2*n)*(1 - w) + w^n*(2 + w)))/9, where w = (-1 + sqrt(-3))/2, a primitive third root of unity;

a(n) = (n + 1 + 2*A049347(n))/3;

a(n) = (2*n - A330396(n-1))/3. (End)

E.g.f.: (3*exp(x)*(1 + x) + exp(-x/2)*(6*cos(sqrt(3)*x/2) - 2*sqrt(3)*sin(sqrt(3)*x/2)))/9. - Stefano Spezia, May 06 2022

Sum_{n>=2} (-1)^n/a(n) = 3*log(2) - 1. - Amiram Eldar, Sep 10 2023