mersenneforum.org Prime creator through sequence
 Register FAQ Search Today's Posts Mark Forums Read

 2007-01-19, 22:28 #1 roger     Oct 2006 22·5·13 Posts Prime creator through sequence 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 Last fiddled with by roger on 2007-01-19 at 22:57
 2007-01-20, 03:07 #2 jasong     "Jason Goatcher" Mar 2005 66638 Posts that's interesting. I'll give it a try with alpertron's app.
 2007-01-20, 03:18 #3 jasong     "Jason Goatcher" Mar 2005 3×7×167 Posts 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.
 2007-01-20, 17:05 #5 grandpascorpion     Jan 2005 Transdniestr 503 Posts 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 ) }
 2007-01-20, 19:35 #6 wblipp     "William" May 2003 New Haven 1001001110012 Posts Isn't this the "Home Prime" problem? http://mathworld.wolfram.com/HomePrime.html (Oh - I see axn1 made the same point through his link) Last fiddled with by wblipp on 2007-01-20 at 19:37 Reason: Acknowledge axn1's prior point
 2007-01-21, 04:00 #7 roger     Oct 2006 4048 Posts 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
2007-01-22, 17:47   #8
ewmayer
2ω=0

Sep 2002
República de California

3×3,877 Posts

Quote:
 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.

How is this different in fundamental nature from the simpler:

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.

Last fiddled with by ewmayer on 2007-01-22 at 17:48

 2007-01-26, 12:12 #9 Eivind   Feb 2006 3316 Posts 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 Last fiddled with by Eivind on 2007-01-26 at 12:16
 2007-01-28, 01:42 #10 jasong     "Jason Goatcher" Mar 2005 3×7×167 Posts 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.
2007-01-28, 12:37   #11
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

29BA16 Posts

Quote:
 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

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Lounge 9 2017-07-15 19:53 Stan Miscellaneous Math 34 2013-08-25 17:35 davar55 Puzzles 16 2009-07-02 19:58 mfgoode Math 58 2005-07-04 21:48 Orgasmic Troll Math 10 2003-10-03 15:45

All times are UTC. The time now is 18:05.

Sat May 15 18:05:20 UTC 2021 up 37 days, 12:46, 0 users, load averages: 2.26, 2.01, 1.99