Finding a perfect number.

[gk245]

Trying to write a program that will figure out if a number is perfect
or not.

Here is my logic:

1) Read in the number
2) Split it up (number - 1)
3) Put all the split up numbers into an array
4) Figure out if the original number is evenly divisible by any of the
numbers in the array.
5) Add up only the numbers that devide the original number evenly in
the array.
6) Compare the total of these to the original number and give a yes or
no answer.

I started it, and here is how its coming out:

int main (void)

{
int number, i, split, total;

printf("Enter number: ");
scanf("%d", &number);


for (i =0 ; i <= number; i++)
{
int array[number];

split = number - 1;
number = split;
array[number] = split;

printf("%d", array[number]); //just to check if the array
worked.


}


}

Obviously, this isn't even close to the solution, but i am getting
something, at least. Ofcourse, the program skips '1' and prints out
the rest up to only 5 digits. It won't 'split' the number any more.

Anyhow, any hints would be great.

 

[Walter Roberson]

Trying to write a program that will figure out if a number is perfect
or not.

That's really an algorithm question, not a question about C.
algorithm questions are more topical in comp.programming and
other similar newsgroups.

Here is my logic:

1) Read in the number
2) Split it up (number - 1)
3) Put all the split up numbers into an array

I don't understand what you mean by "split it up", and I do not
understand how (number - 1) (step 2) is going to give you the
several numbers you expect to use to populate the array in step 3.

4) Figure out if the original number is evenly divisible by any of the
numbers in the array.
5) Add up only the numbers that devide the original number evenly in
the array.
6) Compare the total of these to the original number and give a yes or
no answer.

[OT for comp.lang.C]

You can do noticably better than that.

A perfect number is always of the form (2**N-1)*(2**(N-1)) where
I am here using ** to denote exponentiation. So you can shift bits
of your trial number to the right until you find that the bottom bit
is no longer a zero, counting the number of shifts as you go.
If what is left over does not have exactly the same number of bits as
you shifted, and if those bits are not all 1's, then the number is not
perfect. If that condition is satisfied, then you can test the shifted
number to determine whether it is prime: if it is, then the original
is a perfect number.

For example,
6 = (2**2-1)*(2**(2-1)) = 3*2
28 = (2**3-1)*(2**(3-1)) = 7*4

I started it, and here is how its coming out:

int main (void)

{
int number, i, split, total;
printf("Enter number: ");
scanf("%d", &number);
for (i =0 ; i <= number; i++)
{
int array[number];

That syntax is valid in C99 but not in C89. C89 does not allow
declaration of arrays with a length which is dynamically determined.
(The closest C89 equivilent is to use malloc() or calloc() to dynamically
allocate the necessary memory.)

split = number - 1;
number = split;
array[number] = split;

None of these steps have involved your variable i, so you might
as well have done them outside of the loop instead of inside the loop.
(That would require moving the declaration of array.)

I am concerned that you are declaring your array to have number
elements in it, but you are looping (number+1) times: it hints that
whatever you are thinking of probably has an off-by-one error.

printf("%d", array[number]); //just to check if the array
worked.

}
}

Obviously, this isn't even close to the solution, but i am getting
something, at least. Ofcourse, the program skips '1' and prints out
the rest up to only 5 digits. It won't 'split' the number any more.

I don't know what you mean by "split" in this matter, but the "5 digits"
offers a clue as to a possible explanation.

Your variable number is declared as an int, and your scanf() format is
"%d" which is the appropriate format for an int. But what is the
maximum size of signed int that your implementation supports? If
your signed int happens to be 16 bits long, then 1 bit is {effectively}
needed for the sign and 15 bits for the value, which would give a maximum
possible int of 32767 (32768 in very obscure implementations.)
And 32767 happens to be exactly 5 digits long.

You could try changing to variables of type long and using a "%ld" format
for the scanf(). Be warned, though, that implementations often do not
allow large arrays to be declared in the C99 way your are proceeding,
so if you go much larger than 32768 you might find the program crashing
for lack of memory. The adjustment to make for that would be to
malloc() the necessary memory instead (after sanity-checking the
size of the number!).

 

