A002530 a(n) = 4*a(n-2) - a(n-4) for n > 1, a(n) = n for n = 0, 1.

0, 1, 1, 3, 4, 11, 15, 41, 56, 153, 209, 571, 780, 2131, 2911, 7953, 10864, 29681, 40545, 110771, 151316, 413403, 564719, 1542841, 2107560, 5757961, 7865521, 21489003, 29354524, 80198051, 109552575, 299303201, 408855776, 1117014753, 1525870529, 4168755811

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• frac
• core
• nice

Comments

Denominators of continued fraction convergents to sqrt(3), for n >= 1.

Also denominators of continued fraction convergents to sqrt(3) - 1. See A048788 for numerators. - N. J. A. Sloane, Dec 17 2007. Convergents are 1, 2/3, 3/4, 8/11, 11/15, 30/41, 41/56, 112/153, ...

Consider the mapping f(a/b) = (a + 3*b)/(a + b). Taking a = b = 1 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the following sequence 1/1, 2/1, 5/3, 7/4, 19/11, ... converging to 3^(1/2). Sequence contains the denominators. 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

Sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571), ...; the sum of the first 6 terms of this series = 1.7320490367..., while sqrt(3) = 1.7320508075... - Gary W. Adamson, Dec 15 2007

From Clark Kimberling, Aug 27 2008: (Start)

Related convergents (numerator/denominator):

lower principal convergents: A001834/A001835

upper principal convergents: A001075/A001353

intermediate convergents: A005320/A001075

principal and intermediate convergents: A143642/A140827

lower principal and intermediate convergents: A143643/A005246. (End)

Row sums of triangle A152063 = (1, 3, 4, 11, ...). - Gary W. Adamson, Nov 26 2008

From Alois P. Heinz, Apr 13 2011: (Start)

Also number of domino tilings of the 3 X (n-1) rectangle with upper left corner removed iff n is even. For n=4 the 4 domino tilings of the 3 X 3 rectangle with upper left corner removed are:

. ._. . ._. . ._. . ._.

.|__| .|__| .| | | .|___|

| |_| | | | | | ||| |_| |

||__| |||_| ||__| |_|_| (End)

This is the sequence of Lehmer numbers u_n(sqrt(R),Q) with the parameters R = 2 and Q = -1. It is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for all natural numbers n and m. - Peter Bala, Apr 18 2014

2^(-floor(n/2))*(1 + sqrt(3))^n = A002531(n) + a(n)*sqrt(3); integers in the real quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 11 2018

Let T(n) = 2^(n mod 2), U(n) = a(n), V(n) = A002531(n), x(n) = V(n)/U(n). Then T(n*m) * U(n+m) = U(n)*V(m) + U(m)*V(n), T(n*m) * V(n+m) = 3*U(n)*U(m) + V(m)*V(n), x(n+m) = (3 + x(n)*x(m))/(x(n) + x(m)). - Michael Somos, Nov 29 2022

Examples

			Convergents to sqrt(3) are: 1, 2, 5/3, 7/4, 19/11, 26/15, 71/41, 97/56, 265/153, 362/209, 989/571, 1351/780, 3691/2131, ... = A002531/A002530 for n >= 1.
1 + 1/(1 + 1/(2 + 1/(1 + 1/2))) = 19/11 so a(5) = 11.
G.f. = x + x^2 + 3*x^3 + 4*x^4 + 11*x^5 + 15*x^6 + 41*x^7 + ... - _Michael Somos_, Mar 18 2022
		

References

• Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
• Russell Lyons, A bird's-eye view of uniform spanning trees and forests, in Microsurveys in Discrete Probability, AMS, 1998.
• I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 181.
• Murat Sahin and Elif Tan, Conditional (strong) divisibility sequences, Fib. Q., 56 (No. 1, 2018), 18-31.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• A. Tarn, Approximations to certain square roots and the series of numbers connected therewith, Mathematical Questions and Solutions from the Educational Times, 1 (1916), 8-12.

