Equation wrong

Im trying to write a program that will generate the first 5 amicable pairs. When I run my program, it just generates 1 pair and the pair that it gives me is wrong. It gives me 221 and 330. The first pair should be 220 and 284. So I know somewhere in my equations something is wrong. I cant figure out what it is and I keep going over it and writing it down on paper but I get stuck. Could someone point me in the right direction?

Code:

#include<iostream>
using namespace std;

int main()
{
	int Answer;
	int Answer2;
	int Remainder;
	int Remainder2;
	int Sum1;
	int Sum2;
	int D;
	int F;

	Answer = 220;
	Sum1 = 0;
	D = 1;
	Sum2 = 0;
	F = 1;

	while(Answer <= 7000){
		D = Answer / 2;
		Remainder = Answer % D;
		if(Remainder == 0){
			Sum1 = Sum1 + D;
		}
		D++;
		if(Sum1 > Answer){
			Answer2 = Sum1;
			F = Answer2 / 2;
			Remainder2 = Answer2 % F;
			if(Remainder2 == 0){
				Sum2 = Sum2 + F;
			}
			if(Sum2 == Answer2){
				cout << Answer << " and " << Answer2 << " are amicable pairs.\n" << endl;
			}
			F++;
			Answer = Answer + 1;
		}
	}
	return 0;
}

Arnell22,

I recall discussing this topic in abstract algebra class, it was a class composed of myself and one other person. She was working on the education program, and I was a very interested observer for the most part...I didn't want to scare off the potential school teacher chasing down "green" ideas with the professor. I went and checked the internet, but I haven't gotten the book out yet....

First, I went to the Wikipedia article on amicable numbers: Amicable number - Wikipedia, the free encyclopedia. Then I followed a link in the references to MathWorld: Amicable Pair -- from Wolfram MathWorld. I then became interested in how to assemble an algorithm for constructing sequences of pairs amicable numbers, so the article from MathWork about the divisor function came in handy: Divisor Function -- from Wolfram MathWorld.

Now, I'm looking at your code again. This is what I've got for a walk-through...

The loop enters with answer = 220, d is set to 110 and remainder becomes 0.
sum1 is set to 110, and d is incremented to 111. Since 110 is not larger than 220 the loop condition is tested again, and 220 is indeed less than or equal to 7000.

Again answer is 220, d is set to 110 and remainder becomes 0.
sum1 is then incremented by 110 making it 220, and d is once again incremented to 111. Since 220 is not larger than 220, the loop condition is tested, and 220 is indeed less than or equal to 7000.

Now, as before, answer is 220, d is set to 110 and remainder becomes 0.
sum1 is then incremented by 110 making it 330, and d is once again incremented to 111. 330 is indeed larger than 220 we enter the latter conditional branch. Answer2 is set 330, f is set to 165 and remainder2 is zero. Thus sum2 is set to 165. 165 is not equal to 330, so f is incremented to 166 and answer is incremented to 221. The loop condition is tested, and 221 is indeed less than 7000.

The loop again begins, d is set to 110 (the result of integer division) but remainder is not zero. d is incremented to 111, and 330 is larger than 221. Answer2 is set to 330, f is set to 165 and remainder is indeed zero. Sum2 is increased by 165 making it 330. 330 is indeed equal to itself, thus 221 and 330 are printed as an amicable pair. F is incremented to 166, and answer is set to 222. The loop condition is tested and it continues.

What algorithm for calculating amicable numbers are you attempting to implement? I didn't find any like what you've got.... The sources that I cited earlier mentioned calculating a list of divisors and then comparing their sum to a pair's candidate. There were even some boundaries on the size of a counter-part in a pair when testing (brute force style).

Check out those articles and please check back in.

Best Regards,

I think I figured it out but now it's not doing anything when I run my program.

Code:

#include<iostream>
using namespace std;

int main()
{
	int Answer;
	int Answer2;
	int Remainder;
	int Remainder2;
	int Sum1;
	int Sum2;
	int D;
	int F;
	int Divisor;
	int Divisor1;

	Sum1 = 0;
	Sum2 = 0;
	Divisor = 1;
	Divisor1 = 1;

	cout << "Enter an interger:";
	cin >> Answer;

	while(Answer <= 7000){
		D = Answer / Divisor;
		Remainder = Answer % D;
		if(Remainder == 0){
			Sum1 = Sum1 + Divisor;
			Divisor++;
		}
		if(Sum1 > Answer){
			Answer2 = Sum1;
			F = Answer2 / Divisor1;
			Remainder2 = Answer2 % F;
			if(Remainder2 == 0){
				Sum2 = Sum2 + Divisor1;
				Divisor1++;
			}
			if(Sum2 == Answer2){
				cout << Answer << " and " << Answer2 << " are amicable pairs.\n" << endl;
			}	
		}
		Answer = Answer + 1;
	}
	return 0;
}

Arnell22, What does your walk through look like?

Best Regards,

Arnell22,

This is what I started for a walk-through: Initially sum1 and sum2 are zero, divisor and divisor1 are one. Suppose that answer is read in as a valid candidate (not necessarily a member of any pair) for a member of an amicable pair less than or equal to 7000...say answer is 220 (a known member of a pair) as before.

The loop continuation condition is tested, answer is indeed less than or equal to 7000 (as per the assumptions above). Then d is set equal to 220, because divisor is initially one. Remainder is set to zero because 220 is equal to 220. Sum1 is then set to 1 and divisor is incremented by one. One is not larger than 220, so answer is incremented to 221 and the loop condition is once again evaluated.

Because 221 (answer) is less than or equal to 7000, the loop proceeds to execute. D is set to floor(221/2) or 110, and remainder is set equal to 1. One is not equal to zero, and 1 (sum1) is not larger than 221 (answer). Answer is then incremented to 222, and the loop condition is evaluated.

As before 222 is indeed less than or equal to 7000, the loop proceeds to execute. D is set to 111, and remainder is set to 2. Since 2 is not equal to zero and one (sum1) is not larger than 222 (answer), answer is incremented to 223. The loop condition is again tested.

This procedure continues until divisor evenly divides answer. Alright, I see that's where you accumulate the sum of divisors for the smaller of an amicable pair...an assumption that would have been nice to know at the beginning of this exercise.

The body of the second conditional branch is concerned with accumulating the sum of the divisors for the candidate second of the pair i.e. a sum of answer's divisors incidentally larger than answer.

Why do you increment answer after you have started to accumulate the sum of a candidate pair's divisors? Perhaps there should be another loop flow control structure concerned with the sum of the divisors for the possible second of the pair.

What sort of inputs have you tested? Have any of them ever finished executing?

Best Regards,