Vergelijking met natuurlijke getallen

Wiskunde is niet alleen een vak op school. Kom je ergens in de praktijk (bijvoorbeeld tijdens je werk) een wiskundig probleem tegen dan kun je hier om hulp vragen.
Plaats reactie
Ridder Janssen
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 10 apr 2016, 08:33

Vergelijking met natuurlijke getallen

Bericht door Ridder Janssen » 21 mei 2016, 09:59

Ik kreeg de volgende puzzel, en na een beetje rekenwerk heb ik die om weten te zetten naar de volgende vergelijking, waarvan ik niet weet hoe ik hem op moet lossen.
Wat is de kleinste k>6 zodat er een n>k bestaat zodat k^2=n*(n+1)/2, met n en k natuurlijke getallen.
Reële oplossingen zijn niet zo moeilijk om te vinden, maar ik kom er niet achter hoe je natuurlijke oplossingen kan vinden...

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Vergelijking met natuurlijke getallen

Bericht door arie » 21 mei 2016, 14:50

k^2=n*(n+1)/2
dus
2k^2=n*(n+1)
en
n^2 + n - 2k^2 = 0

Dit is een 2e-graads Diophantische vergelijking
(zie bv http://mathworld.wolfram.com/Diophantin ... owers.html)
die met standaardtechnieken is op te lossen.

Ik kom uit op:
n[i+1] = 3n + 4k + 1
k[i+1] = 2n + 3k + 1

Een eerste oplossing voor (n,k) = (0,0):
dit volgt vrij triviaal uit de vergelijking n^2 + n - 2k^2 = 0
Dan wordt de tweede oplossing:
n[2] = 3n[1] + 4k[1] + 1 = 3*0 + 4*0 + 1 = 1
k[2] = 2n[1] + 3k[1] + 1 = 2*0 + 3*0 + 1 = 1
en de derde oplossing:
n[3] = 3n[2] + 4k[2] + 1 = 3*1 + 4*1 + 1 = 8
k[3] = 2n[2] + 3k[2] + 1 = 2*1 + 3*1 + 1 = 6
en de vierde oplossing:
n[4] = 3n[3] + 4k[3] + 1 = 3*8 + 4*6 + 1 = 49
k[4] = 2n[3] + 3k[3] + 1 = 2*8 + 3*6 + 1 = 35
dus dit is de oplossing die je zocht: k=35 en n=49

Hier nog wat meer waarden:
(k,n) = (0, 0)
(k,n) = (1, 1)
(k,n) = (6, 8 )
(k,n) = (35, 49)
(k,n) = (204, 288)
(k,n) = (1189, 1681)
(k,n) = (6930, 9800)
(k,n) = (40391, 57121)
(k,n) = (235416, 332928)
(k,n) = (1372105, 1940449)
(k,n) = (7997214, 11309768)
(k,n) = (46611179, 65918161)
(k,n) = (271669860, 384199200)
(k,n) = (1583407981, 2239277041)
(k,n) = (9228778026, 13051463048)
(k,n) = (53789260175, 76069501249)
(k,n) = (313506783024, 443365544448)
(k,n) = (1827251437969, 2584123765441)
(k,n) = (10650001844790, 15061377048200)
(k,n) = (62072759630771, 87784138523761)
(k,n) = (361786555939836, 511643454094368)

Ridder Janssen
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 10 apr 2016, 08:33

Re: Vergelijking met natuurlijke getallen

Bericht door Ridder Janssen » 22 mei 2016, 16:29

Heel erg bedankt voor je tijd, arie.

Ik snap nog niet helemaal hoe je die tweedegraads diophantische vergelijking oplost. Ik zie het enkel staan voor de vorm ax^2+bxy+cy^2, maar niet voor ax^2+bxy+cx+dy+ey^2=f.
Zou je wat gedetailleerder willen uitleggen hoe je hem oplost, en waarom die manier van oplossen werkt?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Vergelijking met natuurlijke getallen

Bericht door arie » 22 mei 2016, 20:19

We hadden:
n^2 + n - 2k^2 = 0
vermenigvuldig met 4:
4n^2 + 4n - 8k^2 = 0
voltooi het eerste kwadraat:
4n^2 + 4n + 1 - 1 - 8k^2 = 0
(4n^2 + 4n + 1) - 1 - 8k^2 = 0
(2n + 1)^2 - 1 - 8k^2 = 0
ofwel:
(2n + 1)^2 - 8k^2 = 1
substitueer:
x = 2n + 1
y = k
dan vinden we de Pell's equation:
x^2 - 8y^2 = 1
(zie https://en.wikipedia.org/wiki/Pell's_equation, waarbij hier n = 8 )

Paragraaf 2.1 op die wiki-pagina
(https://en.wikipedia.org/wiki/Pell's_eq ... _fractions)
geeft hiervoor de oplossing.

Voor onze vergelijking van Pell, met n = 8:
Bepaal eerst de continued fraction van wortel(8):
(zie zo nodig http://mathworld.wolfram.com/ContinuedFraction.html)
a0 = 2
a1 = 1
a2 = 4
a3 = 1
a4 = 4
...
ofwel in het kort genoteerd:
[2; 1, 4, 1, 4, ...]

De convergent c0 = 2 = 2/1
x=2 en y=1 is echter geen oplossing voor onze vergelijking.
De convergent c1 = 2 + (1/1) = 2 + 1 = 3 = 3/1
x=3 en y=1 is wel een oplossing voor onze vergelijking.
Dit is onze fundamentele oplossing: x1 = 3 en y1 = 1

Alle overige oplossingen kunnen we vinden via:
x[i+1] = x1*x + n*y1*y
y[i+1] = y1*x + x1*y
en in ons geval:
x[i+1] = 3x + 8y
y[i+1] = x + 3y

Substitueer nu n en k terug:
2n[i+1] + 1 = 3(2n+1) + 8k
k[i+1] = 2n[i] + 1 + 3k[i]
ofwel
2n[i+1] + 1 = 6n[i] + 3 + 8k[i]
k[i+1] = 2n[i] + 3k[i] + 1
ofwel
2n[i+1] = 6n[i] + 8k[i] + 2
k[i+1] = 2n[i] + 3k[i] + 1
ofwel
n[i+1] = 3n[i] + 4k[i] + 1
k[i+1] = 2n[i] + 3k[i] + 1
zoals in mijn eerdere post.

Ridder Janssen
Nieuw lid
Nieuw lid
Berichten: 5
Lid geworden op: 10 apr 2016, 08:33

Re: Vergelijking met natuurlijke getallen

Bericht door Ridder Janssen » 24 mei 2016, 18:08

Heel erg bedankt, arie.
Ik denk dat ik het snap... ongeveer...
Ik zal dit rustig proberen uit te pluizen, als ik nog vragen heb hoor je het wel.

Plaats reactie