【Project Euler】コラッツの問題【プログラミング】
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【Project Euler】コラッツの問題【プログラミング】

2018-03-19 19:00

    Problem 14: Longest Collartz Sequence

    The following iterative sequence is defined for the set of positive integers:

    nn/2 (n is even)
    n → 3n + 1 (n is odd)

    Using the rule above and starting with 13, we generate the following sequence:

    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

    It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

    Which starting number, under one million, produces the longest chain?

    NOTE: Once the chain starts the terms are allowed to go above one million.

    これはコラッツの問題(https://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)と呼ばれるもので、ある自然数nを与えた時に、
    ・nが偶数:nを2で割る
    ・nが奇数:3倍して1を足す
    というもので、どんな値でも必ず1に戻るはずだというものです。この問題はいまだに解決されておらず、また1に戻らない数も見つかっていません。とても不思議な問題です…

    さて、今回はその問題に対して、百万未満の値を入れたときに最も長く試行を繰り返す値は?というものです。
    ・Python

    # モジュールを読み込む
    import numpy as np

    # 初期値を設定する
    values = np.arange(1, 10**6)
    maxVal = 0
    maxCount = 0

    for value in values:
     tmpVal = value
     count = 0
     
     # 1になるまで繰り返す
     while value != 1:
      # 奇数が偶数か判定する
      if value%2 == 0:
       value /= 2
      else:
       value = 3 * value + 1
     
     # 試行回数を数える
     count = count + 1

    if maxCount < count:
     maxVal = tmpVal
     maxCount = count

    ・C++



    広告
    コメントを書く
    コメントをするには、
    ログインして下さい。