Strange loop behavior in Python

Question

The code:

total = 0

for number in xrange(10000):
    divisors = 0
    divisors2 = 0

    for dividend in xrange(1, number/2):
        if number % dividend == 0:
            divisors = divisors + dividend

    for dividend2 in xrange(1, divisors/2):
        if divisors % dividend2 == 0:
            divisors2 = divisors2 + dividend2

    if number == divisors2:
        total = total + number + divisors

print total

The code is supposed to generate amicable numbers(i.e. number that total number of divisors less than itself equal another number that's total number of divisors equal the original number, see Project Euler, problem 21) under 10,000 and add them as it finds them. It's generating 48, which is way too low.

The program ran a lot faster than I expected it to: I'm running through a lot of numbers and I know for a fact that this isn't a very fast way to get the proper divisors, so I suspected something was up with the loop, either that Python was just stopping unexpectedly, or was running the loops out of order. If I put a command to print divisors before the beginning of the next loop, it goes on forever, and tends to print long lines of the same number. Something strange is definitely going on here. I googled "strange loop behavior", and searched here, to no avail. I also checked [here].2

What's going on and what should I do about it?

Thank you in advance.

It might be helpful to wait until the end to sum all the amicable numbers. That way you can examine (print) that list and see what sort of numbers you are getting. — Joel Cornett
– Joel Cornett, Commented Oct 26, 2012 at 21:56
Also, Problem 21 doesn't ask for the total number of amicable numbers, it asks for the sum of all amicable numbers (under 10000). — Joel Cornett
– Joel Cornett, Commented Oct 26, 2012 at 21:57

stacktrace · Accepted Answer · 2012-10-26 22:17:11Z

3

Few issues here:

It should be

total = total + number

And, range(1,x) runs only till x-1. So, you need to specify range(1, n/2 + 1)

answered Oct 26, 2012 at 22:17

stacktrace

3191 silver badge5 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Alok Singhal · Accepted Answer · 2012-10-26 22:06:40Z

2

xrange(1, n)

gives you numbers from 1 ... n-1. To get numbers from 1 ... n, you will need to do xrange(1, n+1). You make this mistake twice in your code.

You are also not checking for the condition about a != b in the original problem.

edited Oct 26, 2012 at 22:06

answered Oct 26, 2012 at 21:59

Alok Singhal

96.9k21 gold badges131 silver badges158 bronze badges

4 Comments

Roman Davis Over a year ago

Fixed the problem. Thought I had fixed it already. Than you. Why should I check for that condition?

Alok Singhal Over a year ago

Let's take 28. The sum of its factors (1, 2, 4, 7, 14) is 28. The sum of the factors of the result is of course 28 again. But (28, 28) is not an amicable pair because the two numbers must be different. In other words, you need to make sure number and divisors are not equal, but number and divisors2 are equal.

Alok Singhal Over a year ago

Also, by adding number + divisors to the total, you are double counting. You will add this pair again when number and divisors swap values in a next iteration of the loop (unless number == divisors, but those cases need to be not counted at all anyway). You can change that part of the code to just total = total + number.

Roman Davis Over a year ago

Ah. I wasn't sure. The question was vague. I anticipated the problem and it's an easy fix: total \ 2.

Joel Cornett · Accepted Answer · 2012-10-26 22:35:00Z

1

Your algorithm's broken. Let's take the amicable number given in the example, 284, and run it through your code:

number = 284
divisors = divisors2 = 0

for dividend in range(1, number/2): #goes through all the numbers (1, 2, ..., 141)
    if not number % dividend: divisors += dividend 

#divisors = 78

for dividend2 in range(1, divisors/2): #goes through all the numbers (1, 2, ..., 38)
    if not divisors % dividend2: divisors2 += dividend2

#divisors2 = 51

if number == divisors2:
    #number != divisors2, because 284 != 51
    #the amicable number never gets added to your sum

answered Oct 26, 2012 at 22:35

Joel Cornett

24.8k9 gold badges69 silver badges91 bronze badges

1 Comment

Roman Davis Over a year ago

Very comprehensive. Thank you very much.

Collectives™ on Stack Overflow

Strange loop behavior in Python

3 Answers 3

Comments

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related