[Bill Pursell]

Trying to write a program that will figure out if a number is perfect
or not.

Here is my logic:

1) Read in the number
2) Split it up (number - 1)
3) Put all the split up numbers into an array
4) Figure out if the original number is evenly divisible by any of the
numbers in the array.
5) Add up only the numbers that devide the original number evenly in
the array.
6) Compare the total of these to the original number and give a yes or
no answer.

I started it, and here is how its coming out:

int main (void)

{
int number, i, split, total;

printf("Enter number: ");
scanf("%d", &number);


for (i =0 ; i <= number; i++)
{
int array[number];

split = number - 1;
number = split;
array[number] = split;

printf("%d", array[number]); //just to check if the array
worked.


}


}

Obviously, this isn't even close to the solution, but i am getting
something, at least. Ofcourse, the program skips '1' and prints out
the rest up to only 5 digits. It won't 'split' the number any more.

Anyhow, any hints would be great.

A few observations:
1) it's not obvious what you mean by a "perfect number". I have no
interest in looking it up...
2) It's very odd that in your loop you are incrementing i and
decrementing number, so that the loop terminates when they meet half
way. I'm not sure that you intended that to happen.

 

[gk245]

Bill Pursell explained on 4/28/2006 :

Trying to write a program that will figure out if a number is perfect
or not.

Here is my logic:

1) Read in the number
2) Split it up (number - 1)
3) Put all the split up numbers into an array
4) Figure out if the original number is evenly divisible by any of the
numbers in the array.
5) Add up only the numbers that devide the original number evenly in
the array.
6) Compare the total of these to the original number and give a yes or
no answer.

I started it, and here is how its coming out:

int main (void)

{
int number, i, split, total;

printf("Enter number: ");
scanf("%d", &number);


for (i =0 ; i <= number; i++)
{
int array[number];

split = number - 1;
number = split;
array[number] = split;

printf("%d", array[number]); //just to check if the array
worked.


}


}

Obviously, this isn't even close to the solution, but i am getting
something, at least. Ofcourse, the program skips '1' and prints out
the rest up to only 5 digits. It won't 'split' the number any more.

Anyhow, any hints would be great.

A few observations:
1) it's not obvious what you mean by a "perfect number". I have no
interest in looking it up...
2) It's very odd that in your loop you are incrementing i and
decrementing number, so that the loop terminates when they meet half
way. I'm not sure that you intended that to happen.

Sorry, a perfect number is a number which in which its devisors (except
the number itself) add up to the original number. So, for example take
6. 6 can be "split-up" to 6,5,4,3,2,1. The devisors (which evenly
devide six,i.e: remainder is 0) here for 6 are 3, 2 and 1 (don't count
6 itself). 3, 2, and 1 add up to 6. So, 6 is a perfect number.

 

[Joe Smith]

Bill Pursell explained on 4/28/2006 :

Trying to write a program that will figure out if a number is perfect
or not.

Here is my logic:

1) Read in the number
2) Split it up (number - 1)
3) Put all the split up numbers into an array
4) Figure out if the original number is evenly divisible by any of the
numbers in the array.
5) Add up only the numbers that devide the original number evenly in
the array.
6) Compare the total of these to the original number and give a yes or
no answer.

I started it, and here is how its coming out:

int main (void)

{
int number, i, split, total;

printf("Enter number: ");
scanf("%d", &number);


for (i =0 ; i <= number; i++)
{
int array[number];

split = number - 1;
number = split;
array[number] = split;

printf("%d", array[number]); //just to check if the array
worked.


}


}

Obviously, this isn't even close to the solution, but i am getting
something, at least. Ofcourse, the program skips '1' and prints out
the rest up to only 5 digits. It won't 'split' the number any more.

Anyhow, any hints would be great.

