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

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

Bericht door Jánošík » 11 apr 2012, 16:25

wnvl schreef:[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?
Daar was ik eerst ook zeer verwonderd over, maar ik denk te weten hoe het komt...
Als ik numdiv gebruik, dan moet ik die functie loslaten op n^2

Code: Selecteer alles

print(sum(n=1,10^6,(numdiv(n^2)+1)/2))
Als ik het zelf bereken, dan gebruik ik factor(n) ... zonder kwadraat! Nadien vermenigvuldig ik elke exponent met 2.

Code: Selecteer alles

{
	som=0;
	for(i=1,1000000,
		f=factor(i);
		l=length(f~);
		som+=(prod(n=1,l,2*f[n,2]+1)+1)/2;
	);
	print(som);
}
Ik kan me voorstellen dat het berekenen van factor(n) veel vlugger is dan numdiv(n^2) :!:
wnvl schreef: 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.
Aha... op die manier... Daar moet zeker iets mee aan te vangen zijn. Alleen loop ik nog een beetje vast op de manier om bepaalde koppels wel of niet mee te tellen.

Een afbeelding voor n=20
Afbeelding
rij=1 -> f(n)=n
rij=2 tot n/2 -> beetje rekenen; ik zie er wel een bepaald ritme in, maar dat moet nu nog in een algoritme gegoten worden
rij=n/2+1 tot n -> f(n)=1
Op die manier wordt het aantal rijen dat berekend moet worden al gehalveerd. En ik heb het gevoel dat er nog wel wat vereenvoudigd kan worden.

De eerst volgende dagen ga ik weinig tijd hebben om er aan verder te werken, maar ik kom er zeker nog op terug!

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

In de opgave van het Project Euler kun je je beter concentreren op de functie dan op de functie .
Maar goed.
Als de verzameling van delers is van , dan geldt:
.

Dan is .

en #.

Dus #,

waarbij verschillende priemgetallen zijn.

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, 19:16

Jánošík schreef:
wnvl schreef: 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.
Aha... op die manier... Daar moet zeker iets mee aan te vangen zijn. Alleen loop ik nog een beetje vast op de manier om bepaalde koppels wel of niet mee te tellen.
Tja, maar zelfs als je nog wat kan vereenvoudigen, blijf je een lus behouden over 10^12 getallen. Ik denk dat we moeten zoeken naar een beter idee om de berekening in 1 minuut rond te krijgen.

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

Zoals op=op al zegt kan je je beter focussen op .

is het aantal koppels met en . (tenzij je een hele makkelijke formule voor kan vinden).

Een goed algoritme heb ik nog niet bedacht, maar ik zit er ook over na te denken voor PE. (Eigenlijk vind ik het jammer dat je deze vraag oppert, in plaats van zelf doorgaat met puzzelen, etc, omdat ik het tegen de spirit van PE vindt ingaan).
``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 » 11 apr 2012, 19:56

Sjoerd Job schreef:Zoals op=op al zegt kan je je beter focussen op .

is het aantal koppels met en . (tenzij je een hele makkelijke formule voor kan vinden).

Een goed algoritme heb ik nog niet bedacht, maar ik zit er ook over na te denken voor PE. (Eigenlijk vind ik het jammer dat je deze vraag oppert, in plaats van zelf doorgaat met puzzelen, etc, omdat ik het tegen de spirit van PE vindt ingaan).
De laatste methode die ik voorstelde en die Jánošík oppikte in zijn laatste post is gericht op g en niet op de individuele f'en.
Maar probleem blijft dat we een lus behouden over alle getallen tussen 1 en 10^12.

Worden de oplossingen na een zekere tijd door PE gepubliceerd?

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, 21:39

op=op schreef:In de opgave van het Project Euler kun je je beter concentreren op de functie dan op de functie .
Maar goed.
Zoiets vermoedde ik al, maar ik had geen idee hoe daar aan te beginnen...
En dan komen we aan de hints die je geeft. Het probleem is dat ik daarmee echt wel op het randje van mijn wiskundige kennis zit!
op=op schreef:Als de verzameling van delers is van , dan geldt:
.
Dit lukt nog wel...
x en y zijn elementen van A, als en alleen als kgv(x,y) een deler van n is.
op=op schreef:Dan is .
Dan is A x A de verzameling van koppels (x,y) waarvoor geldt dat kgv(x,y) een deler is van n
op=op schreef:en #.
Hier ben ik niet echt helemaal zeker
Voor elke deler van n 'tellen we 1 op' en het kwadraat van die som is gelijk aan het aantal elementen in de verzameling koppels (x,y) waarvoor geldt dat kgv(x,y) een deler van n is.
op=op schreef:Dus #,

waarbij verschillende priemgetallen zijn.
En hier krijg ik het echt moeilijk... Wat ik ZIE:

Het aantal koppels (x,y) die n als kgv hebben = ... een reeks termen ...
De eerste term hebben we gehad.

In de tweede term staat voor het aantal priemfactoren die deler zijn van n. Juist?
Maar ik weet niet goed hoe ik moet lezen...

Als ik dit tot nu toe allemaal juist geïnterpreteerd heb, dan heb ik toch nog een paar vragen...


Die rode 'is gelijk aan'... moet dat geen zijn?
Anders hebben we toch opnieuw de -functie ipv .

Verder heb ik ook de indruk dat we hier het aantal niet gesorteerde koppels berekenen. Als x kleiner moet zijn dan y, dan moet ik het uiteindelijke resultaat (als ik daar al ooit toe kom) nog delen door 2.

En tot slot ook nog: hoe kom je aan die laatste vergelijking? Misschien begrijp ik dat al wat beter als ik juist weet hoe ik die termen moet lezen, maar misschien heb je ook nog ergens een linkje naar wat uitgebreidere uitleg?

Met dank.

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, 21:39

wnvl schreef:Tja, maar zelfs als je nog wat kan vereenvoudigen, blijf je een lus behouden over 10^12 getallen. Ik denk dat we moeten zoeken naar een beter idee om de berekening in 1 minuut rond te krijgen.
Ik kan de berekening op dit ogenblik al beperken tot n tussen 3 en n/3. Ook de priemgetallen die daar tussen liggen zijn geen probleem. Voor de andere getallen in die loop 'zie' ik al wel een bepaald patroon, maar daar heb ik nog wel wat werk te doen ;-)
Wat betreft die '1-minuut-regel'... daar heb je absoluut gelijk. Dat zal op deze manier NOOIT lukken, maar dat hoeft voor mij ook niet zo nodig.

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, 21:42

