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.
Jánošík
Gevorderde
Gevorderde
Berichten: 112
Lid geworden op: 25 mar 2012, 19:57

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

Bericht door Jánošík » 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?

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 » 10 apr 2012, 14:35

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.

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 » 10 apr 2012, 14:54

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

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

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)
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...
Laatst gewijzigd door wnvl op 10 apr 2012, 16:14, 1 keer totaal gewijzigd.

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 » 10 apr 2012, 16:03

Ik heb eens even een "verschrikkelijk brute kracht" methode geprobeerd... zo eentje van de soort die pijn doet aan de ogen :shock:

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);
}
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 :wink:
Laatst gewijzigd door Jánošík op 10 apr 2012, 18:02, 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 » 10 apr 2012, 16:16

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.

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 » 10 apr 2012, 18:31

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 :shock: :?

Ik vermoed dus dat er toch nog een andere manier moet zijn om dit op te lossen ! :mrgreen:

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 » 10 apr 2012, 18:31

Eindelijk, ik heb de formule beet.

Ingeval van

Zijn er



mogelijkheden. Kan je nu de formule uitbreiden naar andere gevallen?

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 » 10 apr 2012, 18:49

wnvl schreef:Eindelijk, ik heb de formule beet.

Ingeval van

Zijn er



mogelijkheden. Kan je nu de formule uitbreiden naar andere gevallen?
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?

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

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?

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

wnvl 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.
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 geluk :wink:
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?
Het gaat om de laatste opgave van Project Euler.
Dat betekent dat er een oplossing kan gevonden worden binnen 1 minuut... vooropgesteld dat je het juiste algoritme vindt.

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 » 10 apr 2012, 20:39

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.

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 » 11 apr 2012, 02:07

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 :mrgreen:

PS: kan je toch ook nog eens uitleggen wat jij juist bedoelde met die combinaties?
Bedankt.

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

Jánošík schreef: PS: kan je toch ook nog eens uitleggen wat jij juist bedoelde met die combinaties?
Bedankt.
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, nl

(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.

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

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.
Met PARI GP? Zou mij verwonderen dat ze numdiv zo inefficiënt hebben geïmplementeerd.
Is in jou implementatie de ontbinding in factoren ook meegerekend of vertrek je van de exponenten van de verschillende priemfactoren?

Gesloten