A002530 -id:A002530 - cp's OEIS frontend

A079935 a(n) = 4*a(n-1) - a(n-2) with a(1) = 1, a(2) = 3.

1, 3, 11, 41, 153, 571, 2131, 7953, 29681, 110771, 413403, 1542841, 5757961, 21489003, 80198051, 299303201, 1117014753, 4168755811, 15558008491, 58063278153, 216695104121, 808717138331, 3018173449203, 11263976658481, 42037733184721, 156886956080403

Offset: 1

Benoit Cloitre and Paul D. Hanna, Jan 20 2003

See A001835 for another version.
Greedy frac multiples of sqrt(3): a(1)=1, Sum_{n>0} frac(a(n)*x) < 1 at x=sqrt(3).
The n-th greedy frac multiple of x is the smallest integer that does not cause Sum_{k=1..n} frac(a(k)*x) to exceed unity; an infinite number of terms appear as the denominators of the convergents to the continued fraction of x.
Binomial transform of A002605. - Paul Barry, Sep 17 2003
In general, Sum_{k=0..n} binomial(2n-k,k)*j^(n-k) = (-1)^n* U(2n, i*sqrt(j)/2), i=sqrt(-1). - Paul Barry, Mar 13 2005
The Hankel transform of this sequence is [1,2,0,0,0,0,0,0,0,0,0,...]. - Philippe Deléham, Nov 21 2007
From Richard Choulet, May 09 2010: (Start)
This sequence is a particular case of the following situation:
a(0)=1, a(1)=a, a(2)=b with the recurrence relation a(n+3) = (a(n+2)*a(n+1)+q)/a(n)
where q is given in Z to have Q = (a*b^2 + q*b + a + q)/(a*b) itself in Z.
The g.f is f: f(z) = (1 + a*z + (b-Q)*z^2 + (a*b + q - a*Q)*z^3)/(1 - Q*z^2 + z^4);
so we have the linear recurrence: a(n+4) = Q*a(n+2) - a(n).
The general form of a(n) is given by:
a(2*m) = Sum_{p=0..floor(m/2)} (-1)^p*binomial(m-p,p)*Q^(m-2*p) + (b-Q)*Sum_{p=0..floor((m-1)/2)} (-1)^p*binomial(m-1-p,p)*Q^(m-1-2*p) and
a(2*m+1) = a*Sum_{p=0..floor(m/2)} (-1)^p*binomial(m-p,p)*Q^(m-2*p) + (a*b+q-a*Q)*Sum_{p=0..floor((m-1)/2)} (-1)^p*binomial(m-1-p,p)*Q^(m-1-2*p).
(End)
x-values in the solution to 3*x^2 - 2 = y^2. - Sture Sjöstedt, Nov 25 2011
From Wolfdieter Lang, Oct 12 2020: (Start)
[X(n) = S(n, 4) - S(n-1, 4), Y(n) = X(n-1)] gives all positive solutions of X^2 + Y^2 - 4*X*Y = -2, for n = -oo..+oo, where the Chebyshev S-polynomials are given in A049310, with S(-1, 0) = 0, and S(-|n|, x) = - S(|n|-2, x), for |n| >= 2.
This binary indefinite quadratic form has discriminant D = +12. There is only this family representing -2 properly with X and Y positive, and there are no improper solutions.
See also the preceding comment by Sture Sjöstedt.
See the formula for a(n) = X(n-1), for n >= 1, in terms of S-polynomials below.
This comment is inspired by a paper by Robert K. Moniot (private communication). See his Oct 04 2020 comment in A027941 related to the case of x^2 + y^2 - 3*x*y = -1 (special Markov solutions). (End)
a(n) is also the output of Tesler's formula for the number of perfect matchings of an m x n Mobius band where m and n are both even, specialized to m=2. (The twist is on the length-n side.) - Sarah-Marie Belcastro, Feb 15 2022

			a(4) = 41 since frac(1*x) + frac(3*x) + frac(11*x) + frac(41*x) < 1, while frac(1*x) + frac(3*x) + frac(11*x) + frac(k*x) > 1 for all k > 11 and k < 41.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Dalen Dockery, Marie Jameson, and Samuel Wilson, d-Fold Partition Diamonds, arXiv:2307.02579 [math.NT], 2023.
Tanya Khovanova, Recursive Sequences
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), pp. 609-640.
G. Tesler, Matchings in graphs on non-orientable surfaces, Journal of Combinatorial Theory B, 78(2000), 198-231.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory, Vol. 7, No. 5 (2011), pp. 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012), The John Selfridge Memorial Volume.
Index entries for linear recurrences with constant coefficients, signature (4,-1).

Cf. A002530 (denominators of convergents to sqrt(3)), A079934, A079936, A001353.
Cf. A001835 (same except for the first term).
Row 4 of array A094954.
Cf. similar sequences listed in A238379.

a079935 n = a079935_list !! (n-1)
a079935_list =
   1 : 3 : zipWith (-) (map (4 *) $ tail a079935_list) a079935_list
-- Reinhard Zumkeller, Aug 14 2011

I:=[1,3]; [n le 2 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..40]]; // Vincenzo Librandi, Jun 06 2015

f:= gfun:-rectoproc({a(n) = 4*a(n-1) - a(n-2),a(1)=1,a(2)=3}, a(n), remember):
seq(f(n),n=1..30); # Robert Israel, Jun 05 2015

