mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2006-07-31, 19:21   #1
amcfarlane
 
amcfarlane's Avatar
 
Nov 2004
UK

2×19 Posts
Default Sieving Problems

I've been trying to understand a particular method for sieving and seem to be having some problems. I'm searching for twin-primes of the form k.base^n+/-1 where k is odd and n is fixed.

Now I know that all twin primes (excluding {3,5}) have the form 6n+/-1, so I'm creating a bitfield of k's where k = 3 (mod 6):

Code:
 3   9  15  21  27  33  39  45
51  57  63  69  75  81  87  93
99 105 111 117 123 129 135 141
Now, I'm confident that I don't have to trial divide each full expression:

3*base^n+1, 3*base^n-1, 9*base^n+1, 9*base^n-1 etc,

if nothing else, it's going to be darn slow, so I just need to be looking at the individual values of k (along with my base and n values).

For example: (Assuming base=2, n=2, and k is the range above)

Code:
Divisor		Remove K (for k.base^n+1)	Remove K (for k.base^n-1)
-------		-------------------------	-------------------------
2		none				none
3		none				none
5		21, 51, 81, 111, 141		9, 39, 69, 99, 129
7		33, 75, 117			9, 51, 93, 135
11		63, 129				3, 69, 135
Leaving:

Code:
 -   -  15  --  27  --  --  45
--  57  --  --  --  --  87  --
-- 105 --- --- 123 --- --- ---
Now, by changing the base and/or n, the relative start point of the sieve differs.

For example: (Assuming base=2, n=3, and k is the range above)

Code:
Divisor		Remove K (for k.base^n+1)	Remove K (for k.base^n-1)
-------		-------------------------	-------------------------
2		none				none
3		none				none
5		3, 33, 63, 93			27, 57, 87, 117
7		27, 69, 111			15, 57, 99, 141
11		15, 81				51, 117
Leaving:

Code:
 -   9  --  21  --  --  39  45
--  --  --  --  75  --  --  --
-- 105 --- --- 123 129 135 ---
As you can see, the sequence is different, albeit we are using the same divisors.

Now (and finally you may say), how do I calculate the start position of the sequence for a given base and n value?

(I have been using NewPGen however, I'm having some difficulty in rewriting it to work on by AM64/BSD boxes.)

Last fiddled with by amcfarlane on 2006-07-31 at 19:22
amcfarlane is offline   Reply With Quote
Old 2006-07-31, 19:44   #2
axn
 
axn's Avatar
 
Jun 2003

535910 Posts
Default

So what's the problem, again?
axn is offline   Reply With Quote
Old 2006-07-31, 19:50   #3
amcfarlane
 
amcfarlane's Avatar
 
Nov 2004
UK

1001102 Posts
Default



Given a fixed base and a fixed n, I can perform the sieve easily, but if I change either the base or n, the sieve needs to be adjusted so that the correct values of K are removed ~without~ examing k.base^n+/-1.

Looking at my examples above, in the first example I was able to remove the 1st, 2nd, 4th ... numbers from the list of possible k's, however the second example, I removed the 1st, 3rd, 5th.. k's.

Knowing where the sieve starts relative to the initial (k_min . base^n +/- 1) is the solution - it has to be a simple "mod" operation but I'm darned if I can see it.
amcfarlane is offline   Reply With Quote
Old 2006-07-31, 20:11   #4
axn
 
axn's Avatar
 
Jun 2003

23×233 Posts
Default

Suppose p divided k*b^n+1 (just the +1 case)

i.e. k*b^n+1 = 0 (mod p)
=> k*b^n = -1 (mod p)
=> k = -b^-n (mod p)

b^-n can be calculated as either (b^n)^-1 or (b^-1)^n [Here ^-1 is the modular inverse calculation]

Since you are looking only at k which are multiples of 3, you can quickly check which of k, k+p, or k+2p is divisible by 3 and use that as the "correct" starting point.

WARNING -- the above discussion only covers the +1 series. Don't forget the -1 series also.

Is that what you were looking for?
axn is offline   Reply With Quote
Old 2006-07-31, 21:40   #5
amcfarlane
 
amcfarlane's Avatar
 
Nov 2004
UK

2×19 Posts
Default

I think it might well be... although I admit to not being familiar with the modular inverse -- it does appear to be rather handy. Just testing some code...
amcfarlane is offline   Reply With Quote
Old 2006-08-01, 23:31   #6
amcfarlane
 
amcfarlane's Avatar
 
Nov 2004
UK

2·19 Posts
Default

Yup, exactly what I was after - Thanks.
amcfarlane is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
PC problems Nimras Information & Answers 6 2009-12-15 21:24
Need help with few problems Laserjet Hardware 1 2007-10-13 10:59
Two problems gribozavr Puzzles 11 2007-02-05 05:46
Clock Problems R.D. Silverman Puzzles 5 2006-12-13 00:29

All times are UTC. The time now is 21:33.


Tue May 17 21:33:55 UTC 2022 up 33 days, 19:35, 0 users, load averages: 1.48, 1.50, 1.39

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.

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