I love the idea of using OEIS to automate finding mathematical patterns in the solution. Also, plotting the search space immediately is something I know is often unreasonably effective, but I almost never take the time to do. This is a fantastic little article.
Given that I'm a bit of a moron mathematically, I have, more times than I cared to admit, made serious progress on a problem by (a) writing a Python or C++ program to spew out a highly non-scalable count of some entity whose nature I'm trying to understand and (b) taking that count and sticking it in OEIS.
This has led to some pretty major insights, which one can carefully 'launder' casually as something you knew all along. "Oh, of course the number of subtrees can be found by half-Catalan numbers", you say, with aplomb, as if you hadn't learned about half-Catalan numbers approximately 10 minutes ago.
Unfortunately, if you spot that pattern then you will not guess the correct generalization. It seems that this may be a puzzle that's easier to solve if you aren't good at spotting easy things.
Well tbh, it seems 2^k-1 does actually match the sequence as far as it is shown. Perhaps there is a proof that n=2^k-1 for the numbers where 2^n is divisible by (n+1). I'll have to see.
I got lost at step 3. I wasn't super clear in how we went from line to memoization. Cool article though - I had never thought of plotting before to recognize patterns.
If you write out the coordinates for a straight line from the origin they look like this:
3, 5; 6, 10; 9, 15...
So now, instead of having to test 6, 10 and 9, 15 when we see it, we can just test 3, 5 once and we'll know the answer to all of the points on that line. Then, to answer the question "which line is this point on?" we simplify the fraction (i.e. 2, 6 -> 1, 3).
"While Python is usually great for programming puzzles, this step in particular is crying out for something like QuickCheck: without it, we'll have to roll our own."
Instead of rolling his own, the author could have just used Python's Hypothesis package.[1][2]
