[RESOLVED] [2008] Almost Infinite Loop

[perito]

pfffffffftttttttttttt i waited 1 whole hour before giving up
this loop is almost infinite
i got this code...

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        'n → n/2 (n is even)
        'n → 3n + 1 (n is odd)
        Dim n As Long, ChainLength As Integer, LargestChain As Integer
        LargestChain = 0
        For n = 1 To 1000000
            ChainLength = 0
            Do Until n = 1
                If n Mod 2 = 0 Then
                    n = n / 2
                    ChainLength = ChainLength + 1
                Else
                    n = 3 * n + 1
                    ChainLength = ChainLength + 1
                End If
            Loop
            If ChainLength > LargestChain Then LargestChain = ChainLength
        Next
        TextBox1.Text = LargestChain
        TextBox2.Text = n
    End Sub

The question is the following:

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

n → n/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.

[Tom Sawyer]

Here's the main problem.

You're using n in your for loop. Then in the do loop, you're changing the value of n. The first time through, n=1, so it ignores the do loop and moves on. The next time through, n=2, so n is divided by 2, which makes n=1 and it moves on through the for loop, which makes n=2, so it's divided by 2, which makes n=1 and it moves on through the for loop, which makes n=2, so it's divided by 2, which makes n=1. Continue that forever.

This is actually an infinite loop, there's no almost about it. You're never actually doing any of the processing that you want.

[Tom Sawyer]

Try this instead:

        Dim bNum As Long = 0
        Dim bMaxNum As Long = 0

        Dim n As Long, ChainLength As Integer, LargestChain As Integer
        LargestChain = 0
        For n = 1 To 1000000
            ChainLength = 0
            bNum = n
            Do Until bNum = 1
                If bNum Mod 2 = 0 Then
                    bNum = bNum / 2
                    ChainLength = ChainLength + 1
                Else
                    bNum = 3 * bNum + 1
                    ChainLength = ChainLength + 1
                End If
            Loop
            If ChainLength > LargestChain Then

                LargestChain = ChainLength
                bMaxNum = n

            End If
        Next

According to my test, the number is 837,799 and it produces a chain that's 524 numbers long.

[perito]

your answer is correct
thx