mersenneforum.org Prime creator through sequence
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-01-19, 22:28 #1 roger     Oct 2006 4048 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 1101101100112 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, 08:05 #4 axn     Jun 2003 23·233 Posts http://www.mersenneforum.org/showthread.php?t=3238 for more info
 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 237110 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 10416 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

1172610 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.
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;
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 3·17 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 DB316 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

2C1C16 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 12:58.

Thu May 19 12:58:47 UTC 2022 up 35 days, 11 hrs, 0 users, load averages: 1.81, 1.75, 1.72

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