Links

• Harry J. Smith, Table of n, a(n) for n = 0..2000
• Peter Bala, Notes on 2-periodic continued fractions and Lehmer sequences
• Paul Barry, Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays, JIS 12 (2009) 09.8.6.
• Mario Catalani, Sequences related to convergents to square root of rationals, arXiv:math/0305270 [math.NT], 2003.
• Marcia Edson, Scott Lewis and Omer Yayenie, The k-periodic Fibonacci sequence and an extended Binet's formula, INTEGERS 11 (2011) #A32.
• Aviezri S. Fraenkel, Jonathan Levitt, and Michael Shimshoni, Characterization of the set of values f(n)=[n alpha], n=1,2,..., Discrete Math. 2 (1972), no.4, 335-345.
• Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122-126.
• Clark Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.
• MacTutor, D'Arcy Thompson on Greek irrationals
• 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
• Albert Tarn, Approximations to certain square roots and the series of numbers connected therewith [Annotated scanned copy]
• D'Arcy Thompson, Excess and Defect: Or the Little More and the Little Less, Mind, New Series, Vol. 38, No. 149 (Jan., 1929), pp. 43-55 (13 pages). See page 48.
• Hein van Winkel, Q-quadrangles inscribed in a circle, 2014. See Table 1. [Reference from Antreas Hatzipolakis, Jul 14 2014]
• Russell Walsmith, CL-Chemy Transforms Fibonacci-Type Sequences to Arrays
• E. W. Weisstein, MathWorld: Lehmer Number
• Index entries for "core" sequences
• Index entries for two-way infinite sequences
• Index entries for linear recurrences with constant coefficients, signature (0,4,0,-1).
• Index entries for sequences related to Chebyshev polynomials.

Crossrefs

Cf. A002531 (numerators of convergents to sqrt(3)), A048788, A003297.

Bisections: A001353 and A001835.

Cf. A152063.

Cf. A108412, A049310.

Analog for sqrt(m): A000129 (m=2), A001076 (m=5), A041007 (m=6), A041009 (m=7), A041011 (m=8), A005668 (m=10), A041015 (m=11), A041017 (m=12), ..., A042935 (m=999), A042937 (m=1000).

Programs

Magma

I:=[0,1,1,3]; [n le 4 select I[n] else 4*Self(n-2) - Self(n-4): n in [1..50]]; // G. C. Greubel, Feb 25 2019

Maple

a := proc(n) option remember; if n=0 then 0 elif n=1 then 1 elif n=2 then 1 elif n=3 then 3 else 4*a(n-2)-a(n-4) fi end; [ seq(a(i),i=0..50) ];
A002530:=-(-1-z+z**2)/(1-4*z**2+z**4); # conjectured (correctly) by Simon Plouffe in his 1992 dissertation

Mathematica

Join[{0},Table[Denominator[FromContinuedFraction[ContinuedFraction[Sqrt[3],n]]], {n,1,50}]] (* Stefan Steinerberger, Apr 01 2006 *)
Join[{0},Denominator[Convergents[Sqrt[3],50]]] (* or *) LinearRecurrence[ {0,4,0,-1},{0,1,1,3},50] (* Harvey P. Dale, Jan 29 2013 *)
a[ n_] := If[n<0, -(-1)^n, 1] SeriesCoefficient[ x*(1+x-x^2)/(1-4*x^2+x^4), {x, 0, Abs@n}]; (* Michael Somos, Apr 18 2019 *)
a[ n_] := ChebyshevU[n-1, Sqrt[-1/2]]*Sqrt[2]^(Mod[n, 2]-1)/I^(n-1) //Simplify; (* Michael Somos, Nov 29 2022 *)

PARI

{a(n) = if( n<0, -(-1)^n * a(-n), contfracpnqn(vector(n, i, 1 + (i>1) * (i%2)))[2, 1])}; /* Michael Somos, Jun 05 2003 */

