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.
This is the task and this is my solution:
#include <iostream>
using namespace std;
int n;
int start_n;
bool n_even = false;
int sequence_length = 0;
int longest_sequence = 0;
int longest_sequence_number;
int main()
{
for (n = 2; n <= 1000000; n++)
{
start_n = n;
cout << n << endl;
do
{
sequence_length += 1;
if (n % 2 == 0)
{
n_even = true;
}
else
{
n_even = false;
}
if (n_even == true)
{
n = n / 2;
}
else
{
n = 3 * n + 1;
}
} while (n == 1);
if (sequence_length > longest_sequence)
{
longest_sequence = sequence_length;
longest_sequence_number = start_n;
sequence_length = 0;
}
else
{
sequence_length = 0;
}
}
cout << "Number with the longest sequence: " << longest_sequence_number << endl;
int end;
cin >> end;
}
I tested both the evaluation of the sequence and the generation of n independently, and both work. However, when i put them together the floor loop generates 2, 5, 17, 53, 161, 485, 1457, 4373, 13121, 39365, 118097, 354293 and says the number with the longest sequence is 2.
Is there a problem with my for loop, do while loop, or both?
There are at least 2 problems in your code i can spot right away:
n, which you also use as counter in your for-loop. Don't do this, better change your for-loop to increment start_n and use n for the sequence or vice versa.while(n==1) - shouldn't it be while(n!=1) ?