login
a(0) = 1, a(1) = 2, a(n) = 4*a(n-1) - a(n-2).
(Formerly M1769 N0700)
104

%I M1769 N0700 #318 May 16 2024 15:45:36

%S 1,2,7,26,97,362,1351,5042,18817,70226,262087,978122,3650401,13623482,

%T 50843527,189750626,708158977,2642885282,9863382151,36810643322,

%U 137379191137,512706121226,1913445293767,7141075053842,26650854921601,99462344632562,371198523608647

%N a(0) = 1, a(1) = 2, a(n) = 4*a(n-1) - a(n-2).

%C Chebyshev's T(n,x) polynomials evaluated at x=2.

%C x = 2^n - 1 is prime if and only if x divides a(2^(n-2)).

%C Any k in the sequence is succeeded by 2*k + sqrt{3*(k^2 - 1)}. - _Lekraj Beedassy_, Jun 28 2002

%C For all elements x of the sequence, 12*x^2 - 12 is a square. Lim_{n -> infinity} a(n)/a(n-1) = 2 + sqrt(3) = (4 + sqrt(12))/2 which preserves the kinship with the equation "12*x^2 - 12 is a square" where the initial "12" ends up appearing as a square root. - _Gregory V. Richardson_, Oct 10 2002

%C This sequence gives the values of x in solutions of the Diophantine equation x^2 - 3*y^2 = 1; the corresponding values of y are in A001353. The solution ratios a(n)/A001353(n) are obtained as convergents of the continued fraction expansion of sqrt(3): either as successive convergents of [2;-4] or as odd convergents of [1;1,2]. - _Lekraj Beedassy_, Sep 19 2003 [edited by _Jon E. Schoenfield_, May 04 2014]

%C a(n) is half the central value in a list of three consecutive integers, the lengths of the sides of a triangle with integer sides and area. - Eugene McDonnell (eemcd(AT)mac.com), Oct 19 2003

%C a(3+6*k) - 1 and a(3+6*k) + 1 are consecutive odd powerful numbers. See A076445. - _T. D. Noe_, May 04 2006

%C The intermediate convergents to 3^(1/2), beginning with 3/2, 12/7, 45/26, 168/97, comprise a strictly increasing sequence; essentially, numerators=A005320, denominators=A001075. - _Clark Kimberling_, Aug 27 2008

%C The upper principal convergents to 3^(1/2), beginning with 2/1, 7/4, 26/15, 97/56, comprise a strictly decreasing sequence; numerators=A001075, denominators=A001353. - _Clark Kimberling_, Aug 27 2008

%C a(n+1) is the Hankel transform of A000108(n) + A000984(n) = (n+2)*Catalan(n). - _Paul Barry_, Aug 11 2009

%C Also, numbers such that floor(a(n)^2/3) is a square: base 3 analog of A031149, A204502, A204514, A204516, A204518, A204520, A004275, A001541. - _M. F. Hasler_, Jan 15 2012

%C Pisano period lengths: 1, 2, 2, 4, 3, 2, 8, 4, 6, 6, 10, 4, 12, 8, 6, 8, 18, 6, 5, 12, ... - _R. J. Mathar_, Aug 10 2012

%C Except for the first term, positive values of x (or y) satisfying x^2 - 4*x*y + y^2 + 3 = 0. - _Colin Barker_, Feb 04 2014

%C Except for the first term, positive values of x (or y) satisfying x^2 - 14*x*y + y^2 + 48 = 0. - _Colin Barker_, Feb 10 2014

%C A triangle with row sums generating the sequence can be constructed by taking the production matrix M. Take powers of M, extracting the top rows.

%C M =

%C 1, 1, 0, 0, 0, 0, ...

%C 2, 0, 3, 0, 0, 0, ...

%C 2, 0, 0, 3, 0, 0, ...

%C 2, 0, 0, 0, 3, 0, ...

%C 2, 0, 0, 0, 0, 3, ...

%C ...

%C The triangle generated from M is:

%C 1,

%C 1, 1,

%C 3, 1, 3,

%C 11, 3, 3, 9,

%C 41, 11, 9, 9, 27,

%C ...

%C The left border is A001835 and row sums are (1, 2, 7, 26, 97, ...). - _Gary W. Adamson_, Jul 25 2016

%C Even-indexed terms are odd while odd-indexed terms are even. Indeed, a(2*n) = 2*(a(n))^2 - 1 and a(2*n+1) = 2*a(n)*a(n+1) - 2. - _Timothy L. Tiffin_, Oct 11 2016

