Aliquot Sequence Research  2.0
Compute properties of the sum-of-proper-divisors function.
Functions
pomyang_kparent.c File Reference

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"
Include dependency graph for pomyang_kparent.c:

Functions

PackedArraypomyang_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...
 

Detailed Description

Counts the even numbers with k-preimages under the sum-of-proper-divisors function.

Author
Gavin Guinn (gavin.nosp@m.guin.nosp@m.n1@gm.nosp@m.ail..nosp@m.com)
Date
2021-2-17

NOTE

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.

ALGORITHMS

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.

TECHNIQUE

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

PERFORMANCE

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.

CITATIONS

NOTATION

Function Documentation

◆ pomyang_algorithm()

PackedArray* pomyang_algorithm ( const pomyang_config_t cfg)

Runs the Pomerance-Yang algorithm.

Parameters
cfgSee struct defintion
Returns
PackedArray* containing the number of preimages for even number upto bound. Free'd by caller.

◆ pomyang_count_kparent()

uint64_t* pomyang_count_kparent ( const pomyang_config_t cfg)

runs the Pomerance-Yang algorithm and counts occurrence of kparent numbers.

Parameters
cfgSee struct definition
Returns
uint64_t* buffer of length (UINT8_MAX + 1) with occurrence counts, must be free'd by caller

◆ print_to_file()

void print_to_file ( pomyang_config_t cfg,
const char *  filename,
uint64_t *  count,
float  runtime 
)

Prints Pomerance-Yang algorithm configuration.

Parameters
cfgPointer to config struct.
filenameName of file to write.
countArray of k-parent counts.
runtimeCPU seconds used.