Home Primes...

[Xyzzy]

http://mathworld.wolfram.com/HomePrime.html

Obviously, there are better ways to code this, but I had a lot of fun and learned some stuff in the process...

Too bad "factor" bails so easily...

#!/bin/sh
counter=1
while [ $counter != 48 ]
do
        a=$counter
        while :
        do
                temp=`factor $a`
                b=`echo $temp | cut -d ":" -f2 | tr -d " "`
                echo `echo $temp | tr ":" "=" | sed 's/=/ =/'`
                if [ $a = $b ]
                then
                        break
                fi
                a=$b
        done
echo
(( counter += 1 ))
done

I would be interested in seeing if this could be made into a simpler script... I have a thing for really short scripts, even if they are obfuscated...

[smh]

No script, and definitely not simple, but i have an UBasic program to calculate these numbers with the use of trail factoring and ECM.

It's much faster though.

[marc]

def homePrime(x):
    y = int("".join(factor(x)))
        
    while y != x:
        x, y = y, int("".join(factor(y)))
        
    return y

Assuming you have a factor() which returns a list of str factors.

[patrik]

1. Regarding marc's code: What language is this? How should one start it?

2. Regarding the `` in xyzzy's script: I run a script with a substitution, and once every 50000 times or so I seem to get the error message "Can't reopen pipe to command substitution: No child processes." Does anyone know anything about this? (50000 is just a guess, but it is something between 10^4 and 10^5.)

[marc]

That's Python. You just need a Python installation and a Python factor() function.

[Ken_g6]

Here's a PERL program that uses the same method the original script - calling other factoring programs. But it uses either the simple factor program or the MIRACL factor program from ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip So it works much better, and can find all Homeprimes < 100 that are known.

# Find Homeprimes of the given arguments.
# http://mathworld.wolfram.com/HomePrime.html
# The MIRACL factor program is freeware from Shamus Software, Dublin, Ireland
# Full C source code and MIRACL multiprecision library available
# Email to mscott@indigo.ie for details
# Web page http://indigo.ie/~mscott
# Source code from ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip

use strict;
use FileHandle;

# Compare two numbers too big to fit as ints or longs.
sub numStringCmp ($$) {
    (my $s1, my $s2) = @_;
    my $rel;
    # First compare the sizes.
    $rel = (length($s1) <=> length($s2));
    return $rel if($rel != 0);
    # Then compare the equal-size strings.
    return $s1 cmp $s2;
}

