SolutionEuler/solutions/0000_0029/0021.AmicableNumbers/readme.md

# 亲和数（Amicable Numbers）

以下来自 [wolfram数学世界](https://mathworld.wolfram.com/AmicablePair.html) 。

-----

An amicable pair (m,n) (also Amicable Numbers) consists of two integers m,n for which the sum of proper divisors (the divisors excluding the number itself) of one number equals the other. Amicable pairs are occasionally called [friendly pairs](https://mathworld.wolfram.com/FriendlyPair.html) (Hoffman 1998, p. 45), although this nomenclature is to be discouraged since the numbers more commonly known as friendly pairs are defined by a different, albeit related, criterion. Symbolically, amicable pairs satisfy

$$
  s(m) = n
  s(n) = m
$$

where

$$
s(n)=\sigma(n)-n
$$

is the [restricted divisor function](https://mathworld.wolfram.com/RestrictedDivisorFunction.html). Equivalently, an amicable pair (m,n) satisfies

$$
\sigma(m)=\sigma(n)=s(m)+s(n)=m+n,
$$

where $\sigma(n)$ is the divisor function. The smallest amicable pair is (220, 284) which has factorizations

$$
220	=	11·5·2^2	
284	=	71·2^2
$$

giving restricted divisor functions

$$
s(220)	=	sum{1,2,4,5,10,11,20,22,44,55,110} =	284	
s(284)	=	sum{1,2,4,71,142} =	220.
$$

The quantity

$$
\sigma(m)=\sigma(n)=s(m)+s(n),
$$

in this case, 220+284=504, is called the pair sum. The first few amicable pairs are (220, 284), (1184, 1210), (2620, 2924) (5020, 5564), (6232, 6368), (10744, 10856), (12285, 14595), (17296, 18416), (63020, 76084), ... (OEIS [A002025](http://oeis.org/A002025) and [A002046](http://oeis.org/A002046)). An exhaustive tabulation is maintained by D. Moews.

In 1636, Fermat found the pair (17296, 18416) and in 1638, Descartes found (9363584, 9437056), although these results were actually rediscoveries of numbers known to Arab mathematicians. By 1747, Euler had found 30 pairs, a number which he later extended to 60. In 1866, 16-year old B. Nicolò I. Paganini found the small amicable pair (1184, 1210) which had eluded his more illustrious predecessors (Paganini 1866-1867; Dickson 2005, p. 47). There were 390 known amicable pairs as of 1946 (Escott 1946). There are a total of 236 amicable pairs below 10^8 (Cohen 1970), 1427 below 10^(10) (te Riele 1986), 3340 less than 10^(11) (Moews and Moews 1993ab), 4316 less than 2.01×10^(11) (Moews and Moews 1996), and 5001 less than  approx 3.06×10^(11) (Moews and Moews 1996).

Rules for producing amicable pairs include the [Thâbit ibn Kurrah rule](https://mathworld.wolfram.com/ThabitibnKurrahRule.html) rediscovered by Fermat and Descartes and extended by Euler to [Euler's rule](https://mathworld.wolfram.com/EulersRule.html). A further extension not previously noticed was discovered by Borho (1972).

Pomerance (1981) has proved that

$$
 [amicable numbers <=n]<ne^(-[ln(n)]^(1/3)) 	
$$

for large enough n (Guy 1994). No nonfinite lower bound has been proven.

Let an amicable pair be denoted (m,n), and take m<n. (m,n) is called a regular amicable pair of type (i,j) if

$$(m,n)=(gM,gN),$$

where g=GCD(m,n) is the [greatest common divisor](https://mathworld.wolfram.com/GreatestCommonDivisor.html),

$$GCD(g,M)=GCD(g,N)=1,$$

M and N are squarefree, then the number of prime factors of M and N are i and j. Pairs which are not regular are called irregular or exotic (te Riele 1986). There are no regular pairs of type (1,j) for j>=1. If m=0 (mod 6) and

$$
n=\sigma(m)-m 	
$$

is even, then (m,n) cannot be an amicable pair (Lee 1969). The minimal and maximal values of m/n found by te Riele (1986) were

938304290/1344480478=0.697893577... 	
 
and

4000783984/4001351168=0.9998582518.... 	

te Riele (1986) also found 37 pairs of amicable pairs having the same pair sum. The first such pair is (609928, 686072) and (643336, 652664), which has the pair sum

$$
\sigma(m)=\sigma(n)=m+n=1296000.
$$
 
te Riele (1986) found no amicable n-tuples having the same pair sum for n>2. However, Moews and Moews found a triple in 1993, and te Riele found a quadruple in 1995. In November 1997, a quintuple and sextuple were discovered. The sextuple is (1953433861918, 2216492794082), (1968039941816, 2201886714184), (1981957651366, 2187969004634), (1993501042130, 2176425613870), (2046897812505, 2123028843495), (2068113162038, 2101813493962), all having pair sum 4169926656000. Amazingly, the sextuple is smaller than any known quadruple or quintuple, and is likely smaller than any quintuple.

The earliest known odd amicable numbers all were divisible by 3. This led Bratley and McKay (1968) to conjecture that there are no amicable pairs coprime to 6 (Guy 1994, p. 56). However, Battiato and Borho (1988) found a counterexample, and now many amicable pairs are known which are not divisible by 6 (Pedersen). The smallest known example of this kind is the amicable pair (42262694537514864075544955198125, 42405817271188606697466971841875), each number of which has 32 digits.

A search was then begun for amicable pairs coprime to 30. The first example was found by Y. Kohmoto in 1997, consisting of a pair of numbers each having 193 digits (Pedersen). Kohmoto subsequently found two other examples, and te Riele and Pedersen used two of Kohmoto's examples to calculated 243 type-(3,2) pairs coprime to 30 by means of a method which generates type-(3,2) pairs from a type-(2,1) pairs.

No amicable pairs which are coprime to 2·3·5·7=210 are currently known.

The following table summarizes the largest known amicable pairs discovered in recent years. The largest of these is obtained by defining

a	=	2·5·11

S	=	37·173·409·461·2136109·2578171801921099·68340174428454377539	

p	=	925616938247297545037380170207625962997960453645121	

q	=	210958430218054117679018601985059107680988707437025081922673599999	

q_1	=	(p+q)p^(235)-1	

q_2	=	(p-S)p^(235)-1,	

then p, q, q_1 and q_2 are all primes, and the numbers

n_1	=	aSp^(235)q_1	

n_2	=	aqp^(235)q_2	

are an amicable pair, with each member having 24073 decimal digits (Jobling 2005).

|digits|date|reference|
|------|------|----------|
|4829|Oct. 4, 1997|M. García|
|8684|Jun. 6, 2003|Jobling and Walker 2003|
|16563|May 12, 2004|Walker et al. 2004|
|17326|May 12, 2004|Walker et al. 2004|
|24073|Mar. 10, 2005|Jobling 2005|

Amicable pairs in Gaussian integers also exist, for example

s(8008+3960i)	=	4232-8280i	

s(4232-8280i)	=	8008+3960i	

and

s(-1105+1020i)	=	-2639-1228i	

s(-2639-1228i)	=	-1105+1020i	

(T. D. Noe, pers. comm.).


-----

以下为上文翻译。

-----

亲和数对 \((m, n)\)（亦称作亲和数）由两个整数 \(m, n\) 构成，其中一个数的真约数（即不包括该数本身的约数）之和等于另一个数。亲和数对有时也被称为友好数对（Hoffman 1998, p. 45），但这一名称应避免使用，因为通常所说的友好数对（friendly numbers）是由另一虽相关但不同的准则定义的。用符号表示，亲和数对满足

\[
s(m) = n, \quad s(n) = m,
\]

其中

\[
s(n) = \sigma(n) - n
\]

是约束除数函数（亦称作真约数和函数）。等价地，亲和数对 \((m, n)\) 满足

\[
\sigma(m) = \sigma(n) = s(m) + s(n) = m + n,
\]

这里 \(\sigma(n)\) 是除数函数。最小的亲和数对是 \((220, 284)\)，其因式分解为

\[
\begin{aligned}
220 &= 11 \cdot 5 \cdot 2^2, \\
284 &= 71 \cdot 2^2,
\end{aligned}
\]

对应的约束除数函数值为

\[
\begin{aligned}
s(220) &= \text{sum}\{1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110\} = 284, \\
s(284) &= \text{sum}\{1, 2, 4, 71, 142\} = 220.
\end{aligned}
\]

量

\[
\sigma(m) = \sigma(n) = s(m) + s(n),
\]

在此例中为 \(220 + 284 = 504\)，称为该数对的**对和**。最初的几个亲和数对是 \((220, 284)\), \((1184, 1210)\), \((2620, 2924)\), \((5020, 5564)\), \((6232, 6368)\), \((10744, 10856)\), \((12285, 14595)\), \((17296, 18416)\), \((63020, 76084)\), …（OEIS 序列 [A002025](http://oeis.org/A002025) 与 [A002046](http://oeis.org/A002046)）。D. Moews 维护着一份详尽的列表。

1636 年，费马发现了数对 \((17296, 18416)\)；1638 年，笛卡尔发现了 \((9363584, 9437056)\)，不过这些结果实际上是阿拉伯数学家已知数字的重新发现。截至 1747 年，欧拉已发现了 30 对，后来他又将这个数字扩展到了 60 对。1866 年，16 岁的 B. Nicolò I. Paganini 发现了较小的亲和数对 \((1184, 1210)\)，这一对曾被他那些更著名的前辈们所遗漏（Paganini 1866-1867; Dickson 2005, p. 47）。到 1946 年，已知的亲和数对有 390 对（Escott 1946）。在 \(10^8\) 以下共有 236 对亲和数（Cohen 1970），在 \(10^{10}\) 以下有 1427 对（te Riele 1986），在 \(10^{11}\) 以下有 3340 对（Moews and Moews 1993ab），在 \(2.01 \times 10^{11}\) 以下有 4316 对（Moews and Moews 1996），在约 \(3.06 \times 10^{11}\) 以下有 5001 对（Moews and Moews 1996）。

生成亲和数对的规则包括由费马和笛卡尔重新发现、并由欧拉推广的**塔比特·伊本·库拉规则**，以及由此延伸出的**欧拉规则**。Borho (1972) 发现了之前未被注意到的进一步推广。

Pomerance (1981) 证明了对于足够大的 \(n\)，

\[
[\text{亲和数个数} \leq n] < n e^{-(\ln n)^{1/3}}
\]

（Guy 1994）。目前尚未证明存在非有限的亲和数下界。

记一个亲和数对为 \((m, n)\)，且设 \(m < n\)。若 \((m, n) = (gM, gN)\)，其中 \(g = \gcd(m, n)\) 是最大公约数，且 \(\gcd(g, M) = \gcd(g, N) = 1\)，\(M\) 和 \(N\) 是无平方因子数，并且 \(M\) 与 \(N\) 的素因子个数分别为 \(i\) 和 \(j\)，则称 \((m, n)\) 为类型 \((i, j)\) 的**正则亲和数对**。非正则的数对称为**非正则的**或**奇异的**（te Riele 1986）。对于 \(j \geq 1\)，不存在类型为 \((1, j)\) 的正则对。若 \(m \equiv 0 \pmod{6}\) 且

\[
n = \sigma(m) - m
\]

为偶数，则 \((m, n)\) 不可能是一个亲和数对（Lee 1969）。te Riele (1986) 找到的 \(m/n\) 最小值和最大值分别为

\[
938304290 / 1344480478 = 0.697893577\ldots
\]

和

\[
4000783984 / 4001351168 = 0.9998582518\ldots。
\]

te Riele (1986) 还发现了 37 组具有相同对和的亲和数对。其中第一组是 \((609928, 686072)\) 和 \((643336, 652664)\)，它们的对和为

\[
\sigma(m) = \sigma(n) = m + n = 1296000。
\]

te Riele (1986) 未发现对和相同的 \(n > 2\) 的亲和数 \(n\) 元组。然而，Moews 和 Moews 在 1993 年发现了一个三元组，te Riele 在 1995 年发现了一个四元组。1997 年 11 月，发现了一个五元组和一个六元组。该六元组为 \((1953433861918, 2216492794082)\), \((1968039941816, 2201886714184)\), \((1981957651366, 2187969004634)\), \((1993501042130, 2176425613870)\), \((2046897812505, 2123028843495)\), \((2068113162038, 2101813493962)\)，它们全都具有对和 \(4169926656000\)。令人惊讶的是，这个六元组比任何已知的四元组或五元组都要小，并且很可能小于任何五元组。

最早已知的奇数亲和数都能被 3 整除。这使 Bratley 和 McKay (1968) 猜想不存在与 6 互素的亲和数对（Guy 1994, p. 56）。然而，Battiato 和 Borho (1988) 找到了一个反例，现在已知许多亲和数对不能被 6 整除（Pedersen）。此类中已知的最小例子是亲和数对 \((42262694537514864075544955198125, 42405817271188606697466971841875)\)，其中每个数字都有 32 位。

随后开始了寻找与 30 互素的亲和数对的工作。第一个例子由 Y. Kohmoto 于 1997 年发现，该数对中的每个数字都有 193 位（Pedersen）。Kohmoto 随后又发现了另外两个例子，te Riele 和 Pedersen 利用 Kohmoto 的两个例子，通过一种从类型 \((2,1)\) 数对生成类型 \((3,2)\) 数对的方法，计算出了 243 个与 30 互素的类型 \((3,2)\) 数对。

目前尚未知与 \(2 \cdot 3 \cdot 5 \cdot 7 = 210\) 互素的亲和数对。

下表总结了近年来发现的最大已知亲和数对。其中最大的一对通过如下定义获得：

\[
\begin{aligned}
a &= 2 \cdot 5 \cdot 11, \\
S &= 37 \cdot 173 \cdot 409 \cdot 461 \cdot 2136109 \cdot 2578171801921099 \cdot 68340174428454377539, \\
p &= 925616938247297545037380170207625962997960453645121, \\
q &= 210958430218054117679018601985059107680988707437025081922673599999, \\
q_1 &= (p + q)p^{235} - 1, \\
q_2 &= (p - S)p^{235} - 1,
\end{aligned}
\]

则 \(p, q, q_1, q_2\) 均为素数，且数字

\[
\begin{aligned}
n_1 &= a S p^{235} q_1, \\
n_2 &= a q p^{235} q_2
\end{aligned}
\]

构成一个亲和数对，其中每个成员具有 24073 位十进制数字（Jobling 2005）。

| 位数  | 日期         | 参考文献                |
|-------|--------------|-------------------------|
| 4829  | 1997年10月4日  | M. García              |
| 8684  | 2003年6月6日   | Jobling and Walker 2003 |
| 16563 | 2004年5月12日  | Walker et al. 2004     |
| 17326 | 2004年5月12日  | Walker et al. 2004     |
| 24073 | 2005年3月10日  | Jobling 2005           |

高斯整数中也存在亲和数对，例如

\[
\begin{aligned}
s(8008 + 3960i) &= 4232 - 8280i, \\
s(4232 - 8280i) &= 8008 + 3960i,
\end{aligned}
\]

以及

\[
\begin{aligned}
s(-1105 + 1020i) &= -2639 - 1228i, \\
s(-2639 - 1228i) &= -1105 + 1020i
\end{aligned}
\]

（T. D. Noe，个人通讯）。