the question can be found here

Problem 14

using the following code, a brute force attempt, it executes in approx 3.4 seconds

Function problem14() As String ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1) Dim startTime As DateTime = DateTime.Now() Dim longestChain As Integer = 0 Dim longestStart As Integer = 0 Dim maxValue As Integer = 1000000 Dim currNum As Int64 Dim currChain As Integer For x = 500001 To maxValue currNum = x currChain = 0 While currNum <> 1 If currNum Mod 2 = 0 Then currNum /= 2 Else currNum = (3 * currNum) + 1 End If currChain += 1 End While currChain += 1 If currChain > longestChain Then longestChain = currChain longestStart = x End If Next Dim Timespan As TimeSpan = DateTime.Now() - startTime Return longestStart & vbCrLf & "Execution time: " & Timespan.Seconds() & "s " & Timespan.Milliseconds() & "ms." End Function ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)

In an attempt to optimise it i wanted to create a table of any values i come across. That way if you follow the pattern and get to a number you have already come across you already know the chain length for that number and can simply add it on the the currChain length and stop looping that number. in theory it should be quicker.

However the following runs in approx 8.5 seconds.

Perhaps i am looking at it the wrong way or simply performing the checks on the hashtable takes longer than iterating the required number of times but could someone please explain the problem?

'optimised' code

Function problem14() As String ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1) Dim startTime As DateTime = DateTime.Now() Dim longestChain As Integer = 0 Dim longestStart As Integer = 0 Dim maxValue As Integer = 1000000 Dim cache As New Hashtable Dim currNum As int64 Dim currChain As Integer For x = 500001 To maxValue currNum = x currChain = 0 While currNum <> 1 If currNum Mod 2 = 0 Then currNum /= 2 If cache.ContainsKey(currNum) Then currChain += cache.Item(currNum) - 1 currNum = 1 End If Else currNum = (3 * currNum) + 1 If cache.ContainsKey(currNum) Then currChain += cache.Item(currNum) - 1 currNum = 1 End If End If currChain += 1 End While currChain += 1 cache.Add(x, currChain) If currChain > longestChain Then longestChain = currChain longestStart = x End If Next Dim Timespan As TimeSpan = DateTime.Now() - startTime Return longestStart & vbCrLf & "Execution time: " & Timespan.Seconds() & "s " & Timespan.Milliseconds() & "ms." End Function ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)

Thankyou

This post has been edited by **ghqwerty**: 02 December 2011 - 11:38 AM