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, 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.