Terminating Collatz Sequences

This problem focuses on the Collatz sequence (also known as the 3n+1 problem). Given a positive integer n, a sequence is generated as follows:

\( n \rightarrow \begin{cases} \frac{n}{2} & \text{if } n \text{ is even},\\ 3n+1 & \text{if } n \text{ is odd.} \end{cases}\)

The sequence is said to be terminating if it eventually reaches 1 (assuming it does not enter a cycle). You are to implement two functions:

• has_terminating_sequence(n): Returns True if the sequence starting from n terminates at 1, and False otherwise.
• find_terminating_sequences(n): Returns a list of all positive integers less than n for which the sequence terminates at 1.

The input will be a single integer n (read from standard input) and the output should be the list of numbers (from 1 to n-1) having terminating sequences, printed on one line separated by spaces.

inputFormat

The input consists of a single integer n (\(1 \le n \le 10^6\)) provided via standard input.

outputFormat

Output the list of positive integers less than n which have terminating Collatz sequences. The numbers should be printed in increasing order on a single line, separated by a single space. If no such number exists, output an empty line.

## sample

10

1 2 3 4 5 6 7 8 9