Здесь кажется коварнее: иногда решение соответствует разложению на два составных множителя, например для
![$23023=7\cdot11\cdot13\cdot23$ $23023=7\cdot11\cdot13\cdot23$](https://dxdy-04.korotkov.co.uk/f/f/d/d/fddf650c86d38f0aa9f2ab109705294a82.png)
наилучшее приближение
![$\sqrt{23023}\approx\sqrt{4674}+\sqrt{6950}$ $\sqrt{23023}\approx\sqrt{4674}+\sqrt{6950}$](https://dxdy-03.korotkov.co.uk/f/6/1/b/61be80c6212d36188f456f36052cb06882.png)
соответствует разложению
![$\dfrac{11\cdot23}{7\cdot13}=2, 1, 3, 1, 1, 4, 2$ $\dfrac{11\cdot23}{7\cdot13}=2, 1, 3, 1, 1, 4, 2$](https://dxdy-04.korotkov.co.uk/f/b/8/4/b84fdbe7ba28ce0030afecd7baa62a7e82.png)
. Подручный инструмент для борьбы с цепными дробями:
Код:
fra_chfr_main(p)={sp=#p; numpmax=floor(sp/2); nmax=2^(sp-numpmax)*(2^numpmax-1); for(cnt=1,nmax,if(vecsum(binary(cnt))<=numpmax,print(fra_chfr(p,binary(cnt)))))};
fra_chfr(p,np0)={m=factorback(p); sp=#p; snp0=#np0; np=vector(sp,i,if(i>=sp-snp0+1,np0[i-sp+snp0],0)); m1=factorback(p,np); m2=m/m1; if(m1>m2,[m1,m2]=[m2,m1]);
a=contfrac(m2/m1); sa=#a; a[sa]=a[sa]-1; pq=contfracpnqn(a); x=pq[1,2]*pq[2,2]; y=pq[1,1]*pq[2,1]; d=fra_d(m,x,y); return([m1,m2,x,y,d]);};
Пример использования (на входе - массив простых делителей
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
, на выходе - печать всех возможных разложений на множители (иногда с дубликатами, тут я пока поленился сделать аккуратнее) и соответствующие им
![$x,y,d$ $x,y,d$](https://dxdy-01.korotkov.co.uk/f/0/7/b/07bbc71a629c611538e5cda39ee699eb82.png)
):
Код:
(23:49) gp > fra_chfr_main([7,11,13,23])
[23, 1001, 174, 19194, 4.5078730747833521573646101671686627188 E-7]
[13, 1771, 2180, 11034, 1.6797100425581026541502997663988349877 E-7]
[77, 299, 1122, 13980, 2.0800752218743054735222972986637040989 E-7]
[11, 2093, 3044, 9324, 1.5463421680150141156305087900261879303 E-7]
[91, 253, 4674, 6950, 1.4454141411589071551796186041444902486 E-7]
[143, 161, 72, 20520, 6.7775715710877483065151211079561307366 E-7]
[7, 3289, 470, 16914, 2.9218435717189735088011575289986968511 E-7]
[143, 161, 72, 20520, 6.7775715710877483065151211079561307366 E-7]
[91, 253, 4674, 6950, 1.4454141411589071551796186041444902486 E-7]
[77, 299, 1122, 13980, 2.0800752218743054735222972986637040989 E-7]