Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

prime factorization using base 1

by tye (Cardinal)
on Jan 17, 2001 at 10:43 UTC ( #52469=snippet: print w/ replies, xml ) Need Help??

Description: 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;
Comment on prime factorization using base 1
Download Code
Replies are listed 'Best First'.
Re: prime factorization using base 1
by clemburg (Curate) on Jan 17, 2001 at 14:46 UTC

    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

Re: prime factorization using base 1
by ambrus (Abbot) on Dec 16, 2010 at 10:18 UTC

Back to Snippets Section

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: snippet [id://52469]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2015-07-29 01:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (260 votes), past polls