2020年1月13日月曜日

ab+bc+cd=n

Mathtodonに@antimonさんがこんな問題を出していた。

【問題1】S(n) を「 ab+bc+cd=n (a,b,c,d≥1) の整数解の個数」とする(例: S(5)=5 )。 S(k)=S(k+1) となる最小の整数 k(≥3)を求めよ。

【問題2】kを 問題1 の解とする時、S(S(S(S(S(k))))) を求めよ。

で,@栄造さんにならって,juliaで解いてみた。
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
function s(n)
  m=0
  for b in 1:ceil(Int,(n-1)/2)
    for c in 1:ceil(Int,min((n-1)/2,n/b))
      for a in 1:ceil(Int,(n-c)/b-c)
        for d in 1 :ceil(Int,(n-a*b)/c-b)
          if n == a*b + b*c + c*d
#           println(a," ",b," ",c," ",d)
            m = m+1
          end
        end
      end
    end
  end
  return m
end

for k in 3:20
  println(k,":",s(k))
end

@time println(s(14))
@time println(s(s(14)))
@time println(s(s(s(14))))
@time println(s(s(s(s(14)))))
@time println(s(s(s(s(s(14))))))
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
3:1
4:2
5:5
6:6
7:11
8:13
9:17
10:22
11:27
12:29
13:37
14:44
15:44
16:55
17:59
18:68
19:71
20:81
44
  0.000135 seconds (38 allocations: 1.047 KiB)
319
  0.000084 seconds (36 allocations: 1.156 KiB)
4256
  0.001191 seconds (37 allocations: 880 bytes)
178474
  0.270975 seconds (187 allocations: 11.359 KiB)
13153386
788.437834 seconds (186 allocations: 10.188 KiB)

juliaをたまに使うと,割り算の整数化やかけ算記号が省略できないことなどでつまずく。工夫のないプログラムなので時間はやたらにかかってしまう。

0 件のコメント:

コメントを投稿