2
\$\begingroup\$

Today I read this thing about the Collatz Conjecture and wanted to try and write a program that calculates all the numbers. If you have any idea how the code could be shortened, please tell me.

List<string> liste = new List<string>();
long num = 1;
        long z = num;

        while (num != 100000)
        {
            while (z != 1)
            {
                if (z % 2 == 0)
                {
                    z = z / 2;
                }
                else
                {
                    z = (z * 3) + 1;
                }
            }
            liste.Add(num + ": " + z);
            Console.WriteLine(num+": "+z);
            finalnumber = z;
            num++;
        }

            string path = @"N:\Desktop\test.txt";
            File.Delete(path);
            for (int i = 0; i < liste.Count; i++)
            {
                string appendText = ""+liste[i]+"" + Environment.NewLine;
                File.AppendAllText(path, appendText);
            }
\$\endgroup\$
  • \$\begingroup\$ Welcome to codereview! Have you heard about caching? It can really speed up your code =) \$\endgroup\$ – N3buchadnezzar Jun 24 '16 at 17:22
  • \$\begingroup\$ @N3buchadnezzar no never heard of it, gonna google it \$\endgroup\$ – Devid Demetz Jun 24 '16 at 17:30
  • \$\begingroup\$ Here is one example mathblog.dk/project-euler-14. I am not fluent enough in C++ to write an answer. Hopwfully you will get some ideas from the link =) \$\endgroup\$ – N3buchadnezzar Jun 24 '16 at 17:33
  • 1
    \$\begingroup\$ @N3buchadnezzar Please write all suggestions as answers, not comments. \$\endgroup\$ – 200_success Jun 24 '16 at 17:36
1
\$\begingroup\$

Each time you call File.AppendAllText, you create a new files stream and close it afterwards. Therfore, you should not write the result into the file by calling File.AppendAllText n times. just use string.Join instead:

var content = string.Join(Environment.NewLine, list);
File.WriteAllText(content);

Your code seems not work correctly, because if z == 1 is reached (which is given as initial state), the inner while loop is not entered anymore. I suppose there is a z = num; missing at the end of the outer while loop.


And in the very unlikely event, that you find a start number where the collatz conjecture does not ends up with 1, your program remains in an endless loop and you will never find out which number it was ;).

\$\endgroup\$
1
\$\begingroup\$

Your code does everything at the same time. It calculates the numbers, it prints them and it even writes them to the file. You can focus better on each task if you do it separately so let's start agian...


First you want to calculate the numbers so write a function for it:

static IEnumerable<int> CalcCollatzConjecture(int z)
{
    var zQueue = new Queue<int>(3);
    var finalSequence = new[] { 4, 2, 1 };
    while(!zQueue.SequenceEqual(finalSequence))
    {
        if (z % 2 == 0)
        {
            z = z / 2;
        }
        else
        {
            z = (3 * z) + 1;
        }
        zQueue.Enqueue(z);
        if (zQueue.Count > finalSequence.Length) { zQueue.Dequeue(); }
        yield return z;
    }
}

As each sequence ends with [4, 2, 1] we can add it as a terminator to save some time and not calculating it over and over again. I picked a queue to store the last three zs.

When you have your numbers...

var collatzConjecture = CalcCollatzConjecture(1000000).ToList();

you can do whatever you want to do with them. You can print them (with a function):

static void PrintCollatzConjecture(IEnumerable<int> collatzConjecture)
{
    foreach (var z in collatzConjecture)
    {
        Console.WriteLine(z);
    }
}

or you can save them in a file like @JanDotNet showed it (write a function for it too).

\$\endgroup\$
0
\$\begingroup\$

If you have any idea how the code could be shortened, please tell me.

    ...
    long num = 1;
    ...
    while (num != 100000)
    {
        ...
        num++;
    }

Since the scope of num is the loop, you can not only shorten it but also improve the readability with for (long num = 1; num < 100000; num++).


        while (z != 1)
        {
            if (z % 2 == 0)
            {
                z = z / 2;
            }
            else
            {
                z = (z * 3) + 1;
            }
        }

This can be shortened and probably made faster by using a basic bitwise trick. x & -x selects the least set bit of x, so

        while (z != 4)
        {
            z = 3 * z / (z & -z) + 1;
        }

does almost the same thing: the only difference is that it does an extra z * 3 + 1 at the end, hence the changed loop condition.


Note: there is potential for integer overflow both in your original code and in all of the suggested changes so far: the intermediate values in Collatz chains can get very large. Ideally the code should check for that.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.