Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

prime factorization using base 1

by tye (Sage)
on Jan 17, 2001 at 10:43 UTC ( [id://52469]=CUFP: print w/replies, xml ) Need Help??

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

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

Log In?

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

How do I use this?Last hourOther CB clients
Other Users?
Others lurking in the Monastery: (4)
As of 2024-06-17 10:29 GMT
Find Nodes?
    Voting Booth?

    No recent polls found

    erzuuli‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.