If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000. – Project Euler #1
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000. – Project Euler #1
This problem from Programming Praxis came about in the comments to my last post and intrigued me. So today, we are trying to sum the first one billion primes. Summing the first hundred, thousand, even million primes isn’t actually that bad. But it takes a bit more effort when you scale it up to a billion. And why’s that?
Yesterday’s new post from Programming Praxis asked us to find all triples (a, b, a+b) such that a and b are three digits and a+b is four and concatenating the numbers results in a pandigital number (one with all 10 digits). After that, find the smallest individual number in any of these triples.
A bit shorter on time today, so I’ve just got a quick library that I worked out to solve another problem (I’ll post it later this week when it’s actually working). Basically, when you need to store a heck of a lot of binary flags and don’t want to waste space, the best way to do it would be as one long list of bits. It’s really easy to do in a language like C, but how can you do it in Racket?
When Programming Praxis mentioned that the newest challenge sounded like a Project Euler problem, they were’t wrong. Basically, the idea is to count the number of Pythagorean Triples with perimeters (sum of the three numbers) under a given value. The necessary code to brute force the problem is really straight forward, but then they asked for the count up to one million. With the brute force O(n^2) algorithm (and a relatively high constant), that’s not really feasible. So that’s when we have to get a bit more creative.
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.
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.
Memoization is awesome!
I’ve already written one post on the subject in Python, but this time we’ll do the same in Racket. It’s particularly timely as without it, today’s post on determining the number of prime partitions of a number would take longer to run than I care to wait.
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.