mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2005-12-29, 16:59   #12
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·36 Posts
Default

Quote:
Originally Posted by jasong
Do you believe you can find an n that causes n*2^509203-1 to be prime?
That's trivial:

Let n=2^247636 then n*2^509203-1=2^756839-1 is the 32. Mersenne prime.
R. Gerbicz is offline   Reply With Quote
Old 2005-12-29, 18:20   #13
axn
 
axn's Avatar
 
Jun 2003

2×33×7×13 Posts
Default

Quote:
Originally Posted by R. Gerbicz
That's trivial:

Let n=2^247636 then n*2^509203-1=2^756839-1 is the 32. Mersenne prime.
True! But I think somewhere it is _implied_ that n should be odd.
axn is online now   Reply With Quote
Old 2005-12-30, 13:02   #14
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default

Quote:
Originally Posted by R. Gerbicz
That's trivial:

Let n=2^247636 then n*2^509203-1=2^756839-1 is the 32. Mersenne prime.
Quote:
Originally posted by axn1
True! But I think somewhere it is _implied_ that n should be odd.
I won't even pretend to know enough to join the argument. I'm going to assume Mr. Gerbicz is right about his prime, but if axn1 has a website that proves his opinion(I suppose I should search myself) I'd appreciate a link.

Either way, I'm having a lot of fun with this, so until I talk to B2(the guy who started me on this and should know the answer, since he's the head honcho of Riesel Sieve) I'm going to keep on trucking.

I figure either axn1 is right or B2 had a mental moment and gave me the wrong equation.

Last fiddled with by jasong on 2005-12-30 at 13:03
jasong is offline   Reply With Quote
Old 2005-12-30, 13:08   #15
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

A quick program I knocked up shows that sieving is pretty efficient.

To rule out a specific value of n you need to find a factor, i.e.

x=2^509203

n*x - 1 = 0 (mod p)

For any odd prime p. (Since x is even, n*x will be even so n*x-1 will always be odd, so 2 can never be a factor).

Rearranging this:-

n*x = 1 (mod p)
n = x^-1 (mod p)

So, for each p do the following:-

Calculate the modular inverse of x (mod p). The resulting number is the value of n such that p is a factor of n*x - 1.

You can then rule out this value of n, plus any additional multiple of p. i.e. n, n+p, n+2p, n+3p, etc.

Yves Gallot's proth.exe can do this as well (faster than my program not surprisingly)...

After sieving to an appropriate depth you can then PRP the remaining candidates.
Greenbank is offline   Reply With Quote
Old 2005-12-30, 16:04   #16
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

5·79 Posts
Default

Quote:
Originally Posted by axn1
True! But I think somewhere it is _implied_ that n should be odd.
Why? If we're comparing k*2^n-1 and n*2^k-1, there is for instance 21*2^986130-1, which is prime with an even n (and also 986130*2^21-1, which is also prime :surprised).

Last fiddled with by Ken_g6 on 2005-12-30 at 16:05
Ken_g6 is offline   Reply With Quote
Old 2005-12-30, 16:26   #17
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

5·79 Posts
Default

I found a counterexample:
3*2^702038-1 is prime (from the 321 project).
702038*2^3-1 = 5616303 = 3*7*11*41*593
Ken_g6 is offline   Reply With Quote
Old 2005-12-30, 18:12   #18
axn
 
axn's Avatar
 
Jun 2003

2×33×7×13 Posts
Default

Ooh! Too many posts to reply to

@Greenbank: You have just discovered NewPGen's main sieiving algorithm. The "k*b^n-1" sieve of NewPGen will do just that. And it's bloody fast!

@Ken_g6: You'll see some posts up where jasong said:
Quote:
If I understood B2 correctly, if n*k^n-1 (sic - should be n*2^k-1) can be found prime for a certain k, supposedly there's an n(possibly a different one) that makes k*2^n-1 prime for that same k.
This weaker form of conjucture can only be disproven if k is a Riesel number.

Now, the implied part of n & k both being odd! That's a tricky one. Lets say that we allow n to be even, and that n*2^k-1 is a counter example (in R. Gerbicz's case, n=2^247636.) Basically that means that, our conjucturer, in order to still keep the conjucture going _could_ claim that the actual expression should be (n/2)* 2^(k+1) - 1 and then try to find a prime of the form (k+1) *2^x - 1.

Long story short, in order to avoid any confusion and conclusively disprove the conjucture, I assume that both n & k should be odd! (Phew!)


@jasong: No sites. Just what you see in the posts. But finding an odd n such that n*2^509203-1 should put this conjucture for rest once and for all.

Last fiddled with by axn on 2005-12-30 at 18:15
axn is online now   Reply With Quote
Old 2005-12-30, 20:23   #19
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·36 Posts
Default

Quote:
Originally Posted by axn1
True! But I think somewhere it is _implied_ that n should be odd.
OK

But it isn't hard to prove the conjecture:

Let k is a positive integer, a=2^(k+1) and b=2^k-1 then a and b are relative primes. So by Dirichlet's theorem ( see: http://mathworld.wolfram.com/DirichletsTheorem.html
) the arithmetic progression a*m+b contains an infinite number of primes, here
a*m+b=2^(k+1)*m+2^k-1=(2*m+1)*2^k-1=n*2^k-1 where n=2*m+1 is odd!
So your conjecture is true.
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Choosing Between Multiple Poly Files EdH Msieve 10 2018-03-15 03:16
Question: Multiple sequences in NewPGen format Xentar Conjectures 'R Us 3 2008-01-20 15:56
Combining NewPGen files? roger Riesel Prime Search 4 2008-01-15 00:01
Need to learn how to edit, and make from scratch, NewPGen files. jasong Software 2 2006-05-28 21:16
Sieving with NewPGen Cruelty 15k Search 41 2005-10-27 10:28

All times are UTC. The time now is 04:44.

Sat Apr 17 04:44:49 UTC 2021 up 8 days, 23:25, 0 users, load averages: 1.07, 1.28, 1.38

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.