a[n_] := (MatrixPower[{{1, 2}, {1, 3}}, n].{{1}, {1}})[[1, 1]]; Table[ a[n], {n, 0, 23}] (* Robert G. Wilson v, Jan 13 2005 *)
LinearRecurrence[{4,-1},{1,3},30] (* or *) CoefficientList[Series[ (1-x)/(1-4x+x^2),{x,0,30}],x]  (* Harvey P. Dale, Apr 26 2011 *)
a[n_] := Sqrt[2/3] Cosh[(-1 - 2 n) ArcCsch[Sqrt[2]]];
Table[Simplify[a[n-1]], {n, 1, 12}] (* Peter Luschny, Oct 13 2020 *)

a(n)=([0,1; -1,4]^(n-1)*[1;3])[1,1] \\ Charles R Greathouse IV, Mar 18 2017

my(x='x+O('x^30)); Vec((1-x)/(1-4*x+x^2)) \\ G. C. Greubel, Feb 25 2019

[lucas_number1(n,4,1)-lucas_number1(n-1,4,1) for n in range(1, 25)] # Zerinvary Lajos, Apr 29 2009

For n > 0, a(n) = ceiling( (2+sqrt(3))^n/(3+sqrt(3)) ).
From Paul Barry, Sep 17 2003: (Start)
G.f.: (1-x)/(1-4*x+x^2).
E.g.f.: exp(2*x)*(sinh(sqrt(3)*x)/sqrt(3) + cosh(sqrt(3)*x)).
a(n) = ( (3+sqrt(3))*(2+sqrt(3))^n + (3-sqrt(3))*(2-sqrt(3))^n )/6 (offset 0). (End)
a(n) = Sum_{k=0..n} binomial(2*n-k, k)*2^(n-k). - Paul Barry, Jan 22 2005 [offset 0]
a(n) = (-1)^n*U(2*n, i*sqrt(2)/2), U(n, x) Chebyshev polynomial of second kind, i=sqrt(-1). - Paul Barry, Mar 13 2005 [offset 0]
a(n) = Jacobi_P(n,-1/2,1/2,2)/Jacobi_P(n,-1/2,1/2,1). - Paul Barry, Feb 03 2006 [offset 0]
a(n) = sqrt(2+(2-sqrt(3))^(2*n-1) + (2+sqrt(3))^(2*n-1))/sqrt(6). - Gerry Martens, Jun 05 2015
a(n) = (1/2 + sqrt(3)/6)*(2-sqrt(3))^n + (1/2 - sqrt(3)/6)*(2+sqrt(3))^n. - Robert Israel, Jun 05 2015
a(n) = S(n-1,4) - S(n-2,4) = (-1)^(n-1)*S(2*(n-1), i*sqrt(2)), with Chebyshev S-polynomials (A049310), the imaginary unit i, S(-1, x) = 0, for n >= 1. See also the formula above by Paul Barry (with offset 0). - Wolfdieter Lang, Oct 12 2020
a(n) = sqrt(2/3)*cosh((-1 - 2*n) arccsch(sqrt(2))), where arccsch is the inverse hyperbolic cosecant function (with offset 0). - Peter Luschny, Oct 13 2020
From Peter Bala, May 04 2025: (Start)
a(n) = (1/sqrt(3)) * sqrt(1 - T(2*n-1, -2)), where T(k, x) denotes the k-th Chebyshev polynomial of the first kind.
a(n) divides a(3*n-1); a(n) divides a(5*n-2); in general, for k >= 0, a(n) divides a((2*k+1)*n - k).
The aerated sequence [b(n)]n>=1 = [1, 0, 3, 0, 11, 0, 41, 0, ...] is a fourth-order linear divisibility sequence; that is, if n | m then b(n) | b(m). It is the case P1 = 0, P2 = -6, Q = 1 of the 3-parameter family of divisibility sequences found by Williams and Guy.
Sum_{n >= 2} 1/(a(n) - 1/a(n)) = 1/2 (telescoping series: for n >= 1, 1/(a(n) - 1/a(n)) = 1/A052530(n-1) - 1/A052530(n).) (End)

A134451 Ternary digital root of n.

Original entry on oeis.org

0, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2

Offset: 0

Reinhard Zumkeller, Oct 27 2007

Continued fraction expansion of sqrt(3) - 1. - N. J. A. Sloane, Dec 17 2007. Cf. A040001, A048878/A002530.
Minimum number of terms required to express n as a sum of odd numbers.
Shadow transform of even numbers A005843. - Michel Marcus, Jun 06 2013
From Jianing Song, Nov 01 2022: (Start)
For n > 0, a(n) is the minimal gap of distinct numbers coprime to n. Proof: denote the minimal gap by b(n). For odd n we have A058026(n) > 0, hence b(n) = 1. For even n, since 1 and -1 are both coprime to n we have b(n) <= 2, and that b(n) >= 2 is obvious.
The maximal gap is given by A048669. (End)

			n=42: A007089(42) = '1120', A053735(42) = 1+1+2+0 = 4,
A007089(4)='11', A053735(4)=1+1=2: therefore a(42) = 2.
0.732050807568877293527446341... = 0 + 1/(1 + 1/(2 + 1/(1 + 1/(2 + ...)))). - _Harry J. Smith_, May 31 2009

Harry J. Smith, Table of n, a(n) for n = 0..20000
Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5(4) (1999), 138-150; see Definition 7 for the shadow transform.
N. J. A. Sloane, Transforms.
Eric Weisstein's World of Mathematics, Digital Root.
Eric Weisstein's World of Mathematics, Ternary.

Cf. A000010, A055034, A134452, A160390 (decimal expansion).
Apart from a(0) the same as A040001.
Related base-3 sequences: A053735, A134451, A230641, A230642, A230643, A230853, A230854, A230855, A230856, A230639, A230640, A010063 (trajectory of 1).

