A month or so ago, this article was shared on hackernews: http://scienceblogs.com/goodmath/2010/06/22/the-surprises-never-eend-the-u/
There's clearly a visual pattern there - which is why the images are interesting at all - but it's complex enough that you can't quite nail down exactly what it is, only attributes of it.
Could a neural net be trained on images of the known prime space, and begin filling in blanks outside of it as likely candidates for new primes?