0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

CodeIQ :「フィーバー・ナンバー」 問題の解答

0
Last updated at Posted at 2026-07-04

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でも解を求められるかもしれません。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?