The Hailstone sequence of numbers can be generated from a starting positive integer, n by:

- If n is 1 then the sequence ends.
- If n is even then the next n of the sequence
`= n/2`

- If n is odd then the next n of the sequence
`= (3 * n) + 1`

The (unproven), Collatz conjecture is that the hailstone sequence for any starting number always terminates.

**Task Description:**

- Create a routine to generate the hailstone sequence for a number.
- Use the routine to show that the hailstone sequence for the number 27 has 112 elements starting with
`27, 82, 41, 124`

and ending with `8, 4, 2, 1`

- Show the number less than 100,000 which has the longest hailstone sequence together with that sequence’s length.

(But don’t show the actual sequence!)

#include <iostream>
#include <vector>
#include <utility>
std::vector<int> hailstone(int i)
{
std::vector<int> v;
while(true){
v.push_back(i);
if (1 == i) break;
i = (i % 2) ? (3 * i + 1) : (i / 2);
}
return v;
}
std::pair<int,int> find_longest_hailstone_seq(int n)
{
std::pair<int, int> maxseq(0, 0);
int l;
for(int i = 1; i < n; ++i){
l = hailstone(i).size();
if (l > maxseq.second) maxseq = std::make_pair(i, l);
}
return maxseq;
}
int main () {
// Use the routine to show that the hailstone sequence for the number 27
std::vector<int> h27;
h27 = hailstone(27);
// has 112 elements
int l = h27.size();
std::cout << "length of hailstone(27) is " << l;
// starting with 27, 82, 41, 124 and
std::cout << " first four elements of hailstone(27) are ";
std::cout << h27[0] << " " << h27[1] << " "
<< h27[2] << " " << h27[3] << std::endl;
// ending with 8, 4, 2, 1
std::cout << " last four elements of hailstone(27) are "
<< h27[l-4] << " " << h27[l-3] << " "
<< h27[l-2] << " " << h27[l-1] << std::endl;
std::pair<int,int> m = find_longest_hailstone_seq(100000);
std::cout << "the longest hailstone sequence under 100,000 is " << m.first
<< " with " << m.second << " elements." <<std::endl;
return 0;
}

length of hailstone(27) is 112 first four elements of hailstone(27) are 27 82 41 124
last four elements of hailstone(27) are 8 4 2 1
the longest hailstone sequence under 100,000 is 77031 with 351 elements.

SOURCE

Content is available under GNU Free Documentation License 1.2.

*Related*