De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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=22·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·i2 met i=1,2,....

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 26 januari 2005



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3