Project euler help

[ETAkoG1T]

I am doing project euler problem 23 now. I don't like to cheat but it got a bit frustrating, because the code I thought would work don't give me the right answer!! I don't want anyone to show their code just help me find the problem in mine. And btw there is no error or warning it is just the wrong answer.
Output:

Total: 220489500

Code:

#include <iostream>
#include "stdafx.h"
bool abundant(int num );
const int ArSize = 21000;
int list[ArSize];
int abundant_nums[ArSize] = {0};
int main()
{
	for(int i = 0;i<ArSize;i++)
		list[i] = i;
	int ar = 0;
	for(int i = 0;i<ArSize;i++)
	{
		if(abundant(i))
		{
			abundant_nums[ar];
			ar++;
		}
	}
	for(int i = 0, r = 0, x;;)
	{
		
		x = abundant_nums[i] + abundant_nums[r];
		list[x] = 0;
		r++;
		if(abundant_nums[r] == 0)
		{
			i++;
			r = 0;
		}
		if(abundant_nums[i] == 0)
			break;
	}
	int total = 0;
	for(int i = 0;i<ArSize;i++)
	{
		total += list[i];
	}
	std::cout << "Total: " << total;

	std::cin.get();
	return 0;
}



bool abundant(int num )
{
	if(num == 0)
		return false;
	int factors_sum = 0;
	for(int i = 1; i < num ;)
	{
		if(num % i == 0)
			factors_sum += i;
		i++;
	}
	if(factors_sum > num)
		return true;
	else 
		return false;
}

[ETAkoG1T]

Line 16:: abundant_nums[ar];
I fixed it it is now
abundant_nums[ar] = i;
But still wrong answer, new answer is: 166033432

[Mathhead200]

The for loop on line 20 looks suspicious, can you explain it?

[BlackSheep]

It finds the numbers that can't be written as the sum of abundant numbers by setting all the numbers in a list from 1-listmax to zero if they can be the sum.

1. Where'd you get arsize 21000? Shouldn't it be 28123?
2. Your loop on 20 does have an error. It increments i when the array abundant_nums[r] == 0, but any number that isn't abundant will be represented as 0.
3. You don't check to see if abundant_nums[i/r] is 0 before assigning the sum to x, and setting list[x] to zero. If either one is zero then it's just the abundant number itself and shouldn't be counted (since 0 isn't abundant)
4. In the loop at 12 ar and i have the exact same value.

Basically just find a value to represent unabundant numbers but doesn't lie within your domain. How about 28124?

[ETAkoG1T]

Thanks so much for the reply BlackSheep! Probably the most helpful I have got in this forum. The reason I used 21000 is because there isn't actually any number between 21000 and 28123 that can't be written as the sum of two abundant numbers. I quote from wikipedia:
"Every integer greater than 20161 can be written as the sum of two abundant numbers."
The number 28123 is the number found by mathematical analysis.
(yes kinda confusing)
I'll fix my problem and give you an update shortly :)

[cire]

list is too small (or you need to not do list[x] when x is out of range.)

That abortion of a for loop at line 20 needs to be refactored into the nested for loop it's trying to be. It is not currently correct.

[ETAkoG1T]

UPDATE:
(still not working)
Replies:
3. I tried to change this but gave the same total, I made some changes to the program that I think is good, but not entirely sure.
My program now:

#include <iostream>
#include "stdafx.h"
bool abundant(int num );
const int ArSize = 21000;
int list[ArSize];
int abundant_nums[ArSize] = {0};
int main()
{
	for(int i = 0;i<ArSize;i++)
		list[i] = i;
	int ar = 0;
	for(int i = 0;i<ArSize;i++)
	{
		if(abundant(i))
		{
			abundant_nums[ar] = i;
			ar++;
		}
	}
	abundant_nums[ar - 1] = -2;
	for(int i = 0, r = 0, x;;)
	{
		if(abundant_nums[i] != 0 && abundant_nums[r] != 0)
		{
			x = abundant_nums[i] + abundant_nums[r];
			list[x] = -1;
		}
		r++;
		if(abundant_nums[r] == -2)
		{
			i++;
			r = 0;
		}
		if(abundant_nums[i] == -2)
			break;
	}
	int total = 0;
	for(int i = 0;i<ArSize;i++)
	{
		if(list[i] != -1)
			total += list[i];
	}
	std::cout << "Total: " << total;

	std::cin.get();
	return 0;
}



