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 » 15 apr 2012, 11:35

op=op, kan het zijn dat je laatste vergelijking zou moeten zijn:

op=op schreef:
Als dan is

#


Hierin is telkens en


Ik veronderstel bovendien dat lcd=kgv.

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

Nee, volgens mij stond het goed. Merkwaardig die lcd. Die afkorting gebruik ik nooit. Volgens mij is lcd = ggd. Bedoeld is uiteraard het kgv.

Ik had gehoopt dat hier meer mee te doen was, maar daar twijfel ik nu aan.
Je kunt nog sommeren over alle delers van .

Een oplossing zie ik niet. Ik denk dat we wat ervaring missen. Het voorafgaande probleem gaat ook over delers van getallen. Pas als je een oplossing ziet kun je zeggen of we het zelf hadden kunnen vinden. Als het antwoord daarop negatief is, is alle energie verspilde energie.
Krijgen we wel ooit een oplossing te zien?

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

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

Bericht door David » 15 apr 2012, 12:24

Wellicht lcm; least common multiple, kgv? gcd staat voor greatest common multiple, ggd.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

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 » 15 apr 2012, 13:32

Dit is toch allemaal een beetje te hoog gegrepen voor mij...
Ik denk dat ik maar eens terug ga afzakken naar het PE-punt waar ik gebleven was vóór ik aan dit probleem begon.
Toen ik dit probleem de eerste keer las, had ik het gevoel (de eerste keer dit jaar) dat ik er wel iets mee zou kunnen. Dat gevoel is ondertussen helemaal verdwenen :?

Toch erg bedankt aan iedereen die bijgedragen heeft aan deze thread!

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 » 15 apr 2012, 13:38

op=op schreef: Krijgen we wel ooit een oplossing te zien?
Jánošík schreef:
wnvl schreef:Worden de oplossingen na een zekere tijd door PE gepubliceerd?
Neen! En als het je niet lukt om, op welke manier dan ook, een oplossing te vinden, dan heb je er eigenlijk niets aan.

Eens je een oplossing hebt, ongeacht hoe lang je computer heeft moeten rekenen, dan krijg je toegang tot een forum dat gereserveerd is voor 'oplossers van dat specifieke probleem'.

De 'straffe kerels' kunnen daar dan een beetje snoeven (goed bedoeld hoor) over hoe efficient en snel en met welk algoritme ze het probleem opgelost hebben.
Anderen, zoals ik, kunnen daar dan weer wat van leren.
Maar als je het niet opgelost krijgt... dan leer je niets...
Die laatste uitspraak moet ik toch een beetje nuanceren. Geen oplossing gevonden, maar ik heb wel één en ander bijgeleerd :wink:

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 » 15 apr 2012, 14:43

Laat ons de formule van op=op een keer toepassen...

Stel y=2 en A=5




dus ik heb de koppels (x,y) = (1,2) en (2,2) en verwacht bijgevolg dat onderstaande formule 2 geeft.




n=0;pi1...pin = - : 1*(3)*(5) = 15

n=1;pi1...pin = 2 : 2*(1)*(2) = 2
n=1;pi1...pin = 3 : 3*(3)*(1) = 9
n=1;pi1...pin = 5 : 5*(3)*(1) = 15

n=2;pi1...pin = 2,3 : (2*3)*(0)
n=2;pi1...pin = 2,5 : (2*5)*(0)
n=2;pi1...pin = 3,5 : (3*5)*(0)

n=3;pi1...pin = 2,3,5 : (2*3*5)*(0)

15-2-9-15=-11

Misschien interpretteer ik de formule verkeerd, maar anders klopt het niet.

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 » 15 apr 2012, 16:52

wnvl schreef: Stel y=2 en A=5
Dit is niet een priemfactor ontbinding van .
Hier is
dus ik heb de koppels (x,y) = (1,2) en (2,2) en verwacht bijgevolg dat onderstaande formule 2 geeft.
Je mist mogelijkheid (x,y) = (4,2).

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

Ik dacht dat de formule het aantal (x,y) met x<=y ging opleveren, maar ik corrigeer.
Stel y=2 en A=5




dus ik heb de koppels (x,y) = (1,2), (2,2) en (4,2) verwacht bijgevolg dat onderstaande formule 3 geeft.




n=0;{pi1...pin} = {-} : 1*(3)*(5) = 15

