Subscribe to Stuck in an Infiniteloop        RSS Feed
-----

Practical Numbers

Icon Leave Comment
This seems to be a popular topic as of late. The definition of a practical number:

wiki said:

a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct divisors of n.


For the definition, the wiki is a good resource, but for practical/implementation guidance, it's poor. The initial way to approach this is to iterate through 1 to number-1 and check to see if each can be expressed by the sum of the divisors. I haven't written a solution that follows this thought process, although I may at some point. This approach has large time complexity and can be tricky. Another way to approach this problem is to get the prime factors and use a formula based on the summation of these factors. I have yet to find a decent source that I can reference for this and as of this writing did not write a solution following this approach either.

So you're probably asking yourself, what do you have Knowles? Using the "properties" of practical numbers:

Quote

For every practical number the most recent divisor-summation must always be greater than or equal to the (current divisor – 1). Any number failing this property will not be a practical number. [Since every perfect number is a practical number the sum of the divisors must be equal to or greater than the number]


bool isPractical(int num){
	//if the number is less then zero or odd, return false immediately
	//Get the divisors of num
	//----Go through the divisors 
	//	  if the sum is greater then or equal to the most recent divisor-1 add it to the sum
	//	  otherwise return false 

	if(num < 0) return false;
	else if (num == 1) return true; //1 is a divisor of itself 
	else if (num&1) return false; //odd check 

	//divisors
	vector<int> divisors;
	divisors.push_back(1); //save ourselves an iteration
	for(int i = 2; i < num; i++){
		if((num % i) == 0)
			divisors.push_back(i);
	}
	int sum = 0;

	for(int i = 0; i < divisors.size(); i++){
		if (sum >= divisors.at(i)-1) sum += divisors.at(i);
		else return false;
	}

	return true;
}
int main(){

	//253 to show the practical numbers up to and including 252
	for(int i = 1; i < 253; i++){
		if(isPractical(i)){
			cout << i << " ";
		}
	}
	return 0;
}



The result from the above program:

Quote

1 2 4 6 8 12 16 18 20 24 28 30 32 36 40 42 48 54 56 60 64 66 72 78 80 84 88 90 96
100 104 108 112 120 126 128 132 140 144 150 156 160 162 168 176 180 192 196 198
200 204 208 210 216 220 224 228 234 240 252
Press any key to continue . . .


A list of the first few practical numbers, from here

Quote

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, 80, 84, 88, 90, 96,
100, 104, 108, 112, 120, 126, 128, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198,
200, 204, 208, 210, 216, 220, 224, 228, 234, 240, 252


Neat stuff. As I mentioned above there are quite a few ways to approach this problem (aren't numbers awesome?) so this one method certainly isn't the be all end all.

0 Comments On This Entry

 

January 2022

S M T W T F S
      1
2345678
9101112131415
161718192021 22
23242526272829
3031     

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    18 user(s) viewing

    18 Guests
    0 member(s)
    0 anonymous member(s)