mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2008-05-06, 01:56   #34
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

29DE16 Posts
Default

I've sent an email to michaf asking for his status on his Sierp base 3 reservation and his base 24 reservations on both sides.


Gary
gd_barnes is offline   Reply With Quote
Old 2008-05-06, 03:03   #35
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

186916 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
k's divisible by 3^2 resulting in a k with no prime:
k's divisible by 3^1 resulting in a k with no prime:
Doesn't a k with no prime mean that the conjecture can be no higher than that k?
mdettweiler is offline   Reply With Quote
Old 2008-05-06, 03:45   #36
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

1071810 Posts
Default

Quote:
Originally Posted by Anonymous View Post
Doesn't a k with no prime mean that the conjecture can be no higher than that k?
no known prime
gd_barnes is offline   Reply With Quote
Old 2008-05-06, 04:00   #37
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

Here is a rough diagram showing where I think the different methods for sieving k*2^n+/-1 are efficient.

Code:
many k
values
  ^
  | NewPGen                   same number of
  |(fixed-n)                  k  and n values
  |                                 /
  |                               /
  |                             /
  |                           /
  |                         /
  |                       /
  |                     /
  |               gcwsieve
  |                 /
  |               /
  |             /
  |           /
  |         /         srsieve
  |       /                      sr2sieve     proth_sieve/JJsieve
  |   trial                                     (SPH algorithm)
  | factoring           
  |/              NewPGen (fixed-k)    sr1sieve
  +---------------------------------------------------> many n values
gcwsieve only works for k=n, but the basic algorithm could be generalised.

For an extreme case like the initial stages of Base 3 Sierpinski/Riesel, the ideal sieve would probably be found in the area above the diagonal. This would be a sort of fixed-n sieve that works with multiple n-values.
geoff is offline   Reply With Quote
Old 2008-05-06, 04:41   #38
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
no known prime
Oh, I see.
mdettweiler is offline   Reply With Quote
Old 2008-05-06, 05:43   #39
KEP
Quasi Admin Thing
 
KEP's Avatar
 
May 2005

24·61 Posts
Default

@Gary, you can sure change it, maybe I should just bring it up to n=100,000, so you can do that. No problem at all Good luck on getting your pages done. I'll check back later tonight, if no one has taken the sierpinski gap and reserved it, I'll throw in my last free ressoruce and start working on that range, but of course I'll tell in the base 3 forum weather or not I take it
KEP is offline   Reply With Quote
Old 2008-05-06, 11:36   #40
KEP
Quasi Admin Thing
 
KEP's Avatar
 
May 2005

24·61 Posts
Default

Reenforcement has arrived. 1 quad Q6600 has been thrown into the war. So for now work seems to be done in this way:

1. No reservation of sierpinski base 3
2. Test all sierpinski base 12 candidates up to n=250,000 or prime found
3. Test all riesel base 27 candidates up to n=1,000,000 or prime found
4. Test all sierpinski base 19 candidates up to n=100,000 or primes found
5. Continue on the base 3 riesel conjecture

Regards

KEP
KEP is offline   Reply With Quote
Old 2008-05-06, 19:44   #41
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

101001110111102 Posts
Default

Quote:
Originally Posted by KEP View Post
Reenforcement has arrived. 1 quad Q6600 has been thrown into the war. So for now work seems to be done in this way:

1. No reservation of sierpinski base 3
2. Test all sierpinski base 12 candidates up to n=250,000 or prime found
3. Test all riesel base 27 candidates up to n=1,000,000 or prime found
4. Test all sierpinski base 19 candidates up to n=100,000 or primes found
5. Continue on the base 3 riesel conjecture

Regards

KEP
That's a mother load. Thanks for bringing in that quad! All reservations are reflected on the web pages now.

With the exception of Siemelink's recent primes on Riesel base 19, the CRUS pages should be fully up to date.


Gary
gd_barnes is offline   Reply With Quote
Old 2008-05-06, 19:49   #42
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

2×23×233 Posts
Default

Quote:
Originally Posted by geoff View Post
Here is a rough diagram showing where I think the different methods for sieving k*2^n+/-1 are efficient.

Code:
many k
values
  ^
  | NewPGen                   same number of
  |(fixed-n)                  k  and n values
  |                                 /
  |                               /
  |                             /
  |                           /
  |                         /
  |                       /
  |                     /
  |               gcwsieve
  |                 /
  |               /
  |             /
  |           /
  |         /         srsieve
  |       /                      sr2sieve     proth_sieve/JJsieve
  |   trial                                     (SPH algorithm)
  | factoring           
  |/              NewPGen (fixed-k)    sr1sieve
  +---------------------------------------------------> many n values
gcwsieve only works for k=n, but the basic algorithm could be generalised.

For an extreme case like the initial stages of Base 3 Sierpinski/Riesel, the ideal sieve would probably be found in the area above the diagonal. This would be a sort of fixed-n sieve that works with multiple n-values.

That's an interesting graph, Geoff.

Can you clarify your last statement? Do you mean a fixed-n sieve that works with multiple k-values or a fixed-k sieve that works with multiple n-values?

