Optelketens

1+1=2

en hoe nu verder?

Inhoudsopgave

Inleiding
Deel A: Opteltekens
Deel B: Een eerste schatting voor c(n)
Deel C: De verdubbelingsmethode
Deel D: De factormethode
Deel E: Eigen Onderzoek

Inleiding

Als je 725 moet berekenen, kan je dit ook als volgt berekenen: 724 x 71= 725 . Je telt dus de exponenten bij elkaar op in plaats van dat je vermenigvuldigt. Deze 25-ste macht kan je door het volgende rijtje van zeven optellingen van exponenten bereiken:
1+1=2, 2+1=3, 3+3=6, 6+3=9, 9+9=18, 18+6=24, 24+1=25

Zo’n rijtje noemen we een optelketen en kunnen we ook zo schrijven:
1, 2, 3, 6, 9, 18, 24, 25

Onze opdracht:
Onze opdracht is in vijf delen opgedeeld.
In groepjes van 4 a 5 gaan we aan de slag.
In deel A gaan we voor kleine getallen optelketens maken, en in deel B gaan we onderzoeken of de lengte van deze optelketens kan worden geschat. In deel C en D gaan we ons verdiepen in al bekende methodes om redelijk korte optelketens te maken. In deel E gaan we zelf proberen een methode te ontwikkelen die uitspraken doet over wanneer een bepaalde methode echt korte of zelfs gegarandeerd kortste optelketens oplevert.


Eerste indruk:
Voordat we de opdracht in handen kregen, wisten we niet wat ons te wachten stond; wat voor soort opdracht het zou zijn, hoe we te werk zouden gaan etc. Tijdens het doorlezen van de opdracht begon er al een wat helder beeld van de opdracht te dagen en het leek ons een leuke opdracht. Toen we het startsein kregen, gingen we naar een leeg lokaal, wat vrijwel de hele dag op ons na leeg bleef, gelukkig maar.
De indeling van het werk was vanaf het begin al vrij helder; bij elk onderdeel werd besproken wie wat zou gaan doen. Regelmatig controleerden we elkaar door het werk na te kijken en we vulden elkaar aan waar het nodig was. Omdat Linda niet de hele dag aanwezig kon zijn, moesten we het na 13.00 uur zonder haar doen, maar tegen die tijd hadden we al bijna de opdracht af, en hoefden we het alleen nog maar uit te tikken.

Deel A: Optelketens

Vraag 1 en vraag 2:

Voor elk getal hebben we een kortste optelketen gemaakt en het aantal stappen (van 0 naar 1 niet meegerekend) geteld en omgezet in een tabel.

n Een kortste optelketen c(n)
1 1 0
2 1, 2 1
3 1, 2, 3 2
4 1, 2, 4 2
5 1, 2, 3, 5 3
6 1, 2, 3, 6 3
7 1, 2, 3, 4, 7 4
8 1, 2, 4, 8 3
9 1, 2, 3, 6, 9 4

10 1, 2, 3, 5, 10 4
11 1, 2, 4, 5, 9, 11 5
12 1, 2, 4, 8, 12 4
13 1, 2, 3, 6, 12, 13 5
14 1, 2, 4, 8, 12, 14 5
15 1, 2, 3, 5, 10, 15 5
16 1, 2, 4, 8, 16 4
17 1, 2, 4, 8, 16, 17 5
18 1, 2, 3, 6, 9, 18 5
19 1, 2, 3, 6, 9, 18, 19 6
20 1, 2, 3, 5, 10, 20 5
21 1, 2, 4, 8, 10, 20, 21 6
22 1, 2, 4, 8, 16, 20, 22 6
23 1, 2, 3, 5, 10, 13, 23, 6
24 1, 2, 4, 8, 12, 24 5
25 1, 2, 3, 6, 12, 24, 25 6
26 1, 2, 4, 8, 16, 24, 26 6
27 1, 2, 3, 6, 9, 18, 27 6
28 1, 2, 3, 5, 7, 14, 28 6
29 1, 2, 3, 5, 10, 13, 26, 29 7
30 1, 2, 3, 5, 10, 15, 30 6

31 1, 2, 3, 5, 10, 20, 30, 31 7
32 1, 2, 4, 8, 16, 32 5

Deel B: Een eerste schatting voor c(n)

Vraag 3:

Een belangrijk deel van de speurtocht van de Wiskunde B-dag is gericht op het vinden van de bovengrens voor c(n) die zo dicht mogelijk bij de werkelijke waarde van c(n) ligt. Deze bovengrens noemen we een scherpe bovengrens. We hebben een voorbeeld van een formule voor de bovengrens gekregen: c(n) < = n + 1
2
We controleren met onze tabel uit vraag 1 en vraag 2 of deze formule klop voor de getallen 1 t/m 30.

