A006702 -id:A006702 - cp's OEIS frontend

A003285 Period of continued fraction for square root of n (or 0 if n is a square).

0, 1, 2, 0, 1, 2, 4, 2, 0, 1, 2, 2, 5, 4, 2, 0, 1, 2, 6, 2, 6, 6, 4, 2, 0, 1, 2, 4, 5, 2, 8, 4, 4, 4, 2, 0, 1, 2, 2, 2, 3, 2, 10, 8, 6, 12, 4, 2, 0, 1, 2, 6, 5, 6, 4, 2, 6, 7, 6, 4, 11, 4, 2, 0, 1, 2, 10, 2, 8, 6, 8, 2, 7, 5, 4, 12, 6, 4, 4, 2, 0, 1, 2, 2, 5, 10, 2, 6, 5, 2, 8, 8, 10, 16, 4, 4, 11, 4, 2, 0, 1, 2, 12

Offset: 1

N. J. A. Sloane

Any string of five consecutive terms m^2 - 2 through m^2 + 2 for m > 2 in the sequence has the corresponding periods 4,2,0,1,2. - Lekraj Beedassy, Jul 17 2001
For m > 1, a(m^2+m) = 2 and the continued fraction is m, 2, 2*m, 2, 2*m, 2, 2*m, ... - Arran Fernandez, Aug 14 2011
Apparently the generating function of the sequence for the denominators of continued fraction convergents to sqrt(n) is always rational and of form p(x)/[1 - C*x^m + (-1)^m * x^(2m)], or equivalently, the denominators satisfy the linear recurrence b(n+2m) = C*b(n+m) - (-1)^m * b(n), where a(n) is equal to m for each nonsquare n, or 0. See A006702 for the conjecture regarding C. The same conjectures apply to the sequences of the numerators of continued fraction convergents to sqrt(n). - Ralf Stephan, Dec 12 2013
If a(n)=1, n is of form k^2+1 (A002522 except the initial term 1). See A013642 for a(n)=2, A013643 for a(n)=3, A013644 for a(n)=4, A010337 for a(n)=5, A020347 for a(n)=6, A010338 for a(n)=7, A020348 for a(n)=8, A010339 for a(n)=9, and furthermore A020349-A020439. - Ralf Stephan, Dec 12 2013
From William Krier, Dec 12 2024: (Start)
a(m^2-4) = 4 for even m>=6 since sqrt(m^2-4) = [m-1; 1, (m-4)/2, 1, 2*(m-1)].
a(m^2-4) = 6 for odd m>=5 since sqrt(m^2-4) = [m-1; 1, (m-3)/2, 2, (m-3)/2, 1, 2*(m-1)].
a(m^2+4) = 2 for even m>=2 since sqrt(m^2+4) = [m; m/2, 2*m].
a(m^2+4) = 5 for odd m>=3 since sqrt(m^2+4) = [m; (m-1)/2, 1, 1, (m-1)/2, 2*m]. (End)

