mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-01-19, 22:28   #1
roger
 
roger's Avatar
 
Oct 2006

1000001002 Posts
Default 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
roger is offline   Reply With Quote
Old 2007-01-20, 03:07   #2
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default

that's interesting. I'll give it a try with alpertron's app.
jasong is offline   Reply With Quote
Old 2007-01-20, 03:18   #3
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2007-01-20, 08:05   #4
axn
 
axn's Avatar
 
Jun 2003

53·97 Posts
Default

http://www.mersenneforum.org/showthread.php?t=3238 for more info
axn is offline   Reply With Quote
Old 2007-01-20, 17:05   #5
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
)
}
grandpascorpion is offline   Reply With Quote
Old 2007-01-20, 19:35   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001010000002 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2007-01-21, 04:00   #7
roger
 
roger's Avatar
 
Oct 2006

10416 Posts
Default

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
roger is offline   Reply With Quote
Old 2007-01-22, 17:47   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·3·29·67 Posts
Default

Quote:
Originally Posted by roger View Post
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.

Last fiddled with by ewmayer on 2007-01-22 at 17:48
ewmayer is offline   Reply With Quote
Old 2007-01-26, 12:12   #9
Eivind
 
Feb 2006

3·17 Posts
Default

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
Eivind is offline   Reply With Quote
Old 2007-01-28, 01:42   #10
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

66638 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2007-01-28, 12:37   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

1094910 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Unhappy in choosing prime sequence :-) pepi37 Lounge 9 2017-07-15 19:53
Mersenne Prime Sequence Stan Miscellaneous Math 34 2013-08-25 17:35
A Prime Sequence davar55 Puzzles 16 2009-07-02 19:58
Prime free sequence. mfgoode Math 58 2005-07-04 21:48
Catalan sequence (is C5 prime?) Orgasmic Troll Math 10 2003-10-03 15:45

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


Sun Oct 17 02:18:06 UTC 2021 up 85 days, 20:47, 0 users, load averages: 3.66, 3.57, 3.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.