Amicable Numbers

Amicable Numbers is an independent research project that uses BOINC based volunteer computing and needs your help to find new amicable pairs.

Demonstration, with rods, of the amicability of the pair of numbers (220,284)

Why Amicable Numbers?

Collecting data on all amicable numbers up to a very large limit will facilitate theoretical research in several fields: 1, 2, 3 to name a few examples.

Data from this project will also help to improve understanding of the properties of Divisor function.

Goal

The current goal of Amicable Numbers is to find all amicable pairs with smallest member < 1021.

Methods

BOINC is used because it is the only viable way for this independent project to obtain computational power at this scale.

Terminology

N - the limit for the search. The algorithm must find all amicable pairs with smaller member m ≤ N

m - smaller number in a pair

n - larger number in a pair, or an arbitrary natural number when used in enumerations (i.e. p1, ..., pn)

σ(m) - sum of all divisors of m, including 1 and m.

The following basic algorithm can be derived from the very definition of amicable pairs:

• Iterate over all numbers between 1 and N
• For each number m, calculate n=σ(m)-m
• If n > m, then calculate σ(n)
• If σ(n) = σ(m), then (m, n) - amicable pair

This is very inefficient because it requires one and in many cases two full factorizations per iteration, so improvements were devised.[1]

1. Avoiding factorization of m

2. Trimming down factorization of n

3. Reducing search space

As a result of these improvements, this projects algorithm - download the source code: Amicable.zip - finds all amicable pairs < 10¹³ in just ~24 minutes on Core i7-4770K (8 parallel threads). The asymptotic complexity of the algorithm seems to be O(N×log(log(N))) and there is no strict proof, but run times for N=10¹⁰...10¹⁷ align almost perfectly with C×N×log(log(N)).

The latest source code is also available on GitHub: https://github.com/SChernykh/Amicable

Project team / Sponsors

Sergei Chernykh

Scientific results

New data from this project is published regularly on the Amicable pairs list page.