Prime Partitions II: The Listing

As the continuation of Saturday’s post on counting the number of prime partitions of a number without actually determining what those partitions are, today we’re going to work out the actual list of partitions.

Prime Partitions

Today we’re back into the mathy sort of problems from Programming Praxis, tasked with calculating the number of prime partitions for a given number–essentially, how many different lists of prime numbers are there that sum to the given number.

For example, working with 11, there are six prime partitions (I’ll show the code for this later):

> (prime-partitions 11)
'((2 2 2 2 3) (2 2 2 5) (2 2 7) (2 3 3 3) (3 3 5) (11))


Unfortunately, the number of prime partitions quickly gets ridiculous. Once you get to 1000, there are 48 quadrillion prime partitions… So generating all of them isn’t exactly feasible.

Rule 30 RNG

Today we get away from the word games for a little while and get back to talking about random number generators (previous posts here and here). Or rather one random number generator in specific: a Rule 30 psuedo-random number generator (PRNG). (Here’s the motivating post from Programming Praxis.)

Remember the previous post I made about cellular automaton? The basic idea is to turn those into a random number generator. If you go back to the linked post in particular and give it Rule 30 with a random initial state, you can see how chaotic the rows seem to be. Perfect for a PRNG.

Probability can be a bit counter-intuitive at times. Take for example, the birthday problem / paradox: how many people do you need in a room to have a 50/50 chance that two share the same birthday?

HTML5 Bugs

In the spirit of yesterday’s post about HTML5’s canvas, I’ve got another post. This time, it’s a little buggy. 😄

Line art with an HTML5 canvas

Let’s play with HTML5 canvas elements!

Basically, I want to draw some simple line diagrams. Go from top to bottom on one side while going from right to left along the top or bottom. It sounds complicated, but perhaps it’s easier to explain with a drawing:

n-queens in 18 lines of code

One of the rites of passage for computer scientists it seems is to solve the Eight Queens Problem–where you must place 8 queens on a chessboard so that no pair of queens is attacking each other. Even better is when you can expand that to the n-queens problem with n queens on an n by n chessboard. After finding it again in older posts on both Programming Praxis and DataGenetics, I decided to go ahead and take a crack at it and I think the solution is pretty straight forward.