# Decomposing factorial of 300K as the product of 300K factors larger than 100K

**URL:** <https://racket.discourse.group/t/decomposing-factorial-of-300k-as-the-product-of-300k-factors-larger-than-100k/3683>\
**Category:** Show & Tell\
**Created:** [April 9, 2025, 4:43pm UTC](https://racket.discourse.group/t/decomposing-factorial-of-300k-as-the-product-of-300k-factors-larger-than-100k/3683 "2025-04-09T16:43:51Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![gus-massa](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/gus-massa/32/507_2.png) [@gus-massa](https://racket.discourse.group/u/gus-massa)\
**Post date:** [April 9, 2025, 4:43pm UTC](https://racket.discourse.group/t/decomposing-factorial-of-300k-as-the-product-of-300k-factors-larger-than-100k/3683/1 "2025-04-09T16:43:51Z")

</div>

> **[Decomposing factorial of 300K as the product of 300K factors larger than 100K](https://gus-massa.blogspot.com/2025/04/decomposing-factorial-of-300k-as.html)**
>
> A few days ago, Terence Tao proposed a challenge to decompose the 300K! as the product of 300K factors larger than 100K . A smaller example ...

This is a reply to a challenge proposed by Terence Tao, as a small step to try to prove a conjeture. I solved it with Racket.

Not my prettiest code, a lot of single letter variables, a few unnecessary `set!`. I rewrote most of the code many times until I got a good algorithm and I had to go back to finish a few important task IRL.

- It's nice to have a fast factorization algorithm in the standard library. The docs need a warning about problems factorizing huge numbers, but I didn't have any problems with the numbers I used.
- I used an ordered treelists, because I needed fast insertion deletion and lookup of the nearest value. It would be nice to have a ordered trees in the standard library to be able to do a binary search in O(N\log(N)) instead of O(N\log^2(N)).
- At the end, I used some brute force that I didn't expect. I should have added memoization to the factorization of N! too, and a fancy formula to calculate the factorization of B,.
- [Andrew Sutherland already solved this](https://terrytao.wordpress.com/2025/03/26/decomposing-a-factorial-into-large-factors/#comment-687574), but using an algorithm that is very different from the one proposed by Tao. I'm not sure what is Tao's plan for a general proof.

---

<div class="post-metadata">

**Author:** ![jbclements](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/jbclements/32/11_2.png) [@jbclements](https://racket.discourse.group/u/jbclements)\
**Post date:** [April 10, 2025, 4:00am UTC](https://racket.discourse.group/t/decomposing-factorial-of-300k-as-the-product-of-300k-factors-larger-than-100k/3683/2 "2025-04-10T04:00:00Z")

</div>

Loved this link! Nice work!