login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002522 a(n) = n^2 + 1. 358

%I

%S 1,2,5,10,17,26,37,50,65,82,101,122,145,170,197,226,257,290,325,362,

%T 401,442,485,530,577,626,677,730,785,842,901,962,1025,1090,1157,1226,

%U 1297,1370,1445,1522,1601,1682,1765,1850,1937,2026,2117,2210,2305,2402,2501

%N a(n) = n^2 + 1.

%C An n X n nonnegative matrix A is primitive (see A070322) iff every element of A^k is > 0 for some power k. If A is primitive then the power which should have all positive entries is <= n^2 -2n +2 (Wielandt).

%C a(n) = Phi_4(n), where Phi_k is the k-th cyclotomic polynomial.

%C As the positive solution to x=2n+1/x is x=n+sqrt(a(n)), the continued fraction expansion of sqrt(a(n)) is {n; 2n, 2n, 2n, 2n, ...}. - _Benoit Cloitre_, Dec 07 2001

%C a(n) is one less than the arithmetic mean of its neighbors: a(n) = {a(n-1) + a(n+1)}/2 - 1. E.g., 2 = (1+5)/2 - 1, 5 = (2+10)/2 - 1. - _Amarnath Murthy_, Jul 29 2003

%C Equivalently, the continued fraction expansion of sqrt(a(n)) is (n;2n,2n,2n,....). - _Franz Vrabec_, Jan 23 2006

%C Number of {12,1*2*,21}-avoiding signed permutations in the hyperoctahedral group.

%C The number of squares of side 1 which can be drawn without lifting the pencil, starting at one corner of an n X n grid and never visiting an edge twice is n^2-2n+2. - _SĂ©bastien Dumortier_, Jun 16 2005

%C From _Cino Hilliard_, Feb 21 2006: (Start)

%C Also, except for the first term, numbers that cannot be expressed as a perfect power, i.e., x^2 + 1 != y^n for all x,y,n > 1. Proof: We assume the truth of the following theorem. Proofs can be found in elementary texts on number theory and online. Theorem I: A number N is a sum of two squares if and only if all prime factors of N of the form 4m+3 have even exponents.

%C We are now ready to prove x^2 + 1 != y^n for all x,y,n > 1. We assume equality and seek a contradiction for n even and n odd. If n is even = 2k, x^2 + 1 = y^2k = (y^k)^2 and (y^k - x)(y^k + x) = 1. This implies y^k-x = y^k+x = 1 or 2x = 0 contrary to x > 1. So n must be odd for equality to hold.

%C Then x^2+1 = y^(2k+1) implies all prime factors of y, including those of the form 4m+3 are raised to an odd exponent contrary to Theorem I. So we have shown x^2+1 = y^n is false for n even or n odd. Therefore x^2 + 1 != y^n as was desired. (End)

%C Note that in the above proof, y doesn't necessarily have any prime factors of the form 4m+3. - _Jon Perry_, Aug 06 2012

%C Also, numbers m such that m^3 - m^2 is a square, (n*(1 + n^2))^2. - _Zak Seidov_

%C 1 + 2/2 + 2/5 + 2/10 +...= Pi*coth Pi [Jolley], see A113319. - _Gary W. Adamson_, Dec 21 2006

%C For n>=1, a(n-1) is the minimal number of choices from an n-set such that at least one particular element has been chosen at least n times or each of the n elements has been chosen at least once. Some games define "matches" this way; e.g., in the classic Parker Brothers, now Hasbro, board game Risk, a(2)=5 is the number of cards of three available types (suits) required to guarantee at least one match of three different types or of three of the same type (ignoring any jokers or wildcards). - _Rick L. Shepherd_, Nov 18 2007

%C Sequence allows us to find X values of the equation X^3 + (X - 1)^2 + X - 2 = Y^2. To prove that X = n^2 + 1: Y^2 = X^3 + (X - 1)^2 + X - 2 = X^3 + X^2 - X - 1 = (X - 1)(X^2 + 2X + 1) = (X - 1)*(X + 1)^2 it means: (X - 1) must be a perfect square, so X = n^2 + 1 and Y = n(n^2 + 2). - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Nov 29 2007

