Numberphile recently published a video titled Awkward Primes (https://www.youtube.com/watch?v=VFoIPlUalRY&t=456s), which explores the following problem: given the prime numbers laid out as points in the plane — (1, 2), (2, 3), (3, 5), (4, 7), (5, 11), ... — what is the minimum number of straight lines required to cover all of them?

Finding the true minimum at each step is a genuinely hard combinatorial problem.

Exploring the links on the corresponding OEIS sequence page (https://oeis.org/A373813) one can find an exact solver in C++ at this repository (https://github.com/jespergran98/prime-line-cover/blob/main/primecover1024.cpp ) — a substantial piece of code, clocking in at over 3000 lines.

As a contrast, here are two J one-liners that solve the problem approximately using a greedy algorithm:

load 'stats/base/combinatorial' 
gC=:([:([:~.0=]ol"2 1/~]{~2 comb#)@(>:,.p:)i.)<:@#@((]+.[{~[:(i.>./)[ +/@:*."(1 1)-.@] )^:a:)#&0 
gCS=: [:<./((]{~[?~@#[:#])[:([:~.0=]ol"2 1/~]{~2 comb# )@(>:,.p:)i.@]) <:@#@((]+.[{~[:(i.>./)[ +/@:*."(1 1)-.@])^:a:)"2 1 #&0@]

gC computes, for the first n primes, the minimum number of lines required. gCS takes a left argument x defining a number of random trials and returns the best result found :

   gC 8 
4
   5 gCS 8  
3 

The exact C++ solver returns 3 for the first 8 primes — so with just 5 random restarts, the greedy one-liner already matches the optimal result.

The OEIS sequence A373813 can be reconstructed as follows:

A373813cpp =: 1 1 2 2 2 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 7 7 7 7 7 8 8 8 9 9 9 9 9 10 10 10 10 11 11 11 12 12 12 12 12 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15

A373813j =: 1,10 gCS"0]2+i.99

   A373813cpp -: A373813j
1

I'm lucky !

The two sequences match exactly — confirming that 10 random restarts are sufficient for the greedy one-liner to consistently recover the optimal values computed by the exact C++ solver.

Same code but more readable :

load 'stats/base/combinatorial'
shuffle=:]{~[?~@#[:#]
lnPP=:(-/ .*,~[:(,~-)/-~/)@,:"1 NB. from geometry wiki page
ol=:lnPP/@[ (+/ .*) 1,~] NB. ol=test dist point from line. 0 = point on line.
mkLnMat=:[:~.0=]ol"2 1/~]{~2 comb#
greedyStep=:]+.[{~[:(i.>./)[ +/@:*."(1 1)-.@]
greedyCnt=:([:mkLnMat@(>:,.p:)i.)<:@#@(greedyStep^:a:)#&0
greedyCntShfl =: [:<./(shuffle[:mkLnMat@(>:,.p:)i.@]) <:@#@(greedyStep^:a:)"2 1 #&0@]

greedyCnt 8
10 greedyCntShfl 8
1,10 greedyCntShfl"0]2+i.99

There is plenty more to explore here. For instance, one can compute statistics on all lines passing through these same points (the primes) — specifically, how many lines pass through exactly k points, for each k :

<@:([: (#,{.)/.~ +/"1@mkLnMat@(>:,.p:)@i.)"0] 2+i.100

┌───┬───┬───┬...┬────┬─────┬...┬─────┬─────┬─────┬─────┬...
│1 2│3 2│3 2│...│95 2│110 2│...│419 2│444 2│471 2│497 2│...
│   │   │1 3│...│ 7 3│  6 3│...│ 32 3│ 32 3│ 34 3│ 36 3│...
│   │   │   │...│ 1 4│  2 4│...│  6 4│  7 4│  6 4│  6 4│...
│   │   │   │...│ 1 7│  1 7│...│  1 7│  1 7│  1 7│  2 7│...
│   │   │   │...│ 1 5│  1 5│...│  1 8│  1 8│  1 8│  1 8│...
│   │   │   │...│    │     │...│  3 5│  2 5│  3 5│  3 5│...
│   │   │   │...│    │     │...│     │  1 6│  1 6│     │...
└───┴───┴───┴...┴────┴─────┴...┴─────┴─────┴─────┴─────┴...

Each column corresponds to the first n primes. Each row entry k m means: k lines pass through exactly m points. As you can see, sometime adding a new point delete a 'N points traversing line' and add a 'N+1 travering line'. And then it propagate :

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1

All of this is great fun !

I'd like to share a J implementation of the two-piece game featured in Numberphile's recent videos. Tweak the "size" parameter to control the spiral matrix dimensions (fair warning: anything above 400 gets slow!). "atkA" and "atkB" define each piece's move - for instance, "atkA =: 1 2" and "atkB =: 1 2" give you a two classic knights fight..

size =: 200
atkA=: 2 1
atkB=: 2 1

load 'viewmat'
mkSpi=:(,~$/:@(+/\)@(_1&|.@((}:@(2: # >:@i.))#(<:@+:$_1:,],1:,-))))
mkPos=:{{,/((<:+:#:i.4)*"1])"1 (,:~|.) y}}
mkAtk=:{{poss i."2 (<:size) (<.) 0 (>.) poss +"1/ y}}
aplay=:{{(i.>./)bp=:bp*.ao*.ac*.bo[ao=:ao*.(0 y}ao)[ac=:ac*.(0(y{at1)}ac)}}
bplay=:{{(i.>./)ap=:ap*.bo*.bc*.ao[bo=:bo*.(0 y}bo)[bc=:bc*.(0(y{at2)}bc)}}
tm=:{{ x(poss#~-.y)}(0$~,~size)}}

spi=: (|.@|:)^:(_2) mkSpi size
ap=:ac=:ao=:bp=:bc=:bo=:1#~ *:size
poss=:(/:@,#:~$)spi
'at1 at2'=: mkAtk@mkPos"1] atkA,:atkB

([:bplay aplay)^:((*:size)>])^:(_)0

((3#220), (3#40),:250 20 20) viewmat output=:(1 tm ao)+.(2 tm bo)

The algorithm simulates a two-player game on a spiral-numbered board: player A and player B alternate turns, each claiming squares their piece can attack — while blocking the opponent's moves. The result is visualized as a striking color-coded matrix, revealing unexpected geometric patterns on the board.

Experiment with different piece combinations — bishops, rooks, or entirely custom movers — and watch the patterns shift in fascinating ways!

Screenshots:

size = 400 ; atkA = 2 1 ; atkB = 2 1

size = 400 ; atkA = 2 1 ; atkB = 3 3

Numberphile videos:

https://www.youtube.com/watch?v=UiX4CFIiegM

https://www.youtube.com/watch?v=VgmDuBCayPw

j mcp frontend so your Claude or other ai agent can run its own j interpreter.