%C For each n, a(0) divides a(n), a(1) divides a(2n+1), a(2) divides a(4*n+2), a(3) divides a(6*n+3), a(4) divides a(8*n+4), a(5) divides a(10n+5), and so on. Thus, a(k) divides a((2*n+1)*k) for each k > 0 and n >= 0. A proof of this can be found in Bhargava-Kedlaya-Ng's first solution to Problem A2 of the 76th Putnam Mathematical Competition. Links to the exam and its solutions can be found below. - _Timothy L. Tiffin_, Oct 12 2016

%C From _Timothy L. Tiffin_, Oct 21 2016: (Start)

%C If any term a(n) is a prime number, then its index n will be a power of 2. This is a consequence of the results given in the previous two comments. See A277434 for those prime terms.

%C a(2n) == 1 (mod 6) and a(2*n+1) == 2 (mod 6). Consequently, each odd prime factor of a(n) will be congruent to 1 modulo 6 and, thus, found in A002476.

%C a(n) == 1 (mod 10) if n == 0 (mod 6), a(n) == 2 (mod 10) if n == {1,-1} (mod 6), a(n) == 7 (mod 10) if n == {2,-2} (mod 6), and a(n) == 6 (mod 10) if n == 3 (mod 6). So, the rightmost digits of a(n) form a repeating cycle of length 6: 1, 2, 7, 6, 7, 2. (End)

%C a(A298211(n)) = A002350(3*n^2). - _A.H.M. Smeets_, Jan 25 2018

%C (2 + sqrt(3))^n = a(n) + A001353(n)*sqrt(3), n >= 0; integers in the quadratic number field Q(sqrt(3)). - _Wolfdieter Lang_, Feb 16 2018

%C Yong Hao Ng has shown that for any n, a(n) is coprime with any member of A001834 and with any member of A001835. - _René Gy_, Feb 26 2018

%C Positive numbers k such that 3*(k-1)*(k+1) is a square. - _Davide Rotondo_, Oct 25 2020

%C a(n)*a(n+1)-1 = a(2*n+1)/2 = A001570(n) divides both a(n)^6+1 and a(n+1)^6+1. In other words, for k = a(2*n+1)/2, (k+1)^6 has divisors congruent to -1 modulo k (cf. A350916). - _Max Alekseyev_, Jan 23 2022

%D Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.

%D Eugene McDonnell, "Heron's Rule and Integer-Area Triangles", Vector 12.3 (January 1996) pp. 133-142.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D P.-F. Teilhet, Reply to Query 2094, L'Intermédiaire des Mathématiciens, 10 (1903), 235-238.

%H Indranil Ghosh, <a href="/A001075/b001075.txt">Table of n, a(n) for n = 0..1745</a> (terms 0..200 from T. D. Noe)

%H Christian Aebi and Grant Cairns, <a href="https://arxiv.org/abs/2006.07566">Lattice Equable Parallelograms</a>, arXiv:2006.07566 [math.NT], 2020.

%H Christian Aebi and Grant Cairns, <a href="https://arxiv.org/abs/2312.10866">Less than Equable Triangles on the Eisenstein lattice</a>, arXiv:2312.10866 [math.CO], 2023.

%H Krassimir T. Atanassov and Anthony G. Shannon, <a href="https://doi.org/10.7546/nntdm.2020.26.3.218-223">On intercalated Fibonacci sequences</a>, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 218-223.

%H C. Banderier and D. Merlini, <a href="http://algo.inria.fr/banderier/Papers/infjumps.ps">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.

%H Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Nemeth/nemeth7.html">Ellipse Chains and Associated Sequences</a>, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.

%H H. Brocard, <a href="http://resolver.sub.uni-goettingen.de/purl?PPN598948236_0004/DMDLOG_0053">Notes élémentaires sur le problème de Peel [sic]</a>, Nouvelle Correspondance Mathématique, 4 (1878), 337-343.

%H Chris Caldwell, <a href="http://www.utm.edu/research/primes/prove/prove3_2.html">Primality Proving</a>, Arndt's theorem.

%H J. B. Cosgrave and K. Dilcher, <a href="https://doi.org/10.1090/mcom/3111">A role for generalized Fermat numbers</a>, Math. Comp., 2016.

%H G. Dresden and Y. Li, <a href="https://arxiv.org/abs/2210.04322">Periodic Weighted Sums of Binomial Coefficients</a>, arXiv:2210.04322 [math.NT], 2022.

%H E. I. Emerson, <a href="http://www.fq.math.ca/Scanned/7-3/emerson.pdf">Recurrent Sequences in the Equation DQ^2=R^2+N</a>, Fib. Quart., 7 (1969), pp. 231-242.

