cp's OEIS Frontend

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

%I A003285 M0018 #131 Dec 16 2024 01:50:20
%S A003285 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,
%T A003285 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,
%U A003285 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
%N A003285 Period of continued fraction for square root of n (or 0 if n is a square).
%C A003285 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
%C A003285 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
%C A003285 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
%C A003285 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
%C A003285 From _William Krier_, Dec 12 2024: (Start)
%C A003285 a(m^2-4) = 4 for even m>=6 since sqrt(m^2-4) = [m-1; 1, (m-4)/2, 1, 2*(m-1)].
%C A003285 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)].
%C A003285 a(m^2+4) = 2 for even m>=2 since sqrt(m^2+4) = [m; m/2, 2*m].
%C A003285 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)
%D A003285 A. Brousseau, Number Theory Tables. Fibonacci Association, San Jose, CA, 1973, p. 197.
%D A003285 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003285 Ray Chandler, <a href="/A003285/b003285.txt">Table of n, a(n) for n = 1..10000</a> (first 5000 terms from T. D. Noe)
%H A003285 Marius Beceanu, <a href="http://web.math.princeton.edu/mathlab/jr02fall/Periodicity/mariusjp.pdf">Period of the Continued Fraction of sqrt(n)</a>, (Feb 05 2003)
%H A003285 Leon Bernstein, <a href="http://scholar.google.de/scholar?cluster=3688217905613415587">Fundamental units and cycles in the period of real quadratic number fields</a>, I. Pacific J. Math 63 (1976): 37-61.
%H A003285 Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html#sqrts">All square-root continued fractions eventually repeat</a>
%H A003285 R. Luczak, <a href="https://mathcirclesofchicago.org/wp-content/uploads/2015/08/luczak.pdf">Patterns in the period lengths of simple periodic continued fractional representations of square roots of integers near perfect squares</a>, QED: Chicago's Youth Math Research Symposium (April 2013).
%H A003285 R. Mestrovic, <a href="http://arxiv.org/abs/1202.3670">Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof</a>, arXiv preprint arXiv:1202.3670 [math.HO], 2012-2018. - From _N. J. A. Sloane_, Jun 13 2012
%H A003285 Justin T. Miller, <a href="https://www.math.arizona.edu/~ura-reports/993/miller.justin/Miller.html">Families of Continued Fractions</a>, translated (2000) from a document of Nikos Drakos, Computer Based Learning Unit, University of Leeds.
%H A003285 C. D. Patterson and H. C. Williams, <a href="http://www.jstor.org/stable/2007971">Some Periodic Continued Fractions with Long Periods</a>, Mathematics of Computation, Vol. 44 (1985), No. 170, pp. 523-532.
%H A003285 A. M. Rockett and P. Szuesz, <a href="http://dx.doi.org/10.1515/form.1990.2.119">On the lengths of the periods of the continued fractions of square-roots of integers</a>, Forum Mathematicum, 2 (1990), 119-123.
%H A003285 R. G. Stanton, C. Sudler, Jr. and H. C. Williams, <a href="http://projecteuclid.org/euclid.pjm/1102817507">An Upper Bound for the Period of the Simple Continued Fraction for Sqrt(D)</a>, Pacific Journal of Math., Vol. 67 (1976), No. 2, pp. 525-536.
%H A003285 Hanna Uscka-Wehlou, <a href="http://scholar.google.de/scholar?cluster=8548357010461218230">Continued Fractions and Digital Lines with Irrational Slopes</a>, in Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, Volume 4992/2008, Springer-Verlag.
%H A003285 A. J. van der Poorten, <a href="https://pdfs.semanticscholar.org/c50f/609dc9078d6873ece1002aee061c4e5eab04.pdf">Fractional Parts of the Period of the Continued Fraction Expansion of Quadratic Integers</a> [Refined and revised text of a talk given at the 2nd Conference of the Canadian Number Theory Association, Vancouver, 1989]
%H A003285 A. J. van der Poorten, <a href="https://web.archive.org/web/*/http://www-centre.mpce.mq.edu.au/alfpapers/a075.pdf">An introduction to continued fractions</a>, Unpublished.
%H A003285 A. J. van der Poorten, <a href="/A007400/a007400_4.pdf">An introduction to continued fractions</a>, Unpublished [Cached copy]
%H A003285 H. C. Williams, <a href="http://www.jstor.org/stable/2007664">A Numerical Investigation Into the Length of the Period of the Continued Fraction Expansion of Sqrt(D)</a>, Mathematics of Computation, Vol. 36 (1981), No. 154, pp. 593-601.
%p A003285 f:= n ->  if issqr(n) then 0
%p A003285    else nops(numtheory:-cfrac(sqrt(n),'periodic','quotients')[2]) fi:
%p A003285 map(f, [$1..100]); # _Robert Israel_, Sep 02 2015
%t A003285 a[n_] := ContinuedFraction[Sqrt[n]] // If[Length[ # ] == 1, 0, Length[Last[ # ]]]&
%t A003285 pcf[n_]:=Module[{s=Sqrt[n]},If[IntegerQ[s],0,Length[ContinuedFraction[s][[2]]]]]; Array[pcf,110] (* _Harvey P. Dale_, Jul 15 2017 *)
%o A003285 (PARI) 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
%o A003285 (PARI) isok(n, p) = {localprec(p); my(cf = contfrac(sqrt(n))); setsearch(Set(cf), 2*cf[1]);}
%o A003285 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
%o A003285 (Python)
%o A003285 from sympy.ntheory.continued_fraction import continued_fraction_periodic
%o A003285 def a(n):
%o A003285     cfp = continued_fraction_periodic(0, 1, d=n)
%o A003285     return 0 if len(cfp) == 1 else len(cfp[1])
%o A003285 print([a(n) for n in range(1, 104)]) # _Michael S. Branicky_, Aug 22 2021
%Y A003285 Cf. A013943, A035015, A054269, A061490, A065938, A067280, A097853.
%K A003285 nonn,nice
%O A003285 1,3
%A A003285 _N. J. A. Sloane_