Here’s a game I’ve been trying to make for a while.

For a while I’ve had a hunch that there’s fun to be had in moving between numbers by using something related to the prime numbers.

Over the years I’ve tried out a few different ideas, but none of them ever worked out – they were either too easy, too hard, or just not interesting. This time, I think I’ve found something close enough to the sweet spot that I’m happy to publish it.

Prime Run is a game about adding and subtracting prime numbers. You start at a random number, with a random target. Your goal is to reach the target, by adding or removing any prime factor of your current number.

The game doesn’t say this explicitly, but I suppose doing it in as few moves as possible is an interesting objective.

In a fit of hubris, I’ve put this on the URL isthisprime.com/game2, raising comparisons with my original “Is this prime?” game. This game is definitely not as accessible as that.

Prime Run is fairly easy to play if you’re just concerned with getting to the target, but it’s surprisingly difficult if you want to find the shortest solution.

It turns out I don’t have a very good intuition for which prime numbers are close to a given integer. Do you?

Playing Prime Run is a bit like trying to drive somewhere without a map, just looking at the place names on the road signs. You can usually be sure you’re moving in the right direction, but with some local knowledge you might know there’s a little side road that gets you on a much quicker route.

In Prime Run Land, there’s a town for each positive number, and roads for each prime, connecting them all.

I wanted to have the game tell you if you’d got to the target in the minimum number of moves, but it turns out that finding the shortest path is really hard! The difficulty doesn’t come from factorisation, which is famously difficult (it’s in the NP class, if not NP-complete), but from the enormous combinatorial explosion of possible paths between two numbers.

Once I realised that computing the shortest path on the fly was too hard to do on a mobile phone while keeping it responsive, I looked at pre-computing the matrix of distances between every pair of integers that the game might produce. Just looking at numbers up to $10,\!000 = 10^4$, that makes $10^8$ pairs. My initial brute-force attempts didn’t get much further than $10^6$ pairs.

I tried writing down an abstract description of the problem. I have a big graph with a vertex for each positive integer, and an edge between vertices $a$ and $b$ if there is an $n$ such that $n|a$ and $n|b$. (There are also edges from each prime to $0$, but forget about that because it’s a dead end)

I found out that there are some algorithms for solving this problem. I knew about Dijkstra’s algorithm, which can find the shortest route from a given vertex to each of the other vertices, so I thought that I could just wave my hands and say “do it $N$ times” and end up with a full matrix of distances. I got in a pickle with list indices, I think, so it kept going wrong.

After some googling, I found the Floyd-Warshall algorithm, which aims to produce the entire distance matrix. I think it effectively does what I was trying to do, but correctly. This was also too slow.

Finally, I thought I’d just see if there’s an algorithm in SciPy that does what I want, without thinking about it. There is a function scipy.sparse.csgraph.shortest_path which makes a guess at the best algorithm to use on the given parameters.

This, too, was far too slow.

So I gave up! The game doesn’t tell you if you got the shortest answer.

I’d like it to do something, though. Maybe it’d be feasible to make it use a heuristic algorithm like A* to come up with a “par” score, which you might be able to beat. I’m not sure what the heuristic would look like, though.

More information

Play Prime Run.

The source code is on GitHub, if you’d like to take a look or make a variation on my game.