ALIQUOT SEQUENCE 3630 ENDS AFTER REACHING 100
DIGITS
MANUEL BENITO, WOLFGANG CREYAUFM ¨
ULLER, JUAN L. VARONA, AND PAUL
ZIMMERMANN
Abstract.
In this paper we present a new computational record: the aliquot
sequence starting at 3630 converges to 1 after reaching a hundred decimal
digits. Also, weshow thecurrent status of all thealiquot sequences starting
with a number under 10000; we have reached at leat 95 digits for all of them.
In particular, we have reached at least 112 digits for the so-called “Lehmer
ï¬ve sequencesâ€, and 101 digits for the “Godwin twelve sequencesâ€. Finally,
we give a summary showing the number of aliquot sequences of unknown end
starting with a number
≤
10
6
.
For a positive integer
n
, let
σ
(
n
) denote the sum of its divisors (including 1 and
n
), and
s
(
n
) =
σ
(
n
)
−
n
the sum of its proper divisors (without
n
). A perfect
number is a number
n
such that
s
(
n
) =
n
, and an amicable pair of numbers (
n, m
)
satisï¬es
s
(
n
) =
m
,
s
(
m
) =
n
. In a similar way, tuples of numbers (
a
1
, a
2
, . . . , a
l
)
such that
s
(
a
i
) =
a
i
+1
for 1
≤
i
≤
l
−
1 and
s
(
a
l
) =
a
1
are known as aliquot cycles
or sociable numbers.
Given
n
, the way to compute
σ
(
n
) (and then,
s
(
n
)) is as follows. We ï¬nd the
prime decomposition of
n
=
p
a
1
1
· · ·
p
a
d
d
. Then
σ
(
p
a
1
1
· · ·
p
a
d
d
) = (1 +
p
1
+
· · ·
+
p
a
1
1
)
· · ·
(1 +
p
d
+
· · ·
+
p
a
d
d
)
(1)
=
p
a
1
+1
1
−
1
p
1
−
1
· · ·
p
a
d
+1
d
−
1
p
d
−
1
.
(2)
Indeed, if we expand de expression on the right in (1), all the divisors of
p
a
1
1
· · ·
p
a
d
d
appear as summands.
By iterating the function
s
, i.e., taking
s
0
(
n
) =
n
and
s
k
+1
(
n
) =
s
(
s
k
(
n
)), it
appears the so-called aliquot sequence
{
s
k
(
n
)
}
∞
k
=0
. For each one of these sequences,
there are four possibilities:
(
i
) it terminates at 1 (the previous term being a prime number),
(
ii
) it reaches a perfect number,
(
iii
) it reaches an amicable pair or a cycle,
(
iv
) it is unbounded.
The Catalan-Dickson conjecture says that (
iv
) does not actually happen.
But
other researchers disagree with this conjecture and thinkthat there are unbounded
2000
Mathematics Subject Classiï¬cation.
Primary 11Y55; Secondary 11A25.
Key words and phrases.
Aliquot sequences, sum of divisors, perfect number, amicable pair,
sociable numbers, aliquot cycles.
The ï¬rst author enjoys, during year 2000–01, a study leave given by Consejer´ıa deEducaci´
on,
Cultura, Juventud y Deportes of Gobierno de La Rioja.
Research of the third author supported by grant BFM2000-0206-C04-03 of the DGI and API-
01/B38 of theUR.
1
2
M. BENITO, W. CREYAUFM ¨
ULLER, J. L. VARONA, AND P. ZIMMERMANN
sequences; in fact, the alternative conjecture from Guy-Selfridge [7] (see also [5])
states that there are many sequences that go to inï¬nity, perhaps almost all those
that start at a even number (i.e., the proportion of even integers
n
such that
{
s
k
(
n
)
}
∞
k
=0
is bounded tends to zero).
This new conjecture is based upon the existence of several multiplicative pat-
terns 2
a
p
1
. . . p
m
that, when appearing in the factor decomposition of
n
, they show
up again, with a high order of probability, in the factor decomposition of
s
(
n
).
Following [7], these patterns are called
drivers
or
guides
.
By deï¬nition, a guide is of the form 2
a
, together with a subset of prime factors
of
σ
(2
a
) (= 2
a
+1
−
1). And a driver is of the form 2
a
v
with
a >
0,
v
|
σ
(2
a
) and
2
a
−
1
|
σ
(
v
). This last condition ensures that the power of the prime 2 tends to
persist, at least, as much as if the driver is 2, for which the condition is trivial.
Actually, drivers are much more stable than guides. As stated in [7], the only
drivers are 2, 2
3
·
3, 2
3
·
3
·
5, 2
5
·
3
·
7, 2
9
·
3
·
11
·
31, and the even perfect numbers.
Examples of guides that are not drivers are 2
a
(
a >
1), 2
3
·
5, 2
5
·
3, 2
5
·
3
2
, 2
5
·
3
2
·
7,
2
7
·
3
·
5, . . . .
Using (1), it is easy to observe the behavior of drivers (and guides). For instance,
let us take
n
= 2
3
·
3
·
5
pq
, with
p
and
q
prime numbers,
p
=
q
,
p, q >
5. The same
happens if we have more than two prime factors greater than 5 but, by simplicity,
let us see this example. We can checkthat
s
(
n
) = (1+2+4+8)
·
4
·
6(
p
+1)(
q
+1)
−
2
3
·
3
·
5
pq
= 15
·
2
2
·
2
·
3(
p
+1)(
q
+1)
−
2
3
·
3
·
5
pq
= 2
3
·
3
·
5
·
[3(
p
+1)(
q
+1)
−
pq
] = 2
3
·
3
·
5
m
,
with
m
an odd number that is not divisible by 3. Then, we get again 2
3
·
3
·
5 with 2
and 3 raised to the same power as before (however, it is possible that the power
of 5 changes; this may cause the loss of the driver at a later point). The behavior
is similar if the prime factors greater than 5 are raised to an odd power, because
1 +
p
+
· · ·
+
p
a
is even when
a
is odd. However, a factor
p
a
with
a
a even number
does not contribute with a factor 2 in the ï¬rst summand of
m
.
It is easy to prove that, if
m
is a perfect number, or
s
(
m
)
> m
, and we have
m
a proper divisor of
n
, then
s
(
n
)
> n
(of course, we are not considering the
trivial case
n
= perfect number). Thus, we have
σ
(
m
)
≥
2
m
and
n
=
lm
with
l >
1. To prove the claim, we must check
σ
(
lm
)
>
2
lm
. Let
{
1
, d
1
, d
2
, . . . , d
r
}
be the divisors of
m
. Then, 1
, l, ld
1
, ld
2
, . . . , ld
r
are divisors of
lm
. Therefore,
σ
(
lm
)
≥
1 +
l
+
ld
1
+
ld
2
+
· · ·
+
ld
r
> l
(1 +
d
1
+
d
2
+
· · ·
+
d
r
) =
lσ
(
m
)
≥
2
lm
.
As a consequence, all the drivers, with the exception of 2 (the “downdriverâ€, as
we show below), make
s
(
n
)
> n
. And, as the structure is preserved, it seems that
we can get an always increasing sequence. But a driver can, eventually, disappear.
Let us see again some examples; this time, with the driver 2
3
·
3. Here, and in what
follows, we will use
p, q
to denote distinct prime numbers, being
p, q >
3.
When we have a number with the form
n
= 2
3
·
3
p
, it follows
s
(
n
) = (1 + 2 + 4 +
8)
·
4(
p
+ 1)
−
2
3
·
3
p
= 2
2
·
3
·
[5(
p
+ 1)
−
2
p
]. Now, if
p
has the form
p
= 4
r
+ 1,
then
s
(
n
) = 2
3
·
3
·
[5(2
r
+ 1)
−
p
], and the expression between square brackets
is even, so the power of 2 in
s
(
n
) is at least 4. However, if
p
= 4
r
+ 3, we get
s
(
n
) = 2
3
·
3
·
[5(2
r
+ 2)
−
p
] and, this time, the expression between square brackets
is odd, so the power of 2 remains.
The driver 2
3
·
3 can also disappear with numbers of the form
n
= 2
3
·
3
2
pq
. Here,
s
(
n
) = 15
·
13(
p
+ 1)(
q
+ 1)
−
8
·
9
pq
. If
p, q
≡
1 mod 4, then the 2
3
disappears and,
in its place, 2
2
arises. If
p, q
≡
3 mod 4, the 2
3
persists. If
p
≡
1 and
q
≡
3 mod 4,
ALIQUOT SEQUENCE 3630 ENDS AFTER REACHING 100 DIGITS
3
then, at least, we have a factor 2
3
; but the power of 2 goes up if 8 is not a divisor
of
q
+ 1, i.e., if
q
≡
3 mod 8.
When the driver of the sequence is 2, the sequence usually decreases. For in-
stance, if
n
= 2
pq
, then
s
(
n
) = 3(
p
+ 1)(
q
+ 1)
−
2
pq
=
pq
+ 3(
p
+
q
+ 1). When
p
and
q
are big enough, 3(
p
+
q
+ 1) is tiny compared with
pq
, and so
s
(
n
)
< n
.
As for the other drivers, the driver 2 can disappear. For instance, let
n
be
n
= 2
p
,
with
s
(
n
) = 3(
p
+ 1)
−
2
p
=
p
+ 3. If
p
= 4
r
+ 3, then
s
(
n
) = 2(2
r
+ 3). But, if
p
= 4
r
+ 1, then
s
(
n
) = 2
2
(
r
+ 1) and so we have, at least, a factor 2
2
. The behavior
is similar if
n
= 2
p
2
q
, or if
n
has more prime factors raised to even powers.
Guides in the form 2
a
for
a >
1 make the sequence oscillate; we have
s
(
n
)
< n
or
s
(
n
)
> n
according to the other factors. And these guides change very easily.
And, what occurs when
n
is odd? If
n
=
p
prime,
s
(
n
) = 1 and the sequence
ï¬nishes. Now, let us assume
n
=
pq
. Then,
s
(
n
) = (
p
+ 1)(
q
+ 1)
−
pq
=
p
+
q
+ 1 is
also odd (usually,
s
(
n
)
< n
). The same occurs, for instance, with
n
=
p
2
q
. But it
is also possible that
n
is odd but
s
(
n
) is even. This is what happens when
n
=
p
2
;
indeed, in this case
s
(
n
) = (
p
2
+
p
+ 1)
−
p
2
, that is even.
It is possible (but not very common) that an aliquot sequences reaches a per-
fect number, an amicable pair or a cycle; this is the end of the aliquot sequence.
Otherwise, to get a terminating sequence, it must reach an odd prime number.
Usually, most terms of a sequence are even.
Let us see the way in which a
even term
n
changes to an odd term
s
(
n
).
This occurs when
n
= 2
a
p
2
, with
a >
0 (or similar cases with
p
2
b
or more primes up to even powers).
Indeed,
s
(
n
) = (2
a
+1
−
1)(1 +
p
+
p
2
)
−
2
a
p
2
, an odd number. Only chance can say whether
this term is prime or not. Anyway, the sequence either reachs an even term (case
previously considered) or it continues with odd tems until a prime term appears,
where it stops.
Finally, let us also note that, althoug it seems unlikely that an always increasing
aliquot sequence exists (of course, this would refute Catalan-Dickson conjecture),
H. W. Lenstra proved that it is possible to construct arbitrarily long monotonic
increasing aliquot sequences (that is, for any
k
, we can found
m
such that
s
0
(
m
)
<
s
1
(
m
)
<
· · ·
< s
k
(
m
)); the proof can be found in [5].
1.
The recent and present history
Many other people have been working with aliquot sequences, including P. Poulet,
D. H. Lehmer, P. ErdË
os, J. Godwin, H. Cohen, R. K. Guy, M. Dickerman, H. J. J. te
Riele, . . . . A extensive bibliography on this subject can be found in [6, B6].
The ï¬rst sequence whose end was in doubt started with 138; Lehmer found its
end
s
177
(138) = 1. For numbers
n <
1000, Lehmer could not ï¬nd the end of the
sequences starting from 276, 552, 564, 660, 840 and 966. Except for 840, which
ï¬nished with
s
747
(840) = 1 (found by A. Guy and R. K. Guy), the end for the
others is still unknown; they are the “Lehmer ï¬veâ€. In a similar way, the doubtful
sequences starting between 1000 and 2000 are known as Godwin sequences; now,
“Godwin twelveâ€.
Regarding classiï¬cations of unknown sequences, let us note the following. Sup-
pose that, for two different numbers
n
1
and
n
2
(say,
n
1
< n
2
) there exist
k
1
and
k
2
such that
s
k
1
(
n
1
) =
s
k
2
(
n
2
). Then, both sequences are the same from then on. In
this case, we say that
n
1
is the
main
sequence and
n
2
is a
side
sequence. Only the
main sequences are studied.
4
M. BENITO, W. CREYAUFM ¨
ULLER, J. L. VARONA, AND P. ZIMMERMANN
Table 1.
Aliquot sequences whose end is in doubt.
n
k
digits
guide
276
1284
117
2
·
3
552
818
118
2
5
·
3
·
7
564
3048
115
2
2
·
7
660
468
112
2
2 (
∗
)
966
526
114
2
·
3
1074
1585
105
2
2
·
7
1134
2249
127
2
5
·
3
·
7
1464
1897
101
2
2
·
7
1476
1055
106
2
3
·
3
·
5
n
k
digits
guide
1488
824
103
2
2
·
7
1512
1632
101
2
2
·
7
1560
1336
101
2
5
·
3
·
7
1578
1109
104
2
2 (
∗
)
1632
713
102
2
3
·
3
·
5
1734
1404
103
2
2
·
7
1920
1992
108
2
2
·
7
1992
985
102
2
3
·
3
·
5
2232
390
102
2
6(
∗
)
n
k
digits
guide
2340
471
99
2
3
·
3
·
5
2360
974
95
2
2
·
7
2484
796
97
2
3
·
3
2514
2866
105
2
3
·
3
·
5
2664
761
100
2
2
·
7
2712
1347
95
2
2
·
7
2982
826
97
2
4
·
31
3270
417
98
2
5
·
3
·
7
3366
1062
100
2
3(
∗
)
n
k
digits
guide
3408
840
95
2
3
·
3
·
5
3432
933
103
2
3
·
3
·
5
3564
779
100
2
3
·
3
3678
1201
98
2
2
·
7
3774
1193
98
2
7
·
3
(
∗
)
3876
830
96
2
2
·
7
3906
704
100
2
2
·
7
4116
1192
105
2
3
·
3
4224
519
98
2
3
·
3
·
5
n
k
digits
guide
4290
953
106
2
2
·
7
4350
1165
97
2
2
·
7
4380
965
100
2
2
·
7
4788
2152
105
2
3
·
3
·
5
4800
1135
101
2
4
·
31
4842
473
98
2
2
·
7
5148
1545
95
2
·
3
5208
1710
96
2
3
·
3
·
5
5250
1567
100
2
4(
∗
)
n
k
digits
guide
5352
746
106
2
2
·
7
5400
2776
102
2
2
·
7
5448
1185
96
2
3
·
3
·
5
5736
1093
100
2
2
·
7
5748
1091
108
2
2
·
7
5778
742
95
2
4
·
31
6160
1630
96
2
2(
∗
)
6396
1272
105
2
3
·
3
·
5
6552
932
102
2
3
·
3
n
k
digits
guide
6680
1880
106
2
4
·
31
6822
1177
97
2
4
·
31
6832
885
104
2
3
·
3
6984
1764
96
2
4
·
31
7044
1113
102
2
4
·
31
7392
498
96
2
3
·
3
·
5
7560
846
97
2
3
·
5
(
∗
)
7890
891
99
2
2
·
7
7920
1014
109
2
6
·
127
n
k
digits
guide
8040
2240
106
2
3
·
3
·
5
8154
647
96
2
2
·
7
8184
1241
102
2
2
·
7
8288
849
103
2
8 (
∗
)
8352
1291
96
2
2
·
7
8760
2157
97
2
4(
∗
)
8844
1184
101
2
4
·
31
8904
963
95
2
2
·
7
9120
580
103
2
3
·
3
n
k
digits
guide
9282
556
106
2
3
·
3
9336
608
97
2
6
·
127
9378
2198
101
2
2
·
7
9436
638
102
2
·
3
9462
447
97
2
3
·
3
·
5
9480
1028
98
2
·
3
9588
1848
103
2
5
·
3
·
7
9684
643
101
2
5
·
3
·
7
9708
710
106
2
2
·
7
n
k
digits
guide
9852
669
105
2
2
·
7
According to (1) or (2), to compute an aliquot sequence, we have to decompose
m
into factors to calculate
s
(
m
); and this, for many
m
’s. This is hard when the
number
m
is large. The discovery of better factoring methods and the increase
in the speed of computers lead to progress in the experimental knowledge of the
behavior of aliquot sequences.
Recently, different people have extended the range of aliquot sequences that have
been studied. In different ways, W. Bosma, J. Gerved, S. Wagstaff, P.-L. Mont-
gomery, H. J. J. te Riele, W. Lioen, A. Lenstra, and the authors have been con-
tributing in this subject. Let us cite some recent advances.
In [1], two of the authors, following previous workof A. Guy and R. K. Guy, show
a table with the status of doubtful main aliquot sequences starting at
n <
10000.
In this paper we show an update: see Table 1.
ALIQUOT SEQUENCE 3630 ENDS AFTER REACHING 100 DIGITS
5
Table 2.
Number of aliquot sequences of unknown status starting
with a number
≤
10
6
.
Interval
Number of sequences
Limits of computation
[1
,
100000]
925
>
10
80
(100000
,
200000]
975
>
10
80
(200000
,
300000]
963
>
10
60
(300000
,
400000]
903
>
10
60
(400000
,
500000]
940
>
10
60
(500000
,
600000]
990
>
10
60
(600000
,
700000]
987
>
10
60
(700000
,
800000]
990
>
10
60
(800000
,
900000]
982
>
10
80
(900000
,
10
6
]
987
>
10
80
In the table, we include the number of decimal digits of the last term
s
k
(
n
)
known for each sequence and the guide in that stage. Actually, all the sequences
have a driver in the current stage (a driver is more stable than a guide), except the
ones marked with
(
∗
)
.
In [1], all the sequences in the table had been pursued up to, at least, 75 decimal
digits. Now, we have reached more that 95 digits for all of them; and 100 digits for
many of them. We have reached at least 112 digits for the Lehmer sequences and
101 digits for the Godwin sequences.
It is curious to note that the driver 2
9
·
3
·
11
·
31 has appeared in no place in any
of the sequences related in Table 1.
W. Creyaufm¨
uller is leading a project to study all the aliquot sequences starting
at every
n
≤
10
6
; of course, there are many of them, so they are been studied
up to less digits than in this paper. For a compilation of his work, see [4]. Here,
we summarize the present state of such aliquot sequences with unknown status in
Table 2.
We have not found new experimental evidences in favour of Guy-Selfridge conjec-
ture, because drivers and guides disappear from time to time. For instance, when
we increase the size of the last term reached for the sequences starting at every
n
≤
10
6
, the percentage of unknown sequences decreases in a signiï¬cative way.
It seems feasible that Catalan’s conjecture is true. But the question is how big
are intermediate numbers that we need to factor to reach the end of the sequence?
As we see below, for
n
= 840, we had to go up to 49 digit numbers; for
n
= 1248,
up to 58 digit numbers; for
n
= 3630, up to 100 digit numbers. Perhaps we must
go up to 200 or 1000 digit numbers for
n
= 276, which would make this sequence
out of reach. Perhaps only 130 digits, which would make this sequence computable
with today’s computers and algorithms.
Theoretically speaking, it does not seem an easy question. How many time will
remain this problem open?
2.
Maximum of a terminating sequence
With respect to the height of aliquot sequences that are known to terminate,
there has been considerable progress. When D. H. Lehmer found the end of the
aliquot sequence starting at 138 he found a maximum
s
117
(138) of 12 decimal digits.
6
M. BENITO, W. CREYAUFM ¨
ULLER, J. L. VARONA, AND P. ZIMMERMANN
Later, A. Guy and R. K. Guy found the end for 840 after ï¬nding a maximum
s
287
(840) of 49 digits; and M. Dickerman did the same for 1248, with a maximum
s
583
(1248) of 58 digits.
(Of course, if
p
is a prime number,
s
(
p
) = 1 so the sequence starting in
p
trivially
ï¬nishes. These trivial results are not considered in records.)
In [1], we show that the sequence starting at 4170 converges to 1 after 869
iterations, getting a maximum of 84 decimal digits at iteration 289; this was a new
record for the highest terminating aliquot sequence (found in December 22, 1996).
Later, in October 1999, W. Bosma broke this record: he found that the aliquot
sequence starting with 44922 terminates after 1689 iterations (at 1), after reaching
a maximum of 85 digits at step 1167. In December 3, 1999, he broke again the
record ï¬nding that the sequence starting at 43230 ï¬nished: it terminates (at 1)
after 4357 iterations, after reaching a maximum of 91 digits at step 967.
As of June 10, 2001, M. Benito and J. L Varona have found the end of the
aliquot sequence starting at 3630. It ï¬nishes at
s
2624
(3630) = 1 after reaching a
maximum
s
1263
(3630) with a hundred digits. It is
the present record for the
highest known terminating aliquot sequence
. In Figure 1 we show the shape
of the sequence: in the horizontal axis, the index
k
appears; and in the vertical
axis, log
10
(
s
k
(3630)).
500
1000
1500
2000
2500
20
40
60
80
100
Figure 1.
The aliquot sequence starting at 3630
Moreover, 3630
<
10000 so the present Table 1 has one fewer entry than the
table that appears in [1] (the aforementioned sequences found by W. Bosma start
in a number
>
10000). Now, there are 82 main aliquot sequences (starting in a
number
<
10000) whose end is still unknown.
For sequences of unknown status, the sequence 1134 has been extended by
P. Zimmermann up to 127 digits; this is the largest term of an aliquot sequence
computed so far.
We maintain the following web pages related to aliquot sequences:
http://home.t-online.de/home/Wolfgang.Creyaufmueller/aliquote.htm
http://www.unirioja.es/dptos/dmc/jvarona/aliquot.html
http://www.loria.fr/~zimmerma/records/aliquot.html
ALIQUOT SEQUENCE 3630 ENDS AFTER REACHING 100 DIGITS
7
In these pages, one can ï¬nd links to the aliquot web pages of other authors (in
particular, from W. Bosma and J. Howell). Also, in the
ftp
server
ftp://mat.unirioja.es/pub/aliquot/00xxxx
the sequences of Table 1 can be found.
3.
The method
As we already commented, to compute an aliquot sequence, we have to decom-
pose
m
into factors to calculate
s
(
m
), and iterate this procedure a lot of times. This
is hard when the number
m
is large. And we are dealing with numbers up to more
than a hundred of digits, so powerful algorithms are necessary. In particular, we
have used the elliptic curve method (ECM) and the multiple polynomial quadratic
sieve (MPQS); see a recent report (with many references) about the use of MPQS
in [2]. We have checked the primality of the factors with the Adleman-Pomerance-
Rumely (APR) primality test.
All our workhas been done by using free pack
ages available on internet. We
have run the programs on many computers from the authors and some collegues,
and their respective institutions. The workhas been done mostly during nights and
weekends.
We have used the following packages, that are available at their corresponding
web pages (or anonymous
ftp
sites):
•
UBASIC,
ftp://rkmath.rikkyo.ac.jp/pub/ubibm/
•
PARI-GP,
http://www.parigp-home.de/
•
KANT-KASH (see [8]),
http://www.math.tu-berlin.de/algebra/
•
MIRACL,
http://indigo.ie/~mscott/
•
GMP,
http://www.swox.com/gmp/
UBASIC programs to get aliquot sequences can be downloaded in Creyaufm¨
uller’s
web page. PARI-GP and KANT-KASH programs can be downloaded in Varona’s
web page. A implementation of ECM for GMP can be downloaded in Zimmer-
mann’s web page.
The authors began to investigate the behavior of aliquot sequences around 1985.
During this time, we have used many different kinds of computers, mainly PCs, but
also Unix workstations and Macintoshes. In total, we can estimate that we have
employed about 200 years of CPU time.
One of the most titanic efforts has been to factorize the 109-digit cofactor in
s
1267
(276). The computation time has been the equivalent to about 220 days of
CPU time on an 800 Mhz Pentium III computer (actually, the sieving has been
carried out on a cluster of PCs). This kind of numbers is the reasonable limit
for the MPQS method. For bigger ones, it will be better to use a new method of
factorization: the number ï¬elds sieve (NFS); see, for instance [3].
Acknowledgments
The authors thankall people who helped factorizing numbers from the Lehmer
and several Godwin (1074 and 1134) sequences: Conrad Curry, Jim Howell, Arjen
Lenstra, Paul Leyland, Sam Wagstaff. And to Wieb Bosma for his calculations on
aliquot sequences starting with a number between 10000 and 50000.
Also, thanks to Peter Montgomery for making his program
ecmfft
available,
Herman te Riele and Walter Lioen for their
MPQS
program, Sam Wagstaff for having
8
M. BENITO, W. CREYAUFM ¨
ULLER, J. L. VARONA, AND P. ZIMMERMANN
done some aliquot factorizations on his MasPar, and Arjen Lenstra for his enormous
help with the
ppmpqs
program. And to Yuji Kida for his programs (ECM and
PPMPQS implementations) written in UBASIC.
Finally, thanks to Laureano Lamb´
an, Eloy Mata, David Ortigosa and Julio Rubio
for allowing us to use their personal computers to do some of the computations that
appear in this paper.
References
[1] M. Benito and J.L. Varona, Advances in aliquot sequences,
Math. Comp.
68
(1999), 389–393.
[2] H. Boender and H.J.J. te Riele, Factoring integers with large-prime variations of the quadratic
sieve,
Experimental Mathematics
5
(1996), 257–273.
[3] S. Cavallar, B. Dodson, A.K. Lenstra, P.C. Leyland, W.M. Lioen, P.L. Montgomery, B.A. Mur-
phy, H.J.J. te Riele, and P. Zimmermann, Factorization of RSA-140 using the Number Field
Sieve, in
Advances in Cryptology, Asiacrypt’99
(Berlin, 1999),
Lecture Notes in Computer
Science
1716
(1999), pp. 195–207.
[4] W. Creyaufm¨
uller,
Primzahlfamilien
, 3
rd
ed., Verlagsbuchhandlung Creyaufm¨
uller, Stuttgart,
2000.
[5] P. ErdË
os, On asymptotic properties of aliquot sequences,
Math. Comp.
30
(1976), 641–645.
[6] R.K. Guy,
Unsolved Problems in Number Theory
(2nd ed.), Springer-Verlag, 1994.
[7] R.K. Guy and J.L. Selfridge, What drives an aliquot sequence?,
Math. Comp.
29
(1975),
101–107. Corrigendum,
ibid.
34
(1980), 319–321.
[8] M. Dabe rkow, C. Fie ke r, J. Kl¨
uners, M. Pohst, K. Roegner, M. Sch¨
ornig, and K. Wildanger,
KANT V4,
J. Symbolic Comput.
24
(1997), 267–283.
Instituto Sagasta, Glorieta del Doctor Zub´
ıa s/n, 26003 Logro˜
no, Spain
E-mail address
:
mbenit8@palmera.pntic.mec.es
Freie Waldorfschule Aachen, Anton-Kurze-Allee 10, D-52074 Aachen, Germany
E-mail address
:
Wolfgang.Creyaufmueller@t-online.de
URL
:
http://home.t-online.de/home/Wolfgang.Creyaufmueller/
Departamento de
Matem´
aticas
y
Computaci´
on,
Universidad
de
La
Rioja,
Edificio
J. L. Vives, Calle Luis de Ulloa s/n, 26004 Logro˜
no, Spain
E-mail address
:
jvarona@dmc.unirioja.es
URL
:
http://www.unirioja.es/dptos/dmc/jvarona/welcome.html
INRIA Lorraine, Technopˆ
ole de Nancy-Brabois, 615 rue du Jardin Botanique, BP 101,
F-54600 Villers-l`
es-Nancy, France
E-mail address
:
Paul.Zimmermann@inria.fr
URL
:
http://www.loria.fr/~zimmerma/