A. Brousseau, Number Theory Tables. Fibonacci Association, San Jose, CA, 1973, p. 197.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ray Chandler, Table of n, a(n) for n = 1..10000 (first 5000 terms from T. D. Noe)
Marius Beceanu, Period of the Continued Fraction of sqrt(n), (Feb 05 2003)
Leon Bernstein, Fundamental units and cycles in the period of real quadratic number fields, I. Pacific J. Math 63 (1976): 37-61.
Ron Knott, All square-root continued fractions eventually repeat
R. Luczak, Patterns in the period lengths of simple periodic continued fractional representations of square roots of integers near perfect squares, QED: Chicago's Youth Math Research Symposium (April 2013).
R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012-2018. - From _N. J. A. Sloane_, Jun 13 2012
Justin T. Miller, Families of Continued Fractions, translated (2000) from a document of Nikos Drakos, Computer Based Learning Unit, University of Leeds.
C. D. Patterson and H. C. Williams, Some Periodic Continued Fractions with Long Periods, Mathematics of Computation, Vol. 44 (1985), No. 170, pp. 523-532.
A. M. Rockett and P. Szuesz, On the lengths of the periods of the continued fractions of square-roots of integers, Forum Mathematicum, 2 (1990), 119-123.
R. G. Stanton, C. Sudler, Jr. and H. C. Williams, An Upper Bound for the Period of the Simple Continued Fraction for Sqrt(D), Pacific Journal of Math., Vol. 67 (1976), No. 2, pp. 525-536.
Hanna Uscka-Wehlou, Continued Fractions and Digital Lines with Irrational Slopes, in Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, Volume 4992/2008, Springer-Verlag.
A. J. van der Poorten, Fractional Parts of the Period of the Continued Fraction Expansion of Quadratic Integers [Refined and revised text of a talk given at the 2nd Conference of the Canadian Number Theory Association, Vancouver, 1989]
A. J. van der Poorten, An introduction to continued fractions, Unpublished.
A. J. van der Poorten, An introduction to continued fractions, Unpublished [Cached copy]
H. C. Williams, A Numerical Investigation Into the Length of the Period of the Continued Fraction Expansion of Sqrt(D), Mathematics of Computation, Vol. 36 (1981), No. 154, pp. 593-601.

Cf. A013943, A035015, A054269, A061490, A065938, A067280, A097853.

f:= n ->  if issqr(n) then 0
   else nops(numtheory:-cfrac(sqrt(n),'periodic','quotients')[2]) fi:
map(f, [$1..100]); # Robert Israel, Sep 02 2015

a[n_] := ContinuedFraction[Sqrt[n]] // If[Length[ # ] == 1, 0, Length[Last[ # ]]]&
pcf[n_]:=Module[{s=Sqrt[n]},If[IntegerQ[s],0,Length[ContinuedFraction[s][[2]]]]]; Array[pcf,110] (* Harvey P. Dale, Jul 15 2017 *)

