|
|
A001333
|
|
Numerators of continued fraction convergents to sqrt(2).
(Formerly M2665 N1064)
|
|
354
|
|
|
1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, 47321, 114243, 275807, 665857, 1607521, 3880899, 9369319, 22619537, 54608393, 131836323, 318281039, 768398401, 1855077841, 4478554083, 10812186007, 26102926097, 63018038201, 152139002499, 367296043199
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Number of n-step non-selfintersecting paths starting at (0,0) with steps of types (1,0), (-1,0) or (0,1) [Stanley].
Number of n steps one-sided prudent walks with east, west and north steps. - Shanzhen Gao, Apr 26 2011
Number of ternary strings of length n-1 with subwords (0,2) and (2,0) not allowed. - Olivier Gérard, Aug 28 2012
Number of symmetric 2n X 2 or (2n-1) X 2 crossword puzzle grids: all white squares are edge connected; at least 1 white square on every edge of grid; 180-degree rotational symmetry. - Erich Friedman
a(n+1) is the number of ways to put molecules on a 2 X n ladder lattice so that the molecules do not touch each other.
In other words, a(n+1) is the number of independent vertex sets and vertex covers in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, Apr 04 2017
Number of (n-1) X 2 binary arrays with a path of adjacent 1's from top row to bottom row, see A359576. - R. H. Hardin, Mar 16 2002
a(2*n+1) with b(2*n+1) := A000129(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = -1.
a(2*n) with b(2*n) := A000129(2*n), n >= 1, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = +1 (see Emerson reference).
Bisection: a(2*n) = T(n,3) = A001541(n), n >= 0 and a(2*n+1) = S(2*n,2*sqrt(2)) = A002315(n), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. See A053120, resp. A049310.
For n > 0, the number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 2, s(n) = 2. - Herbert Kociemba, Jun 02 2004
For n > 1, a(n) corresponds to the longer side of a near right-angled isosceles triangle, one of the equal sides being A000129(n). - Lekraj Beedassy, Aug 06 2004
Exponents of terms in the series F(x,1), where F is determined by the equation F(x,y) = xy + F(x^2*y,x). - Jonathan Sondow, Dec 18 2004
Number of n-words from the alphabet A={0,1,2} which two neighbors differ by at most 1. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Aug 30 2006
Consider the mapping f(a/b) = (a + 2b)/(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, 3/2, 7/5, 17/12, 41/29, ... converging to 2^(1/2). Sequence contains the numerators. - Amarnath Murthy, Mar 22 2003 [Amended by Paul E. Black (paul.black(AT)nist.gov), Dec 18 2006]
The intermediate convergents to 2^(1/2) begin with 4/3, 10/7, 24/17, 58/41; essentially, numerators=A052542 and denominators here. - Clark Kimberling, Aug 26 2008
Equals right border of triangle A143966. Starting (1, 3, 7, ...) equals INVERT transform of (1, 2, 2, 2, ...) and row sums of triangle A143966. - Gary W. Adamson, Sep 06 2008
Inverse binomial transform of A006012; Hankel transform is := [1, 2, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
In general, denominators, a(k,n) and numerators, b(k,n), of continued fraction convergents to sqrt((k+1)/k) may be found as follows:
let a(k,0) = 1, a(k,1) = 2k; for n>0, a(k,2n) = 2*a(k,2n-1) + a(k,2n-2) and a(k,2n+1) = (2k)*a(k,2n) + a(k,2n-1);
let b(k,0) = 1, b(k,1) = 2k+1; for n>0, b(k,2n) = 2*b(k,2n-1) + b(k,2n-2) and b(k,2n+1) = (2k)*b(k,2n) + b(k,2n-1).
For example, the convergents to sqrt(2/1) start 1/1, 3/2, 7/5, 17/12, 41/29.
In general, if a(k,n) and b(k,n) are the denominators and numerators, respectively, of continued fraction convergents to sqrt((k+1)/k) as defined above, then
k*a(k,2n)^2 - a(k,2n-1)*a(k,2n+1) = k = k*a(k,2n-2)*a(k,2n) - a(k,2n-1)^2 and
b(k,2n-1)*b(k,2n+1) - k*b(k,2n)^2 = k+1 = b(k,2n-1)^2 - k*b(k,2n-2)*b(k,2n);
for example, if k=1 and n=3, then b(1,n)=a(n+1) and
1*a(1,6)^2 - a(1,5)*a(1,7) = 1*169^2 - 70*408 = 1;
1*a(1,4)*a(1,6) - a(1,5)^2 = 1*29*169 - 70^2 = 1;
b(1,5)*b(1,7) - 1*b(1,6)^2 = 99*577 - 1*239^2 = 2;
b(1,5)^2 - 1*b(1,4)*b(1,6) = 99^2 - 1*41*239 = 2.
(End)
This sequence occurs in the lower bound of the order of the set of equivalent resistances of n equal resistors combined in series and in parallel (A048211). - Sameen Ahmed Khan, Jun 28 2010
Let M = a triangle with the Fibonacci series in each column, but the leftmost column is shifted upwards one row. A001333 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 27 2010
a(n) is the number of compositions of n when there are 1 type of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
Let U be the unit-primitive matrix (see [Jeffery])
U = U_(8,2) = (0 0 1 0)
(0 1 0 1)
(1 0 2 0)
(0 2 0 1).
(End)
For n >= 1, row sums of triangle
m/k.|..0.....1.....2.....3.....4.....5.....6.....7
==================================================
.0..|..1
.1..|..1.....2
.2..|..1.....2.....4
.3..|..1.....4.....4.....8
.4..|..1.....4....12.....8....16
.5..|..1.....6....12....32....16....32
.6..|..1.....6....24....32....80....32....64
.7..|..1.....8....24....80....80...192....64...128
which is the triangle for numbers 2^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012
a(n) is also the number of ways to place k non-attacking wazirs on a 2 X n board, summed over all k >= 0 (a wazir is a leaper [0,1]). - Vaclav Kotesovec, May 08 2012
The sequences a(n) and b(n) := A000129(n) are entries of powers of the special case of the Brahmagupta Matrix - for details see Suryanarayan's paper. Further, as Suryanarayan remark, if we set A = 2*(a(n) + b(n))*b(n), B = a(n)*(a(n) + 2*b(n)), C = a(n)^2 + 2*a(n)*b(n) + 2*b(n)^2 we obtain integral solutions of the Pythagorean relation A^2 + B^2 = C^2, where A and B are consecutive integers. - Roman Witula, Jul 28 2012
Pisano period lengths: 1, 1, 8, 4, 12, 8, 6, 4, 24, 12, 24, 8, 28, 6, 24, 8, 16, 24, 40, 12, .... - R. J. Mathar, Aug 10 2012
This sequence and A000129 give the diagonal numbers described by Theon of Smyrna. - Sture Sjöstedt, Oct 20 2012
a(n) is the top left entry of the n-th power of any of the following six 3 X 3 binary matrices: [1, 1, 1; 1, 1, 1; 1, 0, 0] or [1, 1, 1; 1, 1, 0; 1, 1, 0] or [1, 1, 1; 1, 0, 1; 1, 1, 0] or [1, 1, 1; 1, 1, 0; 1, 0, 1] or [1, 1, 1; 1, 0, 1; 1, 0, 1] or [1, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
For n > 0, a(n+1) is the length of tau^n(1) where tau is the morphism: 1 -> 101, 0 -> 1. See Song and Wu. - Michel Marcus, Jul 21 2020
For n > 0, a(n) is the number of nonisomorphic quasitrivial semigroups with n elements, see Devillet, Marichal, Teheux. A292932 is the number of labeled quasitrivial semigroups. - Peter Jipsen, Mar 28 2021
For n >= 2, 4*a(n) is the number of ways to tile this T-shaped figure of length n-1 with two colors of squares and one color of domino; shown here is the figure of length 5 (corresponding to n=6), and it has 4*a(6) = 396 different tilings.
._
|_|_ _ _ _
|_|_|_|_|_|
|_|
(End)
12*a(n) = number of walks of length n in the cyclic Kautz digraph CK(3,4). - Miquel A. Fiol, Feb 15 2024
|
|
REFERENCES
|
A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.
John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.
J. Devillet, J.‐L. Marichal, and B. Teheux, Classifications of quasitrivial semigroups, Semigroup Forum, 100 (2020), 743-764.
Maribel Díaz Noguera [Maribel Del Carmen Díaz Noguera], Rigoberto Flores, Jose L. Ramirez, and Martha Romero Rojas, Catalan identities for generalized Fibonacci polynomials, Fib. Q., 62:2 (2024), 100-111.
Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
R. P. Grimaldi, Ternary strings with no consecutive 0's and no consecutive 1's, Congressus Numerantium, 205 (2011), 129-149.
A. F. Horadam, R. P. Loh and A. G. Shannon, Divisibility properties of some Fibonacci-type sequences, pp. 55-64 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.
Thomas Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, New York, 2014.
Kin Y. Li, Math Problem Book I, 2001, p. 24, Problem 159.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 102, Problem 10.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.
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).
R. P. Stanley, Enumerative Combinatorics, Volume 1 (1986), p. 203, Example 4.1.2.
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.
R. C. Tilley et al., The cell growth problem for filaments, Proc. Louisiana Conf. Combinatorics, ed. R. C. Mullin et al., Baton Rouge, 1970, 310-339.
|
|
LINKS
|
F. Harary and R. W. Robinson, Tapeworms, Unpublished manuscript, circa 1973. (Annotated scanned copy)
Claude Soudieux, De l'infini arithmétique, Zurich, 1960. [Annotated scans of selected pages. Contains many sequences including A1333]
|
|
FORMULA
|
a(n) = 2a(n-1) + a(n-2);
a(n) = ((1-sqrt(2))^n + (1+sqrt(2))^n)/2.
G.f.: (1 - x) / (1 - 2*x - x^2) = 1 / (1 - x / (1 - 2*x / (1 + x))). - Simon Plouffe in his 1992 dissertation.
a(n) = (-i)^n * T(n, i), with T(n, x) Chebyshev's polynomials of the first kind A053120 and i^2 = -1.
a(n) = a(n-1) + A052542(n-1), n>1. a(n)/A052542(n) converges to sqrt(1/2). - Mario Catalani (mario.catalani(AT)unito.it), Apr 29 2003
E.g.f.: exp(x)cosh(x*sqrt(2)). - Paul Barry, May 08 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)2^k. - Paul Barry, May 13 2003
For n > 0, a(n)^2 - (1 + (-1)^(n))/2 = Sum_{k=0..n-1} ((2k+1)*A001653(n-1-k)); e.g., 17^2 - 1 = 288 = 1*169 + 3*29 + 5*5 + 7*1; 7^2 = 49 = 1*29 + 3*5 + 5*1. - Charlie Marion, Jul 18 2003
For another recurrence see A000129.
a(n) = upper left and lower right terms of [1,1; 2,1]^n. - Gary W. Adamson, Mar 12 2008
If p[1]=1, and p[i]=2, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, Apr 29 2010
For n>=2, a(n)=F_n(2)+F_(n+1)(2), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i)x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012
Dirichlet g.f.: (PolyLog(s,1-sqrt(2)) + PolyLog(s,1+sqrt(2)))/2. - Ilya Gutkovskiy, Jun 26 2016
a(n) = round((1/2)*sqrt(Product_{k=1..n} 4*(1 + sin(k*Pi/n)^2))), for n>=1. - Greg Dresden, Dec 28 2021
Sum_{n>=1} 1/a(n) = 1.5766479516393275911191017828913332473... - R. J. Mathar, Feb 05 2024
|
|
EXAMPLE
|
Convergents are 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, 8119/5741, 19601/13860, 47321/33461, 114243/80782, ... = A001333/A000129.
The 15 3 X 2 crossword grids, with white squares represented by an o:
ooo ooo ooo ooo ooo ooo ooo oo. o.o .oo o.. .o. ..o oo. .oo
ooo oo. o.o .oo o.. .o. ..o ooo ooo ooo ooo ooo ooo .oo oo.
G.f. = 1 + x + 3*x^2 + 7*x^3 + 17*x^4 + 41*x^5 + 99*x^6 + 239*x^7 + 577*x^8 + ...
|
|
MAPLE
|
A001333 := proc(n) option remember; if n=0 then 1 elif n=1 then 1 else 2*procname(n-1)+procname(n-2) fi end;
Digits := 50; A001333 := n-> round((1/2)*(1+sqrt(2))^n);
with(numtheory): cf := cfrac (sqrt(2), 1000): [seq(nthnumer(cf, i), i=0..50)];
a:= n-> (M-> M[2, 1]+M[2, 2])(<<2|1>, <1|0>>^n):
A001333List := proc(m) local A, P, n; A := [1, 1]; P := [1, 1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(A), P[-2]]);
A := [op(A), P[-1]] od; A end: A001333List(32); # Peter Luschny, Mar 26 2022
|
|
MATHEMATICA
|
Insert[Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[2], n]]], {n, 1, 40}], 1, 1] (* Stefan Steinerberger, Apr 08 2006 *)
Table[((1 - Sqrt[2])^n + (1 + Sqrt[2])^n)/2, {n, 0, 29}] // Simplify (* Robert G. Wilson v, May 02 2006 *)
a[0] = 1; a[1] = 1; a[n_] := a[n] = 2a[n - 1] + a[n - 2]; Table[a@n, {n, 0, 29}] (* Robert G. Wilson v, May 02 2006 *)
Table[ MatrixPower[{{1, 2}, {1, 1}}, n][[1, 1]], {n, 0, 30}] (* Robert G. Wilson v, May 02 2006 *)
Join[{1}, Numerator[Convergents[Sqrt[2], 30]]] (* Harvey P. Dale, Aug 22 2011 *)
CoefficientList[Series[(-1 + x)/(-1 + 2 x + x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
Table[Sqrt[(ChebyshevT[n, 3] + (-1)^n)/2], {n, 0, 20}] (* Eric W. Weisstein, Apr 17 2018 *)
|
|
PROG
|
(PARI) {a(n) = if( n<0, (-1)^n, 1) * contfracpnqn( vector( abs(n), i, 1 + (i>1))) [1, 1]}; /* Michael Somos, Sep 02 2012 */
(PARI) {a(n) = polchebyshev(n, 1, I) / I^n}; /* Michael Somos, Sep 02 2012 */
(PARI) a(n) = real((1 + quadgen(8))^n); \\ Michel Marcus, Mar 16 2021
(PARI) { default(realprecision, 2000); for (n=0, 4000, a=contfracpnqn(vector(n, i, 1+(i>1)))[1, 1]; if (a > 10^(10^3 - 6), break); write("b001333.txt", n, " ", a); ); } \\ Harry J. Smith, Jun 12 2009
(Sage) from sage.combinat.sloane_functions import recur_gen2
it = recur_gen2(1, 1, 2, 1)
(Sage) [lucas_number2(n, 2, -1)/2 for n in range(0, 30)] # Zerinvary Lajos, Apr 30 2009
(Haskell)
a001333 n = a001333_list !! n
a001333_list = 1 : 1 : zipWith (+)
a001333_list (map (* 2) $ tail a001333_list)
(Magma) [n le 2 select 1 else 2*Self(n-1)+Self(n-2): n in [1..35]]; // Vincenzo Librandi, Nov 10 2018
(Python)
from functools import cache
@cache
def a(n): return 1 if n < 2 else 2*a(n-1) + a(n-2)
|
|
CROSSREFS
|
See A040000 for the continued fraction expansion of sqrt(2).
See also A078057 which is the same sequence without the initial 1.
Row sums of unsigned Chebyshev T-triangle A053120. a(n)= A054458(n, 0) (first column of convolution triangle).
The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.
Second row of the array in A135597.
Cf. Triangle A106513 (alternating row sums).
|
|
KEYWORD
|
nonn,cofr,easy,core,nice,frac
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|