f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
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?
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik denk dat je formule niet klopt.
Bvb het koppel
;
wordt in jou formule niet verrekend als a>1 en b>1.
Probeer je formule (ik denk dat het eerder een algoritme wordt) wat te verfijnen. Zal zelf ook eens nadenken.
Bvb het koppel
;
wordt in jou formule niet verrekend als a>1 en b>1.
Probeer je formule (ik denk dat het eerder een algoritme wordt) wat te verfijnen. Zal zelf ook eens nadenken.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Inderdaad...
In mijn oorspronkelijk voorbeeld met n=180 ontbreekt het koppel (60,90)
Alleen zie ik ook niet zo onmiddellijk hoe ik dat in de formule/algoritme moet verwerken
edit: ook het koppel (20,45) ontbreekt
In mijn oorspronkelijk voorbeeld met n=180 ontbreekt het koppel (60,90)
Alleen zie ik ook niet zo onmiddellijk hoe ik dat in de formule/algoritme moet verwerken
edit: ook het koppel (20,45) ontbreekt
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Als we in bovenstaande stap elk koppel nog eens vermenigvuldigen met a*b*c, zijn we al een stap in de goede richting. Probeer dit advies nog wat te verfijnen...Jánošík schreef:
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)
Laatst gewijzigd door wnvl op 10 apr 2012, 16:14, 1 keer totaal gewijzigd.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik heb eens even een "verschrikkelijk brute kracht" methode geprobeerd... zo eentje van de soort die pijn doet aan de ogen
dit geeft
(1,180)(2,180)(3,180)(4,45)(4,90)(4,180)(5,36)(5,180)(6,180)(9,20)(9,60)(9,180)(10,36)(10,180)(12,45)(12,90)(12,180)(15,36)(15,180)(18,20)(18,60)(18,180)(20,36)(20,45)(20,90)(20,180)(30,36)(30,180)(36,45)(36,60)(36,90)(36,180)(45,60)(45,180)(60,90)(60,180)(90,180)(180,180)
aantal=38
Het berekenen van de som tot 10^6 duurt zo'n 10 minuten op deze manier...
Ik ga nu eens kijken wat ik kan doen met die exponenten zoals je aangaf in je laatste bericht.
Alvast erg bedankt voor het meedenken
Code: Selecteer alles
bereken(n)={
som=0;
d=divisors(n);
l=length(d);
for(a=1,l,
for(b=a,l,
if(lcm(d[a],d[b])==n,
som++;
print1("("d[a]","d[b]")")
)
);
);
print;
print("aantal="som);
}
(1,180)(2,180)(3,180)(4,45)(4,90)(4,180)(5,36)(5,180)(6,180)(9,20)(9,60)(9,180)(10,36)(10,180)(12,45)(12,90)(12,180)(15,36)(15,180)(18,20)(18,60)(18,180)(20,36)(20,45)(20,90)(20,180)(30,36)(30,180)(36,45)(36,60)(36,90)(36,180)(45,60)(45,180)(60,90)(60,180)(90,180)(180,180)
aantal=38
Het berekenen van de som tot 10^6 duurt zo'n 10 minuten op deze manier...
Ik ga nu eens kijken wat ik kan doen met die exponenten zoals je aangaf in je laatste bericht.
Alvast erg bedankt voor het meedenken
Laatst gewijzigd door Jánošík op 10 apr 2012, 18:02, 1 keer totaal gewijzigd.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik heb mijn bovenstaande post gecorrigeerd
Ik heb er a*b*c van gemaakt, maar beschouw het alleen maar als een idee. Ik ben nog ver verwijderd van een efficiënt algoritme.
Ik heb er a*b*c van gemaakt, maar beschouw het alleen maar als een idee. Ik ben nog ver verwijderd van een efficiënt algoritme.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Een beetje spelen met die exponenten, geeft inderdaad alle geldige koppels. Alleen zie ik niet goed hoe ik dat kan implementeren in mijn formule...
Maar... ik heb mijn "brute kracht"-methode gebruikt om de juiste waarde van f(n) te berekenen voor n van 1 tot 100. Die waarden toonde ik dan samen met numdiv(n) en omega(n). Daar een beetje mee gepuzzeld, en ik vond volgende formule:
f(n)=(numdiv(n^2)+1)/2
De som tot 10^6 vind ik dan met
sum(n=1,10^6,(numdiv(n^2)+1)/2)
Duur voor het berekenen:
10^4 -> 0,015 sec
10^5 -> 1,030 sec
10^6 -> 31,512 sec
10^7 -> 624,223 sec
Het probleem vraagt uiteindelijk naar de som voor 10^12
Als ik bovenstaande tabel verder uitbreid, dan kom ik op zo'n slordige 45 jaar
Ik vermoed dus dat er toch nog een andere manier moet zijn om dit op te lossen !
Maar... ik heb mijn "brute kracht"-methode gebruikt om de juiste waarde van f(n) te berekenen voor n van 1 tot 100. Die waarden toonde ik dan samen met numdiv(n) en omega(n). Daar een beetje mee gepuzzeld, en ik vond volgende formule:
f(n)=(numdiv(n^2)+1)/2
De som tot 10^6 vind ik dan met
sum(n=1,10^6,(numdiv(n^2)+1)/2)
Duur voor het berekenen:
10^4 -> 0,015 sec
10^5 -> 1,030 sec
10^6 -> 31,512 sec
10^7 -> 624,223 sec
Het probleem vraagt uiteindelijk naar de som voor 10^12
Als ik bovenstaande tabel verder uitbreid, dan kom ik op zo'n slordige 45 jaar
Ik vermoed dus dat er toch nog een andere manier moet zijn om dit op te lossen !
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Eindelijk, ik heb de formule beet.
Ingeval van
Zijn er
mogelijkheden. Kan je nu de formule uitbreiden naar andere gevallen?
Ingeval van
Zijn er
mogelijkheden. Kan je nu de formule uitbreiden naar andere gevallen?
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Indrukwekkend Het uitbreiden van die formule naar meer factoren is inderdaad niet zo moeilijk, maar... ik zie dat we ons vorig bericht zo goed als gelijktijdig verzonden hebben. Heb jij mijn vorig bericht gezien?wnvl schreef:Eindelijk, ik heb de formule beet.
Ingeval van
Zijn er
mogelijkheden. Kan je nu de formule uitbreiden naar andere gevallen?
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik zie je post nu. Mooie formule. Je formule is inderdaad wat eenvoudiger dan de mijne. Al komt je formule wat uit de lucht gevallen, ik kan me de logica erachter wel inbeelden.
Wat die 45 jaar betreft, ik zie niet onmiddellijk een snellere oplossing
Waar komt deze oefening eigenlijk vandaan? Heeft ze een praktisch nut?
Wat die 45 jaar betreft, ik zie niet onmiddellijk een snellere oplossing
Waar komt deze oefening eigenlijk vandaan? Heeft ze een praktisch nut?
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Die formule bewijzen kan ik absoluut niet. Ik heb ze eerder toevallig gevonden door vanalles en nog wat te proberen, en natuurlijk met een behoorlijke portie gelukwnvl schreef:Ik zie je post nu. Mooie formule. Je formule is inderdaad wat eenvoudiger dan de mijne. Al komt je formule wat uit de lucht gevallen, ik kan me de logica erachter wel inbeelden.
Het gaat om de laatste opgave van Project Euler.wnvl schreef: Wat die 45 jaar betreft, ik zie niet onmiddellijk een snellere oplossing
Waar komt deze oefening eigenlijk vandaan? Heeft ze een praktisch nut?
Dat betekent dat er een oplossing kan gevonden worden binnen 1 minuut... vooropgesteld dat je het juiste algoritme vindt.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik denk dat we niet alle getallen n een voor een moeten gaan ontbinden, maar omgekeerd werken.
1 kunnen we combineren met alle getallen van 1 tot 10^6
2 kunnen we combineren met alle getallen van 1 tot 10^6 / 2 + even getallen tussen 10^6 / 2 en 10^6
3 kunnen we combineren met alle getallen van 1 tot 10^6 / 3 + getallen deelbaar door 3 tussen 10^6 / 3 en 10^6
4 kunnen we combineren met alle getallen van 1 tot 10^6 / 4 + getallen deelbaar door 2 van 10^6 / 4 tot 10^6 / 2 + getallen deelbaar door 4 van 10^6 / 2 tot 10^6
5 kunnen we combineren met alle getallen van 1 tot 10^6 / 5 + getallen deelbaar door 3 tussen 10^6 / 5 en 10^6
6 kunnen we combineren met alle getallen van 1 tot 10^6 / 6 + getallen deelbaar door 3 en niet door 6 tussen 10^6 / 6 en 10^6 / 5 + getallen deelbaar door 2 en niet door 6 tussen 10^6 / 6 en 10^6 / 3 + getallen deelbaar door 6 tussen 10^6 / 6 en 10^6
...
Misschien dat dit sneller zal zijn, maar 10^12 zal hoog gegrepen zijn.
1 kunnen we combineren met alle getallen van 1 tot 10^6
2 kunnen we combineren met alle getallen van 1 tot 10^6 / 2 + even getallen tussen 10^6 / 2 en 10^6
3 kunnen we combineren met alle getallen van 1 tot 10^6 / 3 + getallen deelbaar door 3 tussen 10^6 / 3 en 10^6
4 kunnen we combineren met alle getallen van 1 tot 10^6 / 4 + getallen deelbaar door 2 van 10^6 / 4 tot 10^6 / 2 + getallen deelbaar door 4 van 10^6 / 2 tot 10^6
5 kunnen we combineren met alle getallen van 1 tot 10^6 / 5 + getallen deelbaar door 3 tussen 10^6 / 5 en 10^6
6 kunnen we combineren met alle getallen van 1 tot 10^6 / 6 + getallen deelbaar door 3 en niet door 6 tussen 10^6 / 6 en 10^6 / 5 + getallen deelbaar door 2 en niet door 6 tussen 10^6 / 6 en 10^6 / 3 + getallen deelbaar door 6 tussen 10^6 / 6 en 10^6
...
Misschien dat dit sneller zal zijn, maar 10^12 zal hoog gegrepen zijn.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik vrees dat ik niet goed begrijp wat je bedoelt met 'combineren van getallen'...
Maar het heeft mij wel op een ander interessant spoor gebracht (of misschien bedoelde je wel juist zoiets)
f(n) wordt berekend met numdiv() en die functie is enkel afhankelijk van de exponenten in de priemontbinding van n
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...
En nu nog een klein maar pikant detail: als ik het aantal delers van n zelf bereken met de hierboven beschreven methode, dan gaat het veeeeeeel sneller dan door gebruik te maken van de ingebouwde numdiv-functie.
De nieuwe tijden zijn nu:
10^4 -> 0,078 sec
10^5 -> 0,811 sec
10^6 -> 8,52 sec
10^7 -> 84 sec
10^8 -> 883 sec
Dit tabelletje uitbreiden, en ik kom op een schatting van 125 dagen voor 10^12.
Da's al een stuk beter, maar nog altijd niet goed genoeg
PS: kan je toch ook nog eens uitleggen wat jij juist bedoelde met die combinaties?
Bedankt.
Maar het heeft mij wel op een ander interessant spoor gebracht (of misschien bedoelde je wel juist zoiets)
f(n) wordt berekend met numdiv() en die functie is enkel afhankelijk van de exponenten in de priemontbinding van n
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...
En nu nog een klein maar pikant detail: als ik het aantal delers van n zelf bereken met de hierboven beschreven methode, dan gaat het veeeeeeel sneller dan door gebruik te maken van de ingebouwde numdiv-functie.
De nieuwe tijden zijn nu:
10^4 -> 0,078 sec
10^5 -> 0,811 sec
10^6 -> 8,52 sec
10^7 -> 84 sec
10^8 -> 883 sec
Dit tabelletje uitbreiden, en ik kom op een schatting van 125 dagen voor 10^12.
Da's al een stuk beter, maar nog altijd niet goed genoeg
PS: kan je toch ook nog eens uitleggen wat jij juist bedoelde met die combinaties?
Bedankt.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Ik bedoel, als we alle koppels met een kgv n kleiner dan 10^6 beschouwen, dan komt een combinatie met 1 10^6 keer voor, nlJánošík schreef: PS: kan je toch ook nog eens uitleggen wat jij juist bedoelde met die combinaties?
Bedankt.
(1,1) (1, 2) .... (1, 10^6)
voor 2 hebben we de combinaties
(2,1) (2,2) (2,3) .... (2,500000) (2,500002) (2,500004) (2,500006) ... (2, 10^6)
enzoverder.
We gaan dus niet alle getallen kleiner dan 10^6 een voor een ontbinden maar zoeken alle koppels die een kgv kleiner dan 10^6 hebben.
Maar ook op deze manier gaat een berekening voor 10^12 heeeeeeeel lang duren. Er moet iets beter bestaan.
Re: f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n
Met PARI GP? Zou mij verwonderen dat ze numdiv zo inefficiënt hebben geïmplementeerd.Jánošík schreef: En nu nog een klein maar pikant detail: als ik het aantal delers van n zelf bereken met de hierboven beschreven methode, dan gaat het veeeeeeel sneller dan door gebruik te maken van de ingebouwde numdiv-functie.
Is in jou implementatie de ontbinding in factoren ook meegerekend of vertrek je van de exponenten van de verschillende priemfactoren?