a(n)=if(issquare(n),return(0));my(s=sqrt(n),x=s,f=floor(s),P=[0],Q=[1],k);while(1,k=#P;P=concat(P,f*Q[k]-P[k]);Q=concat(Q,(n-P[k+1]^2)/Q[k]);k++;for(i=1,k-1,if(P[i]==P[k]&&Q[i]==Q[k],return(k-i)));x=(P[k]+s)/Q[k];f=floor(x)) \\ Charles R Greathouse IV, Jul 31 2011

isok(n, p) = {localprec(p); my(cf = contfrac(sqrt(n))); setsearch(Set(cf), 2*cf[1]);}
a(n) = {if (issquare(n), 0, my(p=100); while (! isok(n, p), p+=100); localprec(p); my(cf = contfrac(sqrt(n))); for (k=2, #cf, if (cf[k] == 2*cf[1], return (k-1))););} \\ Michel Marcus, Jul 07 2021

from sympy.ntheory.continued_fraction import continued_fraction_periodic
def a(n):
    cfp = continued_fraction_periodic(0, 1, d=n)
    return 0 if len(cfp) == 1 else len(cfp[1])
print([a(n) for n in range(1, 104)]) # Michael S. Branicky, Aug 22 2021

A002350 Take solution to Pellian equation x^2 - n*y^2 = 1 with smallest positive y and x >= 0; sequence gives a(n) = x, or 1 if n is a square. A002349 gives values of y.

Original entry on oeis.org

1, 3, 2, 1, 9, 5, 8, 3, 1, 19, 10, 7, 649, 15, 4, 1, 33, 17, 170, 9, 55, 197, 24, 5, 1, 51, 26, 127, 9801, 11, 1520, 17, 23, 35, 6, 1, 73, 37, 25, 19, 2049, 13, 3482, 199, 161, 24335, 48, 7, 1, 99, 50, 649, 66249, 485, 89, 15, 151, 19603, 530, 31, 1766319049, 63, 8, 1

Offset: 1

N. J. A. Sloane

From A.H.M. Smeets, Nov 20 2017: (Start)
a(p*q^2) = b(p,q/gcd(A002349(p),q)) where
b(p,0) = 1, b(p,1) = a(p), b(p,i) = 2*a(p)*b(p,i-1) - b(p,i-2) for i>1. (End)

			For n = 1, 2, 3, 4, 5 solutions are (x,y) = (1, 0), (3, 2), (2, 1), (1, 0), (9, 4).

A. Cayley, Report of a committee appointed for the purpose of carrying on the tables connected with the Pellian equation ..., Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 430-443.
C. F. Degen, Canon Pellianus. Hafniae, Copenhagen, 1817.
D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 55.
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).

Ray Chandler, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
A. Cayley, Report of a committee appointed for the purpose of carrying on the tables connected with the Pellian equation ..., Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 430-443. (Annotated scanned copy)
L. Beeckmans, Squares expressible as sum of consecutive squares, Amer. Math. Monthly, 101 (1994), 437-442.
L. Euler, De solutione problematum diophanteorum per numeros integros (English and Latin), par. 17.
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)

Cf. A002349, A006702, A006703, A006704, A006705. See A033316, A033315, A033319 for records.

PellSolve[(m_Integer)?Positive] := Module[{cf, n, s}, cf = ContinuedFraction[ Sqrt[m]]; n = Length[ Last[cf]]; If[ OddQ[n], n = 2*n]; s = FromContinuedFraction[ ContinuedFraction[ Sqrt[m], n]]; {Numerator[s], Denominator[s]}]; f[n_] := If[ !IntegerQ[ Sqrt[n]], PellSolve[n][[1]], 1]; Table[ f[n], {n, 0, 65}]
Table[If[! IntegerQ[Sqrt[k]], {k, FindInstance[x^2 - k*y^2 == 1 && x > 0 && y > 0, {x, y}, Integers]}, Nothing], {k, 2, 80}][[All, 2, 1, 1, 2]] (* Horst H. Manninger, Mar 23 2021 *)

from sympy.ntheory.primetest import is_square
from sympy.solvers.diophantine.diophantine import diop_DN
def A002350(n): return 1 if is_square(n) else next(a for a,b in diop_DN(n,1)) # Chai Wah Wu, Feb 11 2025

a(prime(i)) = A081233(i). - R. J. Mathar, Feb 25 2025

A002349 Take solution to Pellian equation x^2 - n*y^2 = 1 with smallest positive y and x >= 0; sequence gives a(n) = y, or 0 if n is a square. A002350 gives values of x.

Original entry on oeis.org

0, 2, 1, 0, 4, 2, 3, 1, 0, 6, 3, 2, 180, 4, 1, 0, 8, 4, 39, 2, 12, 42, 5, 1, 0, 10, 5, 24, 1820, 2, 273, 3, 4, 6, 1, 0, 12, 6, 4, 3, 320, 2, 531, 30, 24, 3588, 7, 1, 0, 14, 7, 90, 9100, 66, 12, 2, 20, 2574, 69, 4, 226153980, 8, 1, 0, 16, 8, 5967, 4, 936, 30, 413, 2, 267000, 430, 3

Offset: 1

N. J. A. Sloane

			For n = 1, 2, 3, 4, 5 solutions are (x,y) = (1, 0), (3, 2), (2, 1), (1, 0), (9, 4).

Albert H. Beiler, "The Pellian" (chap 22), Recreations in the Theory of Numbers, 2nd ed. NY: Dover, 1966.
A. Cayley, Report of a committee appointed for the purpose of carrying on the tables connected with the Pellian equation ..., Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 430-443.
C. F. Degen, Canon Pellianus. Hafniae, Copenhagen, 1817.
D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 55.
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).
E. E. Whitford, The Pell Equation.

Ray Chandler, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
A. Cayley, Report of a committee appointed for the purpose of carrying on the tables connected with the Pellian equation ..., Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 430-443. (Annotated scanned copy)
L. Euler, De solutione problematum diophanteorum per numeros integros, par. 17.
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)
E. E. Whitford, The Pell equation, New York, 1912.

