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

Brianna Sorenson; Jonathan P Sorenson; Jonathan Webster

doi:10.2140/obs.2020.4.371

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

Brianna Sorenson, Jonathan P Sorenson, Jonathan Webster

Butler University

Research output: Contribution to journal › Article › peer-review

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    p    (    (    g    (    k    )    k    )    )    >    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
   g    (375)=12863999653788432184381680413559. 
 We prove that our algorithm runs in time sublinear in    g    (    k    )  , and under the assumption of a reasonable heuristic, its running time is
   g    (    k    )exp    [    −    c    (    k    loglog    k    )    /    (log    k    )    2    (1+    o    (1))    ]     for     c    >0. 
 

Original language	American English
Journal	Proceedings of the Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), Open Book Series
Volume	4
Issue number	1
DOIs	https://doi.org/10.2140/obs.2020.4.371
State	Published - Dec 29 2020

Keywords

Erdos–Selfridge function
analytic number theory
binomial coefficients
elementary number theory

Disciplines

Theory and Algorithms
Number Theory

Access to Document

10.2140/obs.2020.4.371License: Unspecified

Cite this

@article{e67d3ab6163c449aab1e1e546e9de54a,

title = "An algorithm and estimates for the Erd{\H o}s–Selfridge function",

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 p ( ( g ( k ) k ) ) > 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 g (375)=12863999653788432184381680413559. We prove that our algorithm runs in time sublinear in g ( k ) , and under the assumption of a reasonable heuristic, its running time is g ( k )exp [ − c ( k loglog k ) / (log k ) 2 (1+ o (1)) ] for c >0. ",

keywords = "Erdos–Selfridge function, analytic number theory, binomial coefficients, elementary number theory",

author = "Brianna Sorenson and Sorenson, {Jonathan P} and Jonathan Webster",

year = "2020",

month = dec,

day = "29",

doi = "10.2140/obs.2020.4.371",

language = "American English",

volume = "4",

journal = "Proceedings of the Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), Open Book Series",

number = "1",

}

TY - JOUR

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

AU - Sorenson, Brianna

AU - Sorenson, Jonathan P

AU - Webster, Jonathan

PY - 2020/12/29

Y1 - 2020/12/29

N2 - 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 p ( ( g ( k ) k ) ) > 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 g (375)=12863999653788432184381680413559. We prove that our algorithm runs in time sublinear in g ( k ) , and under the assumption of a reasonable heuristic, its running time is g ( k )exp [ − c ( k loglog k ) / (log k ) 2 (1+ o (1)) ] for c >0.

AB - 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 p ( ( g ( k ) k ) ) > 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 g (375)=12863999653788432184381680413559. We prove that our algorithm runs in time sublinear in g ( k ) , and under the assumption of a reasonable heuristic, its running time is g ( k )exp [ − c ( k loglog k ) / (log k ) 2 (1+ o (1)) ] for c >0.

KW - Erdos–Selfridge function

KW - analytic number theory

KW - binomial coefficients

KW - elementary number theory

UR - https://msp.org/obs/2020/4-1/obs-v4-n1-p23-s.pdf

U2 - 10.2140/obs.2020.4.371

DO - 10.2140/obs.2020.4.371

M3 - Article

VL - 4

JO - Proceedings of the Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), Open Book Series

JF - Proceedings of the Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), Open Book Series

IS - 1

ER -

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

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this