A013943 -id:A013943 - 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

A035015 Period of continued fraction for square root of n-th squarefree integer.

Original entry on oeis.org

1, 2, 1, 2, 4, 1, 2, 5, 4, 2, 1, 6, 6, 6, 4, 1, 5, 2, 8, 4, 4, 2, 1, 2, 2, 3, 2, 10, 12, 4, 2, 5, 4, 6, 7, 6, 11, 4, 1, 2, 10, 8, 6, 8, 7, 5, 6, 4, 4, 1, 2, 5, 10, 2, 5, 8, 10, 16, 4, 11, 1, 2, 12, 2, 9, 6, 15, 2, 6, 9, 6, 10, 10, 4, 1, 2, 12, 10, 3, 6, 16, 14, 9, 4, 18, 4, 4, 2, 1, 2, 9, 20, 10, 4

Offset: 2

David L. Treumann (alewifepurswest(AT)yahoo.com)

Friesen proved that each value appears infinitely often. - Michel Marcus, Apr 12 2019

			a(2)=1 because 2 is the 2nd smallest squarefree integer and sqrt 2 = [ 1,2,2,2,2,... ] thus has an eventual period of 1.

David W. Wilson, Table of n, a(n) for n = 2..10000
S. R. Finch, Class number theory [broken link]
Steven R. Finch, Class number theory [Cached copy, with permission of the author]
Christian Friesen, On continued fractions of given period, Proc. Amer. Math. Soc. 103 (1988), 9-14.
Ron Knott, An Introduction to Continued Fractions

Cf. A003285, A005117 (squarefree numbers), A013943.

sqf:= select(numtheory:-issqrfree,[$2..1000]):
map(n->nops(numtheory:-cfrac(sqrt(n),'periodic','quotients')[2]),sqf); # Robert Israel, Dec 21 2014

