根据Collatz猜想的循环次数来找到一个达到1的数字

本文关键字：数字 一个 猜想 Collatz 循环 根据 | 更新日期: 2023-09-27 18:08:42

基本上，我想写一个算法来找出哪个数字需要500次迭代才能达到1。我试了一些变化，但都不行。

下面是我的代码: 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace sequence4
{
    class Program
    {
        static void Main(string[] args)
        {
            long startingNumber = 1;
            long count = 0;
            while (count != 500)
            {
                startingNumber = startingNumber * 2;
                count++;
                startingNumber = startingNumber / 3 - 1;
                count++;
            }
            Console.WriteLine(count);
            Console.WriteLine(startingNumber);
        }
    }
}

编辑:更新版本的代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace sequence4
{
    class Program
    {
        static void Main(string[] args)
        {
            int number = 2;
            int count = 0;
            while (count != 500)
            {
                if (number % 2 == 0)
                {
                    number = 2 * number;
                    count++;
                }
                if (number % 2 != 0)
                {
                    number = (number / 3) - 1;
                    count++;
                }
            }
            Console.WriteLine(number);
            Console.WriteLine(count);
        }
    }
}

根据Collatz猜想的循环次数来找到一个达到1的数字

Collatz Conjecture的例子是:

考虑，我们有一个数字7，我们需要使用Collatz猜想到达1

  1. 7是奇数，所以我们使用算法3(7)+ 1 = 22
  2. 22是偶数，所以我们使用22/2 = 11
  3. 11是奇数，所以我们使用算法3(11)+ 1 = 34
  4. 34是偶数，所以我们使用算法34/2 = 17
  5. 17是奇数，所以我们使用算法3(17)+ 1 = 52
  6. 52是偶数所以我们使用算法52/2 = 26
  7. 26是偶数，所以我们使用算法26/2 = 13
  8. 13是奇数，所以我们使用算法13(3)+ 1 = 40
  9. 40是偶数所以我们使用算法40/2 = 20
  10. 20是偶数所以我们使用算法20/2 = 10
  11. 10是偶数所以我们使用算法10/2 = 5
  12. 5是奇数，所以我们使用算法5(3)+ 1 = 16
  13. 16是偶数所以我们使用算法16/2 = 8
  14. 8是偶数所以我们使用算法8/2 = 4
  15. 4是偶数所以我们使用算法4/2 = 2
  16. 2是偶数所以我们使用算法2/2 = 1

对于奇数:x = 3n + 1
对于偶数:x = n/2

对于7，我们使用了16次算法，得到1。因此，16为循环长度。

现在，如果我们以上面的例子为例，我们需要从底线反向移动500倍。对于反向迭代，我们使用:

为奇数

: x = (n - 1)/3
对于偶数:x = n * 2

现在，通过编程实现如下:

using System;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            double output = 1;
            const int iterations = 500;
            for (var i = 1; i <= iterations; i++)
            {
                output = GetOutput(output);
                Console.WriteLine("Number after {0} iterations is: {1}", i, output);
            }
            Console.WriteLine("Required Number is: {0}", output);
            VerifyResult(output, iterations);
            Console.ReadKey();
        }
        private static double GetOutput(double input)
        {
            if (input == 1)
            {
                return 2;
            }
            var output = (input - 1) / 3;
            return output % 1 == 0 && output % 2 != 0 && output > 3 ? output : input * 2;
        }
        //To verify the above results we need this method
        private static void VerifyResult(double output, int iterations)
        {
            //-------------------------VERIFICATION-----------------------
            Console.WriteLine("Press any key to check iterations in reverse");
            Console.ReadKey();
            Console.WriteLine("Running validation process ...");
            var n = output;
            var max = n;
            var count = 0;
            Console.WriteLine("{0} (starting number in Collatz Sequence)", n);
            while (n > 1)
            {
                n = n % 2 == 0 ? n / 2 : 3 * n + 1;
                count++;
                if (n > max) max = n;
                Console.WriteLine(n);
            }
            if (count == iterations) //match here iterations and outputs
            {
                Console.WriteLine("'n'nCONGRATULATION! Verification results matched. :-)'n'n");
                Console.WriteLine("There are {0} cycle length in the sequence", count);
                Console.WriteLine("The largest number in the sequence is {0}", output);
                Console.WriteLine("'n'n-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-");
                Console.WriteLine("'n'nREQUIRED NUMBER: {0}'n'n", output);
                Console.WriteLine("-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-'n");
                Console.WriteLine("'nPress any key to exit");
            }
            else
            {
                Console.WriteLine("Oops... Verification results are not matching. :-(");
            }
        }
    }
}

示例来源:3n+1猜想的算法指南

相关文章：