prime factorization using base 1

[tye]

I recently realized the power of base-1 numbers. They don't have the arbitrary range limitations of Perl's regular number representations while converting between the two is nearly trivial. Plus finding prime base-1 numbers is particularly compact code in Perl. And when the primality test fails you are also handed some factors! So base-1 numbers are perfect for finding prime factorizations! They aren't very space efficient, unfortunately (hey, no one's perfect).

So factor1() returns the prime factorizations of base-1 numbers (as base-1 numbers). factor10() just converts a base-10 number into a base-1 number so factor1() can factor it and then converts the returned list of base-1 factors into base 10 again.

One line of test code is included that factors any base-10 numbers given on the command line.

Now updated to be faster!

#!/usr/bin/perl -w
use strict;

sub factor1 {
    return @_  if  $_[0] !~ /^(..+?)\1+$/;
    return map { factor1($_) }
        ( "$1", $_[0] =~ s/$1/1/g, $_[0] )[0,-1];
}

sub factor10 {
    return map {length} factor1( 1x$_[0] );
}

print join $/, map { join " ", factor10($_) } @ARGV;

[clemburg]

Our regex engine is truly The Little Engine That Could! Nice idea, tye. Going back to the fundamentals often pays ;-) ...

Here is something similar I worked out for a statistics module that needed tie-adjusted ranks (a "tie" occurs in a list of numbers if two numbers have exactly the same value - something that most statistics algorithms don't really like because it violates their assumptions about continuous distributions).

sub ties {
    my @val =  sort @_;
    return () unless @val;
    my @delta = (1) x @val - 1;
    for (my $i = 1; $i < @val; $i++) {
        $delta[$i - 1] = $val[$i] - $val[$i - 1] ? 1 : 0;
    }
    my @ties = map {length} split /1+/, join '', @delta;
    shift @ties unless $ties[0];
    return map {++$_} @ties;
}

Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com

[ambrus]

Some later nodes that refer to this trick are Re: Simple primality testing, Re^2: The Oldest Plays the Piano, Re: Calculate prime factors for a given number in a perl one-liner, Re: is it prime?.

Update 2015-10-22: See also "How does this regular expression work?" (2010-07) question on StackOverflow which asks about a similar regex in the article "A regular expression to check for prime numbers" (2007-03) by Avinash Meetoo