Number Theory Number Theory Math Forum

 November 24th, 2007, 08:27 PM #21 Global Moderator   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 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. November 25th, 2007, 01:43 PM   #23
Global Moderator

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.) 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 � November 5th, 2008, 01:29 PM   #25
Global Moderator

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.) Tags primes, symmetry ,
,

,

,

,

,

,

,

,

,

,

# what is symmetrical prime numbers

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post caters Number Theory 67 March 19th, 2014 05:32 PM mared Algebra 1 January 27th, 2014 07:52 AM ChristinaScience Algebra 3 October 2nd, 2011 11:42 AM Logarithm Real Analysis 1 September 24th, 2011 11:40 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      