2014-12-22

素数腕立て伏せ Advent Calendar 21日目 #prime_num_pushups

素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。
素数腕立て伏せについて : サルノオボエガキ


風邪を引いても熱が出ても構わず素数腕立て伏せやってて結局治ったわけだから、素数のお陰で全快したと言えまいか。
素数腕立て伏せ健康法、イケまいか。

21日目
50回で負け(合成数)


体力も戻ってきたみたいです。59を目指してたけど53にも届かなかったよ。


ところで50は2通りの方法で2つの平方数の和に表せす最小の数字らしいですね。(smallestttってバグってるのかななな)

50 is the smallesttt number with 2 representations as a sum of 2 squares:
50 = 1^2+7^2 = 5^2+5^2
50 - Wolfram|Alpha

ではこの条件に叶う2番めに小さい数字ってなんだろう?
まず$ x = a^2 + b^2 = c^2 + d^2 $として、a,b,c,dはそれぞれ異なる数でないといけない。(←追記:コレ違う)
では50のときは$ a = 1, b = 7 $ だったから$ a = 2 $ で幾つか計算してみよう。
2つの数の組合せを計算しないといけないけど、奇偶を考えればチェックする数が減らせますね。

\[
\begin{eqnarray}
2^2 + 7^2 & = & 53 \nonumber \\
3^2 + 6^2 & = & 45 (ダメ) \nonumber \\
5^2 + 6^2 & = & 61 (ダメ) \nonumber \\
4^2 + 5^2 & = & 41 (ダメ) \nonumber
\end{eqnarray}
\]

うーん、だめだった。では次は和の大きさも考えて候補を減らそう。和の大きい順に抑えていって目標の数より下回ったら終わりということ。

\[
\begin{eqnarray}
2^2 + 8^2 & = & 68 \nonumber \\
5^2 + 7^2 & = & 74 (最大の組合せはダメ) \nonumber \\
3^2 + 7^2 & = & 58 (残ってる組合せで最大の組合せもダメ) \nonumber
\end{eqnarray}
\]

これもダメすね。はい次!

\[
\begin{eqnarray}
2^2 + 9^2 & = & 85 \nonumber \\
7^2 + 8^2 & = & 113 (最大の組合せはダメ) \nonumber \\
6^2 + 7^2 & = & 85 (残ってる中で最大の組合せはビンゴ!)\nonumber
\end{eqnarray}
\]


おぉ、85が2番めに小さな(省略)な数らしいぞ!
たまには地道に計算してみるのもいいものだね〜。

念のため、プログラムで検算してみよう(もちろん使うのはClojure)。

user> (def squares (map (fn [x] (* x x)) (range 1 10)))
#'user/squares
user> (filter (fn [[k v]] (>= (count v) 4))
              (apply merge-with concat
                     (for [x squares, y squares :while (<= y x)] {(+ x y) [x y]})))
([65 (49 16 64 1)] [50 (25 25 49 1)] [85 (49 36 81 4)])
あれれ、85は正しいけど3番目だったみたいだ。(1,7)から(2,7)じゃなくて、(1,6)を調べれば65に行き当たってたのになー。 ということで、2通りの方法で2つの平方数の和で表せる2番めに小さい自然数は65でした(ついでに3番めは85)。


0 件のコメント: