Re: Re: Ggd gedeeltelijk bekend

Dit is een reactie op vraag 33203

Ik was inderdaad met de inverse bezig, maar ik verwacht er weinig van, er zijn teveel stappen en teveel onbekenden.

Probleem is dat ik voor b de range weet (niet 20..1660, maar 40-200) en daarbinnen wil zoeken. Uiteraard is dit maar een voorbeeld, het gaat om 64K en grotere getallen, waar het doorzoeken niet mogelijk is.

De test is eigenlijk: als SQR(b) = element uit N en $>$20 dan gevonden. In mijn voorbeeld is de juiste b=100.

Ik zat daarom te denken aan b mod 20 te gebruiken als sieve en daarna een gcd op die gefilterde getallen, maar dan kan ik net zo goed SQR(k·20) direct testen.

Ik had gehoopt dat er een andere snellere programmeerbare mogelijkheid zou zijn. Ideeen?
Misschien denk ik ingewikkeld, maar ik dacht zelfs aan een aangepaste totient functie.

David
Student hbo - dinsdag 25 januari 2005

Antwoord

De extra eis: "b is een kwadraat" verandert de zaak drastisch, tenslotte zijn kwadraten op den duur zeldzamer dan veelvouden van 20.
Het beste kun je nu eerst die 20 in factoren ontbinden.
20=2²·5.
Omdat je een kwadraat wilt hebben voeg je een extra factor 5 toe en krijgt 100.
100 is dus het kleinste veelvoud van 20 dat ook een kwadraat is.
De getallen die je zoekt zijn dus van de vorm 100·i² met i=1,2,....

woensdag 26 januari 2005

©2001-2024 WisFaq