CODEWITHSUNDEEP
pythoncollatz
Dominik Lemberger
Dominik Lemberger

Reputation: 2436

python Reverse Collatz Conjecture

What the program should do is take steps and a number and than output you how many unique sequences there are with exactly x steps to create number.

Does someone know how I can save some memory - as I should make this work for pretty huge numbers within a 4 second limit.

def IsaacRule(steps, number):
    if number in IsaacRule.numbers:
        return 0
    else:
        IsaacRule.numbers.add(number)
    if steps == 0:
        return 1
    counter = 0
    if ((number - 1) / 3) % 2 == 1:
        counter += IsaacRule(steps-1, (number - 1) / 3)
    if (number * 2) % 2 == 0:
        counter += IsaacRule(steps-1, number*2)

    return counter

IsaacRule.numbers = set()

print(IsaacRule(6, 2))

If someone knows a version with memoization I would be thankful, right now it works, but there is still room for improvement.

Upvotes: 3

Views: 745

Answers (1)

c2huc2hu
c2huc2hu

Reputation: 2497

Baseline: IsaacRule(50, 2) takes 6.96s

0) Use the LRU Cache

This made the code take longer, and gave a different final result

1) Eliminate the if condition: (number * 2) % 2 == 0 to True

IsaacRule(50, 2) takes 0.679s. Thanks Pm2Ring for this one.

2) Simplify ((number - 1) / 3) % 2 == 1 to number % 6 == 4 and use floor division where possible:

IsaacRule(50, 2) takes 0.499s

Truth table: 

| n | n-1 | (n-1)/3 | (n-1)/3 % 2 | ((n-1)/3)%2 == 1 |
|---|-----|---------|-------------|------------------|
| 1 | 0   | 0.00    | 0.00        | FALSE            |
| 2 | 1   | 0.33    | 0.33        | FALSE            |
| 3 | 2   | 0.67    | 0.67        | FALSE            |
| 4 | 3   | 1.00    | 1.00        | TRUE             |
| 5 | 4   | 1.33    | 1.33        | FALSE            |
| 6 | 5   | 1.67    | 1.67        | FALSE            |
| 7 | 6   | 2.00    | 0.00        | FALSE            |

Code: 

def IsaacRule(steps, number):
    if number in IsaacRule.numbers:
        return 0
    else:
        IsaacRule.numbers.add(number)
    if steps == 0:
        return 1
    counter = 0
    if number % 6 == 4:
        counter += IsaacRule(steps-1, (number - 1) // 3)
    counter += IsaacRule(steps-1, number*2)

    return counter

3) Rewrite code using sets

IsaacRule(50, 2) takes 0.381s

This lets us take advantage of any optimizations made for sets. Basically I do a breadth first search here.

4) Break the cycle so we can skip keeping track of previous states.

IsaacRule(50, 2) takes 0.256s

We just need to add a check that number != 1 to break the only known cycle. This gives a speed up, but you need to add a special case if you start from 1. Thanks Paul for suggesting this!

START = 2
STEPS = 50

# Special case since we broke the cycle
if START == 1:
    START = 2
    STEPS -= 1

current_candidates = {START} # set of states that can be reached in `step` steps

for step in range(STEPS):
    # Get all states that can be reached from current_candidates
    next_candidates = set(number * 2 for number in current_candidates if number != 1) | set((number - 1) // 3 for number in current_candidates if number % 6 == 4)

    # Next step of BFS
    current_candidates = next_candidates
print(len(next_candidates))

Upvotes: 1

Related Questions