Length[ContinuedFraction[Sqrt[#]][[2]]]&/@Select[ Range[ 2,200], SquareFreeQ] (* Harvey P. Dale, Jul 17 2011 *)

a(n) = A003285(A005117(n)). - Michel Marcus, Dec 29 2014

Corrected and extended by James Sellers

A121339 Periodic part of continued fraction for square roots of integers.

Original entry on oeis.org

2, 1, 2, 4, 2, 4, 1, 1, 1, 4, 1, 4, 6, 3, 6, 2, 6, 1, 1, 1, 1, 6, 1, 2, 1, 6, 1, 6, 8, 4, 8, 2, 1, 3, 1, 2, 8, 2, 8, 1, 1, 2, 1, 1, 8, 1, 2, 4, 2, 1, 8, 1, 3, 1, 8, 1, 8, 10, 5, 10, 3, 2, 3, 10, 2, 1, 1, 2, 10, 2, 10, 1, 1, 3, 5, 3, 1, 1, 10, 1, 1, 1, 10, 1, 2, 1, 10, 1, 4, 1, 10, 1, 10, 12, 6, 12, 4, 12

Offset: 2

Franklin T. Adams-Watters, Aug 28 2006

			The table starts:
  2
  1 2
  <empty>
  4
  2 4
  1 1 1 4
  1 4

T. D. Noe, Rows n = 2..1000 of triangle, flattened

Cf. A003285 (row lengths), A013943 (row lengths for nonempty rows).

a[n_] := If[ IntegerQ[ Sqrt[n] ], {}, ContinuedFraction[ Sqrt[n] ] // Last]; Table[a[n], {n, 2, 39}] // Flatten (* Jean-François Alcover, Sep 10 2012 *)

A288186 Numbers k such that the continued fractions for sqrt(k) and sqrt(k+1) have the same period.

Original entry on oeis.org

11, 21, 32, 33, 38, 39, 78, 83, 91, 95, 104, 111, 115, 140, 141, 146, 147, 161, 164, 204, 205, 206, 219, 222, 227, 230, 242, 245, 299, 310, 320, 321, 326, 327, 340, 344, 371, 383, 395, 404, 413, 428, 434, 438, 443, 447, 451, 452, 464, 471, 498, 504, 515, 539, 545, 572, 573, 578, 579, 594, 596, 644, 654, 659, 695

Offset: 1

Ilya Gutkovskiy, Jun 06 2017

nonn

Numbers k such that A003285(k) = A003285(k+1).

			11 is in the sequence because sqrt(11) = 3 + 1/(3 + 1/(6 + 1/(3 + 1/(6 + 1/...)))), period 2: [3, 6] and sqrt(12) = 3 + 1/(2 + 1/(6 + 1/(2 + 1/(6 + 1/...)))), period  2: [2, 6].

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Periodic Continued Fraction

Cf. A003285, A013943, A031400, A097853.

A099725 a(n) is the number of 1's in the period of the continued fraction of the square root of the n-th nonsquare integer.

Original entry on oeis.org

0, 1, 0, 0, 3, 1, 0, 0, 0, 4, 2, 1, 0, 0, 2, 0, 4, 2, 2, 1, 0, 0, 0, 2, 0, 4, 3, 2, 2, 1, 0, 0, 0, 0, 0, 0, 6, 6, 2, 6, 2, 1, 0, 0, 2, 2, 2, 0, 0, 4, 6, 2, 2, 4, 2, 1, 0, 0, 4, 0, 2, 2, 2, 0, 4, 4, 3, 6, 2, 2, 2, 1, 0, 0, 0, 2, 6, 0, 3, 0, 0, 5, 4, 6, 8, 2, 2, 8, 2, 1, 0, 0, 6, 0, 0, 4, 2, 4, 4, 0, 4, 4, 6, 2, 7

Offset: 1

Benoit Cloitre, Nov 07 2004

nonn

For sufficiently large period lengths, the fraction of 1's in the repeating part tends to log(4/3)/log(2) = 0.415... as from the Gauss-Kuzmin distribution, i.e., a(n) tends to 0.415...*A013943(n) for sufficiently large A013943(n). - A.H.M. Smeets, Jun 02 2018

The "n-th nonsquare integer" in the definition is A005117(n + 1). - Michael B. Porter, Jun 06 2018

A.H.M. Smeets, Table of n, a(n) for n = 1..10000

Cf. A005117, A013647, A013943.

from math import isqrt
from sympy.ntheory.continued_fraction import continued_fraction_periodic
def A099725(n): return (continued_fraction_periodic(0,1,n+(k:=isqrt(n))+int(n>=k*(k+1)+1))[-1]).count(1) # Chai Wah Wu, Jul 20 2024

A288184 Least odd number k such that the continued fraction for sqrt(k) has period n.

Original entry on oeis.org

5, 3, 41, 7, 13, 19, 73, 31, 113, 43, 61, 103, 193, 179, 109, 133, 157, 139, 337, 151, 181, 253, 853, 271, 457, 211, 949, 487, 821, 379, 601, 463, 613, 331, 1061, 1177, 421, 619, 541, 589, 1117, 571, 1153, 823, 1249, 739, 1069, 631, 1021, 1051, 1201, 751

Offset: 1

Ilya Gutkovskiy, Jun 06 2017

nonn

			a(2) = 3, sqrt(3) = 1 + 1/(1 + 1/(2 + 1/(1 + 1/(2 + 1/...)))), period 2: [1, 2].

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Periodic Continued Fraction

Cf. A000035, A003285, A010337-A010339, A013642-A013644, A013646, A013943, A020347-A020439, A059800, A062769, A097853, A288185.

from sympy import continued_fraction_periodic
def A288184(n):
    d = 1
    while True:
        s = continued_fraction_periodic(0,1,d)[-1]
        if isinstance(s, list) and len(s) == n:
            return d
        d += 2 # Chai Wah Wu, Jun 07 2017

A003285(a(n)) = n, A000035(a(n)) = 1.

A288185 Least even number k such that the continued fraction for sqrt(k) has period n.

Original entry on oeis.org

2, 6, 130, 14, 74, 22, 58, 44, 106, 86, 298, 46, 746, 134, 1066, 94, 1018, 424, 922, 268, 394, 166, 586, 382, 1306, 214, 1354, 334, 1642, 436, 2122, 508, 1114, 454, 4138, 478, 3194, 1108, 4874, 526, 3418, 724, 2458, 604, 9914, 694, 4618, 844, 2746, 1318

Offset: 1

Ilya Gutkovskiy, Jun 06 2017

nonn

			a(2) = 6, sqrt(6) = 2 + 1/(2 + 1/(4 + 1/(2 + 1/(4 + 1/...)))), period 2: [2, 4].

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Periodic Continued Fraction

Cf. A000035, A003285, A010337-A010339, A013642-A013644, A013646, A013943, A020347-A020439, A097853, A240072, A288184.

from sympy import continued_fraction_periodic
def A288185(n):
    d = 2
    while True:
        s = continued_fraction_periodic(0,1,d)[-1]
        if isinstance(s, list) and len(s) == n:
            return d
        d += 2 # Chai Wah Wu, Jun 08 2017

A003285(a(n)) = n, A000035(a(n)) = 0.

A160520 a(n) is the number of distinct values in the periodic part of the continued fraction of the square root of n-th nonsquare positive integer.

Original entry on oeis.org

1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 2, 1, 2, 4, 2, 3, 4, 3, 2, 1, 2, 3, 3, 2, 4, 2, 3, 3, 2, 1, 2, 2, 2, 2, 2, 4, 3, 3, 5, 3, 2, 1, 2, 4, 3, 4, 2, 2, 3, 2, 4, 3, 5, 3, 2, 1, 2, 5, 2, 4, 3, 4, 2, 3, 2, 2, 5, 4, 3, 3, 2, 1, 2, 2

Offset: 1

Dremov Dmitry (dremovd(AT)gmail.com), May 16 2009

nonn

			The 10th nonsquare positive integer is 13; sqrt(13) = cf[3;(1,1,1,1,6)], which has period 5, and 2 distinct values in its periodic part.

Cf. A013943, A099725.

Length@Union@Last@ContinuedFraction@Sqrt@#&/@Select[Range@100,!IntegerQ@Sqrt@#&] (* Giorgos Kalogeropoulos, May 05 2022 *)

import math
def findperiod( d ) :
    if len(d) == 0 :
        return 0
    for p in range( 1, len(d) - 1 ) :
        isPeriod = True
        for i in range(0, p) :
            for j in range(i + p, len(d), p ) :
                if not d[i] == d[j] :
                    isPeriod = False
                    break
            if not isPeriod :
                break
        if isPeriod :
            return len( set( d[:p] ) )
    return -1
def nextv( a, b, n, less = True ) :
    # print a, b, a[1]*a[1], n * a[0] * a[0]
    d = -1
    while (a[1]*a[1] < n * a[0] * a[0]) == less :
        d += 1
        a = ( a[0] + b[0], a[1] + b[1] )
    a = ( a[0] - b[0], a[1] - b[1] )
    return d, a, b
def generated( n ) :
    maxperiod = 100
    s = int( math.sqrt( n ) )
    if s * s == n :
        return []
    a = (1, 0)
    b = (0, 1)
    ds = []
    for i in range( maxperiod ):
        d, b, a = nextv( a, b, n )
        ds.append( d )
        d, b, a = nextv( a, b, n, less = False )
        ds.append( d )
    return ds[1:]
maxn = 1000
ns = [x for x in range( maxn ) if not int( math.sqrt( x ) ) ** 2 == x ]
v = list(map( findperiod, map( generated, ns ) ))
if v.count( -1 ) == 0 :
    print(v)

from math import isqrt
from sympy.ntheory.continued_fraction import continued_fraction_periodic
def A160520(n): return len(set(continued_fraction_periodic(0,1,n+(k:=isqrt(n))+int(n>=k*(k+1)+1))[-1])) # Chai Wah Wu, Jul 20 2024

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

A035015 Period of continued fraction for square root of n-th squarefree integer.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A121339 Periodic part of continued fraction for square roots of integers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A288186 Numbers k such that the continued fractions for sqrt(k) and sqrt(k+1) have the same period.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A099725 a(n) is the number of 1's in the period of the continued fraction of the square root of the n-th nonsquare integer.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A288184 Least odd number k such that the continued fraction for sqrt(k) has period n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A288185 Least even number k such that the continued fraction for sqrt(k) has period n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A160520 a(n) is the number of distinct values in the periodic part of the continued fraction of the square root of n-th nonsquare positive integer.

Views

Author

Keywords

Examples

Crossrefs