ACSU Programming Competition

26 September 1998

Problem 3 - Generation Gap


Description

The Uranoids have a very interesting life cycle. Every Uranoid is hatched on the first day of the year, and lives for exactly one year. They all die on the last day of the year. The next day, which is the first day of the following year, the next generation of Uranoids hatch, continuing the species. (A year might seem like a very short life span, but remember that one Uranian is over 84 Earth years.)

The population of Uranoids does not grow exponentially, as many other non-predated populations do. They grow according to the formula:

     p_{n+1} = { 0,           if p_n = 0 or 1
               { p_n / 2,     if p_n is even
               { 3 * p_n + 1, if p_n is odd
Uranoid scientists are worried that their species will eventually die out. Given the population in year 1, you are to determine the first year in which the Uranoid population is zero.

Input / Output

The first line of input will indicate the number of data sets. This number will be non-negative.

Each data set is a single positive integer. This is the Uranoid population in year 1. You are to output the message "Data set n: year m", where n is the data set number and m is the first year in which the Uranoid population is zero.

You are guaranteed that the Uranoid population will die out on or before year 30000.

Example

Suppose that in year 1, the Uranoid population is 3. The Uranoid population is zero in year 9.
Year       1  2  3  4  5  6  7  8  9
Population 3  10 5  16 8  4  2  1  0

Sample

Sample Input

5
1
2
3
49
806

Sample Output

Data set 1: year 2
Data set 2: year 3
Data set 3: year 9
Data set 4: year 26
Data set 5: year 22

Solution

Here is the solution by Daniel Gerstenzang in C++, and James Singh in Java.

Here is the test input:

10
1
2
3
49
806
2999
5050
9009
15051
30000
Here is the correct output:
Data set 1: year 2
Data set 2: year 3
Data set 3: year 9
Data set 4: year 26
Data set 5: year 22
Data set 6: year 50
Data set 7: year 43
Data set 8: year 41
Data set 9: year 210
Data set 10: year 180

Last updated 28 September 1998.

This page is maintained by Adam Florence. If there are any questions or corrections, please e-mail me.