jmh@ukc.UUCP (J.M.Hague) (12/11/84)
Summary of replies to :
1. Amicable/semi-perfect numbers - request for info
2. Mathematically, what is a star ?
Many thanks to all who replied. Anybody got any ideas on item 2 ?
-------------------------------------------------------------------------
The following references are about amicable numbers:
Lee, E.J. & J.S. Madachy
The history and discovery of amicable numbers.
J. Recreational Mathematics (1972) Vol. 5:
Part 1: pp 77-93,
Part 2: pp 153-173,
Part 3: pp 231-249.
H.J.J. te Riele
Perfect Numbers and Aliquot sequences.
in: H.W. Lenstra, jr & R. Tijdeman
Computational Methods in Number Theory
Part 1. pp 141-157.
Mathematical Centre Tract 154.
Amsterdam 1982.
(This is the old name for CWI).
For an algorithm you may contact H.J.J. te Riele at CWI.
Stars are unknown to us (except of course the ones above us).
dik t. winter
centrum voor wiskunde en informatica (CWI)
postbus 4079
1009 AB amsterdam
nederland
+31 20 592 4102
UUCP: decvax!mcvax!turing!dik
------------------------------------------------------------------------
From: Jeff Shallit <mcvax!seismo!ihnp4!gargoyle!shallit@ukc.ac.uk>
Subject: Re: Amicable (semi-perfect) numbers/ star ?
Organization: Computer Science Dept., Univ. of Chicago
It's possible you may be confusing two concepts here.
A MULTIPERFECT number n is one such that sigma(n) = kn for some
integer k. Here sigma(n)is the sum of the divisors of n.
An example is 120; the divisors are
1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120
and these sum to 360, so in this case k = 3. Perfect numbers
correspond to the case k = 2.
An AMICABLE PAIR is a pair (m,n) with sigma(m) = sigma(n) = m+n.
The smallest example is (220, 284).
A good reference for this sort of thing is Richard K. Guy's
book, "Solved and Unsolved Problems in Number Theory", Springer-Verlag,
1981. Any good bookstore should be able to order this.
There is no FAST systematic way known to generate these guys. However,
recent results of Bach, Miller, and Shallit (Proceedings of the 1984
Symposium on the Theory of Computing) show that if you give me
a number alleged to be multiperfect, then I can quickly tell you yes
or no (whether it REALLY is or not), with some small bounded probability
of error, INDEPENDENT of the number. Same for amicable pairs.
/Jeff Shallit
--------------------------------------------------------------------------
I recall an article on "Amicable numbers" in the pre-1973 editions of
Encyclopaedea Britanica. Also the subject is discussed in L.E.
Dickson's "History of the Theory of Numbers".
There is a very old method (attributed to Thabit ibn Qurrah, 836-901
A.D.) that would generate some but not all of the amicable number
pairs.
For successive integers n>1, compute the integers a, b, and c defined
below:
a = 3*2**n - 1
b = 3*2**(n-1) - 1
c = 9*2**(2*n-1) - 1
If each of a, b, and c is prime, then the integers p=2**n*a*b and
q=2**n*c form a pair of amicable numbers.
Examples:
n a b c p q
--- ---- ---- ------ ------- -------
2 11 5 71 220 284
4 47 23 1151 17296 18416
7 383 191 73727 9363584 9437056
This method does not generate ALL amicable pairs. For example, the
pairs (1184,1210) and (6232,6368) do not fit the above pattern.
uucp: {ucbvax,decvax,ihnp4,allegra,uw-beaver,hplabs}
!tektronix!tekchips!abdali
CSnet: abdali@tektronix
ARPAnet: abdali.tektronix@csnet-relay
US Mail: Kamal Abdali
Computer Research Lab, 50-662
Tektronix, Inc.
Box 500
Beaverton, OR 97077
---------------------------------------------------------------------
From: Arjen Lenstra <mcvax!seismo!ihnp4!gargoyle!lenstra@ukc.ac.uk>
Ask Herman te Riele at the CWI (that is where mcvax is), he knows
everything about amicable numbers. You can reach hem on
mcvax!dik
Or write to
Herman te Riele
Kruislaan 413
1098 SJ Amsterdam
The Netherlands