%C For n>0: a(n-1)=A143053(A000290(n))-1. - _Reinhard Zumkeller_, Jul 20 2008

%C A143053(a(n))=A000290(n+1). - _Reinhard Zumkeller_, Jul 20 2008

%C a(n) = A156798(n)/A087475(n). - _Reinhard Zumkeller_, Feb 16 2009

%C {a(k): 0 <= k < 4} = divisors of 10. - _Reinhard Zumkeller_, Jun 17 2009

%C Number of units of a(n) belongs to a periodic sequence: 1, 2, 5, 0, 7, 6, 7, 0, 5, 2. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 04 2009

%C a(n)=A170949(A002061(n+1)); A170949(a(n))=A132411(n+1); A170950(a(n))=A002061(n+1). - _Reinhard Zumkeller_, Mar 08 2010

%C Appears in A054413 and A086902 in relation to sequences related to the numerators and denominators of continued fractions convergents to sqrt((2*n)^2/4 + 1), n=1, 2, 3, ... . - _Johannes W. Meijer_, Jun 12 2010

%C For n>0, continued fraction [n,n] = n/a(n); e.g., [5,5] = 5/26. - _Gary W. Adamson_, Jul 15 2010

%C The only real solution of the form f(x)= A*x^p with negative p which satisfies f^(m)(x) = f^[-1](x), x>=0, m>=1, with f^(m) the m-th derivative and f^[-1] the compositional inverse of f, is obtained for m=2*n, p=p(n)= -(sqrt(a(n))-n) and A=A(n)=(fallfac(p(n),2*n))^(-p(n)/(p(n)+1)), with fallfac(x,k):=product(x-j,j=0..k-1)(falling factorials). See the T. Koshy reference, pp. 263-4 (there are also two solutions for positive p, see the corresponding comment in A087475). - _Wolfdieter Lang_, Oct 21 2010

%C n + sqrt(a(n)) = [2*n;2*n,2*n,...] with the regular continued fraction with period length 1. This is the even case. For the general case see A087475 with the Schroeder reference and comments. For the odd case see A078370.

%C a(n-1) counts configurations of non-attacking bishops on a 2 X n strip [Chaiken et al., Ann. Combin. 14 (2010) 419]. - _R. J. Mathar_, Jun 16 2011

%C Also numbers n such that 4*n-4 is a square. Hence this sequence is the union of A053755 and A069894. - _Arkadiusz Wesolowski_, Aug 02 2011

%C a(n) is also the Moore lower bound on the order, A191595(n), of an (n,5)-cage. - _Jason Kimberley_, Oct 17 2011

%C Left edge of the triangle in A195437: a(n+1) = A195437(n,0). - _Reinhard Zumkeller_, Nov 23 2011

%C a(n) = A070216(n,1) for n > 0. - _Reinhard Zumkeller_, Nov 11 2012

%C If h (5,17,37,65,101,..) is prime is relatively prime to 6, then h^2-1 is divisible by 24. - _Vincenzo Librandi_, Apr 14 2014

%C The identity (4*n^2+2)^2-(n^2+1)*(4*n)^2=4 can be written as A005899(n)^2-a(n)*A008586(n)^2=4. - _Vincenzo Librandi_, Jun 15 2014

%C a(n) is also the number of permutations simultaneously avoiding 213 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - _Manda Riehl_, Aug 07 2014

%C a(n) = A254858(n-2,3) for n > 2. - _Reinhard Zumkeller_, Feb 09 2015

%C Sum_{n>=0} (-1)^n / a(n) = (1+Pi/sinh(Pi))/2 = 0.636014527491... . - _Vaclav Kotesovec_, Feb 14 2015

