Aliquot Sequence Research
2.0
Compute properties of the sum-of-proper-divisors function.
|
Counts the even numbers with k-preimages under the sum-of-proper-divisors function. More...
#include "../inc/pomyang_kparent.h"
#include <assert.h>
#include <math.h>
#include <omp.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <alloca.h>
#include <time.h>
#include "../inc/moewsmoews_sieve.h"
#include "../inc/math_macros.h"
Functions | |
PackedArray * | pomyang_algorithm (const pomyang_config_t *cfg) |
Runs the Pomerance-Yang algorithm. More... | |
uint64_t * | pomyang_count_kparent (const pomyang_config_t *cfg) |
runs the Pomerance-Yang algorithm and counts occurrence of kparent numbers. More... | |
void | print_to_file (pomyang_config_t *cfg, const char *filename, uint64_t *count, float runtime) |
Prints Pomerance-Yang algorithm configuration. More... | |
Counts the even numbers with k-preimages under the sum-of-proper-divisors function.
The counts of non-aliquots reported by this program will be exactly one less than the published figures! This algorithm enumerates all even k-parent numbers, odd k-parent numbers exist but they are not considered. The user is expected to adjust the count to consider 5 which is the only odd aliquot (see sect. 3, [Chum et al.]). It may seem odd to only count even k-parent numbers while odd k-parents also exist, this program must be seen in the context of using heuristics to approach the Guy-Selfridge conjecture, see [Guy and Selfridge] and [Chum et al.] for details.
This is a rewrite of Anton Mosunov's implementation of the tabulation of untouchable numbers, section 3 of [Chum et al.]. As described in the paper this program is capable of counting of aliquot untouchables and more generally counting numbers with k preimages under the sum-of-proper-divisors (sumdiv
/ s(n)
) function, these numbers are referred to as k-parent. The algorithm employed in [Chum et al.] was originally developed in a paper of [Pomerance and Yang] where the author's describe a family of algorithms for enumerating preimages, the algorithm for s(n) will be referred to as the Pomerance-Yang (pomyang
) algorithm. The pomyang
algorithm takes the sum-of-divisors (sigma) for all odd numbers in the range (1, bound
) as input, to produce these values a technique of [Moews and Moews] for sieving ranges of sigma is used to efficiently generate these values.
The techniques used in this implementation broadly differ from those described in [Chum et al.], notably no disc operations are used. The sum-of-divisors (sigma) for all odd numbers in the range (1, bound
) are sieved on-the-fly rather than ^pre-computed and stored. A buffer is required to hold the counts of preimages for all even numbers less than bound
, this can require huge amounts of memory (using 8 bit counter takes ~500gb
at bound
of 2^40). When enumerating non-aliquots only 1-bit per number is required, however sizeof(bool) == sizeof(uint8_t)
as a byte is the smallest addressable unit of memory. A PackedArray data structure is used to create a buffer that can store 1, 2, or 4 bits of information in exactly that much memory, vasty decreasing memory requirements. Threads must share this buffer when running the otherwise embarrassingly parallel pomyang algorithm, this is accomplished by allocating an array of locks to protect portions of the resource. Locking the entire buffer whenever a thread wants to record a image bottlenecks the whole process.
^ [Chum et al.] indicates only sieving odd sigma upto bound
/ 2 but odd sigma upto bound
is certainly a required input for the Pomerance-Yang algorithm
The parameter num_locks should be set to the highest value possible given memory constraits to optimize for speed. The parameter seg_len has a far more ambiguous effect on performance, if set either to low or high it can seriously impact performance see moews_moews_sieve.c for a more detailed analysis.
PackedArray* pomyang_algorithm | ( | const pomyang_config_t * | cfg | ) |
Runs the Pomerance-Yang algorithm.
cfg | See struct defintion |
uint64_t* pomyang_count_kparent | ( | const pomyang_config_t * | cfg | ) |
runs the Pomerance-Yang algorithm and counts occurrence of kparent numbers.
cfg | See struct definition |
void print_to_file | ( | pomyang_config_t * | cfg, |
const char * | filename, | ||
uint64_t * | count, | ||
float | runtime | ||
) |
Prints Pomerance-Yang algorithm configuration.
cfg | Pointer to config struct. |
filename | Name of file to write. |
count | Array of k-parent counts. |
runtime | CPU seconds used. |