Theory: Halting within a step limit

Simulate a process with a step limit, as a recogniser must.

What to build

A program that applies the Collatz rule from n and reports whether 1 is reached within k steps.

Requirements

  • Each step: if n is even, halve it; otherwise replace it by 3n + 1.
  • Print reaches 1 after S steps if it does within k steps, otherwise unknown after k steps.

Input

Line 1: n. Line 2: k.

Output

One line.

Constraints

1 ≤ n ≤ 10⁶; 0 ≤ k ≤ 10⁴.

Example

Input:

6
100

Output:

reaches 1 after 8 steps

Why it works

Simulation can confirm that a process stops, but when the limit runs out it can only say "unknown", never "never".

Examples

Example 1 · Input
6
100
Expected output
reaches 1 after 8 steps
Example 2 · Input
27
50
Expected output
unknown after 50 steps

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Apply the rule with a loop and count steps; stop as soon as n reaches 1 or the count reaches k.

Hint 2

A start of 1 takes 0 steps.

Solution

Show one correct solution (try it yourself first)
n = int(input())
k = int(input())
steps = 0
while n != 1 and steps < k:
    n = n // 2 if n % 2 == 0 else 3 * n + 1
    steps += 1
print(f"reaches 1 after {steps} steps" if n == 1 else f"unknown after {k} steps")

Lesson: Decidability and the halting problem →