bool abundant(int num )
{
	if(num == 0)
		return false;
	int factors_sum = 0;
	for(int i = 1; i < num ;)
	{
		if(num % i == 0)
			factors_sum += i;
		i++;
	}
	if(factors_sum > num)
		return true;
	else 
		return false;
}

[BlackSheep]

Remember to make sure you're not adding ANY abundant numbers <= 0 (you have a -2 in there somewhere...).

You'll also want to make sure 0 <= x < ArSize.

I made a few small changes to the program and it worked, so you're almost there.

EDIT: Although it really would be good to adopt a nicer for-loop structure. You're only using the syntax to declare variables. Use the break condition and the per-step-action (??) to describe the whole loop.
Like Cire said, this is the perfect problem for a nested for loop.

[Smac89]

Just some tips to make for faster and more concise code:

In your bool abundant(int):

if(factors_sum > num)
    return true; 
  return false;

Also do not check all the factors in the number. Just check all the numbers within a range equal to the square root of the number you are checking. i.e.

line 56: for(int i = 1; i < sqrt(num) ;)

Or for(int i = 1; i < pow(num, 0.5) ;)

I don't understand what you are doing in line 20. Why are you setting all the previous values to -2 wouldn't this just in the end fill every spot in the array with -2 except for the last value stored?

A few more words:
1. The question is asking you to find the sum of all the numbers below 28123 which cannot be written as the sum of 2 abundant numbers.

2. So if I were solving this question, I would first get all the abundant numbers who their sum is less than 28123. i.e. fill an array with 24, 32, 36, 40, 48, etc.

3. Then I would create a nested for-loop. The first for-loop in the nest will go through the values 1-28123 and the for-loop below will go through the array of abundant sums.
-if the value in the first for-loop is not equal to the value in the one below, continue adding the numbers from the first for-loop
-else skip that number and continue

Also try using dynamically allocated arrays:
int *Array = new int[1];

and you can resize it as you wish, you can use this function if you want:

int * Resize(int arr[], int length, int val)
{
  int * array2 = new int [length + 1];
  for (int J = 0; J < length; ++J)
    array2[J] = arr[J];
  
  array2[length] = val;
  
  delete[] arr;
  arr = NULL;
  
  return array2;
}

ex Array = Resize(Array, size, num)

[ETAkoG1T]

Remember to make sure you're not adding ANY abundant numbers <= 0 (you have a -2 in there somewhere...).

You'll also want to make sure 0 <= x < ArSize.

I made a few small changes to the program and it worked, so you're almost there.

You was right about the almost there part, I got the right answer now!!! :) And this was the only change I made from the most recent code I posted:
Line 5:: int list[ArSize * 2];
Line 9:: for(int i = 0;i<ArSize * 2;i++)

What you didn't understand, is that -2 is my technique for signalising the end of the array, (it will never even be able to add it because the loop at that point has ended). -1 was for the numbers that could be added together from abundant numbers. Kinda cool teqnique ey? (And a bit messy)

OMG, that feeling when you have solved a project euler problem :)

Smac89 :
Thanks for the tips, but I don't want to do advanced stuff yet, I am a beginner at c++ and want to follow the learning pattern in my book.

[Smac89]

OMG, that feeling when you have solved a project euler problem :)

Yup :D just solved number 47. And congratz on 23, I am working on that now using the method I described above, I will post here if it worked

[ETAkoG1T]

I had to jump over problem 18, and 22, because they were so hard!!
For problem 18, my problem is that after I have all the values in an array I don't know how to make it go through all the combinations. I guess I need some kind of algorithm and maybe some nested loops. I have a 3/4 dimensional brain, can you help me out on that one?

[ETAkoG1T]

Can I add you as friend?
this is mine:
11576035409494_6454364ad86a3c54da447d11b5eb6f70