a134451 = until (< 3) a053735
-- Reinhard Zumkeller, May 12 2011

A134451:=n->((n+1) mod 2)+2*signum(n)-1; seq(A134451(n), n=0..100); # Wesley Ivan Hurt, Dec 06 2013

Table[Mod[n + 1, 2] + 2 Sign[n] - 1, {n, 0, 100}] (* Wesley Ivan Hurt, Dec 06 2013 *)

a(n) = if(!n, 0, 2 - n%2) \\ Andrew Howroyd, Dec 08 2024

a(n) = n if n <= 2, otherwise a(A053735(n)).
a(A005408(n)) = 1; a(A005843(n)) = 2 for n>0;
a(n) = 0 if n=0, otherwise A000034(n-1).
a(n) = ((n+1) mod 2) + 2*sign(n) - 1. - Wesley Ivan Hurt, Dec 06 2013
Multiplicative with a(2^e) = 2, a(p^e) = 1 for odd prime p. - Andrew Howroyd, Aug 06 2018
a(0) = A055034(1) / A000010(1), a(n) = A000010(n+1) / A055034(n+1), n>1. - Torlach Rush, Oct 29 2019
Dirichlet g.f.: zeta(s)*(1+1/2^s). - Amiram Eldar, Jan 01 2023

A080599 Expansion of e.g.f.: 2/(2-2*x-x^2).

Original entry on oeis.org

1, 1, 3, 12, 66, 450, 3690, 35280, 385560, 4740120, 64751400, 972972000, 15949256400, 283232149200, 5416632421200, 110988861984000, 2425817682288000, 56333385828720000, 1385151050307024000, 35950878932544576000, 982196278209226080000, 28175806418228108640000

Offset: 0

Detlef Pauly (dettodet(AT)yahoo.de), Feb 24 2003

Number of ordered partitions of {1,..,n} with at most 2 elements per block. - Bob Proctor, Apr 18 2005
In other words, number of preferential arrangements of n things (see A000670) in which each clump has size 1 or 2. - N. J. A. Sloane, Apr 13 2014
Recurrences (of the hypergeometric type of the Jovovic formula) mean: multiplying the sequence vector from the left with the associated matrix of the recurrence coefficients (here: an infinite lower triangular matrix with the natural numbers in the main diagonal and the triangular series in the subdiagonal) recovers the sequence up to an index shift. In that sense, this sequence here and many other sequences of the OEIS are eigensequences. - Gary W. Adamson, Feb 14 2011
Number of intervals in the weak (Bruhat) order of S_n that are Boolean algebras. - Richard Stanley, May 09 2011
a(n) = D^n(1/(1-x)) evaluated at x = 0, where D is the operator sqrt(1+2*x)*d/dx. Cf. A000085, A005442 and A052585. - Peter Bala, Dec 07 2011
From Gus Wiseman, Jul 04 2020: (Start)
Also the number of (1,1,1)-avoiding or cubefree sequences of length n covering an initial interval of positive integers. For example, the a(0) = 1 through a(3) = 12 sequences are:
  ()  (1)  (11)  (112)
           (12)  (121)
           (21)  (122)
                 (123)
                 (132)
                 (211)
                 (212)
                 (213)
                 (221)
                 (231)
                 (312)
                 (321)
(End)

			From _Gus Wiseman_, Jul 04 2020: (Start)
