"Rod Pemberton" <do_not_have@[EMAIL PROTECTED]
> wrote Re: OT: Errors in
Marcel's "Perfect Number code" examples?
[..]
> "The perfect number A can be characterized by a unique number n, where
> A = 2^n * (2^n-1 - 1). "
That should be "A = 2^n * (2^n+1 - 1)."
[..]
> "To check A, we must find the sum of all of the divisors of 2^n * (2^n-1
- 1),
> or, equivalently,
>
> [1] x1 = the sum of the divisors of 2^n
> +
> [2] x2 = the sum of the divisors of (2^n-1 - 1).
>
> According to Pythagoras, x1 = 2^n-1."
The '+' is wrong. The divisors of x1 should be multiplied with those
of x2 (when x1 has {2 4} and x2 {3 7}, then {6 14 12 28} are also
divisors).
The program code does it correctly (at least for the testable range).
I have attached the updated do***entation. It is still not very clear.
-marcel
DOC
(*
From Simon Singh's book: "Fermat's Last Theorem", Fourth Estate,
London 1997, ISBN 1-85702-669-1.
Pythagoras defined a Perfect Number as a number A whose divisors
add up to A itself. When this sum is larger than A it is called
'excessive', when it is smaller than A it is called 'defective'.
Example 1: divisors of 10 = {1 2 5}, Sum = 1 + 2 + 5 = 8.
10 is defective.
Example 2: divisors of 6 = {1 2 3}, Sum = 1 + 2 + 3 = 6.
6 is perfect.
Example 3: divisors of 12 = {1 2 3 4 6}, Sum = 1 + 2 + 3 + 4 + 6 = 16.
12 is excessive.
The first perfect number after 6 is 28: {1, 2, 4, 7, 14}.
The next are 496, 8,128, 33,550,336, 8,589,869,056.
Pythagoras found that a perfect number is the sum of a series
of consecutive rational numbers:
6 = 1 + 2 + 3
28 = 1 + 2 + 3 + 4 + 5 + 6 + 7
496 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 ... 30 + 31
8,128 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 ... 126 + 127
Pythagoras also found that the divisors of 2^n add up to 2^n - 1, i.e.,
2^2 = 4, Divisors 1, 2 Sum = 3 = 2^2 - 1
2^3 = 8, Divisors 1, 2, 4 Sum = 7 = 2^3 - 1
2^4 = 16, Divisors 1, 2, 4, 8 Sum = 15 = 2^4 - 1
Euclid found that perfect numbers are always the multiple of two numbers,
one a power of two, the other the next power of 2 minus 1:
6 = 2^1 * (2^2 - 1)
28 = 2^2 * (2^3 - 1)
496 = 2^4 * (2^5 - 1)
8,128 = 2^6 * (2^7 - 1)
As you can see, not *all* n qualify. Euclid proved that 2^(n+1)-1 has to
be
(a Mersenne) Prime.
State of the art (in 1997) was: 2^216,090 * (2^216,091 - 1) is perfect.
Observations
------------
The perfect number A can be characterized by a unique number n, where
A = 2^n * (2^n+1 - 1). So instead of looking for A we can also look for
its 'root' n.
To check A, we must find the sum of all of the divisors of
2^n * (2^n+1 - 1), or, equivalently,
[1] x1 = the sum of the divisors of 2^n
( some operation, see below )
[2] x2 = the sum of the divisors of (2^n+1 - 1).
According to Pythagoras, x1 = 2^n - 1.
The number 2^n - 1 is prime when n is a Mersenne number [Knuth]
{ 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 }.
So we only need to find x2 and verify that x2 = A - x1.
The simple case is where x2 is prime, in that case the divisors
of A are the divisors of x1, appended with these divisors * x2.
In general the divisors of A are div_x1 * div_x2, where the sets
div_x1 and div_x2 should not overlap (this is not completely accurate,
see the program notes).
*)
ENDDOC
|