PARI

{ for (n=0, 50, a=contfracpnqn(vector(n, i, 1+(i>1)*(i%2)))[2, 1]; write("b002530.txt", n, " ", a); ); } \\ Harry J. Smith, Jun 01 2009

PARI

my(w=quadgen(12)); A002530(n)=real((2+w)^(n\/2)*if(bittest(n,0),1-w/3,w/3));
apply(A002530, [0..30]) \\ M. F. Hasler, Nov 04 2019

Python

from functools import cache
@cache
def a(n): return [0, 1, 1, 3][n] if n < 4 else 4*a(n-2) - a(n-4)
print([a(n) for n in range(36)]) # Michael S. Branicky, Nov 13 2022

Sage

(x*(1+x-x^2)/(1-4*x^2+x^4)).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, Feb 25 2019

Formula

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

a(n) = 4*a(n-2) - a(n-4). [Corrected by László Szalay, Feb 21 2014]

a(n) = -(-1)^n * a(-n) for all n in Z, would satisfy the same recurrence relation. - Michael Somos, Jun 05 2003

a(2*n) = a(2*n-1) + a(2*n-2), a(2*n+1) = 2*a(2*n) + a(2*n-1).

From Benoit Cloitre, Dec 15 2002: (Start)

a(2*n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(2*sqrt(3)).

a(2*n) = A001353(n).

a(2*n-1) = ceiling((1 + 1/sqrt(3))/2*(2 + sqrt(3))^n) = ((3 + sqrt(3))^(2*n - 1) + (3 - sqrt(3))^(2*n - 1))/6^n.

a(2*n-1) = A001835(n). (End)

a(n+1) = Sum_{k=0..floor(n/2)} binomial(n - k, k) * 2^floor((n - 2*k)/2). - Paul Barry, Jul 13 2004

a(n) = Sum_{k=0..floor(n/2)} binomial(floor(n/2) + k, floor((n - 1)/2 - k))*2^k. - Paul Barry, Jun 22 2005

G.f.: (sqrt(6) + sqrt(3))/12*Q(0), where Q(k) = 1 - a/(1 + 1/(b^(2*k) - 1 - b^(2*k)/(c + 2*a*x/(2*x - g*m^(2*k)/(1 + a/(1 - 1/(b^(2*k + 1) + 1 - b^(2*k + 1)/(h - 2*a*x/(2*x + g*m^(2*k + 1)/Q(k + 1)))))))))). - Sergei N. Gladkovskii, Jun 21 2012

a(n) = (alpha^n - beta^n)/(alpha - beta) for n odd, and a(n) = (alpha^n - beta^n)/(alpha^2 - beta^2) for n even, where alpha = 1/2*(sqrt(2) + sqrt(6)) and beta = (1/2)*(sqrt(2) - sqrt(6)). Cf. A108412. - Peter Bala, Apr 18 2014

a(n) = (-sqrt(2)*i)^n*S(n, sqrt(2)*i)*2^(-floor(n/2)) = A002605(n)*2^(-floor(n/2)), n >= 0, with i = sqrt(-1) and S the Chebyshev polynomials (A049310). - Wolfdieter Lang, Feb 10 2018

a(n+1)*a(n+2) - a(n+3)*a(n) = (-1)^n, n >= 0. - Kai Wang, Feb 06 2020

E.g.f.: sinh(sqrt(3/2)*x)*(sinh(x/sqrt(2)) + sqrt(2)*cosh(x/sqrt(2)))/sqrt(3). - Stefano Spezia, Feb 07 2020

a(n) = ((1 + sqrt(3))^n - (1 - sqrt(3))^n)/(2*2^floor(n/2))/sqrt(3) = A002605(n)/2^floor(n/2). - Robert FERREOL, Apr 13 2023

Extensions

Definition edited by M. F. Hasler, Nov 04 2019