|
%I #21 Oct 23 2020 20:47:20
%S 1,2,3,3,2,8,15,15,6,24,3,2,12,7,3,61,5,80,11,6,30,59,46,28,42,127,14,
%T 12,2,44,7,32,13,233,8,20,10,13,19,77,3,22,33,23,132,113,33,7,23,75,
%U 27,42,75,71,15,3,73,61,60,11,43,41,15,159,17,54,32,72,59,2,13,5,38,116,69,90,133,300,95,207,105,302,74,110,173,97,93,74,6,47,138,132,107,96,86,114,47,457,24,156
%N a(n) is the smallest positive integer m such that n appears as the denominator of a convergent to sqrt(m).
%C For n > 2, a(n) <= ceiling(n/2)^2 - 1, since for m > 1, sqrt(m^2 - 1) has convergents (2m^2 - m - 1)/(2m - 1) and (2m^2 - 1)/(2m). Apparently, this bound is achieved only for n in {3, 4, 6, 7, 8, 10, 18}.
%C Is there an efficient algorithm for computing a(n)?
%t a[n_] := Module[{a, b, r, q, v}, If[n == 1, Return[1]]; For[m = 1, True, m++, If[IntegerQ[Sqrt[m]], Continue]; r = Sqrt[m] // Floor; a = 0; b = 1; q = {1, 0}; While[q[[2]] < n && b != 0, v = Quotient[r+a, b]; a = b v-a; b = (m - a^2)/b; q = {{0, 1}, {1, v}}.q]; If[q[[2]] == n, Return[m]]]];
%t Array[a, 100] (* _Jean-François Alcover_, Oct 23 2020, after PARI code *)
%o (PARI) { A338307(n) = my(a,b,r,q,v); if(n==1,return(1)); for(m=1,oo, if(issquare(m),next); r=sqrtint(m); a=0; b=1; q=[1,0]~; while(q[2]<n, v=(r+a)\b; a=b*v-a; b=(m-a^2)/b; q=[0,1;1,v]*q;); if(q[2]==n,return(m)); ); }
%Y Cf. A338308.
%K nonn
%O 1,2
%A _Max Alekseyev_, Oct 21 2020
|