Sjoerd Job schreef:(Eigenlijk vind ik het jammer dat je deze vraag oppert, in plaats van zelf doorgaat met puzzelen, etc, omdat ik het tegen de spirit van PE vindt ingaan).
Ook deze reactie vreesde ik een beetje, en ik kan er tot op zekere hoogte inkomen...
Ik hoop echter dat je kan zien dat ik echt niet uit ben op een 'spoiler', maar dat ik 'een duwtje in de goede richting' nodig heb...

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, 21:49

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

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

.
Een formule voor .

Elk getallenpaar is op unieke wijze te schrijven als met .
Wat is de bijdrage aan voor paren met (ggd = 1)?

Zeg en beval priemfactoren.
kan dan op wijzen worden gesplitst in factoren en met ggd = 1.
We eisen nog , dus het aantal wijzen wordt .

Bekijk nu aan de bijdragen aan voor paren met vaste .
Deel die paren dan door en je krijgt weer het aantal met ggd=1, maar nu liggen de waarden tussen 1 en .

Kortom ,
met als .

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

Jánošík schreef:
Sjoerd Job schreef:(Eigenlijk vind ik het jammer dat je deze vraag oppert, in plaats van zelf doorgaat met puzzelen, etc, omdat ik het tegen de spirit van PE vindt ingaan).
Ook deze reactie vreesde ik een beetje, en ik kan er tot op zekere hoogte inkomen...
Ik hoop echter dat je kan zien dat ik echt niet uit ben op een 'spoiler', maar dat ik 'een duwtje in de goede richting' nodig heb...
Ik zie inderdaad dat je net als mij een zetje in de goede richting nodig hebt, heb ik ook wel vaker gehad.

Ik stel alleen wel de volgende eis: publiceer het antwoord voor niet op Wiskunde Forum ;).

Dit soort vraagstukken zijn wel leuk, en ik vermoed dat op=op wel een goed idee geeft: kijken naar paren (x,y) met gcd(x,y) = 1. Hoe snel je deze paren kan genereren weet ik niet, maar ik denk dat dit nog redelijk te doen is, behalve dat tot er van deze paren zijn, wat denk ik best wel veel is!

(Correctie! als je weet, hoeft maar te lopen tot . (dus maximaal tot ).
``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 » 12 apr 2012, 17:00

Jánošík schreef: voor het aantal priemfactoren die deler zijn van n. Juist?
Maar ik weet niet goed hoe ik moet lezen...
Hiér is het aantal delers van .

Als het rijtje van de priemgetallen is, dan is
is het aantal delers van + het aantal delers 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 » 12 apr 2012, 17:17

In het probleem is gegeven. Dat is niet voor niets. Dat moet je op de een of andere manier in het probleem inzetten.
Ik denk dan aan een soort zeef van Eratosthenes met als uitgangspunt.
Die 's zijn daar uitstekend mee te bedienen.
Kortom, ik zou er niet aan beginnen.

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

op=op schreef:In het probleem is gegeven. Dat is niet voor niets. Dat moet je op de een of andere manier in het probleem inzetten.
Ik denk dan aan een soort zeef van Eratosthenes met als uitgangspunt.
Die 's zijn daar uitstekend mee te bedienen.
Kortom, ik zou er niet aan beginnen.
Bij ProjectEuler wordt ook vaak een waarde (als ) gegeven om te controleren of je algoritme werkt. Dit is zodat je kan werken aan je algoritme op een manier dat je nagenoeg instantaan antwoord krijgt, en pas het grotere werk doet op een algoritme wat al werkt.
``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 » 12 apr 2012, 20:08

Ik heb de formule van op=op in PARI GP gestoken voor 10^6.
Resultaat klopt en vraagt een viertal seconden tijd op mijn PC.
Maar 10^{12} ???

Gesloten