f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Voor is
Dus
#
Laatst gewijzigd door op=op op 18 apr 2012, 10:50, 1 keer totaal gewijzigd.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Hier een formule die de som van het aantal delers berekent.
http://en.wikipedia.org/wiki/Divisor_su ... or_problem
Deze heeft complexiteit , iets wat onze formule ook zou moeten hebben om in een redelijke tijd tot een oplossing te komen.
Maar na wat zoeken heeft het mij geen stap dichter gebracht.
http://en.wikipedia.org/wiki/Divisor_su ... or_problem
Deze heeft complexiteit , iets wat onze formule ook zou moeten hebben om in een redelijke tijd tot een oplossing te komen.
Maar na wat zoeken heeft het mij geen stap dichter gebracht.
-
- 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
De complexiteit is niet O(sqrt(x)), maar de afwijking...wnvl schreef:Hier een formule die de som van het aantal delers berekent.
http://en.wikipedia.org/wiki/Divisor_su ... or_problem
Deze heeft complexiteit , iets wat onze formule ook zou moeten hebben om in een redelijke tijd tot een oplossing te komen.
Maar na wat zoeken heeft het mij geen stap dichter gebracht.
``Life is complex. It has real and imaginary parts.''
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Zeg .
Stel .
Als , dan is met .
Als , dan is .
In totaal oplossingen.
Stel nu ( priem, ).
Dan zijn er uiteraard mogelijkheden.
Merk op dat dit gelijk is aan het aantal delers van .
Dan is .
Stel .
Als , dan is met .
Als , dan is .
In totaal oplossingen.
Stel nu ( priem, ).
Dan zijn er uiteraard mogelijkheden.
Merk op dat dit gelijk is aan het aantal delers van .
Dan is .
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Bovenstaande formule met de som van delers van de kwadraten is is de formule van Janosik (wel 1 bij optellen (delers van een kwadraat is altijd oneven) en delen door 2 om de dubbels eruit te halen)
viewtopic.php?f=28&t=6282#p40170
Maar mocht voor deze som nu een formule analoog aan het "Dirichlet's divisor problem"
http://en.wikipedia.org/wiki/Divisor_su ... or_problem
met complexiteit
viewtopic.php?f=28&t=6282#p40170
Maar mocht voor deze som nu een formule analoog aan het "Dirichlet's divisor problem"
http://en.wikipedia.org/wiki/Divisor_su ... or_problem
met complexiteit
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik bedoelde deze formuleSjoerd Job schreef:De complexiteit is niet O(sqrt(x)), maar de afwijking...wnvl schreef:Hier een formule die de som van het aantal delers berekent.
http://en.wikipedia.org/wiki/Divisor_su ... or_problem
Deze heeft complexiteit , iets wat onze formule ook zou moeten hebben om in een redelijke tijd tot een oplossing te komen.
Maar na wat zoeken heeft het mij geen stap dichter gebracht.
Deze formule is exact en heeft complexiteit . Het is geen enkel probleem om de berekening te maken voor
Die afwijking waar je het over hebt, slaagt op de benaderende formule verder in het wikipedia artikel.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Interessante link.
http://mathoverflow.net/questions/93916 ... sum-k1ndk2
Aan de datum van posten en de bijvragen te zien, is de topic opener ook zoek naar een oplossing van het project Euler probleem.
http://mathoverflow.net/questions/93916 ... sum-k1ndk2
Aan de datum van posten en de bijvragen te zien, is de topic opener ook zoek naar een oplossing van het project Euler probleem.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Na berekening van het residue kom ik tot een schatting van het aantal paren (x,y) net x<=y en kgv<=10^12:
132314136789161,7 (een getal van 15 cijfers).
Ter vergelijking, voor 10^6 is de exacte waarde
37429394 en de geschatte
37429124,28.
132314136789161,7 (een getal van 15 cijfers).
Ter vergelijking, voor 10^6 is de exacte waarde
37429394 en de geschatte
37429124,28.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
is het aantal elementen van .
Voorbeeld: n=3.
Als en
met en oneven en ondeelbaar door 3,
dan is en
.
We nemen en en zijn geinteresseerd in .
Zeg zijn de priemgetallen ,
dan is
In zitten slecht elementen van de volgende vorm: met priem.
Dus
De som gaat over alle en met positief verschil.
Deze site geeft wat waarden.
-
- 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
Is het een idee om een sub-forum op te zetten voor meer van deze Euler-problemen die moeilijk zijn?
Ik ben ook nog niet echt verder gekomen, maar ik hoop wel ooit een oplossing te krijgen. Hoe weet ik nog niet.
Ik ben ook nog niet echt verder gekomen, maar ik hoop wel ooit een oplossing te krijgen. Hoe weet ik nog niet.
``Life is complex. It has real and imaginary parts.''
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Niet slecht. We moeten dan wel hebben voor waarden tussen en . De vereiste densiteit van waarden nodig in de buurt van is wel lager dan bij de kleinere waarden.
Weet niet onmiddellijk of dit haalbaar is.
Na het bekijken van de links onder References op je link met waardes voor , denk ik dat het niet haalbaar is.
Weet niet onmiddellijk of dit haalbaar is.
Na het bekijken van de links onder References op je link met waardes voor , denk ik dat het niet haalbaar is.
Laatst gewijzigd door wnvl op 19 apr 2012, 15:15, 5 keer totaal gewijzigd.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Dus
De som gaat over alle en met positief verschil,
en dus is steeds .
en als ik het goed zie zijn dat precies alle getallenparen (x,y) met kgv<=B, dus
De som gaat over alle en met positief verschil,
en dus is steeds .
en als ik het goed zie zijn dat precies alle getallenparen (x,y) met kgv<=B, dus
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
op=op schreef: en dus is steeds .
klopt m.i. welop=op schreef:
denk ik niet (ik was in mijn vorige post ook verkeerd wat dit betreft, maar heb hem aangepast)op=op schreef: en als ik het goed zie zijn dat precies alle getallenparen (x,y) met kgv<=B, dus
juistop=op schreef:
-
- Nieuw lid
- Berichten: 16
- Lid geworden op: 19 apr 2012, 15:26
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik ben niet Nederlands. Maar ik ben ook bezig met dit probleem. Is het acceptabel om Engels te gebruiken op deze forums, of alleen het Nederlands? (Ik gebruik een vertaler)
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
klein rekenvoorbeeldje:op=op schreef:
Stel A=4 en B=2
(n,m)
(1,1):
(1,2):
(2,1):
(2,2):
h(4)=3 wat niet correct is:-(