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
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 » 17 apr 2012, 22:24



Voor is




Dus

#
Laatst gewijzigd door op=op op 18 apr 2012, 10:50, 1 keer totaal gewijzigd.

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 » 17 apr 2012, 23:15

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.

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 » 18 apr 2012, 07:33

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.
De complexiteit is niet O(sqrt(x)), maar de afwijking...
``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 » 18 apr 2012, 08:58

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 .

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 » 18 apr 2012, 12:42

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

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 » 18 apr 2012, 13:04

Sjoerd Job schreef:
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.
De complexiteit is niet O(sqrt(x)), maar de afwijking...
Ik bedoelde deze formule



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.

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 » 19 apr 2012, 02:55

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.

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 » 19 apr 2012, 07:48

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.

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 » 19 apr 2012, 10:36



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.

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 » 19 apr 2012, 13:55

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.
``Life is complex. It has real and imaginary parts.''

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 » 19 apr 2012, 14:21

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.
Laatst gewijzigd door wnvl op 19 apr 2012, 15:15, 5 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 » 19 apr 2012, 14:46

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


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 » 19 apr 2012, 15:04

op=op schreef: en dus is steeds .

op=op schreef:
klopt m.i. wel
op=op schreef: en als ik het goed zie zijn dat precies alle getallenparen (x,y) met kgv<=B, dus
denk ik niet (ik was in mijn vorige post ook verkeerd wat dit betreft, maar heb hem aangepast)

op=op schreef:
juist

IAmNotDutch
Nieuw lid
Nieuw lid
Berichten: 16
Lid geworden op: 19 apr 2012, 15:26

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

Bericht door IAmNotDutch » 19 apr 2012, 15:28

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)

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 » 19 apr 2012, 15:30

op=op schreef:
klein rekenvoorbeeldje:

Stel A=4 en B=2

(n,m)

(1,1):
(1,2):
(2,1):
(2,2):

h(4)=3 wat niet correct is:-(

Gesloten