探索を逆方向から攻める

整数の平方根をとったとき，小数点以下 1 ～ 6 桁が全て同じ数字になるような最小の整数を求めよ。

求める数 x の平方根の整数部分を a 小数部分を b とする。つまりその整数は (a + b) ^ 2 = a ^ 2 + 2 * a * b + b ^2 であるとする。
小数部分を小数点以下 6 桁まで考えると上の式で求められる数値は，整数 x より小さな実数になる。差がきわめて近い物を探索する。

b = 0.111111 * 1:9 # b は 0.111111 ～ 0.999999 の 9 種類
b2 = 2 * b
b.sq = b ^ 2
n = 100000 # 探索範囲上限
for (a in 1:n) {
  x = a * b2 + b.sq # 求める整数から a^2 を引いたものの近似値
  if (any(abs(round(x)-x) < 1e-6)) { # round(x) が実際の求めるべき整数から a^2 を引いたもの
    index = which.min(abs(round(x)-x))
    cat("(", a, "+", b[index], ") ^ 2 = ", (a+b[index])^2, "\n")
  }
}

( 55557 + 0.111111 ) ^ 2 =  3086592595
( 83333 + 0.666666 ) ^ 2 =  6944500000
>
> 55557.111111 ^ 2
[1] 3086592595

> sqrt(3086592595)
[1] 55557.111111 確かに小数点以下 6 桁が同じ数字

求める整数は，3086592595

計算所要時間は n = 100000 まで探索して（2 つの解を求めて） 0.3 秒