A few observations:
1) it's not obvious what you mean by a "perfect number". I have no
interest in looking it up...
2) It's very odd that in your loop you are incrementing i and
decrementing number, so that the loop terminates when they meet half
way. I'm not sure that you intended that to happen.

Sorry, a perfect number is a number which in which its devisors (except
the number itself) add up to the original number. So, for example take 6.
6 can be "split-up" to 6,5,4,3,2,1. The devisors (which evenly devide
six,i.e: remainder is 0) here for 6 are 3, 2 and 1 (don't count 6 itself).
3, 2, and 1 add up to 6. So, 6 is a perfect number.

I suggest we #define devide divide
Joe

 

[Walter Roberson]

split = number - 1;
number = split;
array[number] = split;

None of these steps have involved your variable i, so you might
as well have done them outside of the loop instead of inside the loop.
(That would require moving the declaration of array.)

Ignore that bit -- I missed that you were modifying number as you
went. But it's rather odd, that you keep reducing the size of the
array as you go...

 

[Joe Smith]

split = number - 1;
number = split;
array[number] = split;

None of these steps have involved your variable i, so you might
as well have done them outside of the loop instead of inside the loop.
(That would require moving the declaration of array.)

Ignore that bit -- I missed that you were modifying number as you
went. But it's rather odd, that you keep reducing the size of the
array as you go...

[from earlier post]
That's really an algorithm question, not a question about C.

I disagree, as your reply made it into a question in C, a question I just
thought of for the duration of breakfast, and one which I would love to see
solved with the bit manipulations you mentioned. The lack of topicality is
from the OP's casual relationship with Funk and Wagnall's. Joe

 

[Eric Sosman]

gk245 wrote On 04/28/06 11:51,:

Trying to write a program that will figure out if a number is perfect
or not.

Here is my logic: [...]

Anyhow, any hints would be great.

Here are three, put as questions. If you ponder them
for a while, you may find them helpful:

- Is N divisible by N-1? More generally, what is the
largest integer that might be a divisor of a given
positive N? Still more generally, if U * V == N and
U <= V, what is the largest value U can possibly have?

- Why do you need an array? How many potential divisors
of a number do you need to have on hand simultaneously?

 

[Walter Roberson]

I disagree, as your reply made it into a question in C, a question I just
thought of for the duration of breakfast, and one which I would love to see
solved with the bit manipulations you mentioned.

Not really -- my reply was an algorithm implementable in C,
which is different than making it a C question.

The algorithm I gave was an outline of a method for testing an
arbitrary positive integer for perfectness. If one were trying to
generate perfect numbers, then one would make further use of the
fact that (2**N-1) {** denoting exponentiation} can only be prime
if N itself is prime. Numbers of the form 2**N-1 are known as
Mersenne Numbers, and have been extensively studied.

For more information on Mersenne primes, see
http://primes.utm.edu/mersenne/index.html
Note that only 43 of them are known so far (and therefor only 43
perfect numbers).

To participate in the search for perfect numbers, consider joining
GIMPS, the Great Internet Mersenne Prime Search by running
the Primenet software,
http://www.mersenne.org/prime.htm

Note: the scale of the numbers involved is *way* up there --
currently over 25 million bits (over 9 million decimal digits.)
You will not get very far on a perfect number search without
using much more advanced algorithms than I outlined.

 

[Keith Thompson]

I suggest we #define devide divide
Joe

Joe, was it really necessary to quote the entire article for the sake
of a spelling correction? Please snip whatever isn't relevant to your
followup.

 

[Joe Smith]

news:[email protected]...

[58 lines deleted]

[about ten lines and three misspellings deleted]

Joe, was it really necessary to quote the entire article for the sake
of a spelling correction? Please snip whatever isn't relevant to your
followup.

The removal of the serial, grating misspelling in the post would amount to
an appropriate K&R exercise. I'm certain the answer to your question is no.
Joe

 

[Andrew Poelstra]

Bill Pursell explained on 4/28/2006 :

Trying to write a program that will figure out if a number is perfect
or not.

Here is my logic:

1) Read in the number
2) Split it up (number - 1)
3) Put all the split up numbers into an array
4) Figure out if the original number is evenly divisible by any of the
numbers in the array.
5) Add up only the numbers that devide the original number evenly in
the array.
6) Compare the total of these to the original number and give a yes or
no answer.

