Understanding problem

[luciusFernatore]

(Perfect Numbers) An integer is said to be a perfect number
if the sum of its divisors, including 1 (but not the number itself), is
equal to the number. For example, 6 is a perfect number, because
. Write a function that determines
whether parameter is a perfect number. Use this function in
a program that determines and prints all the perfect numbers
between 1 and 1000. Print the divisors of each perfect number to
confirm that the number is indeed perfect. Challenge the power of
your computer by testing numbers much larger than 1000.

  ///Ejercicio 6_28

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <iomanip>

using std::setw;

void perfectNumbers(int);

int main()
{
	int numberLimits  = 100;
		
	
	for(int numbersTour = 1; numbersTour <= numberLimits; numbersTour ++)
	{
		cout << "The number: " << numbersTour << endl; 
		cout << "Divisors: ";
		perfectNumbers(numbersTour);
		cout << endl;
		cout << endl;	
	}
}
void perfectNumbers(int number)
{
	int divisorSum  = 0;
	
	for(int numericalCheck = 1; numericalCheck < number; numericalCheck ++)
	{
		if(number % numericalCheck == 0)
		{
			cout << numericalCheck << " ";
			divisorSum += numericalCheck;
		}
	}
	
	if(divisorSum ==  number)
	{	
		cout << " ------> YES perfect number";
	}
		
	if(divisorSum != number)
	{	
		cout << " ------> NOT  perfect number";
	}
}

[MikeStgt]

Nice. If you now find an odd Perfect Number you will go down in history.

[jonnin]

try finding factors in pairs.
*do not start at one, move 1 out as a special case.
if (number % x ==0)
then you just found 2 factors:
x, and number/x

if you do that, you only have to check to sqrt(number+1) (the +1 fixes occasional roundoff).

now eliminate ALL screen output, or redirect it to a file.
Trusting mike, I haven't studied the problem, but skip even values.
do that and then try a larger number like a billion. Be sure to compile in *release* or *optimized* settings. Is it subsecond?


Not fully understanding perfect numbers, what do you do for 9? It isn't a perfect number, but is the sum 7? If so, does your program work? Or is 4 (your answer for 9) correct? is 8 2+2+2+1 or 2+1? etc?

[anup30]

>

skip even values

why?

[MikeStgt]

Trusting mike, I haven't studied the problem, but skip even values.

No, do not. Premising everyone is informed about the subject before programming and/or coding I did not mark my hint as joke. Sorry. No odd Prefect Number is known yet.

[jonnin]

I meant skip odd values, based off the above. There may be one, but its not likely in the 'small' (yes, a billion is small) values you will play with for this assignment. You do half the work, get answer twice as fast. part of the assignment was to exercise the cpu, but part of exercising the cpu is also tweaking your code to run faster, and the changes I suggested are fairly simple (even better would be to generate the primes in the desired range and iterate only those for factor searching, or just hard-code an array of those primes if only doing a small test range, and there are other tweaks too, but starting to get way off the path with them and so far its 90% number theory and 10% learning much about code).

[luciusFernatore]

sorry i don't understand about even or odd perfect numbers. can you explain me in other words?

"Not fully understanding perfect numbers, what do you do for 9? It isn't a perfect number, but is the sum 7? If so, does your program work? Or is 4 (your answer for 9) correct? is 8 2+2+2+1 or 2+1? etc?"

those numbers are describing the divisors of each number.

[MikeStgt]

sorry i don't understand about even or odd perfect numbers. can you explain me in other words?

Words may tend to confusion: https://www.merriam-webster.com/dictionary/even
Regarding perfect numbers I refer to odd as n%2=1 and even as n%2=0.

[ne555]

> is 8 2+2+2+1 or 2+1? etc?
8 -> 4 + 2 + 1
you need to compute the «sum of its divisors, including 1 (but not the number itself)»

[jonnin]

hmm. that is annoying... 4 > sqrt and 4 isn't prime. here its the same as 2,2,2,1 but 9 breaks doing it that way. so you want any factors never duplicated not counting itself...

[anup30]

without optimization:

#include<iostream>
using namespace std;

int main(){
	int max=10000,sum;
	for(int i=1; i<=max; i++){
		sum=0;
		for(int j=1; j<i; j++){
			if(i%j==0) sum+=j;			
		}
		if(sum==i)cout << i << " is perfect number\n";
	}
return 0;	
}

output:

6 is perfect number
28 is perfect number
496 is perfect number
8128 is perfect number

[Duthomhas]

Divisors != prime factors.

I teach kids to get the divisors of numbers the same way. On a piece of paper (or two lines of your editor), write the number and underneath it a '1'. Then keep adding one to the lower number until you meet or exceed the value of the upper number:

    12  6  4
     1  2  3

We cannot write '4' on the bottom line, because it already exists on the top. We’re done. Use a std::set (or a std::vector, or an array, etc).

There are no odd perfect numbers in any range you can compute with native C++ integer values, so there is no point in checking odd numbers. For a quick read, this article (https://blogs.ams.org/mathgradblog/2013/07/25/odd-perfect-numbers-exist/) is much nicer than what you can find on Wolfram and the like.

Good job on using a function!

BTW, you can reduce your computation by directly using the formula 2^p-1(2^p-1), since all known perfect numbers are of that formula. You can do up to p=17 with an unsigned long long on a 64-bit machine.

(I just did p=31 using bignums. Oh, and BTW, https://en.wikipedia.org/wiki/List_of_perfect_numbers.)

Hope this helps.

[dhayden]

Be sure that your code does what the assignment requires.

Write a function that determines whether parameter is a perfect number.

First pass: bool isPerfect(unsigned number); // returns whether "number" is perfect

But in the next sentence we see:

Use this function in a program that determines and prints all the perfect numbers between 1 and 1000.

You don't want to compute the factors twice, so maybe:

// Determine if "number" is perfect. If yes then return true and put the factors in "factors".
// Otherwise return false and clear factors.
bool isPerfect(unsigned number, vector<unsigned> &factors);

The optimizations discussed so far are definitely interesting, but without this, you'll lose points on the assignment.

[Duthomhas]

When I wrote my version, I used std::optional:

std::optional <std::set <integer>> is_perfect( integer n )
{
  if (n & 1) return {};
  
  std::set <integer> divisors;

  ...

  return divisors;
};

int main()
{
  integer n = 33'550'336;
  auto ds = is_perfect( n );
  if (ds)
  {
    const char* sep[] = { "", " + " };
    std::cout << n << ": ";
    for (auto d : *ds) std::cout << sep[d != 1] << d << "\n";
  }
}

My integer was at various times unsigned long long and boost::multiprecision::cpp_int.