The a(0) = 1 through a(3) = 12 ordered set partitions with block sizes <= 2 are:
  {}  {{1}}  {{1,2}}    {{1},{2,3}}
             {{1},{2}}  {{1,2},{3}}
             {{2},{1}}  {{1,3},{2}}
                        {{2},{1,3}}
                        {{2,3},{1}}
                        {{3},{1,2}}
                        {{1},{2},{3}}
                        {{1},{3},{2}}
                        {{2},{1},{3}}
                        {{2},{3},{1}}
                        {{3},{1},{2}}
                        {{3},{2},{1}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
S. Alex Bradt, Jennifer Elder, Pamela E. Harris, Gordon Rojas Kirby, Eva Reutercrona, Yuxuan (Susan) Wang, and Juliet Whidden, Unit interval parking functions and the r-Fubini numbers, arXiv:2401.06937 [math.CO], 2024. See page 10.
Jennifer Elder, Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori, Boolean intervals in the weak order of S_n, arXiv:2306.14734 [math.CO], 2023.
Laura Gellert and Raman Sanyal, On degree sequences of undirected, directed, and bidirected graphs, arXiv preprint arXiv:1512.08448 [math.CO], 2015.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 36.
Harri Hakula, Helmut Harbrecht, Vesa Kaarnioja, Frances Y. Kuo, and Ian H. Sloan, Uncertainty quantification for random domains using periodic random variables, arXiv:2210.17329 [math.NA], 2022.
Dixy Msapato, Counting the number of tau-exceptional sequences over Nakayama algebras, arXiv:2002.12194 [math.RT], 2020.
Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Index entries for related partition-counting sequences

Cf. A000085, A000670, A002530, A002605, A005442, A052585, A052611.
Cf. A090932, A102726, A106356, A232464, A333755, A335455, A335456.
Column k=2 of A276921.
Cubefree numbers are A004709.
(1,1)-avoiding patterns are A000142.
(1,1,1)-avoiding compositions are A232432.
(1,1,1)-matching patterns are A335508.
(1,1,1)-avoiding permutations of prime indices are A335511.
(1,1,1)-avoiding compositions are ranked by A335513.
(1,1,1,1)-avoiding patterns are A189886.

[n le 2 select 1 else (n-1)*Self(n-1) + Binomial(n-1,2)*Self(n-2): n in [1..31]]; // G. C. Greubel, Jan 31 2023

a:= n-> n! *(Matrix([[1,1], [1/2,0]])^n)[1,1]:
seq(a(n), n=0..40);  # Alois P. Heinz, Jun 01 2009
a:= gfun:-rectoproc({a(n) = n*a(n-1)+(n*(n-1)/2)*a(n-2),a(0)=1,a(1)=1},a(n),remember):
seq(a(n), n=0..40); # Robert Israel, Nov 01 2015

Table[n!*SeriesCoefficient[-2/(-2+2*x+x^2),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 13 2012 *)
Round@Table[n! ((1+Sqrt[3])^(n+1) - (1-Sqrt[3])^(n+1))/(2^(n+1) Sqrt[3]), {n, 0, 20}] (* Vladimir Reshetnikov, Oct 31 2015 *)

Vec(serlaplace((2/(2-2*x-x^2) + O(x^30)))) \\ Michel Marcus, Nov 02 2015

A002605=BinaryRecurrenceSequence(2,2,0,1)
def A080599(n): return factorial(n)*A002605(n+1)/2^n
[A080599(n) for n in range(41)] # G. C. Greubel, Jan 31 2023

a(n) = n*a(n-1) + (n*(n-1)/2)*a(n-2). - Vladeta Jovovic, Aug 22 2003
E.g.f.: 1/(1-x-x^2/2). - Richard Stanley, May 09 2011
a(n) ~ n!*((1+sqrt(3))/2)^(n+1)/sqrt(3). - Vaclav Kotesovec, Oct 13 2012
a(n) = n!*((1+sqrt(3))^(n+1) - (1-sqrt(3))^(n+1))/(2^(n+1)*sqrt(3)). - Vladimir Reshetnikov, Oct 31 2015
a(n) = A090932(n) * A002530(n+1). - Robert Israel, Nov 01 2015

A048788 a(2n+1) = a(2n) + a(2n-1), a(2n) = 2*a(2n-1) + a(2n-2); a(n) = n for n = 0, 1.

Original entry on oeis.org

0, 1, 2, 3, 8, 11, 30, 41, 112, 153, 418, 571, 1560, 2131, 5822, 7953, 21728, 29681, 81090, 110771, 302632, 413403, 1129438, 1542841, 4215120, 5757961, 15731042, 21489003, 58709048, 80198051, 219105150, 299303201, 817711552, 1117014753

Offset: 0

Robin Trew (trew(AT)hcs.harvard.edu), Dec 11 1999

Numerators of continued fraction convergents to sqrt(3) - 1 (A160390). See A002530 for denominators. - N. J. A. Sloane, Dec 17 2007
Convergents are 1, 2/3, 3/4, 8/11, 11/15, 30/41, 41/56, 112/153, ... - Clark Kimberling, Sep 21 2013
A strong divisibility sequence, that is gcd(a(n),a(m)) = a(gcd(n,m)) for all positive integers n and m. - Peter Bala, Jun 06 2014
From Sarah-Marie Belcastro, Feb 15 2022: (Start)
a(n) is also the number of perfect matchings of an edge-labeled 2 X (n-1) Mobius band grid graph, or equivalently the number of domino tilings of a 2 X (n-1) Mobius band grid. (The twist is on the length-n side.)
a(n) is also the output of Lu and Wu's formula for the number of perfect matchings of an m X n Mobius band grid, specialized to m = 2 with the twist on the length-n side.
2*a(n) is the number of perfect matchings of an edge-labeled 2 X (n-1) projective planar grid graph, or equivalently the number of domino tilings of a 2 X (n-1) projective planar grid. (End)

Russell Lyons, A bird's-eye view of uniform spanning trees and forests, in Microsurveys in Discrete Probability, AMS, 1998.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Peter Bala, Notes on 2-periodic continued fractions and Lehmer sequences
Sarah-Marie Belcastro, Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces, J. Integer Seq. 26 (2023), Article 23.5.6.
Marcia Edson, Scott Lewis and Omer Yayenie, The k-periodic Fibonacci sequence and an extended Binet's formula, INTEGERS 11 (2011) #A32.
W. T. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, Physics Letters A, 293 (2002), 235-246.
D. Panario, M. Sahin, and Q. Wang, A family of Fibonacci-like conditional sequences, INTEGERS, Vol. 13, 2013, #A78.
J. L. Ramirez and F. Sirvent, A q-Analogue of the Bi-Periodic Fibonacci Sequence, J. Int. Seq. 19 (2016) # 16.4.6, t_n at a=2, b=1.
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (0,4,0,-1).

Cf. A002530, A002531.

Bisections are A001835 and A052530.

a:=[0,1,2,3];; for n in [5..40] do a[n]:=4a[n-1]-a[n-2]; od; a; # G. C. Greubel, Dec 23 2019

I:=[0,1,2,3]; [n le 4 select I[n] else 4*Self(n-2)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Dec 10 2013

seq( simplify( `if`(`mod`(n,2)=0, 2*ChebyshevU((n-2)/2, 2), ChebyshevU((n-1)/2, 2) - ChebyshevU((n-3)/2, 2)) ), n=0..40); # G. C. Greubel, Dec 23 2019

Numerator[NestList[(2/(2 + #))&, 0, 40]] (* Vladimir Joseph Stephan Orlovsky, Apr 13 2010 *)
CoefficientList[Series[x(1+2x-x^2)/(1-4x^2+x^4), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 10 2013 *)
a0[n_]:= ((3+Sqrt[3])*(2-Sqrt[3])^n-((-3+Sqrt[3])*(2+Sqrt[3])^n))/6 // Simplify
a1[n_]:= 2*Sum[a0[i], {i, 1, n}]
Flatten[MapIndexed[{a1[#-1],a0[#]}&,Range[20]]] (* Gerry Martens, Jul 10 2015 *)
Round@Table[With[{r=1+Sqrt[2], s=1+Sqrt[3]}, ((r + (-1)^n/r) s^n/2^(n/2) - (1/r + (-1)^n r) 2^(n/2)/s^n) Sqrt[6]/12], {n, 0, 20}] (* or *) LinearRecurrence[ {0,4,0,-1}, {0,1,2,3}, 40] (* Vladimir Reshetnikov, May 11 2016 *)
Table[If[EvenQ[n], 2*ChebyshevU[(n-2)/2, 2], ChebyshevU[(n-1)/2, 2] - ChebyshevU[(n-3)/2, 2]], {n, 0, 40}] (* G. C. Greubel, Dec 23 2019 *)

main(size)=v=vector(size); v[1]=0;v[2]=1;v[3]=2;v[4]=3;for(i=5, size, v[i]=4*v[i-2] - v[i-4]); v; \\ Anders Hellström, Jul 11 2015

a=vector(50); a[1]=1; a[2]=2; for(n=3, #a, if(n%2==1, a[n]=a[n-1]+a[n-2], a[n]=2*a[n-1]+a[n-2])); concat(0, a) \\ Colin Barker, Jan 30 2016

a(n)=([0,1,0,0;0,0,1,0;0,0,0,1;-1,0,4,0]^n*[0;1;2;3])[1,1] \\ Charles R Greathouse IV, Mar 16 2017

apply( {A048788(n)=imag((2+quadgen(12))^(n\/2)*if(bittest(n, 0), quadgen(12)-1, 2))}, [0..30]) \\ M. F. Hasler, Nov 04 2019

{a(n) = my(s=1,m=n); if(n<0,s=-(-1)^n; m=-n); polcoeff(x*(1+2*x-x^2)/(1-4*x^2+x^4) + x*O(x^m), m)*s}; /* Michael Somos, Sep 17 2020 */

@CachedFunction
def a(n):
    if (mod(n,2)==0): return 2*chebyshev_U((n-2)/2, 2)
    else: return chebyshev_U((n-1)/2, 2) - chebyshev_U((n-3)/2, 2)
[a(n) for n in (0..40)] # G. C. Greubel, Dec 23 2019

G.f.: x*(1+2*x-x^2)/(1-4*x^2+x^4). - Paul Barry, Sep 18 2009
a(n) = 4*a(n-2) - a(n-4). - Vincenzo Librandi, Dec 10 2013
a(2*n-1) = A001835(n); a(2*n) = 2*A001353(n). - Peter Bala, Jun 06 2014
From Gerry Martens, Jul 11 2015: (Start)
Interspersion of 2 sequences [a1(n-1),a0(n)] for n>0:
a0(n) = ((3+sqrt(3))*(2-sqrt(3))^n-((-3+sqrt(3))*(2+sqrt(3))^n))/6.
a1(n) = 2*Sum_{i=1..n} a0(i). (End)
a(n) = ((r + (-1)^n/r)*s^n/2^(n/2) - (1/r + (-1)^n*r)*2^(n/2)/s^n)*sqrt(6)/12, where r = 1 + sqrt(2), s = 1 + sqrt(3). - Vladimir Reshetnikov, May 11 2016
a(n) = 2*ChebyshevU(n-1, 2) if n is even and ChebyshevU(n, 2) - ChebyshevU(n-1, 2) if n in odd. - G. C. Greubel, Dec 23 2019
a(n) = -(-1)^n*a(-n) for all n in Z. - Michael Somos, Sep 17 2020

Denominator of g.f. corrected by Paul Barry, Sep 18 2009

Incorrect g.f. deleted by Colin Barker, Aug 10 2012

A152063 Triangle read by rows. Coefficients of the Fibonacci product polynomials F(n) = Product_{k=1..(n - 1)/2} (1 + 4cos^2(kPi/n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 5, 5, 1, 6, 8, 1, 8, 19, 13, 1, 9, 25, 21, 1, 11, 42, 65, 34, 1, 12, 51, 90, 55, 1, 14, 74, 183, 210, 89, 1, 15, 86, 234, 300, 144, 1, 17, 115, 394, 717, 654, 233, 6, 18, 130, 480, 951, 954, 377, 1, 20, 165, 725, 1825, 2622, 1985, 610, 1, 21, 183, 855

Offset: 1

Gary W. Adamson and Roger L. Bagula, Nov 22 2008

The triangle A125076 is formed by reading upward sloping diagonals. - Gary W. Adamson, Nov 26 2008

Bisection of the triangle: odd-indexed rows are reversals of the rows of A126124, even-indexed rows are the reversals of the rows of A123965. - Gary W. Adamson, Aug 15 2010

			First few rows of the triangle are:
1;
1;
1, 2;
1, 3;
1, 5, 5;
1, 6, 8;
1, 8, 19, 13;
1, 9, 25, 21;
1, 11, 42, 65, 34;
1, 12, 51, 90, 55;
1, 14, 74, 183, 210, 89;
1, 15, 86, 234, 300, 144;
1, 17, 115, 394, 717, 654, 233;
1, 18, 130, 480, 951, 954, 377;
1, 20, 165, 725, 1825, 2622, 1985, 610;
1, 21, 183, 855, 2305, 3573, 2939, 987;
...
By row, alternate signs (+,-,+,-,...) with descending exponents. Rows with n terms have exponents (n-1), (n-2), (n-3),...;
Example: There are two rows with 4 terms corresponding to the polynomials
x^3 - 8x^2 + 19x - 13 (roots associated with the heptagon); and
x^3 - 9x^2 + 25x - 21 (roots associated with the 9-gon (nonagon)).

James P. Bradshaw, Philipp Lampe, and Dusan Ziga, Snake graphs and their characteristic polynomials, arXiv:1910.11823 [math.CO], 2019. See 4.7 p. 16.
N. D. Cahill and D. A. Narayan, Fibonacci and Lucas Numbers as Tridiagonal Matrix Determinants, Fibonacci Quarterly, 42(3):216-221, 2004.
M. X. He, D. Simon and P. E. Ricci, Dynamics of the zeros of Fibonacci polynomials, Fibonacci Quarterly, 35(2):160-168, 1997.
V. E. Hoggatt and C. T. Long, Divisibility Properties of Generalized Fibonacci Polynomials, Fibonacci Quarterly, 12:113-120, 1974.

Cf. A000045, A002530 (row sums), A125076, A126124, A123965, A011973.

P := proc(n) option remember; if n < 5 then return
ifelse(n < 3, 1, ifelse(n = 3, 1 + 2*q, 1 + 3*q)) fi;
(1 + 3*q)*P(n - 2) - q^2*P(n - 4) end:
T := n -> local k; seq(coeff(P(n), q, k), k = 0..(n-1)/2):
for n from 1 to 12 do T(n) od;  # (after F. Chapoton)  Peter Luschny, May 27 2024
# Alternative:
P := n -> local k; add(binomial(n-k,k)*(1+x)^(floor(n/2)-k)*x^k, k=0..floor(n/2)):
T := n -> local k; seq(coeff(P(n), x, k), k = 0..n/2):
for n from 0 to 12 do T(n) od; # (after F. Chapoton) Peter Luschny, May 28 2024

Recurrence (as monic polynomials) P(n+4) = (1 + 3*q)*P(n+2) - q^2*P(n). - F. Chapoton, May 27 2024

As monic polynomials, these are the numerators of the polynomials from A011973 evaluated at 1/(1+q). - F. Chapoton, May 28 2024

A189006 Array A(m,n) read by antidiagonals: number of domino tilings of the m X n grid with upper left corner removed iff m*n is odd, (m>=0, n>=0).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 4, 5, 1, 1, 1, 1, 8, 11, 11, 8, 1, 1, 1, 1, 13, 15, 36, 15, 13, 1, 1, 1, 1, 21, 41, 95, 95, 41, 21, 1, 1, 1, 1, 34, 56, 281, 192, 281, 56, 34, 1, 1, 1, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 1, 1, 1, 89, 209, 2245, 2415, 6728, 2415, 2245, 209, 89, 1, 1

Offset: 0

Alois P. Heinz, Apr 15 2011

			A(3,3) = 4, because there are 4 domino tilings of the 3 X 3 grid with upper left corner removed:
  . .___. . .___. . .___. . .___.
  ._|___| ._|___| ._| | | ._|___|
  | |___| | | | | | |_|_| |___| |
  |_|___| |_|_|_| |_|___| |___|_|
Array begins:
  1, 1,  1,  1,   1,    1,    1, ...
  1, 1,  1,  1,   1,    1,    1, ...
  1, 1,  2,  3,   5,    8,   13, ...
  1, 1,  3,  4,  11,   15,   41, ...
  1, 1,  5, 11,  36,   95,  281, ...
  1, 1,  8, 15,  95,  192, 1183, ...
  1, 1, 13, 41, 281, 1183, 6728, ...

Alois P. Heinz, Antidiagonals n = 0..75, flattened
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, FKT algorithm
Wikipedia, Matching (graph theory)
Index entries for sequences related to dominoes

Rows m=0+1, 2-12 give: A000012, A000045(n+1), A002530(n+1), A005178(n+1), A189003, A028468, A189004, A028470, A189005, A028472, A210724, A028474.
Main diagonal gives: A189002.
Cf. A099390, A187596, A187616, A187617, A187618, A004003.

with(LinearAlgebra):
A:= proc(m, n) option remember; local i, j, s, t, M;
      if m=0 or n=0 then 1
    elif m1 or j>1 or s=0 then
               if j

A[1, 1] = 1; A[m_, n_] := A[m, n] = Module[{i, j, s, t, M}, Which[m == 0 || n == 0, 1, m < n, A[n, m], True, s = Mod[n*m, 2];M[i_, j_] /; j < i := -M[j, i]; M[, ] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i-1)*m+j-s; If[i > 1 || j > 1 || s == 0, If[j < m, M[t, t+1] = 1]; If[i < n, M[t, t+m] = 1-2*Mod[j, 2]]]]]; Sqrt[Det[Array[M, {n*m-s, n*m-s}]]]]]; Table[Table[A[m, d-m], {m, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 26 2013, translated from Maple *)

A096147 Prime denominators of the rational convergents to sqrt(3).

Original entry on oeis.org

3, 11, 41, 571, 2131, 110771, 1542841, 15558008491, 808717138331, 1663476485027525263506023431291963826940251, 33648911495192637123958375850447995878147331088460770783226682531

Offset: 1

Cino Hilliard, Jul 24 2004

nonn

Next term is too large to include.
The next term has 79 digits. - Harvey P. Dale, Jul 06 2019
This is the prime subsequence of A002530. - Ray Chandler, Aug 01 2004
Primes p such that 3*p^2 - 2 is a square. - Vincenzo Librandi, May 21 2013

Amiram Eldar, Table of n, a(n) for n = 1..23

Cf. A002530, A079935, A096146.

Select[Denominator[Convergents[Sqrt[3],300]],PrimeQ] (* Harvey P. Dale, Jul 06 2019 *)

Offset corrected by Amiram Eldar, Jul 11 2024

A102341 Areas of 'close-to-equilateral' integer triangles.

Original entry on oeis.org

12, 120, 1848, 25080, 351780, 4890480, 68149872, 949077360, 13219419708, 184120982760, 2564481115560, 35718589344360, 497495864091732, 6929223155685600, 96511629630137568, 1344233586759971040, 18722758603319903340

Offset: 1

Johannes Koelman (Joc_Kay(AT)hotmail.com), Feb 20 2005

A close-to-equilateral integer triangle is defined to be a triangle with integer sides and integer area such that the largest and smallest sides differ in length by unity. The first five close-to-equilateral integer triangles have sides (5, 5, 6), (17, 17, 16), (65, 65, 66), (241, 241, 240) and (901, 901, 902).
After these first five triangles, there are two more (namely (3361,3361,3360,4890480) and (12545,12545,12546,68149872)). - Nícolas V. Calsavara, Jul 13 2023
Then, the next four terms are {three sides a<=b<=c and area}: {46816, 46817, 46817, 949077360}, {174725, 174725, 174726, 13219419708}, {652080, 652081, 652081, 184120982760}, {2433601, 2433601, 2433602, 2564481115560}. Also, if we allow degenerate triangles (area 0), the first case would be {1,1,2,0}. We have 12 cases and a weak conjecture is that the total number of the 'close-to-equilateral' triangles is finite. - Zak Seidov, Feb 23 2005
This is an infinite series; two sides are equal in length to the hypotenuse of almost 30-60 triangles and the third side alternates between that length +/- 1. - Dan Sanders (dan(AT)ified.ca), Oct 22 2005
Heron's formula: a triangle with side lengths (x,y,z) has area A = sqrt(s*(s-x)*(s-y)*(s-z)) where s = (x+y+z)/2. For this sequence we assume integer side-lengths x = y = z +/- 1. Then for A to also be an integer, x+y+z must be even, so we can assume z = 2k for some positive integer k. Now s = (x+y+z)/2 = 3k +/- 1 and A = sqrt((3*k +/- 1)*k*k*(k +/- 1)) = k*sqrt(3*k^2 +/- 4*k + 1). To determine when this is an integer, set 3*k^2 +/- 4*k + 1 = d^2. If we multiply both sides by 3, it is easier to complete the square: (3*k +/- 2)^2 - 1 = 3*d^2. Now we are looking for solutions to the Pell equation c^2 - 3*d^2 = 1 with c = 3*k +/- 2, for which there are infinitely many solutions: use the upper principal convergents of the continued fraction expansion of sqrt(3) (A001075/A001353). - Danny Rorabaugh, Oct 16 2015

			a(2) = 120 because 120 is the area of a triangle with side lengths of 16, 17 and 17.

Danny Rorabaugh, Table of n, a(n) for n = 1..875
Steven Dutch, Almost 30-60 Triples
Project Euler, Problem 94: Almost equilateral triangles
Eric Weisstein's World of Mathematics, Heronian Triangle and Pell Equation

For the continued fraction expansion of sqrt(3), cf. A002530, A002531, A040001.

(2/3) [ A007655(n+2) - (-1)^n*A001353(n+1) ] (conjectured). - Ralf Stephan, May 17 2007
Empirical g.f.: 12*x / ((x^2-14*x+1)*(x^2+4*x+1)). - Colin Barker, Apr 10 2013
a(n) = A001353(n+1)*A195499(n) = A001353(n+1)*A120892(n+1) - Danny Rorabaugh, Oct 16 2015

More terms from Zak Seidov, Feb 23 2005

More terms from Dan Sanders (dan(AT)ified.ca), Oct 22 2005

A109437 a(-1) = a(0) = 0, a(1) = 1; a(n) = 5a(n-1) - 5a(n-2) + a(n-3) + 2*(-1)^(n+1), alternatively a(n) = 3a(n-1) + 3a(n-2) - a(n-3).

Original entry on oeis.org

0, 1, 3, 12, 44, 165, 615, 2296, 8568, 31977, 119339, 445380, 1662180, 6203341, 23151183, 86401392, 322454384, 1203416145, 4491210195, 16761424636, 62554488348, 233456528757, 871271626679, 3251629977960, 12135248285160, 45289363162681, 169022204365563, 630799454299572

Offset: 0

Creighton Dement, Jun 28 2005

See A105968 for a similar sequence. Observe the four periodic sequences (1,1,1,1,); (-1,-1,-1,-1); (1,-1,1,-1,); (-1,1,-1,1,); (a(n)) is the (Type 1A) jbasejfor-transform of the periodic sequence (1,1,1,1) with respect to the floretion given in the program code. A109438 is the (Type 1A) jbasejfor-transform of the periodic sequence (-1,-1,-1,-1) with respect to the floretion given in the program code. A001834 is the (Type 1A) jbasejfor-transform of the periodic sequence (1,-1,1,-1) with respect to the floretion given in the program code. A102871 is the (Type 1A) jbasejfor-transform of the periodic sequence (-1,1,-1,1) with respect to the floretion given in the program code.

Floretion Algebra Multiplication Program, FAMP Code: (-1)^(n+1)jbasejfor[ + .5'ii' + .5'kk' + .5'ij' + .5'ji' + .5'jk' + .5'kj'] 1vesfor = (1,1,1,1,)

R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., Vol. 58, No. 2 (2020), 140-142.
Paul Barry, Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays, JIS 12 (2009) 09.8.6
Charles H. Jepsen, Packing a box with bricks, Math. Mag. 64 (2) (1991) 92-97. b(n) there is 0, 4, 12, 48,... = 4*a(n) here.
Index entries for linear recurrences with constant coefficients, signature (3,3,-1).

Cf. A001353, A001834, A002530, A011916, A102871, A105968, A109438.

with(numtheory):a := cfrac (tan(Pi/3),60): > b := cfrac (tan(Pi/6),60): > seq(nthnumer (b,i)*nthdenom (a,i), i=0..24 ); # Zerinvary Lajos, Feb 08 2007

LinearRecurrence[{3,3,-1},{0,1,3},40] (* Harvey P. Dale, Apr 21 2018 *)

{a(n) = local(s=1); if( n<0, n = -1 - n; s=-1); s * polcoeff( x / ((x + 1) * (x^2 -4*x + 1)) + x * O(x^n), n)} /* Michael Somos, Jul 27 2012 */

G.f.: x/((x+1)*(x^2-4*x+1)).
a(n) = A002530(n)*A002530(n+1). - Zerinvary Lajos, Feb 08 2007
a(-1 - n) = -a(n). a(2*n) = A011916(n). a(2*n + 1) = -A011916(-1 -n). - Michael Somos, Jul 27 2012
6*a(n) = A001353(n)+A001353(n+1)-(-1)^n. - R. J. Mathar, Sep 07 2016
a(n) = ((1 + sqrt(3))*(2 + sqrt(3))^n + (1 - sqrt(3))*(2 - sqrt(3))^n - 2*(-1)^n)/12. - Stefano Spezia, Sep 19 2023
a(n)+a(n+1) = A001353(n+1). - R. J. Mathar, Aug 31 2025

A041023 Denominators of continued fraction convergents to sqrt(15).

Original entry on oeis.org

1, 1, 7, 8, 55, 63, 433, 496, 3409, 3905, 26839, 30744, 211303, 242047, 1663585, 1905632, 13097377, 15003009, 103115431, 118118440, 811826071, 929944511, 6391493137, 7321437648, 50320119025

Offset: 0

N. J. A. Sloane

The following remarks assume an offset of 1. This is the sequence of Lehmer numbers U_n(sqrt(R),Q) for the parameters R = 6 and Q = -1; it is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for all positive integers n and m. Consequently, this is a divisibility sequence: if n divides m then a(n) divides a(m). - Peter Bala, May 28 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Eric W. Weisstein, MathWorld: Lehmer Number
Index entries for linear recurrences with constant coefficients, signature (0,8,0,-1).

Cf. A010472, A041022, A002530.

Denominator[NestList[(6/(6+#))&,0,60]] (* Vladimir Joseph Stephan Orlovsky, Apr 13 2010 *)
a0[n_] := (-((-5+Sqrt[15])*(4+Sqrt[15])^n)+(4-Sqrt[15])^n*(5+Sqrt[15]))/10 // Simplify
a1[n_] := (-(4-Sqrt[15])^n+(4+Sqrt[15])^n)/(2*Sqrt[15]) // Simplify
Flatten[MapIndexed[{a0[#], a1[#]} &,Range[20]]] (* Gerry Martens, Jul 11 2015 *)
Convergents[Sqrt[15],30]//Denominator (* Harvey P. Dale, Aug 13 2016 *)

G.f.: (1+x-x^2)/(1-8*x^2+x^4). - Colin Barker, Jan 01 2012
From Peter Bala, May 28 2014: (Start)
The following remarks assume an offset of 1.
Let alpha = ( sqrt(6) + sqrt(10) )/2 and beta = ( sqrt(6) - sqrt(10) )/2 be the roots of the equation x^2 - sqrt(6)*x - 1 = 0. Then a(n) = (alpha^n - beta^n)/(alpha - beta) for n odd, while a(n) = (alpha^n - beta^n)/(alpha^2 - beta^2) for n even.
a(n) = product {k = 1..floor((n-1)/2)} ( 6 + 4*cos^2(k*Pi/n) ).
Recurrence equations: a(0) = 0, a(1) = 1 and for n >= 1, a(2*n) = a(2*n - 1) + a(2*n - 2) and a(2*n + 1) = 6*a(2*n) + a(2*n - 1). (End)
From Gerry Martens, Jul 11 2015: (Start)
Interspersion of 2 sequences [a0(n),a1(n)] for n>0:
a0(n) = (-((-5+sqrt(15))*(4+sqrt(15))^n)+(4-sqrt(15))^n*(5+sqrt(15)))/10.
a1(n) = (-(4-sqrt(15))^n+(4+sqrt(15))^n)/(2*sqrt(15)). (End)

cp's OEIS Frontend

A079935 a(n) = 4*a(n-1) - a(n-2) with a(1) = 1, a(2) = 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A134451 Ternary digital root of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A080599 Expansion of e.g.f.: 2/(2-2*x-x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A048788 a(2n+1) = a(2n) + a(2n-1), a(2n) = 2*a(2n-1) + a(2n-2); a(n) = n for n = 0, 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Sage

Formula

Extensions

A152063 Triangle read by rows. Coefficients of the Fibonacci product polynomials F(n) = Product_{k=1..(n - 1)/2} (1 + 4*cos^2(k*Pi/n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A189006 Array A(m,n) read by antidiagonals: number of domino tilings of the m X n grid with upper left corner removed iff m*n is odd, (m>=0, n>=0).

A152063 Triangle read by rows. Coefficients of the Fibonacci product polynomials F(n) = Product_{k=1..(n - 1)/2} (1 + 4cos^2(kPi/n)).