November 24th, 2007, 07: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, 11:21 AM  #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, 12: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:
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); } "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, 03:14 PM  #24  
Senior Member Joined: Aug 2008 From: Blacksburg VA USA Posts: 354 Thanks: 7 Math Focus: primes of course  Re: symmetry Quote:
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, 12: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:
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 
Search tags for this page 
symmetrical prime numbers,examples of symmetrical primes,produce all primesprime pattern,what are symmetrical primes,symmetry of the primes,symetrical primes less than 100,what are symmetrical primes only,what are the symmetric primes under 100,Square root of 3569,list of symmetrical primes,symmetrical 2 digit primes,what is symmetrical prime numbers
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 04:32 PM 
symmetry  mared  Algebra  1  January 27th, 2014 06:52 AM 
Symmetry  ChristinaScience  Algebra  3  October 2nd, 2011 10:42 AM 
asymmetry and symmetry ?  Logarithm  Real Analysis  1  September 24th, 2011 10:40 PM 