Search Algorithms For Odd Perfect Numbers
by
Huen Y.K.
CAHRC, P.O.Box 1003, Singapore 911101
http://web.singnet.com.sg/~huens/
email: huens@mbox3.singnet.com.sg
(A short communication - 1st released: 6/1/98)
Abstract
In a previous paper, search algorithms for even perfect numbers and amicable
pairs were described and both were based on the same modifications to the equation
of divisibles taking the general form i/(z^i*(z^i-1)) [3,4,5]. This equation is perfectly general
as it
does not discriminate between even and odd perfect numbers. This is because the
modified equation of divisibles does not require any knowledge of Mersenne primes.
No odd
perfect number has ever been reported so far as it has been conjectured that
if these exist at all, these will be found in the 300 decimal digit region [1,2].
One advantage of the modified equation of divisibles is that it does not
make any assumptions about the nature of divisors. A perfect number, whether odd
or even will be found if the numerator coefficeint equals the power index of the
order variable in the denominator. The search is very thorough but very time
consuming especially at the big integer end. Some short cuts are suggested but
these make the search less thorough.
1. Introduction
Number theorists are more preoccupied with prime numbers than composite numbers
most probably because these are rare especially at the big end of the number axis.
Considering that there is an overwhelming ratio of composite numbers to prime numbers
the lack of interest on composite numbers seems strange. Amongst these rarities are
two well known problems, that of Perfect numbers and Amicable Pairs which have been
described in a previous paper [3]. The conventional method of search for even perfect
number is via the route of Mersenne primes. The defintion itself precludes any possibility
of finding odd perfect numbers since the multiplier 2^(p-1) is always even. The modified
equation of divisibles which takes the form i/(z^i*(z^i-1)) does not follow this path and
is perfectly general. Thus the search algorithm described in the previous paper for
even perfect number will display odd perfect numbers if these exist. However, it
must be pointed out that exhaustive search using Macsyma 2.2 in a Pentium is
out of the question since the search at the big integer end will be excruciatingly
slow. The algorithm is most suitable for computations using a symbolic package
which suggests that a powerful symbolic machine might be the answer.
2. Search Algorithms For Odd Perfect Numbers
Definition: A positive integer n is called a perfect number if it is equal to the
sum of all of its positive divisors, excluding n itself [1]
In the modified equation of divisibles shown in equation (1), note that the lower
bound of i starts from 1 instead of 2 because the divisor 1 is included as one of the
divisors by the above definition. The program lines shown in equation (2) is written in Macsyma 2.2 but can
be easily translated into Maple syntices.
Perf_z:taylor(sum( i/(z^i*(z^i-1)),i,1,ub),z,inf,ub); ...............(1).
Maple: Perf_z:=sort(series(sum(i/(z^i*(z^i-1)),i=1..ub),z=infinity,ub);
where ub is an integer upperbound. Odd perfect numbers, if these occur at all, can
only be found amongst odd composites. This would suggest that the range of search
for the index i in equation (1) should only include odd composite numbers. This is
computationally awkward since it means that the odd composite sequence must be
separately computed. Odd perfect numbers, if these exist at all, will appear in terms
where both the numerators
and the power indices of the order variables in the denominators are odd.
Theorem of Odd Perfect Numbers: Any odd perfect number is identifiable
by a term in the modified
equation of divisibles with both the numerator coefficient and the power index
to the denominator order-variable appearing as odd integers and these must be of the same magnitude.
Proof: An odd composite integer can only be expressed as the product of odd divisors,
but an even composite will always have the divisor 2 included. This means that the numerator
coefficient to an odd composite integer can only stay odd if the number of odd divisors
is odd. Thus keeping the denominator power index odd does not guarantee that the
numerator coefficient will always stay odd.
Odd integers with even number of odd divisors will never
qualify as odd perfect numbers. On the other hand an even composite integer can
have a numerator which
is odd so long as the number of odd divisors in the set is odd irrespective of how many
even divisors it has. The sum of divisors of an even integer can be odd but since
the integer itself is even, it can never result in an odd perfect number.
Thus an odd perfect number
is identified without exception by a term having an odd numerator coefficient and an odd power index in the
denominator and that these two integers must be of the same magnitude. Q.E.D.
This method is thorough and deterministic if odd perfect numbers exist. However
the computations will be painfully slow in the large integer ends. If the prevailing findings
that odd perfect numbers will only occur beyond the 300 decimal digit range is to be
believed, then the present
algorithm will not be effective using Macsyma 2.2 in a Pentium. However,
Macsyma is also ported to Symbolic Machines which should be powerful enough
to use this algorithm. This paper is confined to demonstrations of exploratory
methods at the low end of the natural number range. No odd perfect number
can be found in this range but the statistical findings do give some information
on whether odd perfect numbers could exist. This is not a rigorous algebraic
proof but the numerical findings do point to the existence of odd perfect numbers.
This is indicated by the values of odd numerator coefficients which straddle the
odd power indices of the denominator variables. Since half the terms in the
expansions contain odd integers, the probability of a hit, i.e., when
the numerator coefficient value equals exactly to the denominator power index value
is high.
3. Some Exploratory Examples
Example 1: Demonstration that the modified equation of divisibles also computes
for odd perfect numbers if these exist.
Perf_z:taylor(sum(i/(z^i*(z^i-1)),i,1,500),z,inf,500); .......(2).
Series expansions of equation (2) return three even perfect numbers are 6, 28, and
496 in equation (3). No odd perfect numbers are found
but the term 9/z^15 has odd numerator coefficient and odd power index to the z-variable.
This shows that the present algorithm does attempt to search for odd perfect numbers
even if none are found in the low end.
.....................1..........1.........1.......3........1........6.........1.........7.......4........8......1.......16
Perf_z := O(----) + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + --- + --- + ---
.......................500.......2........3.......4.........5........6.........7........8.......9......10.....11.....12
......................z..........z.........z.......z..........z........z.........z.........z........z.......z........z........z
...........1.....10......9.....15......1.....21......1......22.....11.....14.....1.....36.....6.......16.....13.....28
......+ --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + ---
............13...14.....15....16......17....18......19....20......21.....22....23......24.....25.....26....27....28
...........z......z.......z......z.........z......z.........z.....z.......z..........z.......z.......z........z........z........z......z
...............................................................................................................496
......+ ............................................................................................... + ------
................................................................................................................496
..............................................................................................................z
.....................................1
......+ ...................O(-------)
.......................................500 ............................................................................(3).
.....................................z
Example 2: To find the individual divisors, the numerator coefficient i is raised to
the power of variable x as shown in equation (4). Series expansions of equation (4)
give 16 terms in equation (5) of which the individual odd divisors of the 15th term
are 1, 3, and 5 which sums to the coefficient 9 as predicted in equation (5) (shown in
bold fonts).
Perf_z:taylor(sum(x^i/(z^i*(z^i-1)),i,1,16),z,inf,16);.......(4).
.....................................................2.....................3.....2......................4.....2..........3
....................1.........x.........x.......x + x......x........x + x + x........x........x + x + x......x + x
Perf_z := O(---) + ---- + ---- + ------ + ---- + ----------- + ---- + ----------- + ------
.....................50........2.........3.........4..........5.............6..............7............8................9
....................z.........z.........z..........z..........z..............z...............z.............z................z
....5.....2...................6.....4...3....2...................7...2...........5....3..........8....4....2
..x + x + x......x.......x + x + x + x + x......x.....x + x + x.....x + x + x....x + x + x + x
+ --------- + --- + ------------------ + --- + --------- + ---------- + -----------.........(5).
...........10........11..................12..............13..........14..............15.................16
.........z...........z...................z..................z............z.................z...................z
Example 3: Search For Odd Perfect Numbers Up In The First 5000 Terms
No odd perfect numbers can be found within this range but the numeric explorations
will give some clues on the
possibility of existence of odd perfect numbers.
Perf_z:taylor(sum(i/(z^i*(z^i-1)),i=1..5000),z=infinity,5000); .......(6).
Remarks: The equivalent Maple V R 3's program line is:
Perf_z:=sort(series(sum(i/(z^i*(z^i-1)),i=1..5000),z=infinity,5000);
After expansions, terms with odd numerator coefficients and odd power indices
in the denominators were picked.
There is no shortage of such terms but only terms with comparable magnitudes
of numerator coefficients and denominator power indices are included in Table 1.
Only one term comes fairly close to being labelled as a "nearmiss", i.e.
This term is 1149/z^1155.
Table 1 - Series Terms With Odd Numerators And Denominators
309
+ ---- +
315
z
975
+ ---- +
945
z
1149
+ ----- +
1155
z
1323
+ ----- +
1365
z
1395
+ ----- +
1485
z
1649
+ ----- +
1575
z
1671
+ ----- +
1785
z
1845
+ ----- +
1995
z
1887
+ ----- +
2145
z
2241
+ ----- +
2205
z
2361
+ ----- +
2475
z
2973
+ ----- +
2835
z
4023
+ ----- +
3465
z
3393
+ ----- +
3675
z
4641
+ ----- +
4095
z
5195
+ ----- +
4725
z
4125
+ ----- +
4995
z
From Table 1, some general observations are made being listed below:
(i) Half the terms generated contain
denominator with odd power indices. So there is no shortage of such terms. Majority of
such terms have values of numerator coefficients lower than the power indices.
A minority of terms have numerator coefficients larger than the power indices. In
short, numerator coefficients straddle the values of denominator coefficients which
hint at the possibilities of exact hits, i.e., odd perfect numbers.
(ii) Since odd numerators are in the same subset as prime numbers, the
occurrences of odd perfect numbers will be more affected by primes. This
might explain why odd perfect numbers are not observed in the lower end
of the natural number system since primes are dense at the lower end. However
the exact cause has not been unravelled.
(iii) If terms in Table 1 can be labelled as "nearmisses", most of these terms
have power indices in the denominators ending with the digit 5s. Some even have
both the numerators and the denominator integers ending in 5s. This indicates that
in the search for odd perfect number one can concentrate on odd integers with
the rightmost digits ending in 5s. This is not foolproof as some odd perfect
numbers do not follow this trend.
4. Conclusions
The Theorem of Odd Perfect Numbers does narrow down the search for such
numbers. Numerical investigations amongst the first 5000 terms show
the possibility of extistence of odd perfect numbers as there are nearmisses
and that the numerator coefficients straddle on both sides of the odd integers to be
tested. Unfortunately the equation of divisibles or its variants are not
computationally efficient and would be excruciatingly slow when computing
using a Pentium. The algorithm itself is most suitable for processing by a
symbolic package. This suggests the use of Symbolic Machines if one wishes
to conduct a serious search. Some shortcuts are available one of which is
to concentrate on factorising odd composite numbers. The other is to do
the initial search on integers with the least significant decimal digit ending
in 5s. The reason is that these are the integers most likely to host odd
numerators in the modified equation of divisibles. There is a probability that
some odd perfect numbers will be missed using these shortcuts. Conditions
for the occurrences of odd perfect numbers appear favorable.
6. References
Comments: Not all references in this list are directly referred in the main paper.
Most are provided for readers not familiar with sequence algebra. These papers
can be easily hyperlinked whilst you are in the web. Most html files are quite short
and can be download quite fast with the exception of those published in journals.
1. Burton M. Burton: Elementary Number Theory, Third Edition, WCB publishers, 1994, 17 to
48 to 50.
2. Meows David : Perfect, amicable and socialble
numbers
3.
Search Algorithms For Even Perfect Numbers And Amicable Pairs
- Huen Y.K. (Date Released 30/12/97, 38 Kbytes)
4. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci.
Technol., 1994, VOL. 25, NO.6, pp 913-920.
5. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ.
Sci. Technol., 1996, VOL.27, NO. 5, 685-691.
6. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,1996,
VOL.??, NO.?, ???-??? (In the press as proof paper mes 100421).
7. The twin prime problem revisited, INT.J.MATH.EDUC.SCI.TECHNOL.,199?,VOL.??, NO.?,???-???, proof paper
mes-0488 (10 pages).
8. Is Pie Periodic?, INT.J.MATH.EDUC.SCI.TECHNOL.,199?,VOL.??,NO.?,???-???, (in the press).
================================================
9. Evaluations Of Normc( ) Function
In Macsyma 2.2
- Huen Y.K. (Date Released 17/12/97, 14 Kbytes)
================================================
10.
List Processing In Sequence Algebra
- Huen Y.K. (Date Released 23/12/97, 20 Kbytes)
================================================
11. A Simple Introduction To Sequence
Algebra - by Huen Y.K.
(date release: 15.3.97) (38 KBytes, 11*A4 pages).
========================================================
12. The Canonical Generating Function
or CGF(z) ... - by Huen Y.K.
(date released : 27.5..97) (24 KBytes, 7*A4s).
========================================================
13. Visual Solutions Of Number Theoretic
Problems ..... - by Huen Y.K. (date released : 3.6.97) (38.3 KBytes, 10*A4s).
========================================================
14. Final Value Theorem Applied To Number
Sequences... - by Huen Y.K. (date released : 5.6.97) (29.4 KBytes, 9*A4s).
========================================================
15. Unsolved Problems In Sequence
Algebra - by Huen Y.K. (date released : 6.6.97) (29.4 KBytes, 9*A4s).
========================================================
16. Methods Of Developing Sequence
Algebraic Formulations For Comp(z) and Prime(z) - by Huen Y.K. (date released : 20.6.97) (36.8 KBytes, 10*A4s).
========================================================
17. Composite Number Sequence
Challenge 1/97 - by Huen Y.K. (date released : 28.6.97) (24.8 KBytes, 7*A4s).
========================================================
18. Lemmata, Corollaries, And
Theorems In Sequence Order Analysis. - by Huen Y.K. (date released : 6.7.97) (38.3 KBytes, 12*A4s).
========================================================
19. Improved Formulations For Comp(z)
and Prime(z)
- by Huen Y.K. (date released : 16.9.97) (17 KBytes ).
========================================================
20. Detecting False Reports
in Primality Tests By The Oddcomp(z) Method.
- by Huen Y.K. (date released : 18.9.97, Revised 20/9) (26 KBytes ).
========================================================
21. The Throwing Power Of
Oddcomp(z).
- by Huen Y.K. (date released : 24.9.97 ) (15 Kbytes).
========================================================
22. Sequence Algebraic
Approach To Prime Number Theorem
- by Huen Y.K. (date released : 28.9.97 ) (21 Kbytes).
========================================================
23. Generating Functions -
Closed Forms vs Open Forms
- by Huen Y.K. (date released : 1.10.97 ) (21 Kbytes).
========================================================
24. Generating Large
Odd Composite With Two Prime Factors
- by Huen Y.K. (date released : 3.10.97 ) (13.5 Kbytes).
========================================================
25. In Search Of Counter-
Examples In Maple's Isprime Function.
- by Huen Y.K. (date released : 4.10.97 ) (18 Kbytes).
========================================================
26. A Sequence Algebraist's
View Of Lehmann's Primality Test
- by Huen Y.K. (date released : 6.10.97 ) (26 Kbytes).
========================================================
27. On Odd(z), Oddcomp(z),
Seq1(z) and Seq2(z)
- by Huen Y.K. (date released : 10.10.97 ) (17 Kbytes).
========================================================
28. How To Generate A Short
And Contiguous Oddcomp(z) Sequence?
- by Huen Y.K. (date released : 15.10.97 ) (13 Kbytes).
========================================================
(29) A Sketch Of Test-Tube
Evolution In A Primeval Number Soup - by Huen Y.K.
(date released : 25.11.97) (paper35.htm 1 K).
========================================================
(30) In Search Of Primes From
The XGS Sequence - by Huen Y.K.
(date released : 8.12..97) (paper38.htm 23 K).
=====================END OF PAPER ======================