Kawazoe(@riverplus)さんのCodeIQの問題です。
元のページはリンク切れしていますが、こちらに問題と解答があります。
->https://posfie.com/@riverplus/p/26gXIcE
問題
平方数でない数で平方根を小数表示したときに、小数第1位から第6位に
同じ数字が並ぶもっとも小さな整数を求めてください。
小数 n 桁で小数部分がすべて同じ数字 を x とします。
求める数を z とし、√z 以下で √z に一番近い x を考えますと、
非平方数の平方根は無理数ですので x < √z < (x + 1/10^n)、z は整数
よって z = ceil(x^2) < (x+1/10^n)^2 となる最小の z を求め
平方根を計算します。
x の小数部分は 0.11..1(1がn個)*m(0<m<10) =
0.99..9(9がn個)/9*m = m * (1-1/10^n)/9)
なので、m を 1~9 まで変えながら求める数を探します。
Juliaで書いてみましたが、二進数の小数計算の誤差のためz=9で不正解です。
mが 9 の時 1/10^n を足すと整数になりますので、
mの範囲は 1~8 がよさそうですが 、x が大きくなると
(√z - 1/10^n)^2 +1 < z = (x+ 1/10^n)^2 となる可能性があります。
これを計算してみるとz > 5*10^(n-1) つまり x >= 5*10^(n-1)
一方 ceil(x^2) < (x+1/10^n)^2 が常に成り立つのは
x^2 + 1 <= (x+1/10^n)^2 つまり、5*10^(n-1) <= x の時ですので
求める x は x <= 5*10^(n-1) にあると考えられます、
5*10^(n-1)で重複するようですが、m=1 までに解が得られますので、
x の検索範囲を 1 から 5*10(n-1) とすればよいと考えました。
とはいえやはり小数の精度の問題は不安ですし、
多倍長整数を標準でサポートしているPicatで、
より誤差の出ない方法で書き直しました。
すべて10^n倍して整数の範囲で計算して、最後に10^nで割る方法です。
なお以前Picatにはplay groundが見当たらないと申しましたが、
Attempt This Online(https://ato.pxeger.com)
というところからrunをクリックしてPicatを選べば実行できます。
%Picat 3.9#7 ,vscode
main =>
foreach(I in 1..8),
solve(I),
end.
solve(N) => %やはり小数演算で誤差
printf("ここからはN = %d %n",N),
Flg = 0, %sqrt(4822453704)で誤差 U = 10^N
U = 10**N,
U2 = U*U,
D = (U-1) div 9,
I = 1,
M = 5 * U div 10,
while (I < M ,Flg =:= 0)
J := 1,
while (J < 9,Flg =:= 0)
X := U*I + J*D,
Y :=X+1,
N1 :=pow(X,2) // U2,
Z := (N1+1)*U2,
if (pow(Y,2) > Z) then
Z1 = N1 + 1 ,
Z2 = sqrt(Z1),
printf("%w : %.12f : %.12f n",Z1,Z2),
Flg := 1
end,
J := J +1
end,
I := I + 1
end.
この方法ではN=8が限界ですが、
N=3以降は Z2 の小数部分が0.88.. が続いていて、
整数部分はn-2桁で、10^(N-3)で割った値がが少しずつ小さくなっています。
Jeminiに聞いたら、zの整数部分をkとすると、
z = (k + (m/9))^2 - 1/9^2と考えられるので、
18*k*m + m^2 - 1 が 81 で割り切れなければなりません。
2*k*m + (m^2 - 1)/9 = 0 (mod 9)、よってm=8 の時 k = 8(mod 9)
また√z ≒ k + m/9 -1/(162*k) (テーラー展開)なので、
誤差範囲の考慮から、1/(k*162) <= m/9 * 1/10^n、
よって k >= 10^n / (18 * m) 、
m = 8 のとき k >= 10^n / 144 で一番小さく、10^(n-2)桁だそうです。
私にはこの議論が厳密性には欠けると思いますが、n<=8まではあっています。
これを利用すればもっと大きなNでも解を求められるかもしれません。