PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Sieving: is each prime only considered as factor of one composite?

Author Message
Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 399
ID: 1241833
Credit: 156,962,093
RAC: 1,015,738
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,093,381)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,108,160)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (130,584,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Gold: Earned 500,000 credits (678,219)
Message 143609 - Posted: 24 Sep 2020 | 7:02:34 UTC

I do some manual sieving with sr2sieve and it seems like every potential factor is only tested until one composite is found that it divides. Then that factor/composite pair is logged and the next potential factor is considered.

Is it like that? If so, why? :) It's not unlikely that one prime is the factor of more than one candidate in the sieve.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1501
ID: 306875
Credit: 33,882,306
RAC: 24,116
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,019,473)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)WW Turquoise: Earned 5,000,000 credits (9,640,000)GFN Amethyst: Earned 1,000,000 credits (1,707,013)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 143610 - Posted: 24 Sep 2020 | 7:24:32 UTC

No, it would not work like that. But what are you sieving, and why does it seem to you that the sieve will miss cases where one p eliminates more than one candidate? Especially in the beginning, when the p are small, it should be a frequent occurrence that one p is found to divide more than one candidate. /JeppeSN

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 399
ID: 1241833
Credit: 156,962,093
RAC: 1,015,738
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,093,381)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,108,160)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (130,584,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Gold: Earned 500,000 credits (678,219)
Message 143654 - Posted: 25 Sep 2020 | 6:53:17 UTC - in response to Message 143610.

I'm using sr2sieve to sieve Proth with large k (far out of PG's range) and 1E5 <= n<= 4E6.

It seemed to me like that because I never saw that a factor turned up more than once. Now that I write it, it sounds a bit stupid... So I either just missed it or it happens rarely, but each prime is tested against all candidates?

I guess it just happens very rarely, just now I found about 400 composites with 4E12 prime factors. that means only one in 1E10 primes was actually a factor. So the chance that one prime factors more than one candidate is very low in that range.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1501
ID: 306875
Credit: 33,882,306
RAC: 24,116
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,019,473)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)WW Turquoise: Earned 5,000,000 credits (9,640,000)GFN Amethyst: Earned 1,000,000 credits (1,707,013)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 143680 - Posted: 25 Sep 2020 | 18:01:06 UTC - in response to Message 143654.

I'm using sr2sieve to sieve Proth with large k (far out of PG's range) and 1E5 <= n<= 4E6.

It seemed to me like that because I never saw that a factor turned up more than once. Now that I write it, it sounds a bit stupid... So I either just missed it or it happens rarely, but each prime is tested against all candidates?

I guess it just happens very rarely, just now I found about 400 composites with 4E12 prime factors. that means only one in 1E10 primes was actually a factor. So the chance that one prime factors more than one candidate is very low in that range.


You are absolutely correct! /JeppeSN

Post to thread

Message boards : General discussion : Sieving: is each prime only considered as factor of one composite?

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 2.78, 2.42, 2.34
Generated 13 May 2021 | 20:50:33 UTC