An Algorithm to Compute the Erdos-Selfridge Function

Brianna Sorenson Butler University
Faculty Sponsor(s): Jonathan Sorenson Butler University, Jonathan Webster Butler University
We have a new sieving algorithm to compute values of the Erdos-Selfridge function, g(k), using a space- saving wheel data structure. We implemented our algorithm and, so far, have verified the previous work of Lukes, Scheidler, and Williams (1997) by computing g(k) for all inputs less than or equal to 200, and we have extended this by computed g(k) for all k up to 269. This was done using a single processor only. The code was written in C++ and uses 128 bit hardware arithmetic. Kummer's theorem states that a prime p does not divide the binomial coefficient n choose k if and only if the digits of n's representation in base p match or exceed those of k's representation in base p. This theorem allows us to set up a sieve problem to search for g(k) as the smallest residue, larger than k+1, modulo M, that satisfies Kummer's criteria. Let R be the number of all residues modulo M that satisfy Kummer's criteria. Our uniform distribution heuristic states that these R residues behave as if they were chosen uniformly at random < M. In fact, we applied statistical tests, and they support the heuristic. The heuristic implies that that g(k) is between M/(Rk) and (Mk)/R with high probability.
Mathematics & Computer Science
Oral Presentation

When & Where

10:45 AM
Jordan Hall 238