逆順と平方（３）

逆順と平方（２）からの続き

9桁までの範囲で考えるとしても，３億個のデータのうち条件を満足するのが高々7000個なので，ほとんど無駄な計算をしていることになる。そこで，プログラムは汚くとも，もう少し計算を簡略化できないかと考えた結果，12桁までの計算が数分程度で可能になった。2〜3桁分をまとめてループをまわしているが，この範囲でよいという証明はしたわけではなく，直感に頼っているのだった。

function reverse(n,m)
  nun=zeros(Int,m)
  nre=0
  for k in 1:m
    nun[k] = n % 10
    nre = nre + nun[k]*10^(m-k)
    n = div(n - nun[k],10)
  end
  return nre
end

function counter(n)
  a = [0 1 2 3 10 11 12 13 20 21 22 23 30 31 100 101 102 103 110 111 112 113 120 121 122 123 130 131 200 201 202 203 210 211 212 213 220 221 222 223 230 231 300 301 302 303 310 311 312 313]
  b = [50 4 14]
  c = [10^3 10 10^2]
  cnt=1
  kk = c[n%3+1]
  k1max = b[n%3+1]
  k2max = 1 + div(n+10,14)*49
  k3max = 1 + div(n+10,17)*49
  k4max = 1 + div(n+10,20)*49
  for k1 in 1:k1max
    for k2 in 1:k2max
      for k3 in 1:k3max
        for k4 in 1:k4max
          k=a[k1]+a[k2]*kk+a[k3]*kk*10^3+a[k4]*kk*10^6
          if(k!=0)
            m=Int(ceil(log10(k)+10^(-9)))
            kj=BigInt(k)^2
            mj=Int(ceil(log10(kj)+10^(-9)))
            kr=reverse(k,m)
            krj=BigInt(kr)^2
            if(reverse(kj,mj)==krj)
# println(k,":",kr,":",kr^2,":",reverse(k^2,mj))
              cnt=cnt+1
            end
          end
        end
      end
    end
  end
  return cnt
end

for i in 1:12
  @time println(i," : ",counter(i))
end

1 : 4
0.000491 seconds (176 allocations: 6.000 KiB)
2 : 13
0.000551 seconds (765 allocations: 22.258 KiB)
3 : 37
0.002469 seconds (3.68 k allocations: 96.281 KiB)
4 : 100
0.005823 seconds (18.99 k allocations: 466.195 KiB)
5 : 253
0.021409 seconds (81.69 k allocations: 1.886 MiB)
6 : 615
0.091992 seconds (346.74 k allocations: 7.780 MiB)
7 : 1434
0.441439 seconds (1.61 M allocations: 35.324 MiB, 11.21% gc time)
8 : 3244
1.616126 seconds (6.39 M allocations: 138.140 MiB, 11.31% gc time)
9 : 7116
6.780644 seconds (25.58 M allocations: 546.322 MiB, 13.04% gc time)
10 : 15200
28.310428 seconds (113.32 M allocations: 2.337 GiB, 13.25% gc time)
11 : 23284
108.389549 seconds (437.13 M allocations: 8.934 GiB, 13.71% gc time)
12 : 31368
417.966111 seconds (1.71 G allocations: 34.604 GiB, 14.30% gc time)