Cf. A002350, A006702, A006703, A006704, A006705. See A033316, A033315, A033319 for records.

a[n_] := If[IntegerQ[Sqrt[n]], 0, For[y=1, !IntegerQ[Sqrt[n*y^2+1]], y++, Null]; y]
(* Second program: *)
PellSolve[(m_Integer)?Positive] := Module[{cof, n, s}, cof = ContinuedFraction[ Sqrt[m]]; n = Length[ Last[cof]]; If[ OddQ[n], n = 2*n]; s = FromContinuedFraction[ ContinuedFraction[ Sqrt[m], n]]; {Numerator[s], Denominator[s]}]; f[n_] := If[ !IntegerQ[ Sqrt[n]], PellSolve[n][[2]], 0]; Table[ f[n], {n, 0, 75}]

from sympy.ntheory.primetest import is_square
from sympy.solvers.diophantine.diophantine import diop_DN
def A002349(n): return 0 if is_square(n) else next(b for a,b in diop_DN(n,1)) # Chai Wah Wu, Feb 11 2025

a(prime(i)) = A081234(i). - R. J. Mathar, Feb 25 2025

More terms from Enoch Haga, Mar 14 2002

Better description from Robert G. Wilson v, Apr 14 2003

A006703 Solution to Pellian: y such that x^2 - n*y^2 = +-1.

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 3, 1, 0, 1, 3, 2, 5, 4, 1, 0, 1, 4, 39, 2, 12, 42, 5, 1, 0, 1, 5, 24, 13, 2, 273, 3, 4, 6, 1, 0, 1, 6, 4, 3, 5, 2, 531, 30, 24, 3588, 7, 1, 0, 1, 7, 90, 25, 66, 12, 2, 20, 13, 69, 4, 3805, 8, 1, 0, 1, 8, 5967, 4, 936, 30, 413, 2, 125, 5, 3, 6630, 40, 6, 9

Offset: 1

N. J. A. Sloane

nonn

A. Cayley, Report of a committee appointed for the purpose of carrying on the tables connected with the Pellian equation ..., Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 430-443.
C. F. Degen, Canon Pellianus. Hafniae, Copenhagen, 1817.
D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 55.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..10000
A. Cayley, Report of a committee appointed for the purpose of carrying on the tables connected with the Pellian equation ..., Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 430-443. (Annotated scanned copy)
M. Zuker, Fundamental solution to Pell's Equation x^2 - d*y^2 = +-1 [Broken link]

Cf. A006702 (for the x values), A077233.