I started it, and here is how its coming out:

int main (void)

{
int number, i, split, total;

printf("Enter number: ");
scanf("%d", &number);


for (i =0 ; i <= number; i++)
{
int array[number];

split = number - 1;
number = split;
array[number] = split;

printf("%d", array[number]); //just to check if the array
worked.


}


}

Obviously, this isn't even close to the solution, but i am getting
something, at least. Ofcourse, the program skips '1' and prints out
the rest up to only 5 digits. It won't 'split' the number any more.

Anyhow, any hints would be great.

A few observations:
1) it's not obvious what you mean by a "perfect number". I have no
interest in looking it up...
2) It's very odd that in your loop you are incrementing i and
decrementing number, so that the loop terminates when they meet half
way. I'm not sure that you intended that to happen.

Sorry, a perfect number is a number which in which its devisors (except
the number itself) add up to the original number. So, for example take
6. 6 can be "split-up" to 6,5,4,3,2,1. The devisors (which evenly
devide six,i.e: remainder is 0) here for 6 are 3, 2 and 1 (don't count 6
itself). 3, 2, and 1 add up to 6. So, 6 is a perfect number.

Well, you don't need to split it up that much; only those values x < n/2
are relevant, because no number can be evenly divided into more than its
half.

 

[Kevin D. Quitt]

If n is prime and (2^n - 1) is prime (i.e. a Mersenne prime), then
(2^(n-1)) (2^n - 1) is a perfect number.


The 39 known Mersenne prime exponents:

2 3 5 7 13 17 19 31 61 89
107 127 521 607 1279 2203 2281 3217 4253 4423
9689 9941 11213 19937 21701 23209 44497 86243 110503 132049
216091 756839 859433 1257787 1398269 2976221 3021377 6972593 13466917

