CODEWITHSUNDEEP
python
Nasif Imtiaz Ohi
Nasif Imtiaz Ohi

Reputation: 1713

Why do I get a memory error?

Here is my code:

i=int(input("enter your number"))
j=int(input("enter your number"))
if i>j: #making x always greater than y
    x=i
    y=j
elif i<j:
    x=j
    y=i
else:
    print("invalid")
k=y
cyclelength=[]
while k<=x:
    list=[k]
    while k!=1:
        if(k%2==0):
            k=i//2
        else:
            k=3*k+1
        list.append(k)
    cyclelength.append(len(list))
    k+=1
print(y," ",x," ",max(cyclelength))

I get the following exception:

Traceback (most recent call last):
  File "C:/Python32/uva100.py", line 21, in <module>
    list.append(k)
MemoryError

Upvotes: 1

Views: 171

Answers (4)

jfs
jfs

Reputation: 414079

You might mean k //= 2 instead of k=i//2

def cyclelength(k):
    assert k > 0
    count = 1
    while k != 1:
       k = k // 2 if k % 2 == 0 else 3 * k + 1
       count += 1
    return count

k_with_max_cyclelength = max(range(y, x+1), key=cyclelength)

Or to get both:

k, max_cyclelength = max(((k, cyclelength(k)) for k in range(y, x+1)),
                         key=lambda pair: pair[1])

Upvotes: 5

Hugh Bothwell
Hugh Bothwell

Reputation: 56624

This looks like you're playing with the Collatz conjecture. Try

def get_int(prompt):
    while True:
        try:
            return int(raw_input(prompt))
        except ValueError:
            pass

def sequence_length(k):
    length = 0
    while k > 1:
        k = 3*k+1 if k&1 else k//2
        length += 1
    return length

def max_sequence_length(lo, hi):
    best_k, best_length = None, 0
    for k in xrange(lo, hi+1):
        length = sequence_length(k)
        if length > best_length:
            best_k, best_length = k, length
    return best_k, best_length

def main():
    lo = get_int("Enter the start number: ")
    hi = get_int("Enter the finish number: ")
    lo, hi = min(lo, hi), max(lo, hi)
    best_k, best_length = max_sequence_length(lo, hi)
    print("In {}..{}, max cycle length is {} at k = {}".format(lo, hi, best_length, best_k))

if __name__=="__main__":
    main()

Upvotes: 0

trutheality
trutheality

Reputation: 23455

I think you're going for

n=y
cyclelength=[]
while n<=x:
    k=n
    list=[k]
    while k!=1:
        if(k%2==0):
            k//=2
        else:
            k=3*k+1
        list.append(k)
    cyclelength.append(len(list))
    n+=1

Upvotes: 0

Simon Bergot
Simon Bergot

Reputation: 10582

Another problem in this block:

while k!=1:
    if(k%2==0):
        k //= 2
    else:
        k=3*k+1

k has the value 1 when you exit.

So you increment k to 2, reenter the while because k < x and reset k to 1

--> infinite loop

you have to define a new variable in you inner while or extract this block in another function

Upvotes: 2

Related Questions