CODEWITHSUNDEEP
pythonoptimization
Barend
Barend

Reputation: 43

Finding the collatz conjecture that uses n steps to get to one using python

So I'm trying to write some python code that lets me find the collatz conjecture based on the n steps used to get to 1.
I have some that works with small amount of steps, but large amount of steps takes way to long to calculate. So I was wondering if any of you know a way to speed up this process:

def cj(i):

out = []
out.append(i)
while i != 1:
    if i%2==0:
        i = i/2
        out.append(i)
    else:
        i = i*3+1
        out.append(i)
return out

This loops trough all numbers until one matches the amount of steps I'm looking for:

def cj_steps(n):
x = 1
while True:
    if len(cj(x))-1 ==  n:
        return x
    else:
        x +=1

This, like I said, works with small amount of steps, but take for instance 812 steps, what is already starting to take a lot of time. So I was hoping that someone could give me a hint or tip to how to improve the speed of this function.

Thank you.

Upvotes: 4

Views: 405

Answers (1)

wim
wim

Reputation: 363073

Here is an idea for you. Suppose that you compute the collatz sequence from 10:

>>> collatz(10)
[10, 5, 16, 8, 4, 2, 1]

You saw that there are 6 steps back to 1.

Suppose later that you're computing the collatz sequence from, say, 12. After four steps of computation:

>>> collatz(12)
[12, 6, 3, 10, ...

Hold on a minute!! It took 3 steps to get from 12 to 10. We already know that from 10, it takes 6 steps. So that tells us already that there are 6+3 steps from 12, without needing to bother to compute the sequence all the way back again.

Furthermore, if we ever see 12 again whilst expanding a collatz sequence, can remember that we are now 9 steps from unity.

How can you use this information to make your algorithm smarter?

Upvotes: 5

Related Questions