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: 431
ID: 1241833
Credit: 238,686,572
RAC: 961,968
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,445,099)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 Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Amethyst: Earned 1,000,000 credits (1,152,703)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Amethyst: Earned 1,000,000 credits (1,572,374)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 Silver: Earned 200,000,000 credits (207,672,000)GFN Turquoise: Earned 5,000,000 credits (7,489,336)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
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.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,400,000

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1513
ID: 306875
Credit: 35,040,536
RAC: 20,610
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 (174,818)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,790,513)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 Ruby: Earned 2,000,000 credits (2,059,478)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: 431
ID: 1241833
Credit: 238,686,572
RAC: 961,968
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,445,099)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 Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Amethyst: Earned 1,000,000 credits (1,152,703)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Amethyst: Earned 1,000,000 credits (1,572,374)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 Silver: Earned 200,000,000 credits (207,672,000)GFN Turquoise: Earned 5,000,000 credits (7,489,336)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
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.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,400,000

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1513
ID: 306875
Credit: 35,040,536
RAC: 20,610
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 (174,818)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,790,513)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 Ruby: Earned 2,000,000 credits (2,059,478)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 0.91, 0.89, 0.83
Generated 4 Aug 2021 | 21:05:54 UTC