An algorithm and estimates for the Erdős-Selfridge function

DOI10.2140/OBS.2020.4.371MaRDI QIDQ5853810zbMATH OpenOpenAlexFDO

Authors Brianna Sorenson, Jonathan Webster, Jonathan P. Sorenson

Publication date 11 March 2021

Published in Open Book Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.08559

zbMATH Keywords

analytic number theorybinomial coefficientselementary number theoryErdős-Selfridge function

Mathematics Subject Classification ID

Binomial coefficients; factorials; (q)-identities (11B65) Number-theoretic algorithms; complexity (11Y16)

Abstract: Let $p(n)$ denote the smallest prime divisor of the integer $n$. Define the function $g(k)$ to be the smallest integer $>k+1$ such that $$. So we have $g(2)=6$ and $g(3)=g(4)=7$. In this paper we present the following new results on the ErdH{o}s-Selfridge function $g(k)$: We present a new algorithm to compute the value of $g(k)$, and use it to both verify previous work and compute new values of $g(k)$, with our current limit being ${\displaystyle }$ g(323)= 1 69829 77104 46041 21145 63251 22499. ${\displaystyle }$ We define a new function $hatg(k)$, and under the assumption of our Uniform Distribution Heuristic we show that ${\displaystyle }$ log g(k) = log hat{g}(k) + O(log k) ${\displaystyle }$ with high "probability". We also provide computational evidence to support our claim that $hatg(k)$ estimates $g(k)$ reasonably well in practice. There are several open conjectures on the behavior of $g(k)$ which we are able to prove for $hatg(k)$, namely that ${\displaystyle }$ 0.525ldots +o(1) quad le quad frac{log hat{g}(k)}{k/log k} quad le quad 1+o(1), ${\displaystyle }$ and that ${\displaystyle }$ limsup_{k ightarrowinfty} frac{hat{g}(k+1)}{hat{g}(k)}=infty.${\displaystyle }$ Let $G(x,k)$ count the number of integers $nlex$ such that $$. Unconditionally, we prove that for large $x$, $G(x,k)$ is asymptotic to $x/hatg(k)$. And finally, we show that the running time of our new algorithm is at most $g(k)exp[-c(kloglogk)/(logk{)}^2(1+o(1))]$ for a constant $c>0$.

Recommendations

• Further tabulation of the Erdös-Selfridge function
• Prime factors of consecutive integers
• A Method of Tabulating the Number-Theoretic Function g(k)
• A New Function Associated with the Prime Factors of \binomnk
• Sur la loi de répartition du k-ième facteur premier d'un entier

Cited in

(4)

• scientific article; zbMATH DE number 4017268 (Why is no real title available?)
• Prime factors of consecutive integers
• A Method of Tabulating the Number-Theoretic Function g(k)
• Further tabulation of the Erdös-Selfridge function

This page was built for publication: An algorithm and estimates for the Erdős-Selfridge function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853810)