The longest Collatz chain
Take a natural number. If it is even, halve it; if odd, multiply by three and add one. Repeat until you get 1. The Collatz conjecture says that 1 is always reached, whatever number you start with; it has been checked by computer for all numbers below 2⁶⁸, but nobody has managed to prove it.
From 27 it takes 111 steps to reach one, and on the way the number climbs to 9232. For each n find the number from 1 to n whose path to one is the longest, and the length of this path in steps. If there are several such numbers, print the smallest.
Input
The first line holds q (1 ≤ q ≤ 100), then q numbers n (1 ≤ n ≤ 2·10⁶).
Output
For each n, the starting number and the number of steps.
Examples
Example 1
5 1 2 3 10 27
1 0 2 1 3 7 9 19 27 111
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The path from 6 goes through 3, the path from 7 through 11, 17, 13, 10, 5… How many times do different starting numbers recompute the same tail?
2The idea
Remember the path length steps[k] for each k. Go through k in increasing order: walk the path from k until the number drops below k, as the path length from there is already known. Usually this happens within a few steps, and for an even k at once.
3Walkthrough
The numbers on the path climb above n, up to 157 billion for starts up to two million, so remembering everything in an array is impossible. Nor is it needed here: remember only numbers up to n, and above that go step by step. Larger values could also be remembered in a dictionary, but the gain is small and the memory cost large.
All queries use the same steps, so the table is built once up to the largest n, and for the answer keep “the best start not above k”, an array that follows the running maximum.
In Go the values on the path do not fit in 32 bits: for starts up to two million they reach 1.6·10¹¹, so int64 is needed.
3+Solution
4Complexity
On average a few steps for each k before it drops below k: about O(n) for the whole table, plus O(1) per query. Without memory, about a hundred steps for each of the n numbers, and again for each query.
5Common mistakes
- Without memory. Correct, but the fourth test is two million whole paths, and then another million.
- 32-bit values. Already on the path from 113,383 the number climbs to 2,482,111,348, above 2³¹.
- Not the smallest start. With equal lengths, the answer is the smaller number.