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 jeweet, 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
![Very Happy :D](./images/smilies/icon_biggrin.gif)
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
![Wink :wink:](./images/smilies/icon_wink.gif)
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 voorniet 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
![Exclamation :!:](./images/smilies/icon_exclaim.gif)
Ook dit moet ik nog eens goed bestuderenSjoerd Job schreef:...behalve dat toter
van deze paren zijn, wat denk ik best wel veel is!
(Correctie! als jeweet, hoeft
maar te lopen tot
. (dus maximaal tot
).
![Wink :wink:](./images/smilies/icon_wink.gif)
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Oke... dat is duidelijk!op=op schreef:Hiér ishet aantal delers van
.
Alshet 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} ???
![Very Happy :D](./images/smilies/icon_biggrin.gif)
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![](http://latex.codecogs.com/png.latex?\tau[2..n]= (0..0))
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
Die kunnen worden berekend met de zeef van Erathostenes.
array
tel nu bij
de eerste
tel nu bij
de eerste
tel nu bij
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 bijmet m even 1 op.
de eerstemet
is 3.
tel nu bijmet m een drievoud 1 op.
de eerstemet
is 5.
tel nu bijmet 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
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![](http://latex.codecogs.com/png.latex?g(10^{12}))
Jammer...![Sad :(](./images/smilies/icon_sad.gif)
ook in tijd komt dit op minstens 2 weken voor
Jammer...
![Sad :(](./images/smilies/icon_sad.gif)
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![Confused :?](./images/smilies/icon_confused.gif)
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
![Confused :?](./images/smilies/icon_confused.gif)
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 nietJá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.
![Sad :(](./images/smilies/icon_sad.gif)
(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
#
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
#![](http://latex.codecogs.com/png.latex?\{x : \mbox{ lcd}(x,y) \le A\} =)
![](http://latex.codecogs.com/png.latex?\sum_{n=0}^k(-1)^n \sum_{p_{i_1},\cdots, p_{i_n}}p_{i_1}\cdots p_{i_n} (p_{i_{n+1}}+1)\cdots (p_{i_k}+1)\left[\frac{A}{p_{i_1}\cdots p_{i_n}}\right])
Hierin is telkens
en ![](http://latex.codecogs.com/png.latex?p_{i_1}<\cdots <p_{i_n})
ofwel
Als
Stel ja.
Dan kunnen we bij elke
Helaas, het is ietsje ingewikkelder.
Als
Hetzelfde geldt natuurlijk voor alle andere exponenten.
Als
#
Hierin is telkens