%C a(n-1) is the maximum number of stages in the Gale-Shapley algorithm for finding a stable matching between two sets of n elements given an ordering of preferences for each element (see Gura et al.). - _Melvin Peralta_, Feb 07 2016

%C Because of Fermat's little theorem, a(n) is never divisible by 3. - _Altug Alkan_, Apr 08 2016

%C Sum_{n>=0} 1/a(n) = (1 + Pi*coth(Pi))/2 = 2.076674047468581174... . - _Vaclav Kotesovec_, Apr 10 2016

%C For n > 0, if a(n) points are placed inside an n X n square, it will always be the case that at least two of the points will be a distance of sqrt(2) units apart or less. - _Melvin Peralta_, Jan 21 2017

%C Also the limit as q->1^- of the unimodal polynomial (1-q^(n*k+1))/(1-q) after making the simplification k=n. The unimodal polynomial is from O'Hara's proof of unimodality of q-binomials after making the restriction to partitions of size <=1. See G_1(n,k) from arXiv:1711.11252. As the size restriction s increases, G_s->G_infinity=G: the q-binomials. Then substituting k=n and q=1 yields the central binomial coefficients: A000984. - _Bryan T. Ek_, Apr 11 2018

%D S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 120).

%D E. Gura and M. Maschler, Insights into Game Theory: An Alternative Mathematical Experience, Cambridge, 2008; p. 26.

%D L. B. W. Jolley, Summation of Series, Dover Publications, 1961, p. 176.

%D Thomas Koshy, Fibonacci and Lucas Numbers with Applications, John Wiley and Sons, New York, 2001.

%H Vincenzo Librandi, <a href="/A002522/b002522.txt">Table of n, a(n) for n = 0..1000</a>. Format corrected by _Peter Kagey_, Jan 25 2016

%H R. P. Boas & N. J. A. Sloane, <a href="/A005381/a005381.pdf">Correspondence, 1974</a>

%H S. Chaiken et al., <a href="https://arxiv.org/abs/1105.5087">Nonattacking Queens in a Rectangular Strip</a>, arXiv:1105.5087 [math.CO], 2011.

%H Bryan Ek, <a href="https://arxiv.org/abs/1804.05933">Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics</a>, arXiv:1804.05933 [math.CO], 2018.

%H Guo-Niu Han, <a href="http://www-irma.u-strasbg.fr/~guoniu/papers/p77puzzle.pdf">Enumeration of Standard Puzzles</a>

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a> [Cached copy]

%H Cheyne Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint 1410.2657 [math.CO], 2014.

%H C. Homberger, V. Vatter, <a href="http://arxiv.org/abs/1308.4946">On the effective and automatic enumeration of polynomial permutation classes</a>, arXiv preprint arXiv:1308.4946 [math.CO], 2013.

%H S. J. Leon, <a href="http://www.prenhall.com/divisions/esm/app/ph-linear/leon/html/perron.html">Linear Algebra with Applications: the Perron-Frobenius heorem</a>

%H T. Mansour and J. West, <a href="https://arxiv.org/abs/math/0207204">Avoiding 2-letter signed patterns</a>, arXiv:math/0207204 [math.CO], 2002.

%H Michelle Rudolph-Lilith, <a href="http://arxiv.org/abs/1508.07894">On the Product Representation of Number Sequences, with Application to the Fibonacci Family</a>, arXiv preprint arXiv:1508.07894 [math.NT], 2015.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/NumberPicking.html">Number Picking</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Near-SquarePrime.html">Near-Square Prime</a>

%H Helmut Wielandt, <a href="http://resolver.sub.uni-goettingen.de/purl?GDZPPN002381516">Unzerlegbare nicht negativen Matrizen</a>, Math. Z. 52 (1950), 642-648.

%H Reinhard Zumkeller, <a href="/A161700/a161700.txt">Enumerations of Divisors</a>

%H <a href="/index/Cy#CyclotomicPolynomialsValuesAtX">Index to values of cyclotomic polynomials of integer argument</a>

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

%F O.g.f.: (1-x+2*x^2)/((1-x)^3). - _Eric Werley_, Jun 27 2011