sub factorList ($) {
    (my $cand) = @_;
    #print "trying $cand\n";
    # Localize the filehandle $IN.
    my $IN = FileHandle->new();
    if(length($cand) < 12 && $cand =~ /^[0-9]*$/) {
        # Use the simpler factorer.
        open($IN, "factor $cand |") || die "Couldn't factor: $!";
        my $factline = <$IN>;
        close $IN;
        chomp $factline;
        (undef, my @factors) = split(/ /, $factline);
        return @factors;
    }

    # Make sure factor2 can handle a number this size and type.
    my $args = "";
    $args .= '-d '.(length($cand)+2).' ' if(length($cand) >= 149);
    $args .= '-f ' if($cand =~ /[+\-*#]/);    # Handle formulas.
    open($IN, "factor2 -s $args$cand |") || die "Couldn't factor: $!";
    if($cand =~ /[+\-*#]/) {    # Handle formulas.
        # The first line is the candidate computed from the
        # formula, if one was given.
        $cand = <$IN>;
        chomp($cand);
    }
    my @factors = ();
    while(<$IN>) {
        last if(/^this number is prime!/);
        s/[^0-9 &]//g;
        if(/^& /) {
            (undef, my $num) = split(/ /);
            # This could mean the factorer couldn't factor this
            # factor, or that it couldn't be bothered to.
            # The following line avoids recursive loops.
            die "Couldn't factor $cand\n" if($num eq $cand);
            @factors = (@factors, factorList($num));
            next;
        }
        push @factors, $_;
    }
    close $IN;
    return sort numStringCmp @factors;
}

foreach my $cand (@ARGV) {
    my $x = $cand;
    my $y = join('', factorList($cand));
    while($y ne $x) {
        $x = $y;
        print "Factoring $x\n";
        $y = join('', factorList($x));
    }
    print $cand, ': ', $y, "\n";
}

Requirements:
- PERL
- The MIRACL factor.exe program, renamed to factor2
- The GNU factor program (optional). If you don't have/want it, change "length($cand) < 12" to "length($cand) < 0".

Oh, and I thought you might like to see how far it gets with that unknown one, 49=77:

Factoring 77
Factoring 711
Factoring 3379
Factoring 31109
Factoring 132393
Factoring 344131
Factoring 1731653
Factoring 71143523
Factoring 11115771019
Factoring 31135742029
Factoring 717261644891
Factoring 11193431873899
Factoring 116134799345907
Factoring 3204751189066719
Factoring 31068250396355573
Factoring 62161149980213343
Factoring 336906794442245927
Factoring 734615161567701999
Factoring 31318836286194043641
Factoring 333431436916146111627309
Factoring 33205716184556772142207827
Factoring 31367222155734752971376323127
Factoring 733915126325777821480557336017
Factoring 476734743112036198712947236602187
Factoring 377171280957470909577133234490256751
Factoring 3096049809383121823389214993262890297
Factoring 73796236325118712936424989555929478399
Factoring 13118114526141133089538087518197265265053
Factoring 319521441731977174163487542111577539726749
Factoring 595415617656474189392601483764603009147911
Factoring 13842314669573706744784027901056001426046777
Factoring 3129192501509379967095393172011476342474406759
Factoring 3203927133121399320591151296378525102203388346189
Factoring 133119651853912195249113288820301002347322382772769
Factoring 11103725795898241052711667094407302642807490159301277
Factoring 1152194718705941109372661574127837007959097317735411121
Factoring 6318653972357749718234812726673333988788742328093848793
Factoring 711111311391974493533533521186754240313734089696843349346661
Factoring 3771113711016948131790459407678947892694155341923379077407684653
Factoring 7310113562312583178332057129971031882457634609852680847686251943317
Factoring 3111197172271564982895268105721087453190074064393495190773755017652247
Factoring 373111539295698434141591345095168649790005875768086611455076505611166279
Factoring 33333711151101316117103176926136887884135060403955118931001222053567659972075047
Factoring 37987951744462008749649348751784002342702203325604103216176784227054268232116293
Factoring 711131272236782094454737267090807771975783627239622801952043181949336676523721088629
Factoring 11875268711137089799261311878547509623397801472835395151221348397140205614034351359377
Factoring 727431892383195200824551792309011586997602061240784213075478539371666587718903373678159

It might get further, but I killed it after several minutes.

[Uncwilly]

Originally Posted by Ken_g6

727431892383195200824551792309011586997602061240784213075478539371666587718903373678159

Using Dario's applet
717133578549596081307550033105521651212411487965543982552577200370139716504126134573487841

then

1013140899118131107973159425637372267366503456262916700717404858255585899140058606434748914537 (composite)

[Uncwilly]

Originally Posted by Uncwilly

Using Dario's applet
717133578549596081307550033105521651212411487965543982552577200370139716504126134573487841

then

1013140899118131107973159425637372267366503456262916700717404858255585899140058606434748914537 (composite)

After following the links on this thread, I realised that 49 has been taken to 100 steps http://www.worldofnumbers.com/topic1.htm . They are currently stuck with a 204 digit cofactor, namely:
346369145517616832561580518436338147877062893457679622195929206654524672587613049343558394373396338194585783775269785675210636696425094776859733305947996048061499249566197147212934512427988113420226762897

There have been around 5500 ECM curves run on it.

[smh]

There have been around 5500 ECM curves run on it.

Actually a few more:

5500 curves with B1=11M
9650 curves with B1=43M
2280 curves with B1=110M