Factoring factorials

There was a new post on Programming Praxis a few days ago that seemed pretty neat:

Given a positive integer n, compute the prime factorization, including multiplicities, of n! = 1 · 2 · … · n. You should be able to handle very large n, which means that you should not compute the factorial before computing the factors, as the intermediate result will be extremely large.

read more...


Smallest consecutive four-factor composites

Another post from Programming Praxis, from this past Tuesday:

The smallest pair of consecutive natural numbers that each have two distinct prime factors are 14 = 2 * 7 and 15 = 3 * 5. The smallest triplet of consecutive natural numbers that each have three distinct prime factors are 644 = 2^2 * 7 * 23, 645 = 3 * 5 * 43 and 646 = 2 * 17 * 19. What is the smallest set of four consecutive natural numbers that each have four distinct prime factors?

read more...


Nested Primes

Yesterday’s post from Programming Praxis poses an interesting problem: find the largest prime n such that the result of repeatedly removing each digit of n from left to right is also always prime.

For example, 6317 would be such a number, as not only is it prime, but so are 317, 17, and 7.

read more...


The Sum Of The First Billion Primes

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?

read more...


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.

read more...