So based on this, what software do you feel would work best for sieving base 3? It almost looks like srsieve sieving many k's across a somewhat narrower n-range because there are SO many k's for base 3 and it's such a prime base. But I know sr2sieve has been improved a lot to handle many k's.

Also, you said gcwsieve could be generallized. Does that mean that the program can be changed so that k does not have to equal n?

Thanks for the info.


Gary

Last fiddled with by gd_barnes on 2008-05-06 at 19:51
gd_barnes is offline   Reply With Quote
Old 2008-05-09, 03:00   #43
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
Can you clarify your last statement? Do you mean a fixed-n sieve that works with multiple k-values or a fixed-k sieve that works with multiple n-values?
I mean a fixed-n sieve that accepts multiple n values, analogous to srsieve which is a fixed-k sieve that accepts multiple k values.

Quote:
So based on this, what software do you feel would work best for sieving base 3? It almost looks like srsieve sieving many k's across a somewhat narrower n-range because there are SO many k's for base 3 and it's such a prime base. But I know sr2sieve has been improved a lot to handle many k's.
I don't know of any existing software that is efficient for sieving the early stages of base 3. Trial factoring with PFGW then sieving in batches with srsieve is probably the best that you can do with existing software.

Quote:
Also, you said gcwsieve could be generallized. Does that mean that the program can be changed so that k does not have to equal n?
In principle yes. The algorithm used by gcwsieve is a sort of mass trial-factoring algorithm, but instead of computing each trial independantly it re-uses some of the computations from the previous trial. The case where n=k is particularly simple to code and only requires one modular multiplication per k,n pair for each trial factor. The general case would be more complicated to code but would probably require no more than two modular multiplications per k,n pair. (This is still much less efficient than a fixed-k sieve with a large n-range or a fixed-n sieve with a large k-range however).

Having said that I should make it clear that I am not planning to write any such programs in the near future, I don't have the time.
geoff is offline   Reply With Quote
Old 2008-05-09, 04:02   #44
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

2×23×233 Posts
Default

Quote:
Originally Posted by geoff View Post
I mean a fixed-n sieve that accepts multiple n values, analogous to srsieve which is a fixed-k sieve that accepts multiple k values.



I don't know of any existing software that is efficient for sieving the early stages of base 3. Trial factoring with PFGW then sieving in batches with srsieve is probably the best that you can do with existing software.



In principle yes. The algorithm used by gcwsieve is a sort of mass trial-factoring algorithm, but instead of computing each trial independantly it re-uses some of the computations from the previous trial. The case where n=k is particularly simple to code and only requires one modular multiplication per k,n pair for each trial factor. The general case would be more complicated to code but would probably require no more than two modular multiplications per k,n pair. (This is still much less efficient than a fixed-k sieve with a large n-range or a fixed-n sieve with a large k-range however).

Having said that I should make it clear that I am not planning to write any such programs in the near future, I don't have the time.

Now I get it. Speaking of the fixed-n sieve with multiple n-values, it makes me wonder if using NewPGen with the increment counter set on would work well for this. That's what I use for my 'all twin prime search' where I sieve all k<1M for 1000 n-values at a time. It's not extremely efficient but it is the most effective way I know of for twin prime searching.

I think I'll play around with NewPGen here. The fact that it's such a prime base with so many k's may make it a possibility. I never thought I'd say that about NewPGen again except for special multiple-prime forms such as twins, SG's, etc. But it may make sense, as KEP has alluded to, to use PFGW to a very small n-value (perhaps n=2500 or less) and leave thousands or even millioins of k's remaining and then use NewPgen with the increment counter set on to sieve a large range of those k across one n-value at a time. With base 3 being such a prime base, that might be a possibility.

For that matter, perhaps we shouldn't use PFGW trial factoring at all! Maybe we could sieve billions of k's at once starting at n=1 with NewPgen's increment counter and go up from there. Of course, then you get into the issue of huge file sizes requiring more manual intervention, the fact that NewPGen (or any sieving software for that matter) doesn't actually do prime searching so it continues sieving k's after primes would have been found, etc.

Thanks for your input.


Gary

Last fiddled with by gd_barnes on 2008-05-09 at 04:04
gd_barnes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bases 101-250 reservations/statuses/primes gd_barnes Conjectures 'R Us 983 2022-05-21 14:30
Bases 251-500 reservations/statuses/primes gd_barnes Conjectures 'R Us 2417 2022-05-21 14:30
Bases 33-100 reservations/statuses/primes Siemelink Conjectures 'R Us 1716 2022-05-20 05:39
Riesel base 3 reservations/statuses/primes KEP Conjectures 'R Us 1132 2022-05-07 18:19
Bases 6-32 reservations/statuses/primes gd_barnes Conjectures 'R Us 1416 2022-04-24 08:50

All times are UTC. The time now is 19:13.


Tue May 24 19:13:29 UTC 2022 up 40 days, 17:14, 0 users, load averages: 1.95, 1.80, 1.98

Powered by vBulletin® Version 3.8.11
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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