(Note that there is no proof yet that there are no other Mersenne
primes between #37 and #39 other than #38.)

Perfect Number
Number of Digits
#1 1
#2 2
#3 3
#4 4
#5 8
#6 10
#7 12
#8 19
#9 37
#10 54
#11 65
#12 77
#13 314
#14 366
#15 770
#16 1,327
#17 1,373
#18 1,937
#19 2,561
#20 2,663
#21 5,834
#22 5,985
#23 6,751
#24 12,003
#25 13,066
#26 13,973
#27 26,790
#28 51,924
#29 66,530
#30 79,502
#31 130,100
#32 455,663
#33 517,435
#34 757,263
#35 841,842
#36 1,791,864
#37 1,819,050
#38 4,197,919
#39 8,107,892


I also have the list of the 39 known perfect numbers available, 8MB compressed.

 

[Walter Roberson]

If n is prime and (2^n - 1) is prime (i.e. a Mersenne prime), then
(2^(n-1)) (2^n - 1) is a perfect number.

I believe I said that earlier.

The 39 known Mersenne prime exponents:

If you had followed the link I gave, you would have found 43:
http://primes.utm.edu/mersenne/index.html

2 3 5 7 13 17 19 31 61 89
107 127 521 607 1279 2203 2281 3217 4253 4423
9689 9941 11213 19937 21701 23209 44497 86243 110503 132049
216091 756839 859433 1257787 1398269 2976221 3021377 6972593 13466917

The additional known ones are 20996011 2036583 25964951 30402457

(Note that there is no proof yet that there are no other Mersenne
primes between #37 and #39 other than #38.)

http://www.mersenne.org/status.htm
"All exponents below 17,546,00 have been tested at least once".

 

[Joe Smith]

"Walter Roberson"

Not really -- my reply was an algorithm implementable in C,
which is different than making it a C question.

[Walter's assertion]

To participate in the search for perfect numbers, consider joining
GIMPS, the Great Internet Mersenne Prime Search by running
the Primenet software,
http://www.mersenne.org/prime.htm

Note: the scale of the numbers involved is *way* up there --
currently over 25 million bits (over 9 million decimal digits.)
You will not get very far on a perfect number search without
using much more advanced algorithms than I outlined.

Indeed.

[snip]

To retort properly requires, among other things, access to UC, which I do
not have. As I understand you, you claim that a sufficient condition for a
number to be 'imperfect' is easily determined by bit manipulations,
something as germane to C as good humor.

My serious misgiving is that the problem has not been stated to my
satisfaction. I suspect that I shall not have this problem after I activate
the above link. Joe

----------

 

[googmeister]

A perfect number is always of the form (2**N-1)*(2**(N-1)) where

I think you mean "An even perfect number." The existence
of an odd perfect number is a long-standing open question.

 

[Walter Roberson]

[with respect to an algorithm outline I posted earlier in the thread]

To retort properly requires, among other things, access to UC, which I do
not have.

UC? You don't have access to uppercase?? Unlimited computing?
Microcontrollers? University of California or Cincinnati or Canberra
or Canterbury?

As I understand you, you claim that a sufficient condition for a
number to be 'imperfect' is easily determined by bit manipulations,
something as germane to C as good humor.

No, the bit manipulations I described only get you as far as
reducing down to a number that you then have to determine the
primality of. There is no known test for primality that is
easily determined by bit manipulations.

My serious misgiving is that the problem has not been stated to my
satisfaction.

A perfect number is a number for which the sum of the unique factors
(including 1) is equal to the number itself. For example,
28 is divisible by 1, 2, 4, 7, and 14, and 1+2+4+7+14 = 28.

That's all there is to the definition.

 

[Joe Smith]

[with respect to an algorithm outline I posted earlier in the thread]

To retort properly requires, among other things, access to UC, which I do
not have.

UC? You don't have access to uppercase?? Unlimited computing?
Microcontrollers? University of California or Cincinnati or Canberra
or Canterbury?

Said connection has been established, so I have an informed feel for the
problem. I would never Feit too long about precisely which alma matters.
Indeed, I was thrilled to hear of a rising star in the alma that didn't
matter too much to me.

No, the bit manipulations I described only get you as far as
reducing down to a number that you then have to determine the
primality of. There is no known test for primality that is
easily determined by bit manipulations.

Interesting. Yet I would bet dollars to donuts that a brute force assault
on 'imperfection' would use the bit manipulations and then , with the usual
suspects, determine prime versus just a usda number.

[query for a precise statement of the problem]

A perfect number is a number for which the sum of the unique factors
(including 1) is equal to the number itself. For example,
28 is divisible by 1, 2, 4, 7, and 14, and 1+2+4+7+14 = 28.

That's all there is to the definition.

In the same conversation that empowered me to *feel* the problem, it was
stated that the divisors add to 2N. Joe

 

[Kevin D. Quitt]

If you had followed the link I gave, you would have found 43:
http://primes.utm.edu/mersenne/index.html

Indeed - thanks. I've updated my lists of perfect numbers and mersenne primes.

 

[Joe Smith]

"Eric Sosman"

gk245 wrote On 04/28/06 11:51,:

Trying to write a program that will figure out if a number is perfect
or not.

Here is my logic: [...]

Anyhow, any hints would be great.

I might be the culprit whose insult chased away the OP, so
in the interest of follow-through:

Here are three, put as questions. If you ponder them
for a while, you may find them helpful:

- Is N divisible by N-1? Iff N ==2
More generally, what is the
largest integer that might be a divisor of a given
positive N? Still more generally, if U * V == N and
U <= V, what is the largest value U can possibly have?

Are U, V and N all positive integers?

- Why do you need an array? How many potential divisors
of a number do you need to have on hand simultaneously?

He needs a memory technique. Which, I dunno. Joe