タクシー数をRubyで調べてみた

不思議な数をRubyで検証シリーズ第2弾！（あと何回続くんだ？）

前回の第1回はこちら↓
[ある範囲内の整数にカプレカ数があるかRubyで調べてみた](https://qiita.com/yosaprog/items/87956b49c259e7282274)

今回は**タクシー数**です。
前回同様Youtubeから題材をいただきました。

[予備校のノリで学ぶ「大学の数学・物理」
ラマヌジャンの天才エピソードでおなじみ【タクシー数】](https://youtu.be/Y8ji2smizYY)



# タクシー数とは
> n 番目のタクシー数（タクシーすう、taxicab number、Ta(n)もしくはTaxicab(n)と表記される）とは、**2つの立方数の和**として n 通りに表される最小の正の整数と定義される。
「タクシー数」と言う名前はハーディが乗ったタクシーの番号1729についてそれがTa(2)であることをシュリニヴァーサ・ラマヌジャンが指摘したエピソードから来ている

> 引用元：[Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%BF%E3%82%AF%E3%82%B7%E3%83%BC%E6%95%B0)

**立法数**とは**ある数を3乗した数のこと**です。
平方数が2乗なのでその進化系ですね。

![スクリーンショット 2020-07-04 18.31.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/358307/da25100f-5659-0ff4-c527-4e076a77fdf2.png)


そしてタクシー数は立法数の和（足し算）で何通りかに表されるものらしい


#調べてみた

内容: `x^3 + y^3`でn通りに表される最小の正の整数（`x, y`の組み合わせの出力を含む）
条件: `(1 ≦ x ≦ y ≦ 500)`

```taxi.rb
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
```

```rb
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)`

```taxu.rb
hash = {}

(1..5).each do |y|
  (1..5).each do |x|
    hash.store([x, y], x ** 3 + y ** 3)
  end
end

p hash
```

```rb
{[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通りになります。

![スクリーンショット 2020-07-04 18.43.14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/358307/e6421526-0584-1e8a-2a28-7fd935398ec2.png)

表を見ていただいてお分かりの通り、xとyを入れ替えて求められる答えは同じです。
`(x, y) = (2, 5)`のときも、`(x, y) = (5, 2)`のときも答えは`133`。
これは2通りとは数えません。1通りです。
なので表の中で求める必要があるのはこの範囲

![スクリーンショット 2020-07-04 18.57.40.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/358307/df95655f-d529-e489-b5bb-d508c9206738.png)

ということで、`x`と`y`が同じ場合は`hash`に要素を追加したらループを抜けるように`break`します

```taxu.rb
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
```

```rb
{[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を逆にしたハッシュを作ります。

```taxi.rb
def safe_invert(orig_hash)
  orig_hash.each_key.group_by { |key| orig_hash[key] }.sort.to_h
end

p safe_invert(hash)
```

```rb
{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 リファレンスマニュアル)](https://docs.ruby-lang.org/ja/latest/method/Hash/i/invert.html)

そして`sort`でkeyの昇順に並べ替えると同時に配列に変換されてしまうので、
`.to_h`でハッシュに戻します。

`x, y`が1〜5までではこの処理のメリットがいまいちピンとこないと思いますが、
`Ta(2)`である**1729**が出現するよう範囲を1〜12まで広げると、出力結果でこのように…

```rb
{ ......, 1729=>[[9, 10], [1, 12]], ......}
```

valueの配列の長さが2つになり、1729の立法数の和としての表し方が2通りあることがわかりますね。

```taxi.rb
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は網羅的な検証には向かないかも:sweat:

　

もっといい書き方がありましたらコメントで教えてください！

**(2020/07/05 追記)**
コメントにて改良版をご提案いただきました！