|
| |
|
|
A001333
|
|
Numerators of continued fraction convergents to sqrt(2).
(Formerly M2665 N1064)
|
|
261
|
|
|
|
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
(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.
Number of (n-1) X 2 binary arrays with a path of adjacent 1's from top row to bottom row. - 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.
Binomial transform of A077957. - Paul Barry, Feb 25 2003
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 (amarnath_murthy(AT)yahoo.com), Mar 22 2003 [Amended by Paul E. Black (paul.black(AT)nist.gov), Dec 18 2006]
a(n) mod 10 = A131707. See A131711. - Paul Curtz, Apr 08 2008
Prime numerators with an odd index are prime RMS numbers(A140480) and also NSW primes(A088165). [From Ctibor O. Zizka, Aug 13 2008]
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. [From Gary W. Adamson, Sep 06 2008]
Inverse binomial transform of A006012 ; Hankel transform is := [1, 2, 0, 0, 0, 0, 0, 0, 0, ...] . [From Philippe DELEHAM, Dec 04 2008]
Contribution from Charlie Marion, Jan 07 2009: (Start)
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.
Cf. A000129, A142238-A142239, A153313-A153318.
(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 [From Sameen Ahmed KHAN (rohelakhan(AT)yahoo.com), 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->inf} M^n, the left-shifted vector considered as a sequence. [From 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. [From Milan Janjic, Aug 13 2010]
Equals the INVERTi transform of A055099. [From Gary W. Adamson, Aug 14 2010]
(Start) 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).
Then a(n)=(1/4)*Trace(U^n). (See also A084130, A006012.) - L. Edson Jeffery, April 4, 2011. (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 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]). [From Vaclav Kotesovec, May 8 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
A001333 and A000129 give the diagonal numbers described by Theon from Smyrna - Sture Sjöstedt, Oct 20 2012
|
|
|
REFERENCES
|
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
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.
E. I. Emerson, Recurrent sequences in the equation DQ^2=R^2+N, Fib. Quart., 7 (1969), 231-242, see Ex. 1, pp. 237-238.
Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.
S. Gao, H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks (submitted to INTEGERS: The Electronic Journal of Combinatorial Number Theory).
David Garth and Adam Gouge, Affinely Self-Generating Sets and Morphisms, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.5.
R. P. Grimaldi, Ternary strings ..., 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.
Y. Kong, Ligand binding on ladder lattices, Biophysical Chemistry, Vol. 81 (1999), pp. 7-21.
D. V. Kruchinin, Integer properties of a composition of exponential generating functions, arXiv preprint arXiv:1211.2100, 2012. - From N. J. A. Sloane, Jan 02 2013
Kuba, Markus; Panholzer, Alois. Enumeration formulae for pattern restricted Stirling permutations. Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From N. J. A. Sloane, Sep 25 2012
Kin Y. Li, Math Problem Book I, 2001, p. 24, Problem 159
J. V. Leyendekkers and A. G. Shannon, Pellian sequence relationships among pi, e, sqrt(2), Notes on Number Theory and Discrete Mathematics, Vol. 18, 2012, No. 2, 58-62; http://www.nntdm.net/papers/nntdm-18/NNTDM-18-2-58-62.pdf. See Table 2. - From N. J. A. Sloane, Dec 23 2012
Munarini, Emanuele, Combinatorial properties of the antichains of a garland. Integers, 9 (2009), 353-374.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 102, Problem 10.
H. Prodinger and R. F. Tichy, Fibonacci numbers of graphs, Fibonacci Quarterly, 20 (1982), 16-21.
B. S. Rao, Heptagonal numbers in the associated Pell sequence ..., Fib. Quarterly, 43 (2005), 302-306.
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.
E. R. Suryanarayan, The Brahmagupta Polynomials, Fibonacci Quarterly, 34.1 (1996), 30-39.
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.
Gy. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see Eq. (21)).
Gy. Tasi et al., Quantum algebraic-combinatoric study of the conformational properties of n-alkanes. II, J. Math. Chemistry, 27, 2000, 191-199 (see p. 193).
V. Thebault, Concerning two classes of remarkable perfect square pairs, Amer. Math. Monthly, 56 (1949), 443-448.
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
|
T. D. Noe, Table of n, a(n) for n = 0..500
Antoni Amengual, The intriguing properties of the equivalent resistances of n equal resistors combined in series and in parallel, American Journal of Physics, 68(2), (2000) 175-179. [From Sameen Ahmed KHAN (rohelakhan(AT)yahoo.com), Jun 28 2010]
Joerg Arndt, Fxtbook, pp.313-315
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
Fan Chung, Ron Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194
Nick Hobson, Python program for this sequence
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 143
L. E. Jeffery, Unit-primitive matrices)
Sameen Ahmed Khan, The bounds of the set of equivalent resistances of n equal resistors combined in series and in parallel, arXiv:1004.3346 [From Sameen Ahmed KHAN (rohelakhan(AT)yahoo.com), Jun 28 2010]
Tanya Khovanova, Recursive Sequences
Kin Y. Li, Problem 159
Dmitry Kruchinin, Integer properties of a composition of exponential generating functions, arXiv:1211.2100
_Simon Plouffe_, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Eric Weisstein's World of Mathematics, Square Root
Eric Weisstein's World of Mathematics, Pythagoras's Constant
Eric Weisstein's World of Mathematics, Square Triangular Number
Index entries for "core" sequences
Index entries for sequences related to Chebyshev polynomials.
Index entries for sequences related to linear recurrences with constant coefficients, signature (2,1)
|
|
|
FORMULA
|
a(n) = A055642(A125058(n)). - Reinhard Zumkeller, Feb 02 2007
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))). - Michael Somos, Sep 02 2012
A000129(2n) = 2*A000129(n)*a(n). - John McNamara, Oct 30, 2002
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), C(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
a(n+2) = A078343(n+1) + A048654(n). - Creighton Dement (creighton.k.dement(AT)uni-oldenburg.de), Jan 19 2005
Conjecture: For prime p, a(p) congruent to 1 mod p ( compare with similar comment for A000032 ) - Creighton Dement (creighton.k.dement(AT)uni-oldenburg.de), Oct 11 2005
a(n) = A000129(n)+A000129(n-1) = A001109(n)/A000129(n) = sqrt(A001110(n)/A000129(n)^2) = ceiling(sqrt(A001108(n))). - Henry Bottomley, Apr 18 2000
Also the first differences of A000129 (the Pell numbers) because A052937(n) = A000129(n+1)+1. - Graeme McRae, Aug 03 2006
a(n) = Sum_{k,0<=k<=n} A122542(n,k). - Philippe DELEHAM, Oct 08 2006
For another recurrence see A000129.
a(n) = Sum_{k, 0<=k<=n}A098158(n,k)*2^(n-k). - Philippe DELEHAM, Dec 26 2007
a(n) = upper left and lower right terms of [1,1; 2,1]^n. - Gary W. Adamson, Mar 12 2008
E.g.f.: exp(x)*cosh(x*sqrt(2)) = G(0)/2; G(k)=(-1)^k+1/(((3+sqrt(2))^k)-x*(1+sqrt(2))*((17+12*sqrt(2))^k)/(x*(1+sqrt(2))*((3+sqrt(2))^k)-(k+1)/G(k+1)) ; (continued fraction). - Sergei N. Gladkovskii, Dec 04 2011
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)}C(n-i-1,i)x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012
a(-n) = (-1)^n * a(n). - Michael Somos, Sep 02 2012
|
|
|
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.
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. [From Milan Janjic, Apr 29 2010]
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)];
A001333:=-(z+1)/(-1+2*z+z**2); [Simon Plouffe in his 1992 dissertation.]
a:= proc(n) local M; M := (Matrix([[2, 1], [1, 0]])^n); M[2, 1]+M[2, 2] end: seq (a(n), n=0..30); # Alois P. Heinz, Aug 01 2008
|
|
|
MATHEMATICA
|
Insert[Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[2], n]]], {n, 1, 40}], 1, 1] - Stefan Steinerberger, Apr 08 2006
f[n_] := ((1 - Sqrt[2])^n + (1 + Sqrt[2])^n)/2; Table[Simplify@ f@n, {n, 0, 29}] (* Or *)
a[0] = 1; a[1] = 1; a[n_] := a[n] = 2a[n - 1] + a[n - 2]; Table[a@n, {n, 0, 29}] (from Robert G. Wilson v, May 02 2006)
a=c=0; t={b=1}; Do[c=a+b+c; AppendTo[t, c]; a=b; b=c, {n, 40}]; t (* or *) LinearRecurrence[{2, 1}, {1, 1}, 40] [From Vladimir Joseph Stephan Orlovsky, Mar 23 2009]
Join[{1}, Numerator[Convergents[Sqrt[2], 30]]] (* From Harvey P. Dale, Aug 22 2011 *)
|
|
|
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 */
(Sage) from sage.combinat.sloane_functions import recur_gen2
it = recur_gen2(1, 1, 2, 1)
[it.next() for i in range(30)] ## Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 24 2008
(Sage) [lucas_number2(n, 2, -1)/2 for n in xrange(0, 30)]# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 30 2009]
(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); ); } [From Harry J. Smith, Jun 12 2009]
(Haskell)
a001333 n = a001333_list !! n
a001333_list = 1 : 1 : zipWith (+)
a001333_list (map (* 2) $ tail a001333_list)
-- Reinhard Zumkeller, Jul 08 2012
|
|
|
CROSSREFS
|
For denominators see A000129.
See A040000 for the continued fraction expansion of sqrt(2).
a(n)+a(n+1) = 2 A000129(n+1). 2*a(n) = A002203(n) (companion Pell numbers).
See also A078057 which is the same sequence without the initial 1.
Cf. also A152113.
Row sums of unsigned Chebyshev T-triangle A053120. a(n)= A054458(n, 0) (first column of convolution triangle).
Row sums of A140750, A160756, A135837.
Equals A034182(n-1) + 2 and A084128(n)/2^n. First differences of A052937. Partial sums of A052542. Pairwise sums of A048624. Bisection of A002965.
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.
A048211, A153588, A174283, A174284, A174285, A174286, A176499, A176500, A176501, A176502. [From Sameen Ahmed KHAN (rohelakhan(AT)yahoo.com), Jun 28 2010]
Cf. A055099 [From Gary W. Adamson, Aug 14 2010]
Cf. A028859, A001906 / A088305, A033303, A000225, A095263, A003945, A006356, A002478, A214260, A001911 and A000217 for other restricted ternary words - Olivier Gérard, Aug 28 2012
Sequence in context: A077851 A089737 * A123335 A078057 A089742 A187258
Adjacent sequences: A001330 A001331 A001332 * A001334 A001335 A001336
|
|
|
KEYWORD
|
nonn,cofr,easy,core,nice,frac
|
|
|
AUTHOR
|
N. J. A. Sloane, R. K. Guy
|
|
|
EXTENSIONS
|
Chebyshev comments from Wolfdieter Lang, Jan 10 2003
|
|
|
STATUS
|
approved
|
| |
|
|
