Project Euler 555 - McCarthy 91 Function

Official link: https://projecteuler.net/problem=555

Thought Process

Another really fun problem!

I started with some research on the McCarthy 91 Function and at the bottom of the Wikipedia page there is an article which links to Donald E. Knuths Generalizations of this function: https://arxiv.org/pdf/cs/9301113v1.pdf

Specifically Theorem 1. Using this and noticing patterns, which can be proved from the theorem I was able to solve the problem.

Note: I recommend you stop reading here and try to figure it out from here, I promise you that you have everything you need already!

From here I started looking for ways to calculate the fixed points faster.

I noticed that if t = m + k - 2s then if M(t, m, k, s) = t, that is t, is a fixed point then all values from t - (k - s) + 1 to t are also fixed points. The proof of this is not too difficult.

With this, the algorithm for a naïve answer is simple to formulate. My code ran in ~40 seconds, and I also had fun making a fast divisors function (About time, I've been using the simplest version for a while now)

After solving and looking at the thread I made a minor update resulting in runtime goin to ~6 seconds:

Interactive Code

Enter 2 Integers separated by a space (p, m)

Code will output S(p, m)

Page updated

Google Sites

Report abuse