info prev up next book cdrom email home

Erdös-Selfridge Function

The Erdös-Selfridge function $g(k)$ is defined as the least integer bigger than $k+1$ such that all prime factors of ${g(k)\choose k}$ exceed $k$ (Ecklund et al. 1974). The best lower bound known is

g(k)\geq \mathop{\rm exp}\nolimits \left({c {\ln^3 k\over\ln\ln k}^{1/2}}\right)

(Granville and Ramare 1996). Scheidler and Williams (1992) tabulated $g(k)$ up to $k=140$, and Lukes et al. (1997) tabulated $g(k)$ for $135\leq k\leq 200$. The values for $n=2$, 3, ... are 4, 7, 7, 23, 62, 143, 44, 159, 46, 47, 174, 2239, ... (Sloane's A046105).

See also Binomial Coefficient, Least Prime Factor


Ecklund, E. F. Jr.; Erdös, P.; and Selfridge, J. L. ``A New Function Associated with the prime factors of ${n\choose k}$. Math. Comput. 28, 647-649, 1974.

Erdös, P.; Lacampagne, C. B.; and Selfridge, J. L. ``Estimates of the Least Prime Factor of a Binomial Coefficient.'' Math. Comput. 61, 215-224, 1993.

Granville, A. and Ramare, O. ``Explicit Bounds on Exponential Sums and the Scarcity of Squarefree Binomial Coefficients.'' Mathematika 43, 73-107, 1996.

Lukes, R. F.; Scheidler, R.; and Williams, H. C. ``Further Tabulation of the Erdös-Selfridge Function.'' Math. Comput. 66, 1709-1717, 1997.

Scheidler, R. and Williams, H. C. ``A Method of Tabulating the Number-Theoretic Function $g(k)$.'' Math. Comput. 59, 251-257, 1992.

Sloane, N. J. A. Sequence A046105 in ``The On-Line Version of the Encyclopedia of Integer Sequences.''

© 1996-9 Eric W. Weisstein