Sieve of Vic? (better+beautifull prime finding formula)
in [Math]
|
Prev: limit of a sum
Next: Conjeture or theorem?2
From: Victor Reijkersz on 18 Jul 2010 06:40 Sieve of Vic? I think i have discovered a more beautifull way to find the prime numbers by using a Sieve. But i might be mistaken and have rediscovered the wheel. My prime finding sieve method shows the iterative nature of the primes very well and is therefore intriguing. In short each primes causes an infinite number of other numbers to be composite-numbers, but the composite numbers that are caused by each prime are spread out in the exact same pattern as the primes themselves are spread out. I am not a mathimatican so please bare with me while I illustrate by example instead of by formula. I would appreciate any serious feedback. It might be I re-invented the wheel. I dont know. I dont do maths often. only have been looking at primes as a sudoko puzzle. But i thought i might actually have stumbled on an original thought. Hence this post. I am using a sieve approach for finding prime numbers. Just like Eratosthenes. Noting all the numbers on a big sheet starting with 2 and numbering to however much you like. Number 2 is the first prime in my mind. I note it on the primelist. For every prime i find i have to cross out its power. 2 * 2 = 4. I make a note on 4 that its the 1st composite-number caused by prime2. Number 3 is not crossed out so its a prime. I note it on the primelist. I now also cross out its power. 3*3=9. I make a note on 9 that its the 1st composite-number caused by prime3. Number 4 is crossed out so its not a prime. Prime2 however left off here. The pattern of prime 2 can now also be established. Its size is 1 because its the first pattern defined and its only pattern slot is 1 too. 1 because thats the difference between the first prime (2) and the next (3). Knowing this pattern i know now the 2nd composite-number caused by 2 must be current number(4) + (slot value(1) * prime(2)) = 6. I make a note on 6 that its the 2nd composite number caused by prime2. Number 5 is not crossed out so its a prime. I note it on the primelist. I now also cross out its power 5*5 =25. I make a note on 25 that its the 1st composite-number caused by prime5. Number 6 is crossed out so its not a prime. Prime2 however left off here. Knowing this pattern i know now the 3rd composite-number caused by 2 must be current number(6) + (slot value(1) * prime(2)) = 8. I make a note on 8 that its the 3rd composite number caused by prime2. Number 7 is not crossed out so its a prime. I note it on the primelist. I now also cross out its power 7*7 =49. I make a note on 49 that its the 1st composite-number caused by prime7. Number 8 is crossed out so its not a prime. Prime2 however left off here. Knowing this pattern i know now the 4th composite-number caused by 2 must be current number(8) + (slot value(1) * prime(2)) = 10. I make a note on 10 that its the 4th composite number caused by prime2. Number 9 is crossed out so its not a prime. Prime3 however left off here. The pattern of prime 3 can now also be established. Its size is 1 because its the second pattern defined and its only pattern slot is 2. 2 because thats the difference between the second prime (3) and the next (5). Knowing this pattern i know now the 2nd composite-number caused by 3 must be current number(9) + (slot value(2) * prime(3)) = 15. I make a note on 15 that its the 2nd compositie number caused by prime3. Number 10 is crossed out so its not a prime. Prime2 however left off here. Knowing this pattern i know now the 5th composite-number caused by 2 must be current number(10) + (slot value(1) * prime(2)) = 12. I make a note on 12 that its the 5th composite number caused by prime2. Number 11 is not crossed out so its a prime. I note it on the primelist. I now also cross out its power 11*11 =121. I make a note on 121 that its the 1st composite-number caused by prime11. Number 12 is crossed out so its not a prime. Prime2 however left off here. Knowing this pattern i know now the 5th composite-number caused by 2 must be current number(12) + (slot value(1) * prime(2)) = 14. I make a note on 14 that its the 6th composite number caused by prime2. etc... etc... for number 13 and number 14 Number 15 is crossed out so its not a prime. Prime3 however left off here. Knowing this pattern i know now the 3rd composite-number caused by 3 must be current number(15) + (slot value(2) * prime(3)) = 21. I make a note on 21 that its the 3rd compositie number caused by prime3. ...etc.. etc.. Number 25 is crossed out so its not a prime. Prime5 however left off here. The pattern of prime 5 can now also be established. Its size is 2 because its the third pattern defined and its pattern size is 2 with the pattern slots being [2, 4] because thats respectivly the difference between the third prime (5) and the next (7) and the next one(7) and the next-next one(11). Knowing this pattern i know now the 3rd composite-number caused by 5 must be current number(25) + (slot value(2) * prime(5)) = 25. I make a note on 35 that its the 2nd compositie number caused by prime5. etc.. etc... Number 35 is crossed out so its not a prime. Prime5 however left off here. Knowing this pattern i know now the 4th composite-number caused by 5 must be current number(35) + (slot value(4) * prime(5)) = 55. I make a note on 55 that its the 4th compositie number caused by prime5. etc.. Number 55 is crossed out so its not a prime. Prime5 however left off here. Knowing this pattern i know now the 5th composite-number caused by 5 must be current number(55) + (slot value(2) * prime(5)) = 65. Since this the third slot value we have look up for 5 and the pattern size was only 2 we return here to slot 1. I make a note on 65 that its the 5th compositie number caused by prime5. etc.. ad infinitum... TABLE OF PATTERN SIZE Prime2 = 1 Prime3 = 1 (1*1) Prime5 = 2 ( 2*1) Prime 7 = 8 (4*2) Prime 11= 48 (6*8) Prime 13 = 480 (10*48) Prime 17= 5760 (12*480) Prime 19 = 92160 (16*5760) Next pattern size is thus based on the ((current prime - 1 ) * current pattern size) TABLE OF SLOT VALUES OF PATTERNS Number 2. [ 1 ] Number 3. [ 2 ] Number 5. [ 2, 4 ] Number 7. [ 4, 2, 4, 2, 4, 6, 2, 6 ] (8 numbers) Number 11. [ 2, 4, 2, 4, 6, ... ] (48 numbers) Number 13. [ 4, 2, 4, 6, .. ] (480 numbers) TABLE OF COMPOSITE NUMBERS CREATED BY PRIMES Prime2 : 4,6,8,10,12,14,etc.. Prime3 : 9,15,21,27,33,etc... Prime5: 25,35,55,65,85,95,115,125,etc... Prime7: 49,77,91,119,etc... i can be contacted too at vic(a)xs4all.nl thanks for any feedback, Vic
From: Jacko on 18 Jul 2010 09:31 Replacing division by a multiplication.
From: Victor Reijkersz on 18 Jul 2010 09:42 On Jul 18, 3:31 pm, Jacko <jackokr...(a)gmail.com> wrote: > Replacing division by a multiplication. Sure thats what a sieve does (multiplication) compared to testing all numbers by dividing them by previous primes. Thing is that with this method no composite number has to be crossed off the list twice or more. Take for example 45. Using the sieve of Eratosthenes prime 3 (15x3) would cross it off and prime 5 would cross it off (9x5). With my sieve only prime 3 crosses it off since prime 5 jumps it. When the numbers get larger and larger this method gives a considerable speed increase at the cost of having to keep track of a table of found primes. best regards, Vic
From: Jacko on 18 Jul 2010 09:56 Data structures optimizions. Options: Replace the square number by the number for a simple < test, as this number needs to be available to do the stepping forward, and freeing the blocks of numbers much lower in value than where your up to is essential for the p^2 marking. This < test can step this number up, making an easy fixed size block free and allocation strategy. The large number of blocks in operation for large p => p^2 active, may make this algorithm limited by virtual memory page thrashing. Use a tail insert list to store the sqaure numbers (you don't want to be squaring all numbers, just square rooting found ones, or just keep the p too, but more space), and compare making no blocks needed before there needed, and it looks like you need the number too, so that large steps, can also use this common compareation feature, by doing an ordered insert based on p. This would certainly need associated nodes on the found prime list, storing a handle on the best insertion point (faster). Cheers Jacko
From: Jacko on 18 Jul 2010 10:24
I'd suggest the optimal insert point is after all primes less than the prime to be inserted, and after and prime greater than the prime to be inserted which has an inserted at time (p^2-p)?? making it more relevant to be placed first. This reduces to a primes found list (p), and a marked number list (m) with an associated prime pointer to (p) element. The Seive of ? |