Amicable Numbers
Amicable Numbers is an independent research project that uses BOINC based volunteer computing and needs your help to find new amicable pairs.,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.https://sech.me/ap/articles.html#a1
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 < 1013 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=1010...1017 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.
Contributing
If you're interested in supporting this project, visit the official website and attach to the project using its official URL: https://sech.me/boinc/Amicable/.
