コラッツの問題

なんか問題出されてたのでやってみた。
~~問題の内容を曖昧にしか覚えてないけど確か~~
~~「1 から 20000の間でもっともステップ数の多いものをだしなさい」~~
~~的なものだった気がする。~~
問題見つけた↓
https://gist.github.com/kawasima/0a3953fd4d39c9c86546#file-02-md

# コラッツの問題
http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84%E3%81%AE%E5%95%8F%E9%A1%8C

# 愚直な実装

```scala
import scala.testing.Benchmark

/**
 * Created by FScoward on 2014/11/15.
 */
object Main extends Benchmark {
  
  def run: Unit = {
    val result = (2 to 100000).par.map{x =>
      (x, collatz(x))
    }.maxBy(_._2)
    
    println(result._1 + "が最大で、" + result._2 + "ステップを要しました。")
  }
  
  def collatz(n: Int, count: Int = 1): Int = {
    if (n == 1) {
      count
    } else if (n % 2 == 0) {
      collatz(n / 2, count + 1)
    } else {
      collatz(n * 3 + 1, count + 1)
    }
  }
}
```

`run 5`で実行

```
77031が最大で、351ステップを要しました。                                                                        
77031が最大で、351ステップを要しました。                                                                        
77031が最大で、351ステップを要しました。                                                                        
77031が最大で、351ステップを要しました。                                                                        
77031が最大で、351ステップを要しました。                                                                        
Main$   58      26      21      24      26
[success] Total time: 4 s, completed 2014/11/15 1:17:37
```

# 終わりに
CPUを最大限に使うがこれ以上0の数を増やすと全然応答返ってこない。
調べてみると113383が1000000000ステップ以上かかっているからっぽい。
※以下の結果は1000000000を超えたら止めるようにしてます。

```
[info] Running Main 5
113383が最大で、1000000001ステップを要しました。                                                                
113383が最大で、1000000001ステップを要しました。                                                                
113383が最大で、1000000001ステップを要しました。                                                                
113383が最大で、1000000001ステップを要しました。                                                                
113383が最大で、1000000001ステップを要しました。                                                                
Main$   2813    2669    2662    2659    2639
[success] Total time: 15 s, completed 2014/11/15 9:57:37
```

さて、チューニングって何したらいいんだろう。
どなたかこれより早く出来るという方がいれば教えて下さい。

# 追記
Int.MaxValueまでやってみた
Intの最大値でも足りない・・・
```
[info] Running Main 5
113383が最大で、2147483647ステップを要しました。                                                                
113383が最大で、2147483647ステップを要しました。                                                                
113383が最大で、2147483647ステップを要しました。                                                                
113383が最大で、2147483647ステップを要しました。                                                                
113383が最大で、2147483647ステップを要しました。                                                                
Main$   5834    5631    5635    5653    5634
[success] Total time: 33 s, completed 2014/11/15 10:11:35
```

# 追記2
1への収斂の仕方は同様になることを考えてゴニョゴニョすればもっと早くなる？
（数字が大きくなればなるほど）

# 追記3

会社の後輩に言われて気付いたのですが

intだと計算中に計算結果が溢れる・・・

エラーでないのか・・・

というわけで、BigDecimalで計算するように修正

```scala
  def collatz(n: BigDecimal, count: BigDecimal = 1): BigDecimal= {
    if (n == 1) {
      count
    } else if (n % 2 == 0) {
      collatz(n / 2, count + 1)
    } else {
      collatz(n * 3 + 1, count + 1)
    }
  }
```