2021年1月5日火曜日

逆順と平方(1)

 中嶋慧さんが,次のようなプログラムについての話題を提供していた。ある数nの逆順に並べた数をrev(n)とする。例えば,rev(123)は321である。このとき,rev(n^2)=rev(n)^2を満たすm桁の数nは,何個あるかという問題だ。pythonでは時間がかかるので,juliaにするとよいのではないかという提案だったが,残念ながら,工夫に乏しい10^8個の計算はやたら時間を食うだけだった(追伸:条件が rev(rev(k)^2) = k^2 であると誤解していたので,その後訂正したところ,中嶋さんの結果と一致した)。


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(m)
  cnt = 1
  kmax = Int64(ceil(10^(m-1)*sqrt(10)))
  for k in 10^(m-1)+1:kmax
    kr = reverse(k,m)
    m2 = Int(ceil(log10(k*k)))
    if(reverse(k*k,m2)==kr*kr)
# if(2000<=k<=2299)
# println(k,":",kr,":",kr^2,":",reverse(kr^2,m2),":",k^2)
# end
      cnt = cnt+1
    end
  end
  return cnt
end

function list(l)
  sum = 0
  for i in 1:l
    @time sum = sum + counter(i)
    println(i," : ",sum)
  end
end

list(9)
0.000003 seconds (6 allocations: 576 bytes)
1 : 4
0.000009 seconds (44 allocations: 4.469 KiB)
2 : 13
0.000097 seconds (434 allocations: 50.859 KiB)
3 : 37
0.000901 seconds (4.33 k allocations: 540.750 KiB)
4 : 100
0.011719 seconds (43.25 k allocations: 5.939 MiB)
5 : 253
0.145435 seconds (432.46 k allocations: 62.688 MiB, 12.05% gc time)
6 : 615
1.100731 seconds (4.32 M allocations: 692.869 MiB, 17.40% gc time)
7 : 1434
11.497505 seconds (43.25 M allocations: 7.088 GiB, 16.11% gc time)
8 : 3244
132.445766 seconds (432.46 M allocations: 77.329 GiB, 16.48% gc time)
9 : 7116

0 件のコメント:

コメントを投稿