f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door wnvl » 12 apr 2012, 20:18

Sjoerd Job schreef: (Correctie! als je weet, hoeft maar te lopen tot . (dus maximaal tot ).
Kan je dit evt. verduidelijken, Sjoerd Job? Volgens mij kan je dit niet gebruiken om de lust voor 10^12 af te breken.
Laatst gewijzigd door wnvl op 13 apr 2012, 00:18, 2 keer totaal gewijzigd.

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door op=op » 12 apr 2012, 20:21

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.
Dat verandert de zaak. Het bracht me blijkbaar op het verkeerde been.

Jánošík
Gevorderde
Gevorderde
Berichten: 112
Lid geworden op: 25 mar 2012, 19:57

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door Jánošík » 12 apr 2012, 20:34

op=op schreef:
met
als .
Indrukwekkend!
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 :D
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: 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.

Jánošík
Gevorderde
Gevorderde
Berichten: 112
Lid geworden op: 25 mar 2012, 19:57

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door Jánošík » 12 apr 2012, 20:46

Sjoerd Job schreef:Ik stel alleen wel de volgende eis: publiceer het antwoord voor niet op Wiskunde Forum ;).
Geen probleem! Ik zoek geen spoilers, en ik geef er ook geen.
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 :!:
Sjoerd 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 ).
Ook dit moet ik nog eens goed bestuderen :wink:

Jánošík
Gevorderde
Gevorderde
Berichten: 112
Lid geworden op: 25 mar 2012, 19:57

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door Jánošík » 12 apr 2012, 20:51

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
Oke... dat is duidelijk!
Bedankt.

Jánošík
Gevorderde
Gevorderde
Berichten: 112
Lid geworden op: 25 mar 2012, 19:57

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door Jánošík » 12 apr 2012, 20:54

wnvl 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} ???
Ik ook, en ook bij mij klopt het :D
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...

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door op=op » 13 apr 2012, 07:15

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.

Jánošík
Gevorderde
Gevorderde
Berichten: 112
Lid geworden op: 25 mar 2012, 19:57

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door Jánošík » 13 apr 2012, 09:45

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...
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...
Het vinden van alle verschillende machts-identiteiten is geen probleem.
Maar heeft iemand een idee of het ook mogelijk om te berekenen hoevaak elke identiteit voorkomt?

Sjoerd Job
Vergevorderde
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

Bericht door Sjoerd Job » 13 apr 2012, 10:22

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.
Hier is best wel een makkelijke implementatie voor te schrijven ja! Een goede naam hiervoor lijkt mij de `getelde zeef' ofzo iets...

---

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.''

Jánošík
Gevorderde
Gevorderde
Berichten: 112
Lid geworden op: 25 mar 2012, 19:57

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door Jánošík » 13 apr 2012, 11:13

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... :(

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door wnvl » 13 apr 2012, 12:27

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.

Jánošík
Gevorderde
Gevorderde
Berichten: 112
Lid geworden op: 25 mar 2012, 19:57

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door Jánošík » 13 apr 2012, 13:27

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 :?
Jep... en dat zal ook wel zo bedoeld zijn door PE, net om brute kracht uit te sluiten.
wnvl schreef:Ik zag na wat gegoogle dat het eerste antwoord op deze vraag 11 uur na publicatie is toegekomen bij project Euler.
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.
Edit: bovenstaande link kan je alleen zien als je zelf aangemeld bent bij PE.

Sjoerd Job
Vergevorderde
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

Bericht door Sjoerd Job » 14 apr 2012, 08:49

Jánošík schreef:
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 :?
Jep... en dat zal ook wel zo bedoeld zijn door PE, net om brute kracht uit te sluiten.
wnvl schreef:Ik zag na wat gegoogle dat het eerste antwoord op deze vraag 11 uur na publicatie is toegekomen bij project Euler.
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.
Edit: bovenstaande link kan je alleen zien als je zelf aangemeld bent bij PE.
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?
(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.''

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door op=op » 14 apr 2012, 14:14

Ik denk niet dat het ons veel verder brengt, maar:
Als kwadraatvrij is, dan is
#.

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

Bericht door op=op » 14 apr 2012, 16:26

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

Gesloten