%F Sequences of the form a(n) = n^2 + K with offset 0 have o.g.f. (K - 2*K*x + K*x^2 + x + x^2)/(1-x)^3 and recurrence a(n) = 3*a(n-1) - 3*a(n-2) + a*(n-3). - _R. J. Mathar_, Apr 28 2008

%F a(n)*a(n-2) = (n-1)^4 + 4. - _Reinhard Zumkeller_, Feb 12 2009

%F For n > 1, a(n)^2 + (a(n) + 1)^2 + ... + (a(n) + n - 2)^2 + (a(n) + n - 1 + a(n) + n)^2 = (n+1) *(6*n^4 + 18*n^3 + 26*n^2 + 19*n + 6) / 6 = (a(n) + n)^2 + ... + (a(n) + 2*n)^2. - _Charlie Marion_, Jan 10 2011

%F a(n) = 2*a(n-1) - a(n-2) + 2. a(n) = a(n-1) + 2*n - 1. - _Eric Werley_, Jun 27 2011

%F a(n) = (n-1)^2 + 2(n-1) + 2 = 122 read in base n - 1 (for n > 3). - _Jason Kimberley_, Oct 20 2011

%F a(n)*a(n+1) = a(n(n+1) + 1) so a(1)a(2) = a(3). More generally, a(n)*a(n+k) = a(n(n+k) + 1) + k^2 - 1. - _Jon Perry_, Aug 01 2012

%F a(n) = (n!)^2* [x^n] BesselI(0, 2*sqrt(x))*(1+x). - _Peter Luschny_, Aug 25 2012

%F E.g.f.: exp(x)*(1 + x + x^2). - _Geoffrey Critzer_, Aug 30 2013

%F 4*a(n) = A001105(n-1) + A001105(n+1). - _Bruno Berselli_, Jul 03 2017

%e G.f. = 1 + 2*x + 5*x^2 + 10*x^3 + 17*x^4 + 26*x^5 + 37*x^6 + 50*x^7 + 65*x^8 + ...

%p A002522 := proc(n)

%p numtheory[cyclotomic](4,n) ;

%p end proc:

%p seq(A002522(n),n=0..20) ; # _R. J. Mathar_, Feb 07 2014

%t Table[n^2 + 1, {n 0, 50}]; (* _Vladimir Joseph Stephan Orlovsky_, Dec 15 2008 *)

%o (MAGMA) [n^2 + 1: n in [0..50]]; // _Vincenzo Librandi_, May 01 2011

%o (PARI) a(n)=n^2+1 \\ _Charles R Greathouse IV_, Jun 10 2011

%o (Haskell)

%o a002522 = (+ 1) . (^ 2)

%o a002522_list = scanl (+) 1 [1,3..]

%o -- _Reinhard Zumkeller_, Apr 06 2012

%o (Maxima) A002522(n):=n^2+1$ makelist(A002522(n),n,0,30); /* _Martin Ettl_, Nov 07 2012 */

%Y Left edge of A055096.

%Y Cf. A059100, A117950, A087475, A117951, A114949, A117619 (sequences of form n^2 + K).

%Y a(n+1) = A101220(n, n+1, 3).

%Y Cf. A059592, A124808, A117950, A132411, A132414, A028872, A005408, A000124, A016813, A086514, A000125, A058331, A080856, A000127, A161701-A161704, A161706, A161707, A161708, A161710-A161713, A161715, A006261.

%Y Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), this sequence (g=5), A051890 (g=6), A188377 (g=7). - _Jason Kimberley_, Oct 30 2011

%Y Cf. A002496 (primes).

%Y Cf. A254858.

%Y Cf. A302612, A302644, A302645, A302646.

%K nonn,easy,changed

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Zerinvary Lajos_, May 28 2006

%E Partially edited by _Joerg Arndt_, Mar 11 2010

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 00:54 EDT 2018. Contains 315220 sequences. (Running on oeis4.)