n=1;{pi1...pin} = {2} : 2*(1)*(2) = 2
n=1;{pi1...pin} = {3} : 3*(3)*(1) = 9
n=1;{pi1...pin} = {5} : 5*(3)*(1) = 15

n=2;{pi1...pin} = {2,3} : (2*3)*(0)
n=2;{pi1...pin} = {2,5} : (2*5)*(0)
n=2;{pi1...pin} = {3,5} : (3*5)*(0)

n=3;{pi1...pin} = {2,3,5} : (2*3*5)*(0)

Dit levert 15-2-9-15=-11 op.
Maar ik geraak er spijtig genoeg nog niet uit en kom zelf ook niet tot een formule die mij juist lijkt.

Is het correct dat ik {pi1...pin} laat lopen over {2,3,5}?

De exponenten a van de priemontbinding van y die spelen toch ook een rol?

Ik verwacht eigenlijk eerder een factor
in plaats van

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 » 16 apr 2012, 07:25

Stel y=2 en A=5



dus ik heb de koppels (x,y) = (1,2), (2,1), (2,2), (2,4) en (4,2) en verwacht bijgevolg dat onderstaande formule 5 geeft.



n=0;{pi1...pin} = {-} : (2+1)*[5] = 15

n=1;{pi1...pin} = {2} : 2*[5/2] = 4

Dit levert 15-4=11 op, en dat klopt inderdaad niet. Ik zal het nog eens nakijken.

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, 00:06

A=10

Stel y=4=2^2
(1,4) (4,1) (2,4) (4,2) (4,4) (4,8) (8,4)
aantal koppels=7

Stel y=2
(1,2) (2,1) (2,2) (3,2) (2,3) (4,2) (2,4) (5,2) (2,5) (6,2) (2,6) (8,2) (2,8) (10,2) (2,10)
aantal koppels=15

In beide gevallen bevat y dezelfde priemfactoren (p=2), maar de uitkomst is verschillend.
Dus mocht er een gesloten formule bestaan voor het aantal koppels voor een zekere y, dan moeten de exponenten van de priemontbinding van y er een rol in spelen.

Ik heb overigens het "gevoel" dat we voor de berekening van het aantal koppels die y bevatten voor een zekere A in eerste instantie een goed algoritme nodig hebben, dat in een tweede stap omgezet kan worden in een formule (als een formule überhaupt wel mogelijk is). Ik zal eens nadenken over een efficiënt algoritme.
Laatst gewijzigd door wnvl op 17 apr 2012, 01:29, 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, 01:23

Algoritme dat voor vaste y en A het aantal koppels (x,y) berekent zodat KGV(x,y)<=A
Stel

, , ..., is de verzameling met alle priemgetallen <= A
y= (a kan 0 zijn)

z=0

for k=1 to n
{

loop over alle deelverzamelingen met k elementen Q={} uit de verzameling P
{

v= alle combinaties zodat
z=z+v

}

}

z=aantal koppels (x,y) met kgv<=A
Bovenstaande zou ik als skelet gebruiken voor de programmering. Er zijn uiteraard optimalisaties mogelijk om de binnenste loop af te breken. Ik betwijfel of je dit wel in een formule gegoten krijgt.

Iemand met een ander algoritme?

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, 13:14

Als dan is

#


Hierin is telkens en


Stel y=2 en A=5
dus ik heb de koppels (x,y) = (1,2), (2,2) en (4,2) en verwacht bijgevolg dat bovenstaande formule 3 geeft.

n=0;{pi1...pin} = {-} : (1+1)*[5/2] = 4

n=1;{pi1...pin} = {2} : 1*[5/4] = 1

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, 14:02

De volgende eigenschap zou ons verder kunnen helpen.
.




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

op=op schreef:Als dan is

#


Hierin is telkens en


Stel y=2 en A=5
dus ik heb de koppels (x,y) = (1,2), (2,2) en (4,2) en verwacht bijgevolg dat bovenstaande formule 3 geeft.

n=0;{pi1...pin} = {-} : (1+1)*[5/2] = 4

n=1;{pi1...pin} = {2} : 1*[5/4] = 1
Goed, deze lijkt te kloppen.

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, 17:11

Het aantal priemgetallen kleiner dan 10^12 is 37,607,912,018.
Wat ook niet echt hoopgevend is voor een mogelijke piste.

Gesloten