You're reading: cp's mathem-o-blog

Prime Run

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.

Prime Run Land

Challenge for the future: replace the game’s current minimalist interface with a map like this, that’s filled in on the fly as you move.

In the map above – which I’m glad to say took me almost as long to draw as it took to make the actual game – there are two routes from 779 to 559. One route went for the big numbers straight away, heading down route 41 as far as possible before fiddling about in the low-numbered roads. The second route nips along routes 19 and 2 to get to 151, which gets you there much quicker.

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.

Mr L-P declines to comment on whether “I need a quick two minute puzzle” is a euphemism for going to the toilet

Either way, I consider this game a success because it occupied all my “I need a quick two minute puzzle” moments for a week or two.

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.

One Response to “Prime Run”

  1. Avatar Roger

    Here’s a short Mathematica program that will find the shortest path(s) between two given integers:


    short[s_, t_] := Module[{paths}, paths = {{s}};
    While[Not[MemberQ[Last@Transpose@paths, t]],
    paths = Flatten[addelement /@ paths, 1]];
    Select[paths, MemberQ[#, t] &]
    ]
    addelement[path_] :=
    Module[{l, f}, l = Last@path;
    f = First@Transpose@FactorInteger@Last@path;
    Select[Append[path, #] & /@ Select[Join[l + f, l - f], # > 1 &],
    Sort@# == Union@# &]]

    I was surprised to see that the shortest path from 2 to 17 was 12 steps (including both 2 and 17).

    It runs pretty quickly on numbers with few prime factors, but for example on two randomly chosen reasonably composite numbers, 95256 and 166617, it takes about 35 seconds on my machine to come up with {95256, 95253, 127004, 127002, 127063, 124980, 124977, 166636, 166634, 166617}

    Reply

Leave a Reply to Roger

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Google+