My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 24th, 2007, 08:27 PM   #21
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
After looking at your spreadsheet and explanation for a while, I have determined that your process is a recursive wheel sieve. Here's a page about wheel sieves:

http://www.cs.kent.ac.uk/people/staff/c ... rimes.html

I'm curious as to why you think your sieve outperforms the Sieve of Atkin. Have you done asymptotic analysis, testing, or something else?

Here's a quick spreadsheet I whipped up that sieves for primes up to 10,000:
http://math.crg4.com/simpleExcelSieve.zip
CRGreathouse is offline  
 
November 25th, 2007, 12:21 PM   #22
Member
 
Joined: Nov 2007
From: New Zealand

Posts: 38
Thanks: 0

You wrote

You missed the number 2809 (in the spreadsheet)

This is not actually a miss, because when you look at the top I am only
sieving up to 47.

To complete full sieving we have to go sqrt(3569)=59 with 3569 being the
full number range. This will remove the composites 2809, 3127, 3233, 3551 and 3481.

To the speed of this sieve.

The procedure is Lookup - multiply - mark - with every step

Atkins is

Divide - build remainder - decide on remainder - choose function.
Get solutions for functions
Solution for function requires 1 multiplication, 2 suares, one sum
and only from now on it is multiply mark.

I also doubt whether the method is correct, but that would be a new topic.
Macky is offline  
November 25th, 2007, 01:43 PM   #23
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Macky
To the speed of this sieve.

The procedure is Lookup - multiply - mark - with every step

Atkins is

Divide - build remainder - decide on remainder - choose function.
Get solutions for functions
Solution for function requires 1 multiplication, 2 suares, one sum
and only from now on it is multiply mark.
The sieve of Atkin has sublinear complexity, when implemented as in the Atkin/Bernstein paper. It doesn't even have to consider any constant fraction of composites. Yours is necessarily of linear or superlinear complexity, since it passes over a constant fraction of the numbers (in your case, at least two out of every six numbers) in the range at least once. So the sieve of Atkin has lower asymptotic complexity, and so will be faster for large enough numbers.

For small ranges, the sieve of Eratosthenes is hard to beat, since it either doesn't do lookups or does only O(sqrt(n) / log (n)) lookups. Without understanding your method it's hard to compare directly.

As for practical implementation of the sieve of Atkin: You shouldn't be calculating remainders at all for the main loop. The four steps "Divide - build remainder - decide on remainder - choose function." are not needed -- instead you just loop in steps of 60 like so:

Code:
for (long n = start; n <= end; n += 60) {
	work_1_mod_4 (n + 1);
	work_1_mod_4 (n + 13);
	work_1_mod_4 (n + 17);
	work_1_mod_4 (n + 29);
	work_1_mod_4 (n + 37);
	work_1_mod_4 (n + 41);
	work_1_mod_4 (n + 49);
	work_1_mod_4 (n + 53);
	work_1_mod_6 (n + 7);
	work_1_mod_6 (n + 19);
	work_1_mod_6 (n + 31);
	work_1_mod_6 (n + 43);
	work_11_mod_12 (n + 11);
	work_11_mod_12 (n + 23);
	work_11_mod_12 (n + 47);
	work_11_mod_12 (n + 59);
}
Now here's the really interesting part. Yes, finding solutions for the functions is hard. But it's even harder than you say:
"Solution for function requires 1 multiplication, 2 suares, one sum"
That method of finding solutions would require two nested loops up to the square root, which is clearly impossible for any fast method. (No fast method can loop even once up to the square root.) Instead, for each of the modular classes there is a special method, each of which has its own section in the Bernstein/Atkin paper. These complicated algorithms allow for fast computation of the solutions to each quadratic.

The magic of the method is there: because the relations are quadratic rather than linear like your method and that of Eratosthenes, not all numbers must be passed over. Most numbers can be left as composite without a single pass over them. This means that for large enough numbers only 10%, or 1%, or even 0.001% of numbers are even considered as possible primes. Of course there are still a great many passes, but the number dwindles as the area considered increases in size. (Since the sieve starts "all composite" rather than "all prime", each pass flips the bit rather than setting it.)
CRGreathouse is offline  
November 4th, 2008, 04:14 PM   #24
Senior Member
 
Joined: Aug 2008
From: Blacksburg VA USA

Posts: 354
Thanks: 7

Math Focus: primes of course
Re: symmetry

Quote:
Originally Posted by Macky
Here is a little brain twister called the Twin Prime Conjecture.
Primes sieving patterns have symmetry at the symmetry lines
2*3=6, 2*3*5=30, 2*3*5*7=210, 2*3*5*7*11=2310 and so on.
I call these ranges symmetry regions... .
well, I just came across your posting today, this area is of interest to me

I think it's a bit more broad than symmetry around the primorials, rather it's symmetry around the PPP (Primorials and Primorial Products), OEIS A129912

This sequence (mine) begins:
[2, 6, 12, 30, 60, 180, 210, 360, 420, 1260, 2310, 2520, 4620, 6300,

You can see the patterns:

line at 60 includes 12 pairs 59/61, 53/67, 47/73, 41/79, 31/89 etc

line at 12 includes 11/13, 7/17, 5/19

line at 180 includes 22 pairs

etc etc

I wrote simple Pari script to crank the pairs out
billymac00 is offline  
November 5th, 2008, 01:29 PM   #25
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re:

Quote:
Originally Posted by Macky
You will also find that the lower and upper numbers have a distinctive pattern and most composites have only 2 factors, which means the 2 factor primes are not randomly distributed - they follow a pattern like any other combination.
No, actually. The expected number of prime factors increases without bound as the numbers examined grow in size.

10^10 + 1, 2, 3, ... has 3, 3, 2, 3, 3, 3, 3, 7, 2, 7 prime factors.
10^20 + 1, 2, 3, ... has 4, 4, 3, 6, 7, 4, 3, 8, 3, 4 prime factors.
10^50 + 1, 2, 3, ... has 7, 4, 6, 5, 6, 4, 3, 11, 3, 6 prime factors.
10^70 + 1, 2, 3, ... has 9, 8, 4, 9, 7, 9, 5, 10, 3, 6 prime factors.

Can you see the increasing trend? In fact Ramanujan showed that the average number of prime factors of n is of order O(log log n), so numbers around 10^10 average about 3 prime factors, numbers around 10^1000 average around 8 prime factors, and numbers around 10^1000000 average around 15 prime factors.

Numbers around e^(e^2) ~= 1618 average 2 prime factors, so you must be looking at numbers around that size if you came to that conclusion. (Actually a bit smaller since you're only looking at composites, probably about 1000.)
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
primes, symmetry



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
primes and twin primes: Number between powers of 10 caters Number Theory 67 March 19th, 2014 05:32 PM
symmetry mared Algebra 1 January 27th, 2014 07:52 AM
Symmetry ChristinaScience Algebra 3 October 2nd, 2011 11:42 AM
asymmetry and symmetry ? Logarithm Real Analysis 1 September 24th, 2011 11:40 PM





Copyright © 2019 My Math Forum. All rights reserved.