The stupid question is the question not asked PerlMonks

### prime factorization using base 1

by tye (Sage)
 on Jan 17, 2001 at 10:43 UTC 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;
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

Create A New User
Node Status?
node history
Node Type: snippet [id://52469]
help
Chatterbox?
 [Corion]: Heh. After a bit of hacking, the Pg parser now "just" fails because some Win32 functions of Postgres aren't included in the lib I'm hacking up. Progress, I guess :)

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (6)
As of 2018-03-23 21:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (296 votes). Check out past polls.

Notices?