n = 1 c(n) = 0 (1 + 1)/ 2 = 1
n = 2 c(n) = 1 (2 + 1)/ 2 = 1,5
n = 3 c(n) = 2 (3 + 1)/ 2 = 2
n = 4 c(n) = 2 (4 + 1)/ 2 = 2,5
n = 5 c(n) = 3 (5 + 1)/ 2 = 3
n = 6 c(n) = 3 (6 + 1)/ 2 = 3,5
n = 7 c(n) = 4 (7 + 1)/ 2 = 4
n = 8 c(n) = 3 (8 + 1)/ 2 = 4,5
n = 9 c(n) = 4 (9 + 1)/ 2 = 5
n = 10 c(n) = 4 (10 + 1)/ 2 = 5,5

n = 11 c(n) = 5 (11 + 1)/ 2 = 6
n = 12 c(n) = 4 (12 + 1)/ 2 = 6,5
n = 13 c(n) = 5 (13 + 1)/ 2 = 7
n = 14 c(n) = 5 (14 + 1)/ 2 = 7,5
n = 15 c(n) = 5 (15 + 1)/ 2 = 8
n = 16 c(n) = 4 (16 + 1)/ 2 = 8,5
n = 17 c(n) = 5 (17 + 1)/ 2 = 9
n = 18 c(n) = 5 (18 + 1)/ 2 = 9,5
n = 19 c(n) = 6 (19 + 1)/ 2 = 10
n = 20 c(n) = 5 (20 + 1)/ 2 = 10,5
n = 21 c(n) = 6 (21 + 1)/ 2 = 11
n = 22 c(n) = 6 (22 + 1)/ 2 = 11,5
n = 23 c(n) = 6 (23 + 1)/ 2 = 12
n = 24 c(n) = 5 (24 + 1)/ 2 = 12,5
n = 25 c(n) = 6 (25 + 1)/ 2 = 13
n = 26 c(n) = 6 (26 + 1)/ 2 = 13,5
n = 27 c(n) = 6 (27 + 1)/ 2 = 14

n = 28 c(n) = 6 (28 + 1)/ 2 = 14, 5
n = 29 c(n) = 7 (29 + 1)/ 2 = 15
n = 30 c(n) = 6 (30 + 1)/ 2 = 15,5

Vraag 4:

Stel je wilt 27 maken, dan kun je steeds 1 + 1 + 1 …… doen (26 stappen). Maar omdat je na
1 + 1 = 2 een twee krijgt, kan je verder gaan met 2 + 2 + 2 + 2 ….., wat dus twee keer zo snel gaat. Daarom deel je n + 1 door 2.

Deel C: De verdubbelingsmethode

Vraag 5:

Als n = 2k dan is c(n) = k (zie ook uitleg bij vraag 6 en de tabel bij vraag 1&2)
n = 2² = 4
n = 2³ = 8
n = 24 = 16

n = 25 = 32

Vraag 6:

Om in een optelketen van tien stappen krijg je bij de volgende optelketen 1024 als hoogst mogelijk antwoord: 1,2,4,8,16,32,64,128, 256, 512, 1024
In andere woorden: 1024 = 210
Dus als c(n) = q, voor een willekeurig getal q, dan is het grootste getal n: n = 2q
In feite doe je de uitkomst van de voorafgaande som keer twee, oftewel je gebruikt een macht van 2. Dus als je tien stappen moet maken, moet je tien keer x2 doen, dus 210

Vraag 7:

We gaan een optelketen maken voor 1308 door de verdubbelingsmethode de gebruiken:
1,2,4,8,16,64,128,256,512,1024,1280(=1024+256), 1296(=1280+16), 1304(=1296+8), 1308(=1304+4)


Vraag 8:

Het is mogelijk om met de verdubbelingsmethode elk getal n te maken; omdat je een twee hebt om te rekenen, kan je elk even getal maken en omdat je een één hebt om mee te rekenen, kan je elk oneven getal maken.

Deel D: De factormethode

Door de factoren van het getal n te gebruiken, kunnen we ook een optelketen maken. Dit heet de factormethode.
Een voorbeeld: n = 15: 1, 2, 3, 6, 12, 15 . We hebben gebruik gemaakt van het getal, en tevens ook factor, 3.

Vraag 9:

We gaan de factormethode toepassen op het getal 85:
1,2,4,5,10,20,40,80,85
En ook op het getal 1122:
1,2,3,6,12,24,48,51,102,204,408,816,1020,1122
Bij het getal n = 85 hebben we gebruik gemaakt van de factor 5, bij het getal n = 1122 hebben we gebruik gemaakt van de factor 51.

Vraag 10:

We onderzoeken de getallen 63 en 1023.
We vergelijken het aantal stappen dat je bij de verdubbelingsmethode nodig hebt met het aantal stappen dat je bij de factormethode nog hebt.

Verdubbelingsmethode bij de getallen 63 en 1023:

1, 2, 4, 8, 16, 32, 48, 56, 60, 62, 63
(10 stappen)

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 768, 896, 960, 992, 1008, 1016, 1020, 1022, 1023 (18 stappen)

Factormethode bij de getallen 63 en 1023:
1, 2, 3, 5, 10, 15, 30, 60, 63 (factor 5)
(8 stappen)

