Decomposing factorial of 300K as the product of 300K factors larger than 100K
a year ago
- #mathematics
- #factorial-decomposition
- #number-theory
- 陶哲轩提出挑战：将300K!分解为300K个大于100K的因数。
- 一个较小的例子是将10!分解为10个大于等于3的因数。
- 陶的方法涉及使用B-heavy素数和N!-heavy素数，并利用2的幂次调整因数。
- 目标是通过优化2的分配确保所有因数超过阈值（100K）。
- 使用Racket实现素数分解与平衡，最终得到所有因数>100K的分解结果。
- 最优方案采用贪心算法匹配B-heavy与N!-heavy素数，最小化2的消耗。
- 最终通过A=283次重复成功分解，剩余53个2，所有因数均>100K。