不思議な数をRubyで検証シリーズ第2弾！（あと何回続くんだ？）
前回の第1回はこちら↓
ある範囲内の整数にカプレカ数があるかRubyで調べてみた
今回はタクシー数です。
前回同様Youtubeから題材をいただきました。
予備校のノリで学ぶ「大学の数学・物理」
ラマヌジャンの天才エピソードでおなじみ【タクシー数】
タクシー数とは
n 番目のタクシー数（タクシーすう、taxicab number、Ta(n)もしくはTaxicab(n)と表記される）とは、2つの立方数の和として n 通りに表される最小の正の整数と定義される。
「タクシー数」と言う名前はハーディが乗ったタクシーの番号1729についてそれがTa(2)であることをシュリニヴァーサ・ラマヌジャンが指摘したエピソードから来ている
引用元：Wikipedia
立法数とはある数を3乗した数のことです。
平方数が2乗なのでその進化系ですね。
そしてタクシー数は立法数の和（足し算）で何通りかに表されるものらしい
調べてみた
内容: x^3 + y^3でn通りに表される最小の正の整数（x, yの組み合わせの出力を含む）
条件: (1 ≦ x ≦ y ≦ 500)
def safe_invert(orig_hash)
orig_hash.each_key.group_by { |key| orig_hash[key] }.sort.to_h
end
hash = {}
(1..500).each do |y|
(1..500).each do |x|
hash.store([x, y], x ** 3 + y ** 3)
if x == y
break
end
end
end
taxi = []
n = 1
safe_invert(hash).each do |k, v|
if v.size == n
taxi.push("Ta(#{n}) => #{k}: #{v}")
n += 1
end
end
puts taxi
Ta(1) => 2: [[1, 1]]
Ta(2) => 1729: [[9, 10], [1, 12]]
Ta(3) => 87539319: [[255, 414], [228, 423], [167, 436]]
立法数の和として3通りで表せる最小の数が既に8753万とは、かなり大きな数ですね。
コード説明
順を追って説明します
簡略化するために範囲を小さくしてみていきましょう
条件: (1 ≦ x ≦ y ≦ 5)
hash = {}
(1..5).each do |y|
(1..5).each do |x|
hash.store([x, y], x ** 3 + y ** 3)
end
end
p hash
{[1, 1]=>2, [2, 1]=>9, [3, 1]=>28, [4, 1]=>65, [5, 1]=>126,
[1, 2]=>9, [2, 2]=>16, [3, 2]=>35, [4, 2]=>72, [5, 2]=>133,
[1, 3]=>28, [2, 3]=>35, [3, 3]=>54, [4, 3]=>91, [5, 3]=>152,
[1, 4]=>65, [2, 4]=>72, [3, 4]=>91, [4, 4]=>128, [5, 4]=>189,
[1, 5]=>126, [2, 5]=>133, [3, 5]=>152, [4, 5]=>189, [5, 5]=>250}
まずxとyに1〜5までの整数を与え.
それぞれ3乗した数を足した答え（和）を総当たりに調べてhashに追加していきましょう。
Hashクラスのstoreメソッドは、第一引数にkey、第二引数にvalueとする要素を追加するメソッドです。
hashの長さは 5 × 5 = 25通りになります。
表を見ていただいてお分かりの通り、xとyを入れ替えて求められる答えは同じです。
(x, y) = (2, 5)のときも、(x, y) = (5, 2)のときも答えは133。
これは2通りとは数えません。1通りです。
なので表の中で求める必要があるのはこの範囲
ということで、xとyが同じ場合はhashに要素を追加したらループを抜けるようにbreakします
hash = {}
(1..5).each do |y|
(1..5).each do |x|
hash.store([x, y], x ** 3 + y ** 3)
if x == y
break
end
end
end
p hash
{[1, 1]=>2,
[1, 2]=>9, [2, 2]=>16,
[1, 3]=>28, [2, 3]=>35, [3, 3]=>54,
[1, 4]=>65, [2, 4]=>72, [3, 4]=>91, [4, 4]=>128,
[1, 5]=>126, [2, 5]=>133, [3, 5]=>152, [4, 5]=>189, [5, 5]=>250}
続いて後半
特にメソッドの中が複雑です。
hashの中はkeyに[x, y]という配列、valueに立法数の和という要素が入っていましたが、
safe_invertメソッドを通すと、重複を考慮した上でkeyとvalueを逆にしたハッシュを作ります。
def safe_invert(orig_hash)
orig_hash.each_key.group_by { |key| orig_hash[key] }.sort.to_h
end
p safe_invert(hash)
{2=>[[1, 1]], 9=>[[1, 2]], 16=>[[2, 2]], 28=>[[1, 3]], 35=>[[2, 3]],
54=>[[3, 3]], 65=>[[1, 4]], 72=>[[2, 4]], 91=>[[3, 4]], 126=>[[1, 5]],
128=>[[4, 4]], 133=>[[2, 5]], 152=>[[3, 5]], 189=>[[4, 5]], 250=>[[5, 5]]}
each_key.group_by { |key| orig_hash[key] }で各keyをvalueに、
orig_hash[key](つまりvalue)をkeyとするハッシュを作ります。
key valueの反転です。
難しい発想ですがこちらを参考にしました
Hash#invert (Ruby 2.7.0 リファレンスマニュアル)
そしてsortでkeyの昇順に並べ替えると同時に配列に変換されてしまうので、
.to_hでハッシュに戻します。
x, yが1〜5までではこの処理のメリットがいまいちピンとこないと思いますが、
Ta(2)である1729が出現するよう範囲を1〜12まで広げると、出力結果でこのように…
{ ......, 1729=>[[9, 10], [1, 12]], ......}
valueの配列の長さが2つになり、1729の立法数の和としての表し方が2通りあることがわかりますね。
taxi = []
n = 1
safe_invert(hash).each do |k, v|
if v.size == n
taxi.push("Ta(#{n}) => #{k}: #{v}")
n += 1
end
end
puts taxi
最後に出来上がったハッシュに対してeachで
valueの配列の長さが1から順に最初にマッチしたものを空の配列taxiに追加し、
結果を出力して終了です。
余談
Wikipediaを見て知ってしまったのですが
Ta(4)は範囲を1〜19000まで広げないと出てきません。
試しに(1..19000)で実行してみましたが、
数分待っても処理が終わらず断念。
やはりRubyは網羅的な検証には向かないかも
もっといい書き方がありましたらコメントで教えてください！
(2020/07/05 追記)
コメントにて改良版をご提案いただきました！