Kan je dit evt. verduidelijken, Sjoerd Job? Volgens mij kan je dit niet gebruiken om de lust voor 10^12 af te breken.Sjoerd Job schreef: (Correctie! als je weet, hoeft maar te lopen tot . (dus maximaal tot ).
f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Laatst gewijzigd door wnvl op 13 apr 2012, 00:18, 2 keer totaal gewijzigd.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Dat verandert de zaak. Het bracht me blijkbaar op het verkeerde been.Sjoerd Job schreef: Bij ProjectEuler wordt ook vaak een waarde (als ) gegeven om te controleren of je algoritme werkt. Dit is zodat je kan werken aan je algoritme op een manier dat je nagenoeg instantaan antwoord krijgt, en pas het grotere werk doet op een algoritme wat al werkt.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Indrukwekkend!op=op schreef:
met
als .
Ik begrijp zelfs bijna hoe je er aan komt. Maar ik zal je volledige bericht toch nog een paar keer moeten lezen denk ik...
Ik heb de formule in een PARI-programma gegoten, en het resultaat klopt
Alleen blijft het probleem dat ik ook hier de volledige reeks tot 10^12 moet doorlopen, en ook met dit dit algoritme duurt dat te lang (2,2 sec voor 10^6, snelste tijd tot nu toe ik schat op zo'n maand voor 10^12)
Laatst gewijzigd door Jánošík op 12 apr 2012, 20:55, 1 keer totaal gewijzigd.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Geen probleem! Ik zoek geen spoilers, en ik geef er ook geen.Sjoerd Job schreef:Ik stel alleen wel de volgende eis: publiceer het antwoord voor niet op Wiskunde Forum .
Ter illustratie (hoewel een beetje off-topic): ik heb een tijd geleden een website gevonden waar zo goed als ALLE antwoorden van PE te vinden zijn. Daar gebruik ik er geen enkele van.
Sterker nog... stel dat ik dankzij de berichten in dit forum uiteindelijk tot een oplossing kom, maar dat ik niet de volledige achterliggende theorie begrijp. Wel... in dat geval weiger ik het antwoord in te sturen. Net zo lang tot ik het wel begrijp, of tot ik een antwoord op een andere manier gevonden heb
Ook dit moet ik nog eens goed bestuderenSjoerd Job schreef:...behalve dat tot er van deze paren zijn, wat denk ik best wel veel is!
(Correctie! als je weet, hoeft maar te lopen tot . (dus maximaal tot ).
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Oke... dat is duidelijk!op=op schreef:Hiér is het aantal delers van .
Als het rijtje van de priemgetallen is, dan is
is het aantal delers van + het aantal delers van
Bedankt.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik ook, en ook bij mij klopt hetwnvl schreef:Ik heb de formule van op=op in PARI GP gestoken voor 10^6.
Resultaat klopt en vraagt een viertal seconden tijd op mijn PC.
Maar 10^{12} ???
2,2 sec op een 2,1 GHz toestel.
Ik heb in een ander bericht ook al geschreven dat dit niet voldoende is om g(10^12) te berekenen.
Edit:
Ik ga dit nu ook eens proberen in VB6 te schrijven.
Mijn zelfgemaakte omega(n) zal wel niet zo snel zijn als die van PARI, maar het uiteindelijke programma kan gecompileerd worden, wat toch ook weer behoorlijk wat snelheidswinst moet opleveren...
Edit 2:
resultaten voor VB6 programma
10^5 -> 0,5 sec
10^6 -> 8,5 sec
10^7 -> 170 sec
Ook niet haalbaar dus...
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Dan is het volgende nog een mogelijkheid.
Het meeste rekenwerk zit in het berekenen van de 's.
Die kunnen worden berekend met de zeef van Erathostenes.
array
tel nu bij met m even 1 op.
de eerste met is 3.
tel nu bij met m een drievoud 1 op.
de eerste met is 5.
tel nu bij met m een 5-voud 1 op.
enz.
Het meeste rekenwerk zit in het berekenen van de 's.
Die kunnen worden berekend met de zeef van Erathostenes.
array
tel nu bij met m even 1 op.
de eerste met is 3.
tel nu bij met m een drievoud 1 op.
de eerste met is 5.
tel nu bij met m een 5-voud 1 op.
enz.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Dat wil ik zeker eens proberen voor n=10^6 (benieuwd hoe snel dit gaat lopen).
Maar bij n=10^12 ga ik absoluut veel te weinig geheugen hebben.
Met slechts 1 byte per array-element, komt dat op iets minder dan een terabyte!
Voor ik dit probleem opgeef, wil ik graag nog heel even terugkomen op een vorig idee...
Maar heeft iemand een idee of het ook mogelijk om te berekenen hoevaak elke identiteit voorkomt?
Maar bij n=10^12 ga ik absoluut veel te weinig geheugen hebben.
Met slechts 1 byte per array-element, komt dat op iets minder dan een terabyte!
Voor ik dit probleem opgeef, wil ik graag nog heel even terugkomen op een vorig idee...
Het vinden van alle verschillende machts-identiteiten is geen probleem.Jánošík schreef:bvb: , dan numdiv(n)
Elk getal dat juist a,b, en c als exponenten in de priemontbinding heeft, ongeacht de volgorde ervan of de grondtallen, zal hetzelfde aantal delers hebben
Ik meen ooit ergens gelezen te hebben dat de gesorteerde reeks exponenten uit de priemontbinding van een getal de 'machts-identiteit' van dat getal genoemd word.
Nu probeer ik te onderzoeken hoeveel verschillende machts-identiteiten er zijn onder 10^12, en hoe vaak komen die voor. Als ik dat weet, dan denk ik dat het probleem zo goed als opgelost is...
Maar heeft iemand een idee of het ook mogelijk om te berekenen hoevaak elke identiteit voorkomt?
-
- Vergevorderde
- Berichten: 1144
- Lid geworden op: 21 jan 2006, 15:09
- Locatie: Krimpen aan den IJssel
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Hier is best wel een makkelijke implementatie voor te schrijven ja! Een goede naam hiervoor lijkt mij de `getelde zeef' ofzo iets...op=op schreef:Dan is het volgende nog een mogelijkheid.
Het meeste rekenwerk zit in het berekenen van de 's.
Die kunnen worden berekend met de zeef van Erathostenes.
array
tel nu bij met m even 1 op.
de eerste met is 3.
tel nu bij met m een drievoud 1 op.
de eerste met is 5.
tel nu bij met m een 5-voud 1 op.
enz.
---
Ik heb het ge-implementeerd in C, en tot en met 10^6 is `instantaan', maar tot en met 10^12 levert een `Killed' op, waarschijnlijk in verband met geheugengebruik.
Hrm. Dit blijkt inderdaad het geval te zijn.
Ervan uitgaande dat ik blokjes geheugen wil opslaan, kost dit mij bytes, wat dus al enkele terabytes is (4tb)... te veel geheugen voor mijn zielige computertje...
Ik zou natuurlijk kunnen proberen te werken met een databestand waar ik alles in opsla, maar dat lijkt mij nog steeds heel erg veel werk en ruimte innemen. Het zou dus makkelijker moeten kunnen.
``Life is complex. It has real and imaginary parts.''
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Het het ook even in VB6 gemaakt (gecompileerd)
-> 0,28 sec
-> 3,5 sec
-> 43 sec
-> out of memory
ook in tijd komt dit op minstens 2 weken voor
Jammer...
-> 0,28 sec
-> 3,5 sec
-> 43 sec
-> out of memory
ook in tijd komt dit op minstens 2 weken voor
Jammer...
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Op mijn computer duurde een lus van 1 tot 10^12 met telkens 1 modulo berekening al een maand (PARI GP).
Alles met een lus van 1 tot 10^12 lijkt me dus hopeloos
Ik zag na wat gegoogle dat het eerste antwoord op deze vraag 11 uur na publicatie is toegekomen bij project Euler.
Alles met een lus van 1 tot 10^12 lijkt me dus hopeloos
Ik zag na wat gegoogle dat het eerste antwoord op deze vraag 11 uur na publicatie is toegekomen bij project Euler.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Jep... en dat zal ook wel zo bedoeld zijn door PE, net om brute kracht uit te sluiten.wnvl schreef:Op mijn computer duurde een lus van 1 tot 10^12 met telkens 1 modulo berekening al een maand (PARI GP).
Alles met een lus van 1 tot 10^12 lijkt me dus hopeloos
De 'Fastest Solver' verstuurde zijn antwoord 10u34min30sec na publicatie van het probleem. Maar vlak na (of misschien juist door) de publicatie is de PE-server voor dik 10 uur offline geweest.wnvl schreef:Ik zag na wat gegoogle dat het eerste antwoord op deze vraag 11 uur na publicatie is toegekomen bij project Euler.
Edit: bovenstaande link kan je alleen zien als je zelf aangemeld bent bij PE.
-
- Vergevorderde
- Berichten: 1144
- Lid geworden op: 21 jan 2006, 15:09
- Locatie: Krimpen aan den IJssel
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Zelfs een lus met alleen maar een addition (sneller dan modulo-berkening) duurt al lang! Dus helemaal brute kracht gaat niet . Dan wordt natuurlijk de vraag: hoe wel?Jánošík schreef:Jep... en dat zal ook wel zo bedoeld zijn door PE, net om brute kracht uit te sluiten.wnvl schreef:Op mijn computer duurde een lus van 1 tot 10^12 met telkens 1 modulo berekening al een maand (PARI GP).
Alles met een lus van 1 tot 10^12 lijkt me dus hopeloos
De 'Fastest Solver' verstuurde zijn antwoord 10u34min30sec na publicatie van het probleem. Maar vlak na (of misschien juist door) de publicatie is de PE-server voor dik 10 uur offline geweest.wnvl schreef:Ik zag na wat gegoogle dat het eerste antwoord op deze vraag 11 uur na publicatie is toegekomen bij project Euler.
Edit: bovenstaande link kan je alleen zien als je zelf aangemeld bent bij PE.
(en nee, deze oplossing is al geen brute kracht meer!)
Zijn er makkelijkere formules te vinden? Iets wat makkelijker te hanteren is? Er moet een oplossing te vinden zijn, zelfs wanneer we geen toegang hebben tot een supercomputer.
Ik vond de zeef al best een goede optimalizatie, maar kennelijk niet goed genoeg.
``Life is complex. It has real and imaginary parts.''
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik denk niet dat het ons veel verder brengt, maar:
Als kwadraatvrij is, dan is
#.
Als kwadraatvrij is, dan is
#.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
We weten dat .
ofwel .
Als en gegeven is, is er dan precies 1 met ?
Stel ja.
Dan kunnen we bij elke eenvoudig het aantal -en vinden waarvoor .
Helaas, het is ietsje ingewikkelder.
Als en
, dan is
met
als , anders is .
Hetzelfde geldt natuurlijk voor alle andere exponenten.
Als dan is
#
Hierin is telkens en
ofwel .
Als en gegeven is, is er dan precies 1 met ?
Stel ja.
Dan kunnen we bij elke eenvoudig het aantal -en vinden waarvoor .
Helaas, het is ietsje ingewikkelder.
Als en
, dan is
met
als , anders is .
Hetzelfde geldt natuurlijk voor alle andere exponenten.
Als dan is
#
Hierin is telkens en