1, 2, 3, 6, 12, 24, 48, 96, 192, 384, 768, 960, 1008, 1020, 1023 (factor 3)
(14 getallen)

Vraag 11:
We zoeken een voorbeeld waarbij de factormethode een optelketen geeft die 8 stappen korter is dan de keten van de verdubbelingsmethode.
De verdubbelingsmethode: (35 stappen)
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 393216, 458752, 491520, 507904, 516096, 520192, 522240, 523264, 523776, 524032, 524160, 524224, 524256, 524272, 524280, 524284, 524286

De factormethode: (met factor 3 en 27 stappen)

1, 2, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 491520, 516096, 572240, 523776, 524160, 524256, 524280, 524286


Tot de 2de macht n Aantal stappen verdubbeling 2 (a) Verschil a en b Aantal stappen factor 2 (b)
21-1 1 0 0 0
22-1 3 2 0 2
23-1 7 4 0 4
24-1 15 6 1 5
25-1 31 8 1 7
26-1 63 10 2 8
27-1 127 12 2 10
28-1 255 14 3 11
29-1 511 16 3 13
210-1 1023 18 4 14
211-1 2047 20 4 16
212-1 4095 22 5 17
213-1 8191 24 5 19
214-1 16383 26 6 20
215-1 32767 28 6 22
216-1 65535 30 7 23
217-1 131071 32 7 25
218-1 262134 34 8 26
219-1 524287 36 8 28

Bij de tweede kolom kun je zien dat 2n = 2n-1 * 2 + 1.

Deel E: Eigen onderzoek

We gaan onderzoeken of een aantal al bestaande methodes bij de optelketens kloppen. Als eerste gaan we de formule c(2n) = c(n)+1 uitproberen.

Vraag 12:


N=1 c(2n)=0+1=1
N=2 c(2n)=1+1=2
N=3 c(2n)=2+1=3
N=4 c(2n)=2+1=3
N=5 c(2n)=3+1=4
N=6 c(2n)=3+1=4
N=7 c(2n)=4+1=5
N=8 c(2n)=3+1=4
N=9 c(2n)=4+1=5
N=10 c(2n)=4+1=5
N=11 c(2n)=5+1=6
N=12 c(2n)=4+1=5
N=13 c(2n)=5+1=6
N=14 c(2n)=5+1=6
N=15 c(2n)=5+1=6
N=16 c(2n)=4+1=5
N=17 c(2n)=5+1=6
N=18 c(2n)=5+1=6
N=19 c(2n)=6+1=7
N=20 c(2n)=5+1=6

Als je deze antwoorden vergelijkt met de tabel van vraag 1 & 2, zie je dat de antwoorden kloppen!

We gaan nu de antwoorden van vraag 3 aanscherpen met behulp van de formule (n/3)+3

N=16 (16/3)+3=8,33333

N=17 (17/3)+3=8,67777
N=18 (18/3)+3=9
N=19 (19/3)+3=9,33333
N=20 (20/3)+3=9,67777
N=21 (21/3)+3=10
N=22 (22/3)+3=10,3333
N=23 (23/3)+3=10,6777
N=24 (24/3)+3=11
N=25 (25/3)+3=11,3333

Nu gaan we de stelling: als n=a x b, geldt dan c(n)=c(a) + c(b)? controleren.

Stel n=144
144= 12 x 12
c(n) van 12 = 1,2,4,8,12= 4 stappen
c(n) van 144= 1,2,4,8,16,32,64,128,144= 8 stappen
8=4+4, dus de stelling klopt
stel n=961
961= 31 x 31
c(n) van 31: 1,2,3,5,10,15,30,31 = 7 stappen
c(n) van 961: 1,2,3,5,10,15,30,60,120,240,480,960,961= 12 stappen
12= 7+7, dus de stelling klopt niet


stel n=9
9= 3 x 3
c(n) van 3: 1,2,3= 3 stappen
c(n) van 9: 1,2,3,6,9= 4 stappen
4=2+2, dus de stelling klopt

Met de verdubbelingsmethode maak je een getal n door de beginwaarde steeds te verdubbelen totdat je niet meer verder kan, omdat je anders over het getal heengt die je wilt krijgen. Je moet dan na de verdubbelingsmethode de gebruikte getallen steeds toevoegen om bij het getal te komen die je wilt krijgen.
De ondergrens is de waarde van c(n) die je krijgt als je van de waarde n de kortste optelketen maakt.


De methode:
Je moet zo ver mogelijk de verdubbelingsmethode of de factormethode gebruiken, om zo dicht mogelijk bij het getal n te komen. Dat getal moet je aanvullen met zo groot mogelijk eerder gebruikte getallen en zo krijg je een zo kort mogelijke optelketen. C(n) kun je daarbij afschatten als de ondergrenswaarde.

Vraag 13:

We gaan nu met behulp van de voorgaande methodes een zo kort mogelijke optelketen van het getal 8127 maken. De factormethode is in dit geval het kortst.

De factormethode:
1, 2, 3, 6, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 8064, 8120, 8127 (we hebben de factor 7 gebruikt)
(17 stappen)