3n+1

View as PDF

Submit solution

All submissions

Best submissions

Points: 3

Time limit: 1.0s

Memory limit: 16M

Problem type

Pick a positive integer $n$ ~n~. If it is odd, multiply it by three and then add one. Otherwise (if it is even), divide it by two. The positive integer obtained is the new $n$ ~n~, and this procedure is repeated.

It is believed that $n$ ~n~ will eventually become $1$ ~1~ (this is called the Collatz conjecture.) Computers have checked that any value of $n$ ~n~ less than $10^{20}$ ~10^{20}~ does, indeed, eventually become $1$ ~1~ if this procedure is applied enough times.

You will be given the value of $n$ ~n~. Determine how many times this procedure must be applied before $n$ ~n~ becomes $1$ ~1~.

Input Specification

The initial value of $n$ ~n~.

Output Specification

The number of operations we have to perform on $n$ ~n~ before it becomes $1$ ~1~.

Constraints

Any value of $n$ ~n~, initial or intermediate, will be less than $2^{31}$ ~2^{31}~.

Sample Input

Sample Output

Explanation

$n$ ~n~ will go through these steps:

$\displaystyle 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1$

Comments

0

stanwww commented on Oct. 30, 2024, 12:46 p.m.

The input data has been set so any intermediate results will be less than 2^31 so n is only 35655. Can you also check if new test cases are needed?

6

OneYearOld commented on Oct. 28, 2020, 1:23 p.m. ← edited →

The test data is very weak. $0 < n < 35655$ ~0 < n < 35655~.

1

QooModa commented on May 10, 2022, 10:15 p.m.

Genuine question.

How do you check the test data?

It would help me solve other problems, I think...

Thanks!

-1

Smug_Void commented on March 29, 2023, 3:20 p.m.

copy the input data and then just print it out

0

FlowerPollinator commented on Sept. 26, 2022, 11:06 p.m.

You don't, unless the problem originated from somewhere else