f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Geplaatst: 10 apr 2012, 13:52
Gegeven is een positief geheel getal n, en ik ben op zoek naar het aantal koppels (x,y) waar positieve gehele getallen zijn, en kgv(x,y)=n.
bvb: n=180 geeft
{(1,180)(2,180)(3,180)(4,180)(5,180)(6,180)(9,180)(10,180)(12,180)(15,180)(18,180)(20,180)(30,180)(36,180)(45,180)(60,180)(90,180)(180,180)(4,45)(5,36)(9,20)}
Bij al deze koppels is het eerste getal kleiner dan of gelijk aan het tweede, en het kleinste gemeen veelvoud van de getallen in elk koppel is 180.
Er zijn 21 koppels, en voor zover ik kan zien zijn er geen andere koppels die aan de kriteria voldoen. Dus f(180)=21.
Ik vind die koppels in 2 stappen.
1) Elke deler van n geeft samen met n een geldig koppel.
2) De ontbinding van n in priemfactoren geeft bvb
Daarmee kan je volgende (niet geordende) koppels vormen:
(1, PQR)
(P, QR)
(Q, PR)
(R, PQ)
(PQ, R)
(PR, Q)
(QR, P)
(PQR, 1)
Het aantal koppels dat zo gevormd wordt is waarbij t het aantal unieke priemfactoren in de ontbinding is.
Als we de getallen ordenen, dan komt elk koppel 2 keer voor. Er blijven dan geldige koppels over.
Merk op dat het koppel (1, PQR) ook reeds in stap 1 gevonden werd.
Het totaal aantal koppels kan nu berekend worden met de formule
waarbij d het aantal delers van n is, en t het aantal unieke priemfactoren in de ontbindig van n.
In PARI GP wordt dat
numdiv(n) + 2^(omega(n)-1) - 1
Nu wil ik .
In PARI GP:
sum(n=2,10^6,numdiv(n) + 2^(omega(n)-1) - 1)
Volgens de oplossing van het probleem moet dit 37429394 zijn.
Mijn formule in PARI GP geeft echter 17562876.
Het is dus duidelijk dat ik ergens een aantal koppels mis...
Iemand enig idee waar ik in de fout ga?
bvb: n=180 geeft
{(1,180)(2,180)(3,180)(4,180)(5,180)(6,180)(9,180)(10,180)(12,180)(15,180)(18,180)(20,180)(30,180)(36,180)(45,180)(60,180)(90,180)(180,180)(4,45)(5,36)(9,20)}
Bij al deze koppels is het eerste getal kleiner dan of gelijk aan het tweede, en het kleinste gemeen veelvoud van de getallen in elk koppel is 180.
Er zijn 21 koppels, en voor zover ik kan zien zijn er geen andere koppels die aan de kriteria voldoen. Dus f(180)=21.
Ik vind die koppels in 2 stappen.
1) Elke deler van n geeft samen met n een geldig koppel.
2) De ontbinding van n in priemfactoren geeft bvb
Daarmee kan je volgende (niet geordende) koppels vormen:
(1, PQR)
(P, QR)
(Q, PR)
(R, PQ)
(PQ, R)
(PR, Q)
(QR, P)
(PQR, 1)
Het aantal koppels dat zo gevormd wordt is waarbij t het aantal unieke priemfactoren in de ontbinding is.
Als we de getallen ordenen, dan komt elk koppel 2 keer voor. Er blijven dan geldige koppels over.
Merk op dat het koppel (1, PQR) ook reeds in stap 1 gevonden werd.
Het totaal aantal koppels kan nu berekend worden met de formule
waarbij d het aantal delers van n is, en t het aantal unieke priemfactoren in de ontbindig van n.
In PARI GP wordt dat
numdiv(n) + 2^(omega(n)-1) - 1
Nu wil ik .
In PARI GP:
sum(n=2,10^6,numdiv(n) + 2^(omega(n)-1) - 1)
Volgens de oplossing van het probleem moet dit 37429394 zijn.
Mijn formule in PARI GP geeft echter 17562876.
Het is dus duidelijk dat ik ergens een aantal koppels mis...
Iemand enig idee waar ik in de fout ga?