mersenneforum.org Sieving multiple NewPGen files in a row(How?)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2005-12-29, 16:59   #12
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·36 Posts

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.

2005-12-29, 18:20   #13
axn

Jun 2003

2×33×7×13 Posts

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.

2005-12-30, 13:02   #14
jasong

"Jason Goatcher"
Mar 2005

3×7×167 Posts

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

 2005-12-30, 13:08 #15 Greenbank     Jul 2005 2×193 Posts 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.
2005-12-30, 16:04   #16
Ken_g6

Jan 2005
Caught in a sieve

5·79 Posts

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

 2005-12-30, 16:26 #17 Ken_g6     Jan 2005 Caught in a sieve 5·79 Posts I found a counterexample: 3*2^702038-1 is prime (from the 321 project). 702038*2^3-1 = 5616303 = 3*7*11*41*593
2005-12-30, 18:12   #18
axn

Jun 2003

2×33×7×13 Posts

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

2005-12-30, 20:23   #19
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·36 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH Msieve 10 2018-03-15 03:16 Xentar Conjectures 'R Us 3 2008-01-20 15:56 roger Riesel Prime Search 4 2008-01-15 00:01 jasong Software 2 2006-05-28 21:16 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