Calculating M(n)

March 01, 2020

Calculating values of M(n) is now linear in memory since Dr. Jonathan Webster and I have created and implemented a new solution.

M(n) is defined as the number of distinct integers in the n by n multiplication table. Dr. Jonathan Webster and I at Butler University have implemented an algorithm in C++ to determine values of M(n) for n up to 230. The algorithm uses linear space complexity and has been implemented in parallel.

I presented a poster with Jonathan Webster at ANTS 2018 in Madison, Wisconsin. The poster discussed the history of the problem and the new algorithm we implemented to calculate M(n) in asymptotically less space, and practically less time.

At Butler University's Undergraduate Research Conference I presented my contribution to the problem and optimizations on the algorithm. I gave this presentation in April of 2019. In addition, I created a website that visualizes the problem by generating graphics that represent the algorithm at different values of n.

Most recently, the paper has been submitted to arXiv.