%H Margherita Maria Ferrari and Norma Zagaglia Salvi, <a href="https://www.emis.de/journals/JIS/VOL20/Salvi/salvi3.html">Aperiodic Compositions and Classical Integer Sequences</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.8.

%H R. K. Guy, <a href="/A001075/a001075.pdf">Letter to N. J. A. Sloane concerning A001075, A011943, A094347</a> [Scanned and annotated letter, included with permission]

%H Kiran S. Kedlaya, <a href="http://kskedlaya.org/putnam-archive/2015.pdf">The 76th William Lowell Putnam Mathematical Competition</a>, Dec 05 2015.

%H Kiran S. Kedlaya, <a href="http://kskedlaya.org/putnam-archive/2015s.pdf">Solutions to the 76th William Lowell Putnam Mathematical Competition</a>, Dec 05 2015.

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H Clark Kimberling, <a href="http://dx.doi.org/10.1007/s000170050020">Best lower and upper approximates to irrational numbers</a>, Elemente der Mathematik, 52 (1997) 122-126.

%H Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla, and Fausto Jarquín-Zárate, <a href="https://arxiv.org/abs/1904.13002">The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d))</a>, arXiv:1904.13002 [math.NT], 2019.

%H Eugene McDonnell, <a href="https://code.jsoftware.com/wiki/Doc/Articles/Play123">Heron's Rule and Integer-Area Triangles</a>, At Play With J, 2010.

%H Valcho Milchev and Tsvetelina Karamfilova, <a href="https://arxiv.org/abs/1707.09741">Domino tiling in grid - new dependence</a>, arXiv:1707.09741 [math.HO], 2017.

%H Yong Hao Ng, <a href="https://math.stackexchange.com/a/2664328/130022">A partition in three classes of the set of all prime numbers?</a>, Mathematics Stack Exchange.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H F. V. Waugh and M. W. Maxfield, <a href="http://www.jstor.org/stable/2688511">Side-and-diagonal numbers</a>, Math. Mag., 40 (1967), 74-83.

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-1).

%F G.f.: (1 - 2*x)/(1 - 4*x + x^2). - _Simon Plouffe_ in his 1992 dissertation

%F E.g.f.: exp(2*x)*cosh(sqrt(3)*x).

%F a(n) = 4*a(n-1) - a(n-2) = a(-n).

%F a(n) = (S(n, 4) - S(n-2, 4))/2 = T(n, 2), with S(n, x) := U(n, x/2), S(-1, x) := 0, S(-2, x) := -1. U, resp. T, are Chebyshev's polynomials of the second, resp. first, kind. S(n-1, 4) = A001353(n), n >= 0. See A049310 and A053120.

%F a(n) = A001353(n+2) - 2*A001353(n+1).

%F a(n) = sqrt(1 + 3*A001353(n)) (cf. Richardson comment, Oct 10 2002).

%F a(n) = 2^(-n)*Sum_{k>=0} binomial(2*n, 2*k)*3^k = 2^(-n)*Sum_{k>=0} A086645(n, k)*3^k. - _Philippe Deléham_, Mar 01, 2004

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

%F a(n) = cosh(n * log(2 + sqrt(3))).

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*2^(n-2*k)*3^k. - _Paul Barry_, May 08 2003

%F a(n+2) = 2*a(n+1) + 3*Sum_{k>=0} a(n-k)*2^k. - _Philippe Deléham_, Mar 03 2004

%F a(n) = 2*a(n-1) + 3*A001353(n-1). - _Lekraj Beedassy_, Jul 21 2006

%F a(n) = left term of M^n * [1,0] where M = the 2 X 2 matrix [2,3; 1,2]. Right term = A001353(n). Example: a(4) = 97 since M^4 * [1,0] = [A001075(4), A001353(4)] = [97, 56]. - _Gary W. Adamson_, Dec 27 2006

%F Binomial transform of A026150: (1, 1, 4, 10, 28, 76, ...). - _Gary W. Adamson_, Nov 23 2007

%F First differences of A001571. - _N. J. A. Sloane_, Nov 03 2009

%F Sequence satisfies -3 = f(a(n), a(n+1)) where f(u, v) = u^2 + v^2 - 4*u*v. - _Michael Somos_, Sep 19 2008

%F a(n) = Sum_{k=0..n} A201730(n,k)*2^k. - _Philippe Deléham_, Dec 06 2011