r[x_, n_] := Reduce[ y > 0 && (x^2 - n*y^2 == -1 || x^2 - n*y^2 == 1 ), y, Integers]; a[n_ /; IntegerQ[ Sqrt[n]]] = 0; a[n_] := a[n] = (k = 1; While[r[k, n] === False, k++]; y /. ToRules[r[k, n]]); Table[ Print[ a[n] ]; a[n], {n, 1, 79}] (* Jean-François Alcover, Jan 30 2012 *)
nmax = 500;
nconv = 200; (* The number of convergents'nconv' should be increased if the linear recurrence is not found for some terms. *)
x[n_] := x[n] = Module[{lr}, If[IntegerQ[Sqrt[n]], 1, lr = FindLinearRecurrence[ Numerator[ Convergents[Sqrt[n], nconv]]]; SelectFirst[lr, # > 1 &]/2]];
a[n_] := If[n == 2, 1, SelectFirst[{Sqrt[(x[n]^2 - 1)/n], Sqrt[(x[n]^2 + 1)/n]}, IntegerQ]];
Array[a, nmax] // Quiet (* Jean-François Alcover, Mar 08 2021 *)

Corrected and extended by T. D. Noe, May 19 2007

A077232 a(n) is smallest natural number satisfying Pell equation a^2 - d(n)*b^2= +1 or = -1, with d(n)=A000037(n) (a nonsquare). Corresponding smallest b(n)=A077233(n).

Original entry on oeis.org

1, 2, 2, 5, 8, 3, 3, 10, 7, 18, 15, 4, 4, 17, 170, 9, 55, 197, 24, 5, 5, 26, 127, 70, 11, 1520, 17, 23, 35, 6, 6, 37, 25, 19, 32, 13, 3482, 199, 161, 24335, 48, 7, 7, 50, 649, 182, 485, 89, 15, 151, 99, 530, 31, 29718, 63, 8, 8, 65, 48842, 33, 7775, 251, 3480, 17, 1068, 43, 26, 57799, 351, 53, 80, 9, 9, 82, 55, 378, 10405, 28, 197, 500, 19, 1574, 1151, 12151, 2143295, 39, 49, 5604, 99, 10, 10, 101, 227528

Offset: 1

Wolfdieter Lang, Nov 08 2002

If d(n)=A000037(n) is from A003654 (that is if the regular continued fraction for sqrt(d(n)) has odd (primitive) period length) then the -1 option applies. For such d(n) the minimal a(n) and b(n) numbers for the +1 option are 2*a(n)^2+1 and 2*a(n)*b(n), respectively (see Perron I, pp. 94,95).
If d(n)=A000037(n)= k^2+1, k=1,2,.., then the a^2 - d(n)*b^2 = -1 Pell equation has the minimal solution a(n)=k and b(n)=1. If d(n)=A000037(n)= k^2-1, k=2,3,..., then the a^2 - d(n)*b^2 = +1 Pell equation has the minimal solution a=k and b=1.
The general integer solutions (up to signs) of Pell equation a^2 - d(n)*b^2 = +1 with d(n)=A000037(n), but not from A003654, are a(n,p)= T(p+1,a(n)) and b(n,p)= b(n)*S(p,2*a(n)), p=0,1,... If d(n)=A000037(n) is also from A003654 then these solutions are a(n,p)= T(p+1,2*a(n)^2+1) and b(n,p)= 2*a(n)*b(n)*S(p,2*(2*a(n)^2+1)), p=0,1,... Here T(n,x), resp. S(n,x) := U(n,x/2), are Chebyshev's polynomials of the first, resp. second, kind. See A053120 and A049310.
The general integer solutions (up to signs) of the Pell equation a^2 - d(n)*b^2 = -1 with d(n)=A000037(n)= A003654(k), for some k>=1, are a(n,p) = a(n)*(S(n,2*(2*a(n)^2)+1) + S(n-1,2*(2*a(n)^2)+1)) and b(n,p) = b(n)*(S(n,2*(2*a(n)^2)+1) - S(n-1,2*(2*a(n)^2)+1)) with the S(n,x) := U(n,x/2) Chebyshev polynomials. S(-1,x) := 0.
If the trivial solution x=1, y=0 is included, the sequence becomes A006702. - T. D. Noe, May 17 2007

			d=10=A000037(7)=A003654(3), therefore a(7)^2=10*b(7)^2 -1, i.e. 3^2=10*1^2 -1 and 2*a(7)^2+1=19 and 2*a(7)*b(7)=2*3*1=6 satisfy 19^2 - 10*6^2 = +1.
d=11=A000037(8) is not in A003654, therefore there is no (nontrivial) solution of the a^2 - d*b^2 = -1 Pell equation and a(8)=10 and b(8)=A077233(8)=3 satisfy 10^2 - 11*3^2 = +1.
10=d(7)=A000037(7)=A003654(3)=3^2+1 hence a(7)=3 and b(7)=1 are the smallest numbers satisfying a^2-10*b^2=-1.
8=d(6)=A000037(6)=3^2-1 (not in A003654) hence a(6)=3 and b(6)=1 are the smallest numbers satisfying a^2-8*b^2=+1.

T. Nagell, "Introduction to Number Theory", Chelsea Pub., New York, 1964, table p. 301.
O. Perron, "Die Lehre von den Kettenbruechen, Bd.I", Teubner, 1954, 1957 (Sec. 26, p. 91 with explanation on pp. 94,95).

Ray Chandler, Table of n, a(n) for n = 1..10000
A. M. Legendre, Fractions les plus simples m/n qui satisfont à l'équation m^2 - an^2 =+-1 pour tout nombre non quarré a depuis 2 jusqu'à 1003, Essai sur la Théorie des Nombres An VI, Table XII. [_Paul Curtz_, Apr 10 2019]
Index entries for sequences related to Chebyshev polynomials.

Cf. A000037, A003654, A003814, A006702, A033313, A077233.

nmax = 500;
nconv = 200; (* The number of convergents 'nconv' should be increased if the linear recurrence is not found for some terms. *)
nonSquare[n_] := n + Round[Sqrt[n]];
a[n_] := a[n] = Module[{lr}, lr = FindLinearRecurrence[ Numerator[ Convergents[ Sqrt[nonSquare[n]], nconv]]]; (1/2) SelectFirst[lr, #>1&]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, nmax}] (* Jean-François Alcover, Mar 10 2021 *)

a(n)=sqrt(A000037(n)*A077233(n)^2 + (-1)^(c(n))) with c(n)=1 if A000037(n)=A003654(k) for some k>=1 else c(n)=0.

A068717 a(n) = -1 if A067280(n) == 0 (mod 2), otherwise a(n) = A049240(n).

Original entry on oeis.org

0, -1, 1, 0, -1, 1, 1, 1, 0, -1, 1, 1, -1, 1, 1, 0, -1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 0, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1

Offset: 1

Frank Ellermann, Feb 25 2002

Previous name was: x*x - n*y*y = +-1 has infinitely many solutions in integers (x,y).

			a(2)= -1: x*x - 2*y*y = -1 is soluble, e.g., 7*7 - 2*5*5 = -1.

H. Davenport, The Higher Arithmetic. Cambridge Univ. Press, 7th ed., 1999, table 1.

John Robertson, Solving the generalized Pell equation x^2-dy^2=N.

Cf. A068716, A068718, A067280, A049240, A006702, A006703.

from math import isqrt
from sympy import continued_fraction_periodic
def A068717(n): return 0 if (a:=isqrt(n)**2==n) else (-1 if len(continued_fraction_periodic(0,1,n)[1]) & 1 else 1-int(a)) # Chai Wah Wu, Jun 14 2022

a(n) = -1 if A067280(n) == 0 (mod 2), otherwise a(n) = A049240(n).

New name from formula by Joerg Arndt, Aug 29 2020

A068716 a(n) = 1 if x^2 + 1 = n * y^2 has infinitely many solutions in integers (x,y), otherwise a(n) = 0.

Original entry on oeis.org

0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0

Offset: 1

Frank Ellermann, Feb 25 2002

nonn

			a(2) = 1 as x*x + 1 = 2 * y*y is soluble, e.g., 7*7 + 1= 2*5*5.

H. Davenport, The Higher Arithmetic. Cambridge Univ. Press, 7th ed., 1999, table 1.

John Robertson, Solving the generalized Pell equation x^2-dy^2=N.

Cf. A068717, A067280, A006702, A006703.

a(n) = 1 - (A067280(n) mod 2 ).

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 31 2003

A175155 Numbers m satisfying m^2 + 1 = x^2 * y^3 for positive integers x and y.

Original entry on oeis.org

0, 682, 1268860318, 1459639851109444, 2360712083917682, 86149711981264908618, 4392100110703410665318, 8171493471761113423918890682, 15203047261220215902863544865414318, 5484296027914919579181500526692857773246, 28285239023397517753374058381589688919682, 12439333951782387734360136352377558500557329868

Offset: 1

Michel Lagneau, Feb 27 2010

nonn

This sequence is infinite. The fundamental solution of m^2 + 1 = x^2 y^3 is (m,x,y) = (682,61,5), which means the Pellian equation m^2 - 125x^2 = -1 has the solution (m,x) = (682,61) = (m(1),x(1)). This Pellian equation admits an infinity of solutions (m(2k+1),x(2k+1)), k=1,2,..., given by the following recursive relation, starting with m(1)=682, x(1)= 61: m(2k+1) + x(2k+1)*sqrt(125) = (m(1) + x(1)*sqrt(125))^(2k+1).
Squares of these terms are in A060355, since both a(n)^2 and a(n)^2 + 1 are powerful (A001694). - Charles R Greathouse IV, Nov 16 2012
It appears that y = A077426. - Robert G. Wilson v, Nov 16 2012
Also m^2 + 1 is powerful. Other solutions arise from solutions x to x^2 - k^3*y^2 = -1. - Georgi Guninski, Nov 17 2012
Although it is believed that the b-file is complete for all terms m < 10^100, the search only looked for y < 100000. - Robert G. Wilson v, Nov 17 2012

			For m=682, m^2 + 1 = 465125 = 61^2 * 5^3.

Albert H. Beiler, "The Pellian" (Chap. 22), Recreations in the Theory of Numbers, 2nd ed. NY: Dover, 1966.
A. Cayley, Report of a committee appointed for the purpose of carrying on the tables connected with the Pellian equation ..., Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 430-443.
J. M. De Koninck, Ces nombres qui nous fascinent, Ellipses, 2008, p. 108.

Robert G. Wilson v, Table of n, a(n) for n = 1..292. [This list has not been proved to be complete! - _N. J. A. Sloane_, Nov 17 2012]
E. E. Whitford, The Pell equation, New York, 1912.
Wikipedia, Pell's equation

Pellian equation: A006704, A006702, A006705, A006703, A003153, A001571, A001570.

C:=array(0..20,0..20):C[1,1]=1: C[2,1]=1: n1:=682:x1:=61:for nn from 1 by 2 to 15 do:s:=0:for i from 2 to 15 do:for j from 1 to i do:C[i,j]:= C[i-1,j] + C[i-1,j-1]: od:od:for n from 1 by 2 to nn+1 do:s:=s + C[nn+1,n] * n1^(nn-n+1)*x1^(n-1)*125^((n-1)/2):od:print (s):od: # Michel Lagneau
# 2nd program R. J. Mathar, Mar 16 2016:
# print (nonsorted!) all solutions of A175155 up to search limit
with(numtheory):
# upper limit for solutions n
nsearchlim := 10^40 :
A175155y := proc(y::integer)
    local disc;
    disc := y^3 ;
    cfrac(sqrt(disc),periodic,quotients) ;
end proc:
for y from 2 do
    if issqrfree(y) then
        # find continued fraction for x^2-(y^3=disc)*y^2=-1, sqrt(disc)
        cf := A175155y(y) ;
        nlen :=  nops(op(2,cf)) ;
        if type(nlen,odd) then
            # fundamental solution
            fuso := numtheory[nthconver](cf,nlen-1) ;
            fusolx := numer(fuso) ;
            fusoly := denom(fuso) ;
            solx := fusolx ;
            soly := fusoly ;
            while solx <= nsearchlim do
                rhhs := solx^2-y^3*soly^2 ;
                if rhhs = -1 then
                    # print("n=",solx,"x=",soly,"y=",y^3) ;
                    print(solx) ;
                end if;
                # solutions from fundamental solution
                tempx := fusolx*solx+y^3*fusoly*soly ;
                tempy := fusolx*soly+fusoly*solx ;
                solx := tempx ;
                soly := tempy ;
            end do;
        end if;
    fi;
end do:

nmax = 10^50; ymax = 100; instances = 10; fi[y_] := n /. FindInstance[0 <= n <= nmax && x > 0 && n^2 + 1 == x^2*y^3, {n, x}, Integers, instances]; yy = Select[Range[1, ymax, 2], !IntegerQ[Sqrt[#]] && OddQ[ Length[ ContinuedFraction[Sqrt[#]][[2]]]]&]; Join[{0}, fi /@ yy // Flatten // Union // Most] (* Jean-François Alcover, Jul 12 2017 *)

is(n)=ispowerful(n^2+1) \\ Charles R Greathouse IV, Nov 16 2012

m(1)=682, x(1) = 61 and m(2k+1) + x(2k+1)*sqrt(125) = (m(1) + x(1)*sqrt(125))^(2k+1) m(2k+1) = C(2k+1,0) * m(1)^(2k+1) + C(2k+1,2)*m(1)^(2k-1)*x(1)^2 + ...

Added condition that x and y must be positive. Added missing initial term 0. Added warning that b-file has not been proved to be correct - there could be missing entries. - N. J. A. Sloane, Nov 17 2012

A341862 a(n) is the even term in the linear recurrence signature for numerators and denominators of continued fraction convergents to sqrt(n), or 0 if n is a square.

Original entry on oeis.org

0, 0, 2, 4, 0, 4, 10, 16, 6, 0, 6, 20, 14, 36, 30, 8, 0, 8, 34, 340, 18, 110, 394, 48, 10, 0, 10, 52, 254, 140, 22, 3040, 34, 46, 70, 12, 0, 12, 74, 50, 38, 64, 26, 6964, 398, 322, 48670, 96, 14, 0, 14, 100, 1298, 364, 970, 178, 30, 302, 198, 1060, 62, 59436

Offset: 0

Georg Fischer, Feb 22 2021

nonn

The Everest et al. link states that "the continued fraction expansion of a quadratic irrational is eventually periodic, which implies that the numerators px and denominators qx of its convergents satisfy linear recurrence relations".
Let k be the period length minus one of the continued fraction of sqrt(n). Then the linear recurrence signatures with constant coefficients have the form (0, 0, ..., 0, a(n), 0, 0, ..., 0, (-1)^(n+1)), with k zeroes before and behind a(n).
a(n) is twice the numerator of the convergent to sqrt(n) with index k (starting with 0).
These properties result from the mirrored structure of the period of such continued fractions.
The sequence has remarkably many terms in common with A180495 and with 2*A033313.

			The numerators for sqrt(13) begin with 3, 4, 7, 11, 18, 119, ... (A041018) and have the signature (0,0,0,0,36,0,0,0,0,1). The continued fraction has period [1,1,1,1,6], so k=4 and a(13) = 2*A041018(4) = 2*18 = 36. The signature ends with (-1)^4.
The numerators for sqrt(19) begin with 4, 9, 13, 48, 61, 170, 1421, ... (A041028) and have the signature (0,0,0,0,0,340,0,0,0,0,0,-1). The continued fraction has period [2,1,3,1,2,8], so k=5 and a(19) = 2*A041028(5) = 2*170 = 340. The signature ends with (-1)^5.

Jean-François Alcover, Table of n, a(n) for n = 0..10000
Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward, Recurrence Sequences, AMS Mathematical Surveys and Monographs, Volume 104 (2003) p. 8, 5th paragraph.

Cf. A006702, A033313, A180495.

a(n) = 2*A006702(n) if n is not square, otherwise 0.

cp's OEIS Frontend

A003285 Period of continued fraction for square root of n (or 0 if n is a square).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

A002350 Take solution to Pellian equation x^2 - n*y^2 = 1 with smallest positive y and x >= 0; sequence gives a(n) = x, or 1 if n is a square. A002349 gives values of y.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

A002349 Take solution to Pellian equation x^2 - n*y^2 = 1 with smallest positive y and x >= 0; sequence gives a(n) = y, or 0 if n is a square. A002350 gives values of x.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A006703 Solution to Pellian: y such that x^2 - n*y^2 = +-1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Extensions

A077232 a(n) is smallest natural number satisfying Pell equation a^2 - d(n)*b^2= +1 or = -1, with d(n)=A000037(n) (a nonsquare). Corresponding smallest b(n)=A077233(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A068717 a(n) = -1 if A067280(n) == 0 (mod 2), otherwise a(n) = A049240(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Formula

Extensions

A068716 a(n) = 1 if x^2 + 1 = n * y^2 has infinitely many solutions in integers (x,y), otherwise a(n) = 0.

Views

Author

Keywords