Decomposing factorial of 300K as the product of 300K factors larger than 100K
a year ago
- #mathematics
- #factorial-decomposition
- #number-theory
- Terence Tao proposed a challenge to decompose 300K! into 300K factors larger than 100K.
- A smaller example is decomposing 10! into 10 factors greater than or equal to 3.
- Tao's method involves using B-heavy primes and N!-heavy primes, leveraging powers of 2 to adjust factors.
- The goal is to optimize the use of 2s to ensure factors remain above the threshold (100K).
- A Racket implementation was used to factorize and balance primes, achieving decomposition with factors > 100K.
- The optimal method involves a greedy algorithm to match B-heavy primes with N!-heavy primes, minimizing 2 usage.
- Successful decomposition was achieved with factors > 100K using A=283 repetitions, leaving 53 leftover 2s.