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

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

Copyright

Public Domain (Please credit me; if you find this code useful I would love to hear about your work!)

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

• [Chum et al.] Chum, K., Guy, R. K., Jacobson, J. M. J., and Mosunov, A. S. (2018). Numerical and statistical analysis of aliquot sequences. Experimental Mathematics, 29(4):414–425.
• [Pomerance and Yang] Pomerance, C. and Yang, H.-S. (2014). Variant of a theorem of Erdos on the sum-of-proper-divisors function. Mathematics of Computation, 83(288):1903–1913.
• [Moews and Moews] Moews, D. and Moews, P. C. (1991). A search for aliquot cycles below 10 10. Mathematics of Computation, 57(196):849.
• [Guy and Selfridge] Guy, R. K. and Selfridge, J. L. (1975). What drives an aliquot sequence? Mathematics of Computation, 29(129):101–101.

NOTATION

• sumdiv / s(n) == sum-of-proper-divisors
• sigma == sum-of-divisors
• kparent == number with k preimages under s(n)

Function Documentation

pomyang_algorithm()

PackedArray* pomyang_algorithm

(

const pomyang_config_t *

cfg

)

Runs the Pomerance-Yang algorithm.

Parameters

cfg	See 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

cfg	See 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

cfg	Pointer to config struct.
filename	Name of file to write.
count	Array of k-parent counts.
runtime	CPU seconds used.