Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Suppose the divisors of nn greater than 11 begin d1<⋯<dkd_1<\cdots<d_k, with sum NN. Put L=lcm⁡(d1,…,dk)L=\operatorname{lcm}(d_1,\ldots,d_k). Then L∣nL\mid n, so L≤nL\le n. Every did_i divides LL. Conversely, if 2≤e≤dk2\le e\le d_k divides LL, it divides nn and hence is one of the did_i, since these are the entire prefix through dkd_k. Thus LL has precisely the same divisor prefix.

Every original witness therefore gives a partition PP of NN into distinct integers at least 22 such that the divisors of lcm⁡(P)\operatorname{lcm}(P) up to max⁡(P)\max(P) are exactly PP, and gives such a witness of size no larger than the original integer. Conversely, any partition passing this test realizes its sum as a divisor prefix of lcm⁡(P)\operatorname{lcm}(P). Taking minima proves the formula, including the convention that an empty family means no witness exists. Every part is at most NN, so each candidate least common multiple divides lcm⁡(1,…,N)\operatorname{lcm}(1,\ldots,N); there are finitely many partitions.

The checker enumerates all increasing distinct-part partitions of each NN in [2,64][2,64]. It verifies partition validity, uniqueness and counts against a separate subset-sum dynamic program, tests the exact divisor-prefix predicate, and minimizes the candidate least common multiples. The retained table contains every minimum and one corresponding prefix. A separate divisor sieve for n≤10000n\le10000 crosschecks all the attained minima; completeness over all nn comes from the reduction, not from this sieve bound.

There are 83,691 tested partitions. Only N=4N=4 has no valid prefix. The largest minimum is f(58)=265f(58)=265, with prefix (5,53)(5,53), whose least common multiple is 265265. The boundary values are f(2)=2f(2)=2, f(3)=3f(3)=3, f(5)=5f(5)=5 and f(6)=4f(6)=4. These exact finite conclusions are the whole computational scope.