Prime creator through sequence

[roger]

While going through the internet, I came across a sequence of rules that (I think) guaranteed a prime number.
It was called "the repeated factorization of concatenated prime factors."
The steps are : Choose a composite number
Factor the number
Put the factors in ascending (smallest->largest) order without spaces.
This is your new number
If the result is prime, you're done.
If the result is composite, go back to step 2.

I tested it out on some very small numbers, and then on a 6-digit one (30+ iterations). Currently I am working on a 18-digit composite, which on iteration 60, has revealed a C105, factored down from a ~C110.
I'm using Msieve for this, and it appears to be the fastest for these numbers (below 110 digits).

Anyone else interested?

Roger

[jasong]

that's interesting. I'll give it a try with alpertron's app.

[jasong]

I got sick of editing after about 5 minutes. Maybe someone could write a program, possibly using Alpertron's app, that could test if this method is better than random chance.

[axn]

http://www.mersenneforum.org/showthread.php?t=3238 for more info

[grandpascorpion]

So basically, the only counterexample would be a number that ultimately entered into a loop (kind of like an aliquot sequence).

I wrote a little function in PARI to do this. Just to get the bowl rolling:

mcat(a)={
print("Processing: ",a);
while(!ispseudoprime(a),
sa = 1;
fs=factor(a);
for(j=1,length(fs[,1]),
for(k=1,fs[j,2],
if (k==1,multp = 10^floor(1+log(fs[j,1])/log(10) ) );
if(sa==1,
sa=fs[j,1]
,
sa = sa* multp + fs[j,1]
)
)
);
print (" ",sa," vs. ",fs);
a=sa
)
}

[wblipp]

Isn't this the "Home Prime" problem?

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

(Oh - I see axn1 made the same point through his link)

[roger]

Yeah, this is a HomePrime sequence.

The 'official' websites are
Maintained by Patrick De Geest
1. mailto:pdg@worldofnumbers.com
2. mailto:Patrick.DeGeest@skynet.be
Website 1 : http://www.worldofnumbers.com/index.html
Website 2 : http://users.skynet.be/worldofnumbers/ (mirrorsite)

To GrandpaScorpion: how is your code implemented so that PARI can use it? I pasted the code, and tried changing the sa value, but all that happened was that I could change the code. I have almost no experience with coding, so if possible, laymans terms are greatly appreciated!

Thanks,

Roger

[ewmayer]

Originally Posted by roger

The steps are : Choose a composite number
Factor the number
Put the factors in ascending (smallest->largest) order without spaces.
This is your new number
If the result is prime, you're done.

Yeah, that last line tells me all I need to know about this supposedly-prime-producing "algorithm."

How is this different in fundamental nature from the simpler:

1) Start with an odd number >= 1;
2) Add 2.
3) If the result is prime, you're done.
4) If the result is composite, go back to step 2.

In fact, the add-2 prime-generating "algorithm" is exponentially superior in terms of runtime, since it requires no factorization, just a primality test.

[Eivind]

This code is too advanced for me - i was thinking more like:

1) Start with any integer >= 1
2) Add 1
3) If the result is prime, you're done.
4) Go back to step 2.



-Eivind

[jasong]

Not because I think it's a good algorithm, but simply because I think it would be fun, I'm going to check the answers on the home prime effort for 49 after the last major factorization, and maybe try to continue the sequence.

[xilman]

Originally Posted by grandpascorpion

So basically, the only counterexample would be a number that ultimately entered into a loop (kind of like an aliquot sequence).

Please post your proof of this claim and that the sequence of numbers can not grow indefinitely.

I don't at present understand how you reached your conclusion and would like to be educated.

Alex Kruppa and I have spent quite a bit of effort on the HP(49) sequence and it has yet to terminate.


Paul