Amicable Numbers

BOINC project Amicable Numbers is an independent research project that uses volunteer computing to find new amicable pairs.

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 get 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. p₁, ..., p_n)

σ(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 1 and in many cases 2 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.