%F G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(3*k - 4)/(x*(3*k - 1) - 2/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 28 2013

%F a(n) = Sum_{k=0..n} A238731(n,k). - _Philippe Deléham_, Mar 05 2014

%F a(n) = (-1)^n*(A125905(n) + 2*A125905(n-1)), n > 0. - _Franck Maminirina Ramaharo_, Nov 11 2018

%F a(n) = (tan(Pi/12)^n + tan(5*Pi/12)^n)/2. - _Greg Dresden_, Oct 01 2020

%F From _Peter Bala_, Aug 17 2022: (Start)

%F a(n) = (1/2)^n * [x^n] ( 4*x + sqrt(1 + 12*x^2) )^n.

%F The g.f. A(x) satisfies A(2*x) = 1 + x*B'(x)/B(x), where B(x) = 1/sqrt(1 - 8*x + 4*x^2) is the g.f. of A069835.

%F The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for all primes p >= 3 and positive integers n and k.

%F Sum_{n >= 1} 1/(a(n) - (3/2)/a(n)) = 1.

%F Sum_{n >= 1} (-1)^(n+1)/(a(n) + (1/2)/a(n)) = 1/3.

%F Sum_{n >= 1} 1/(a(n)^2 - 3/2) = 1 - 1/sqrt(3). (End)

%F a(n) = binomial(2*n, n) + 2*Sum_{k > 0} binomial(2*n, n+2*k)*cos(k*Pi/3). - _Greg Dresden_, Oct 11 2022

%F 2*a(n) + 2^n = 3*Sum_{k=-n..n} (-1)^k*binomial(2*n, n+6*k). - _Greg Dresden_, Feb 07 2023

%e 2^6 - 1 = 63 does not divide a(2^4) = 708158977, therefore 63 is composite. 2^5 - 1 = 31 divides a(2^3) = 18817, therefore 31 is prime.

%e G.f. = 1 + 2*x + 7*x^2 + 26*x^3 + 97*x^4 + 362*x^5 + 1351*x^6 + 5042*x^7 + ...

%p A001075 := proc(n)

%p orthopoly[T](n,2) ;

%p end proc:

%p seq(A001075(n),n=0..30) ; # _R. J. Mathar_, Apr 14 2018

%t Table[ Ceiling[(1/2)*(2 + Sqrt[3])^n], {n, 0, 24}]

%t CoefficientList[Series[(1-2*x) / (1-4*x+x^2), {x, 0, 24}], x] (* _Jean-François Alcover_, Dec 21 2011, after _Simon Plouffe_ *)

%t LinearRecurrence[{4,-1},{1,2},30] (* _Harvey P. Dale_, Aug 22 2015 *)

%t Round@Table[LucasL[2n, Sqrt[2]]/2, {n, 0, 20}] (* _Vladimir Reshetnikov_, Sep 15 2016 *)

%t ChebyshevT[Range[0, 20], 2] (* _Eric W. Weisstein_, May 26 2017 *)

%t a[ n_] := LucasL[2*n, x]/2 /. x->Sqrt[2]; (* _Michael Somos_, Sep 05 2022 *)

%o (PARI) {a(n) = subst(poltchebi(abs(n)), x, 2)};

%o (PARI) {a(n) = real((2 + quadgen(12))^abs(n))};

%o (PARI) {a(n) = polsym(1 - 4*x + x^2, abs(n))[1 + abs(n)]/2};

%o (PARI) a(n)=polchebyshev(n,1,2) \\ _Charles R Greathouse IV_, Nov 07 2016

%o (PARI) my(x='x+O('x^30)); Vec((1-2*x)/(1-4*x+x^2)) \\ _G. C. Greubel_, Dec 19 2017

%o (SageMath) [lucas_number2(n,4,1)/2 for n in range(0, 25)] # _Zerinvary Lajos_, May 14 2009

%o (Haskell)

%o a001075 n = a001075_list !! n

%o a001075_list =

%o 1 : 2 : zipWith (-) (map (4 *) $ tail a001075_list) a001075_list

%o -- _Reinhard Zumkeller_, Aug 11 2011

%o (SageMath)

%o def a(n):

%o Q = QuadraticField(3, 't')

%o u = Q.units()[0]

%o return (u^n).lift().coeffs()[0] # _Ralf Stephan_, Jun 19 2014

%o (Magma) I:=[1, 2]; [n le 2 select I[n] else 4*Self(n-1) - Self(n-2): n in [1..30]]; // _G. C. Greubel_, Dec 19 2017

%Y Bisections are A011943 and A094347.

%Y Cf. A001353, A065918, A071954, A001571, A001834, A003500, A016064, A082840, A026150, A277434.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, Jul 10 2000

%E Chebyshev comments from _Wolfdieter Lang_, Oct 31 2002