Fastest sieving program?

[paulunderwood]

Fixing n is fine, but keeping k small with give you more speed. Then you are into the territory of PrimeGrid's searches or Riesel Prime Search.

[science_man_88]

Originally Posted by PawnProver44

Ok, I'll do some of the work to fix the variable n. The k value I am trying to find. That shouldn't be too hard, right

k*149^n+1 = 6x+1 = (remainder multiplication( k* 5+1) for k*149^n to be usable we can split n into even and odd odd powers of 5 are remainder 5 on division by 6 and, even powers are remainder 1 on division by 6 neither time is b^n going to divide by 6 the factor of 6 must come from k ( aka k must be divisible by 6 for k*149^n+1 to be remainder 1 on division by 6) the other case is k*149^n+1 = 6y+5 = (6y+4) +1 so k*149^n = remainder 4 on division by 6 k*5^n has to have remainder of 4 when divided by 6 we have 5^n splitting into 1 and 5 remainders on division by 6 so k= 6z+4 or 6a+2 respectively ( in respect to order) make sense so so given a particular n you can narrow k down to 2 in every 6 numbers.

[PawnProver44]

Originally Posted by science_man_88

k*149^n+1 = 6x+1 = (remainder multiplication( k* 5+1) for k*149^n to be usable we can split n into even and odd odd powers of 5 are remainder 5 on division by 6 and, even powers are remainder 1 on division by 6 neither time is b^n going to divide by 6 the factor of 6 must come from k ( aka k must be divisible by 6 for k*149^n+1 to be remainder 1 on division by 6) the other case is k*149^n+1 = 6y+5 = (6y+4) +1 so k*149^n = remainder 4 on division by 6 k*5^n has to have remainder of 4 when divided by 6 we have 5^n splitting into 1 and 5 remainders on division by 6 so k= 6z+4 or 6a+2 respectively ( in respect to order) make sense so so given a particular n you can narrow k down to 2 in every 6 numbers.

Thanks for your help. I picked n=275523, so there should be more to eliminate now, right?

[paulunderwood]

Originally Posted by PawnProver44

Thanks for your help. I picked n=275523, so there should be more to eliminate now, right?

If you are going to search fixed n=275523 and b=2, you will not get into the top5000, however you might consider running a 4-chances sieve of a twin prime or Sophie Germain.

[science_man_88]

Originally Posted by PawnProver44

Thanks for your help. I picked n=275523, so there should be more to eliminate now, right?

so based on what I said k must be 0 or 2 when dividing by 6 for k*149^275523+1 to have potential to be prime. remainder math is also known as modular arithmetic or where the symbol is a special type of equals and the variables can change. technically using remainder math , you can show that unless where m doesn't share a factor with l, that k*b^n+c can't be prime because otherwise the number in question can be represented as a expression using that common factor which it then also shares. example with simpler numbers: since 5 and 10 have a common factor 5, one factor of 15 must be 5 so we already know it's not prime.

[science_man_88]

Originally Posted by paulunderwood

No

I think if I remember correct you can always turn a form the doesn't have this restriction into one that does for example 60*152^n+7 can be turned into form k*b^n+7 with b prime with k =60*8^n and b =19 so any factorable number as b can be turned into a prime base by altering k with all the other factors of b raised to the power of n being factored in. I think it's this possibility they may be confusing with necessity. doh http://mathworld.wolfram.com/ProthsTheorem.html shows that b=2 is proth numbers

[ET_]

If you want to enter the Top-5000 arena, consider checking prime factors of double Mersenne numbers (http://www.doublemersennes.org ).

[PawnProver44]

Originally Posted by science_man_88

so based on what I said k must be 0 or 2 when dividing by 6 for k*149^275523+1 to have potential to be prime. remainder math is also known as modular arithmetic or where the symbol is a special type of equals and the variables can change. technically using remainder math , you can show that unless where m doesn't share a factor with l, that k*b^n+c can't be prime because otherwise the number in question can be represented as a expression using that common factor which it then also shares. example with simpler numbers: since 5 and 10 have a common factor 5, one factor of 15 must be 5 so we already know it's not prime.

I noticed that the sequence k*b^n+-c generates infinitely many primes if k + c = b and k and c are coprime.

Example: 96*23^n+73

[science_man_88]

Originally Posted by PawnProver44

I noticed that the sequence k*b^n+-c generates infinitely many primes if k + c = b and k and c are coprime.

Example: 96*23^n+73

and yet I bet using another mod or a program that takes advantage of factoring algorithms is so far ahead of this that it's not funny I was originally just saying there are conditions on k,b, and c that we can prove allow us to say k*b^n+c can't be prime in certain scenarios.

[PawnProver44]

Originally Posted by science_man_88

and yet I bet using another mod or a program that takes advantage of factoring algorithms is so far ahead of this that it's not funny I was originally just saying there are conditions on k,b, and c that we can prove allow us to say k*b^n+c can't be prime in certain scenarios.

We can use modular congruence to fix variables k, b, and c so there are no primes of the form k*b^n+c, for example 3 always divides the sequence 50*13^n+7, and 5: 57*31^n+28

[Batalov]

Originally Posted by paulunderwood

Only c=+-1 will get you into the top5000, because the proof is rapid.

There are some exceptions... but they are rare:

-----  -------------------------------- ------- ----- ---- --------------
 rank           description              digits  who year comment
-----  -------------------------------- ------- ----- ---- --------------
  206  46821*2^3021380-374567            909531  p363 2013
  217  18976*2^2976221-18975             895937  p373 2014 
 1816  37674760044125*2^1513679-67931    455677  p339 2012 (**)
 2241  31723*2^1398273-507567            420927  p363 2013 (**)