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

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,4

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

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.

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

Example

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

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

Prog

(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) { default(realprecision, 2000); 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) apply( {A002530(n, w=quadgen(12))=real((2+w)^(n\/2)*if(bittest(n, 0), 1-w/3, w/3))}, [0..30]) \\ M. F. Hasler, Nov 04 2019
(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
(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
(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

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

Sequence in context: A085368 A041405 A042483 * A042709 A231067 A042327

Adjacent sequences: A002527 A002528 A002529 * A002531 A002532 A002533

Keyword

nonn,easy,frac,core,nice

Author

N. J. A. Sloane

Extensions

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

Status

approved