Using List comprehensions to solve Collatz conjecture

Question

Is there a way to use list comprehension's to workout Collatz conjecture without using a while statement or another method to append the n value to the ls without adding ls after each statement?

from random import choice
from time import sleep

n = choice([x for x in range(2, 99*99) if all(x%y != 0 for y in range(2, x))])
ls = []
ls.append(n)
while True:
    if n % 2 == 0:
        n = n // 2
        ls.append(n)
    elif n % 2 != 0:
        n = (3 * n) + 1
        ls.append(n)
    if n == 1:
        break
print(ls)

Nothing is wrong with a while loop but with larger values it seems to take way to long and personally for me there seems like a way to make this more compact — Jay_ gov, Mar 14 '22 at 20:04
a list comprehension isnt a replacement for iterative logic, you'd need to determine ahead of time how many iterations you'll need to perform — Sayse, Mar 14 '22 at 20:06
[This](https://stackoverflow.com/questions/42707435/using-while-loops-in-a-list-comprehension) might contain some useful discussion. — BrokenBenchmark, Mar 14 '22 at 20:06
There's no way to clean way to break in a comprehension (you could probably define some custom iterator but it would be ugly and confusing) — juanpa.arrivillaga, Mar 14 '22 at 20:08
@juanpa.arrivillaga I think [this](https://tio.run/##VYyxDoIwGIT3PsU5kLRIgsAiJDwJMaZCkSblb1M7lKdHqi7ecjd897ktLJaaq/P7Pnu7wkuajtKrsz5gXKweFWOE/rf5EDFbjwhNCX4qXhdo27xtBfQMaQyP2YZTj8sH3P7AKMRNMOa8psAHQtejyelcpStlNZR5KVBZ1gzfJMU9KXRQnhu5PibZgQpUh2jf3w) is not that terrible. — Kelly Bundy, Mar 14 '22 at 20:16

Kelly Bundy · Accepted Answer · 2022-06-15T07:14:33.700

One way ("missing" the initial number, but I don't think that's important for the purpose):

print(f'{n}:')
print([n := 3*n+1 if n%2 else n//2
       for _ in iter(lambda: n, 1)])

Output for n = 92:

92:
[46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

And one (ab)using a list comp, based on kolypto's:

print([memo
       for memo in [[n]]
       for n in memo
       if n == 1 or memo.append(n//2 if n%2==0 else n*3+1)
      ][0])

Output for n = 92:

[92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

I still think the while loop is the appropriate way, but it turns out it's not a lot faster. Times for solving all n from 1 to 5000:

 78 ms  while_loop_ewz93
 87 ms  list_comp_Kelly
126 ms  list_comp_kolypto
 82 ms  list_comp_kolypto_Kellied

My iter(lambda: n, 1) simulates while n != 1:. More generally, while condition: can be simulated with iter(lambda: bool(condition), False). (The explicit bool isn't necessary if the condition already is a bool, for example iter(lambda: mystring.startswith('x'), False).)

Benchmark code (Try it online!) with ewz93's and kolypto's modified to also not include the start number (for fairer comparison):

from timeit import repeat

def while_loop_ewz93(n):
    ls = []
    while n != 1:
        n = n // 2 if n % 2 == 0 else (3 * n) + 1
        ls.append(n)
    return ls

def list_comp_Kelly(n):
    return [n := 3*n+1 if n%2 else n//2
            for x in iter(lambda: n, 1)]

def list_comp_kolypto(n):
    return [
        *(lambda memo: [
            memo.append(n // 2 if n%2==0 else n*3+1) or memo[-1]
            for n in memo
            if memo[-1] != 1
        ])([n])
    ]

def list_comp_kolypto_Kellied(n):
    return [
        memo
        for memo in [[n]]
        for n in memo
        if n == 1 or memo.append(n//2 if n%2==0 else n*3+1)
    ][0]

funcs = [
    while_loop_ewz93,
    list_comp_Kelly,
    list_comp_kolypto,
    list_comp_kolypto_Kellied,
]

for _ in range(3):
    for func in funcs:
        t = min(repeat(lambda: list(map(func, range(1, 5001))), number=1))
        print('%3d ms ' % (t * 1e3), func.__name__)
    print()

That is actually pretty cool, however when I try this with with a fixed seed I get different results from OP's or my solution. It seems like the first item is always missing and n%2 causes an endless loop for me, but when I change these two parts it works for me and gives the exact same result. — ewz93, Mar 14 '22 at 20:41
@ewz93 Yes, I knew about the "missing" initial number, I don't think it necessarily matters but I mentioned that now. With the n%2 endless loop, I guess you mean you removed `== 0` from your solution? That negates the truth value, so you either need to do `not n%2` or switch the two possible outcomes. — Kelly Bundy, Mar 14 '22 at 20:47

ewz93 · Answer 2 · 2022-03-14T20:45:35.737

2

Well while is what you use when you don't know yet how many steps it will take and since that is kind of baked into the logic of finding the conjecture for a value there is not really a way around it. I personally think there is nothing bad about using while loops.

You can still make the code a bit more compact and readable while keeping the while loop, e.g. like this:

from random import choice

n = choice([x for x in range(2, 99 * 99) if all(x % y != 0 for y in range(2, x))])

ls = [n]
while n != 1:
    n = n // 2 if n % 2 == 0 else (3 * n) + 1
    ls.append(n)
print(ls)

Edit:

A slightly modified version of @Kelly Bundys answer does the trick for me to make it even more compact (let's not mention the readability though):

from random import choice

n = choice([x for x in range(2, 99 * 99) if all(x % y != 0 for y in range(2, x))])

ls = [n] + [n := n // 2 if n % 2 == 0 else (3 * n) + 1 for _ in iter(lambda: n, 1)]
print(ls)

edited Mar 14 '22 at 20:45

answered Mar 14 '22 at 20:13

ewz93

2,444
1
4
12

i had no idea you could add if and else values in the same line – Jay_ gov Mar 14 '22 at 20:16
1

These are called ternary operators or conditional expressions. They are (sometimes) a nice way to shorten code and make it more readable (but you should only use them if the if condition is something basic otherwise it gets hard to read). Check out this documentation: https://book.pythontips.com/en/latest/ternary_operators.html#ternary-operators – ewz93 Mar 14 '22 at 20:18
@ewz93 That page saying "They became a part of Python in version 2.4" makes me wonder how old and up to date that page is :-P – Kelly Bundy Mar 14 '22 at 20:23

score 1 · Answer 3 · answered Mar 18 '22 at 14:01

1

    seq = [
        *(lambda memo: [n] + [
            memo.append(n // 2 if n%2==0 else n*3+1) or memo[-1]
            for n in memo
            if memo[-1] != 1
        ])([n])
    ]

It's not a pure comprehension, but sort of.

The core idea was to introduce a named list, memo, which I can refer to as a variable and push values to

answered Mar 18 '22 at 14:01

kolypto

31,774
17
105
99

1

Included this and a more efficient version (only building one full-length list) in my benchmark now. – Kelly Bundy Mar 18 '22 at 20:52
"kolypto_kellied" :D :D :D – kolypto Mar 18 '22 at 23:59
1

Btw I like the idea of iterating over that memo list that has a one element head start. I'm not sure I've done or seen that before. In this case it's still an abuse of the list comprehension, since we're throwing away one list or another. But if we want a **list** of **multiple** sequences, for **multiple** start values, then at least my version becomes a rather proper list comprehension usage. [Demo](https://tio.run/##RY6xDsIwDET3fMUtSC1UlDYgsfhLogyVSEUk5KZJFr4@pC4CL/a9s60L7/xcWN9DLCXlKeYEgtEdrh1uVqnkViEKtaqQPi8RsgzP@5D@3K0bNUa4tT@DZfn7wc9VE2HAfnKeQnD8aLjvRzEPI9EF7pUc@KhPQ6tqmBA952aL1JbyAQ). – Kelly Bundy Mar 19 '22 at 00:24

score 0 · Answer 4 · answered May 20 '22 at 12:21

0

n=1024
ls=[n]
[ls.append(n//2 if n%2==0 else 3*n+1) for n in ls if n!=1]
print (ls)

answered May 20 '22 at 12:21

Juan Lozano

1

Using List comprehensions to solve Collatz conjecture

4 Answers4

Edit:

Linked

Related