Last summer, someone asked on stackoverflow how to factor a positive integer into prime numbers, and give the output on the form of powers at the right position in a sequence. Let us take a simple example: 825 is 3 × 5 × 5 × 11. The first prime numbers are 2, 3, 5, 7, 11. So 825 can be represented uniquely as the sequence (0 1 2 0 1) because it is equal to 2⁰ × 3¹ × 5² × 7⁰ × 11¹.

Like a lot of people there, I could not resist giving an implementation of the requested functionality in one of my favorite programming languages to show how easy it was. In Factor the math.primes and math.primes.factors vocabularies make it a very easy task. Let us describe it step by step.

The Factor implementation

group-factors takes a number to factor and returns a sequence of pairs, each containing a prime factor and the number of times this factor appears, starting with the lowest prime factor and ending with the highest one.

( scratchpad ) 825 group-factors .
{ { 3 1 } { 5 2 } { 11 1 } }

Next, we need the first prime numbers up-to the highest prime factor (11 in our case). Starting from our list, we can extract the first element of the last pair, which is the highest prime factor, and ask for the primes-numbers up to this number using primes-upto:

( scratchpad ) { { 3 1 } { 5 2 } { 11 1 } } last first primes-upto .
V{ 2 3 5 7 11 }

Then, starting again from the original factors list and this new primes number list, we can look up for each prime its corresponding power, or use 0 if it is not present. Easy, no?

Here is the complete implementation with the necessary plumbing added:

USING: assocs kernel math.primes math.primes.factors sequences ;
: count-factors ( n -- seq )
    group-factors [ last first primes-upto ] keep
    [ at 0 or ] curry map ;

Testing it gives, as expected:

( scratchpad ) 825 count-factors .
V{ 0 1 2 0 1 }

Doing it in J

Incidentally, while browsing stackoverflow today, I found this question again and realized that no one had given the obvious answer in J: there exists a built-in operator doing exactly the requested operation.

_ q:825
0 1 2 0 1

The reverse functionality is easy to use as well:

_(q:^:_1) 0 1 2 0 1
825

However, despite the conciseness of the J solution, I will rather use Factor for real work, as I usually expect to be able to decipher the code I wrote the day before.

blog comments powered by Disqus