Les 2: Getaltheorie

Les 2: Getaltheorie#

ALs je les 1 hebt gevolgd, heb je in elk geval wat basiscommando’s gezien, zoals print, if, while, for etc, en verschillende variabelen, zoals integers, floats, string, list, boolean… Zo niet, ga terug naar les 1.

In dit lesje ga je nu vooral zelf veel aan de slag. We gaan wat vraagstukken uit getaltheorie pakken, denk aan verschillende families van priemgetallen, fibanaccirij, open problemen, etc, waar je vooral een computer voor nodig hebt om uit te werken. Sommige opgaven zou je ook algebraisch op kunnen lossen, maar het is voor nu de bedoeling dat je algoritmisch denken leert.

Lesdoelen:

kennis maken met algoritmes door middel van getaltheoretische vraagstukken
modulo rekenen voor delingsvraagstukken
werken met lijsten, manipulatie en gebruik voor programma’s
oefenen met een aantal opdrachten

Algoritmes#

Een algoritme is niets meer dan een set regels die gevolgd worden: je geeft een input, programma doet er wat mee, en je krijgt een output. Als je een eitje wilt bakken pak je eerst een ei (input), dan volg een je een programma (pan invetten, gasfornuis aan, 3 minuten wachten eitje flippen, 3 minuten wachten en eitje op bord leggen) en de output is een eitje op je bord.

Met programmeer taal is dat niets anders. Het enige waar jij als programmeur op moet letten is dat computers inherent dom zijn. Je moet STAP VOOR STAP uitleggen wat het programma doet, computer doet letterlijk wat je zegt en denkt niet “oh je zou wel dit bedoelen”.

Voor we naar een aantal voorbeelden gaan, moet je een belangrijk wiskundig concept leren gebruiken, en dat is modulo rekenen.

Modulo rekenen#

Modulo rekenen is een moeilijk woord voor “rekenen met rest”, zoals je op de basisschool hebt geleerd: “Wat is de rest als je 17 deelt door 5?” Of versimpelder: “ik heb 17 koekjes en 5 leerlingen. Hoeveel koekjes houd je over als je zo eerlijk mogelijk wilt delen?”. 5 past soweiso 3x in 17 (namelijk 3*5 = 15) en dan houd je nog 2 over. We zeggen dan dus dat 17/5 rest 2 heeft. In programmeren is dat het % symbool. Kijk naar de output van onderstaande code, er komt 2 uit.

print(17%5)

Verander wat getallen in de bovenste code: wat is de rest van je geboortejaar gedeeld door je geboortedag? (1987%16 in mijn geval)

We gebruiken modulo rekenen om deelbaarheid van getallen te testen. In les 1 heb je een programma gezien voor het genereren van alle even getallen onder de 20 Dat kan ook met modulo rekenen: een getal is deelbaar door 2 als getal%2==0 (de rest is 0 bij deling door 2). Als het ONeven is, dan is de uitkomst gelijk aan 1. Ga dat maar na. Hieronder een voorbeeld van zo’n programma, waarbij we gelijk lijst

for n in range(1,21):   #let op, van 1 TOT 21 is 1 TOT en MET 20
    if(n%2==0):         #als getal n deelbaar is door 2 (heeft rest 0)
        print(n)        # dan print n
    

Priemgetallen Een belangrijk concept in de wiskunde is het concept van ‘ondeelbare getallen’, ook wel priemgetallen. De definitie is: een priemgetal is een geheel getal groter dan 1, die als delers alleen 1 en zichzelf hebben. De eerste paar zijn: 2,3, 5, 7, 11, 13…

Om te checken of een getal een priemgetal is, is een methode alle getallen lager dan dat getal af te gaan en kijken of er rest 0 is bij deling.

Bijvoorbeeld: is 91 een priemgetal? 91 gedeeld door 2: kan niet 91 gedeeld door 3: kan niet 91 gedeeld door 4: kan niet … 91 gedeeld door 7: kan wel! 91/7 = 13 Dus 91 is geen priemgetal.

Je programma zou dus alle getallen af kunnen gaan lager dan die waarde, en zodra een deler is gevonden, stoppen. Hieronder het zelfde voorbeeld in programmeertaal:

n = 91
for i in range(2,n): #let op dat we starten bij 2, want elk getal is deelbaar door 1. En eindigen bij n is hier oké, als er geen delers zijn gevonden tot n-1, dan is het een priemgetal
    if(n%i==0):      # als n deelbaar is door een getal lager dan n:
        print(n, " is geen priemgetal, het is deelbaar door:", i) # dan is het geen priemgetal
        break  #we hoeven niet meer verder te zoeken dus we stappen uit de for-loop
    elif(i==n-1):   #zijn we bij het laatste gekomen, dan zijn we nooit 'gebreakt' en dus is n een priemgetal
        print(n, "is een priemgetal")

Dit is dus een algoritme: de input is een getal, het programma gaat er mee aan de slag, en de output is het wel of niet zijn van priemgetal.

Er is nog wat op te merken aan de efficientie van de bovenstaande code. Moet je echt door ALLE getallen heen lopen? Als een getal al niet deelbaar is door 2, dan is het zeker niet deel baar door 4, 6, 8, … en als het niet deelbaar is door 3, dan zeker ook niet door 6, 9, 12, … We testen dus eigenlijk te veel getallen. Je wilt dus eigenlijk alleen maar alle andere priemgetallen afgaan om te kijken of het deelbaar is. Het is dus fijn om een lijst van priemgetallen te hebben tot een bepaalde waarde, daar gaat de rest van de les over.

OPDRACHTJE: Ook is het niet nodig om 2 tot en met n te checken, je kan ook tot wortel(n) gaan: kan je bedenken waarom?

LIJSTEN MAKEN#

Voor veel opdrachten zoals hiervoor beschreven is het handig om een lijst bij te houden. We gaan een lijst van priemgetallen tot een bepaalde waarde N genereren.

De syntax van een lijst is rechte haken, en die sla je op in een variabele. Dat mag van alles zijn, mijn persoonlijke voorkeur heeft het om in de naam het woord ‘lijst’ of ‘list’ te plaatsen zodat ik weet dat de variabele een lijst en niet een getal is. Priemlijst zal dus de variabele zijn dat een lijst is van priemgetallen. Om een lijst te bouwen moet je het in je allereerste regels definieren, en met priemlijst = [] maak je een LEGE lijst aan, priemlijst is een variabele list maar zonder items er nog in. Je zou het eventueel alvast kunnen vullen: priemlijst = [2, 3, 5] met bijvoorbeeld de eerste drie priemen, maar dat is niet per se nodig. Om praktische redenen is het handig om wel alvast één waarde er in te zetten, dat zal een vraag zijn later in deze les wat er gebeurd als je dat niet doet.

Om een priemlijst tot bijvoorbeeld 100 te maken, moet je dus elk getal van 1 tot 100 aflopen en controleren of het een priem is. Zo ja dan wil je dat opslaan in de lijst. Dat kan als volgt: priemlijst.append(getal) slaat getal op aan het einde van de lijst. Het .append() deel kan je lezen als ‘appendix’, en ‘dat is toevoeging aan het einde’. In woorden kan je de regel dus lezen als ‘aan de priemlijst voeg ik toe de waarde van getal’

priemlijst = [2]                 # maak een  lijst aan en noem deze priemlijst, en zet alvast waarde 2 erin
N = 1000000                        # we gaan priemlijsten maken tot priem
for getal in range(2,N):      # voor elk getal lager dan N gaan we controleren of het een priemgetal is
    for i in range(2,getal):    # voor elke i lager dan het getal gaan we controleren of het een deler is
        if(getal%i==0):         #als het een deler is, dan is het geen priemgetal
            break               #dan stappen we uit de for loop en wordt i eentje opgehoogd
        elif(i==getal-1):      #als we nog niet gebreakt zijn, dan zijn we bij de voorlaatste waarde gekomen. 
            priemlijst.append(getal)   #dan is het getal dus een priemgetal, en voegen we toe
 
print(priemlijst)

Ga je nu grote lijsten maken, dan kan het nogal duren. We hebben eerder al wat optimalisaties genoemd, maar er zijn er meer:

je hoeft niet ALLE getallen te checken, als je al weet dat 2 een priemgetal is, kan je alle veelvouden van 2 al overslaan. Dat is de HELFT van alle getallen!
je kan gaan tot de wortel(N) (bedenk maar waarom)
je hoeft ook alleen maar de priemgetallen te controleren: terwijl je de lijst bouwt, kan je ook de lijst weer even erbij pakken!
en de volgorde van de check of we al klaar zijn kan eentje eerder (de elif en if kunnen omgedraaid)

Kan je dit aanpassen hierboven? Hieronder staat ook al het antwoord, maar probeer het eerst zelf!

import math
priemlijst = [2]
N=1000000
for getal in range(3,N,2):      #de extra ,2 in range zorgt voor stapgrotte twee, we kijken dus alleen naar onevengetallen
    ishetpriem = True           #tenzij er een deler is gevonden, gaan we uit dat het een priemgetal is
    for p in priemlijst:
        
        if (p > int(math.sqrt(getal))): #als de priemgetal groter is dan de wortel van het getal, hoeven we niet meer verder te gaan
            break
        if(getal%p==0):
            ishetpriem = False   #er is een delergevonden! 
            break
    if(ishetpriem):              #als er geen deler is gevonden, dan is getal een priem, voeg het toe
        priemlijst.append(getal)

print(priemlijst)

Vragen:

wat als je priemlijst = [] doet, wat gaat er dan mis?
wat gebeurd er eigenlijk op de regel if (p>int(math.sqrt(getal))) ? kan de int weg? wat doet het?
is dit werkelijk sneller dan de vorige methode? Ga eens timen voor N tot 1 miljoen hoe lang het duurt. (spoiler: lang, meer dan minuten)

Meer over lijsten#

Nu we met lijsten bezig zijn, wil je deze ook zelf kunnen manipuleren. Een van de vraagstukken is bijvoorbeeld: hoeveel priemtweelingen zijn er? Een priemtweeling is een paar priemen die 2 van elkaar verschillen: 3,5 5,7 11,13, 17,19 etc. Dan wil je dus door de lijst heen kunnen lopen en ééntje verder of ééntje terug willen kijken of het verschil 2 is. Het kijken in een lijst kan rechte haken, met daarin de zogeten index: priemlijst[0] is het eerste element van de priemlijst, en priemlijst[5] is de 6e item in de priemlijst. Denk aan recursieformules, daar is u_0 ook de eerste term en u_5 de zesde term.

Wil je bepaalde waarden van een lijst aflezen, kan dat met lijst[i] waarbij i de INDEX is van de lijst. Je kan ook lijsten zelf nog manipuleren als je dat zou willen, wil je de vijfde element van een lijst definieren: lijst[4]=3 slaat dus getal 3 op op index 4 (wat de vijfde element is). Wil je weten hoe lang je lijst is, kan dat met len(list). wil je heel snel de LAATSTE item van de lijst weten, zonder te weten hoe lang deze is

Wil je waarden verwijderen, dan kan dat bijvoorbeeld met remove commando lijst.remove(lijst[4]) verwijderd de 5e waarde van de lijst. Alle waarden erachter schuiven dan eentje op.

Bekijk de voorbeelden hieronder, experimenteer!

lijst=[1,2,3,4,5,6]
print('de eerste waarde is', lijst[0])  # dit print als het goed is 1 af
print('de derde waarde is', lijst[2])   # dit print als het goed is 3 af
print('de lengte van de lijst is', len(lijst))
print('de laatste waarde van de lijst is', lijst[-1])

lijst.remove(lijst[2])
print('de derde waarde is verdwenen uit de lijst:', lijst)

lijst2=[1,2,2,3,3,3,4,4,4,4]
lijst2.remove(4)
print(lijst2)

Zoeken in lijsten

Met een for-loop kan je ook zoeken in lijsten. Daarbij kan je gebruik maken van booleaanse variabelen (zie les 1).

Voorbeeld: je hebt de lijst [5,6,2,3,7,2,1], en je vraagt je af of het getal 3 in deze lijst staat. Dan ga je één voor één de lijst af, en zodra de waarde gelijk is aan 3, wil je printen “gevonden, hij staat er in”, en anders “helaas, niet gevonden”. Deze opdracht kan je als volgt in pythonscript schrijven, probeer stapsgewijs te volgen wat het doet. We maken gebruik van les 1:

de fstring
de for loop
booleaanse variabelen
if en else

lijst = [5,6,3,4,7,2,1]
zoekditgetal = 3
is_gevonden = False     #we zetten in variabele is_gevonden nu een False, want we hebben het getal nog niet gevonden
for getal in lijst:
    if(getal == zoekditgetal):
        is_gevonden = True   #we veranderen de variabele naar True, want het is gevonden!

if(is_gevonden):
    print(f"de waarde {zoekditgetal} is gevonden")
else:
    print(f"de waarde {zoekditgetal} is niet gevonden")

de waarde 3 is gevonden

Typische Foutmeldingen#

voor je zelf aan de slag gaat, nog even over ‘wat als het nou niet lukt’? Nogmaals, computers zijn dom, ze doen letterlijk wat je vraagt, en als ze het niet snappen zijn het net leerlingen: gelijk stoppen en schreeuwen.

Maar python is zo’n fijne programmeertaal, het laat op zijn minst zien WAAR het fout gaat, met een interpretatie waarom. En jullie zijn zo verwend: je kan je code in chatgpt plakken en vragen waarom het fout gaat en een verbetering vragen. Maar dat kost veel energie, dus ga eerst maar zelf nadenken. Hieronder een lijst van typische fouten, en wat je kan doen om het te verbeteren. Daaronder staan codeblokken waar het indezelfde volgorde hieronder het fout gaat. Probeer het te verbeteren dat je op zijn minst geen foutmelding meer krijgt.

“IndententationError: (un)expected indent”: er is een tabje te veel of te weinig geplaatst, loop al je tabjes na
“Typerror” dit komt als je bijvoorbeeld een string en een getal op wilt tellen, of een lijst en een getal. Soms ook omdat je een komma in plaats van een decimale punt hebt gebruikt: kommas zijn gereserveerd voor lijsten of zogheten tuples (komt misschien nog wel eens aan bod als ik er aan denk).
“NameError” kan voorkomen als je bijvoorbeeld niet boven in je code een bibliotheek hebt aangeroepen (bijvoorbeeld import math of import numpy as np). Of als je een variabele aanroept die je niet hebt gedefinieerd, of een typfout maakt: ljist in plaats van lijst bijvoorbeeld
“SyntaxError” kan voorkomen als je bijvoorbeeld een : vergeet achter een if, for, while, else, etc. Vaak geeft het expected : of iets dergelijks. Ook kan het zijn dat je een haakje te veel of te weinig hebt getypt, dan staat er mismatched ). Ook kan het zijn dat je een “ bent vergeten aan het einde van een string.
“IndexError: list index out of range” kan voorkomen als je lijst van 5 waarden hebt maar je vraagt het zesde getal op. Die is er niet, ‘buiten bereik’…
“ZeroDivisionError: division by zero” deze moet duidelijk zijn… delen door nul is…
“ModuleNotFoundError: No module named ‘…’” kan zijn dat je een bibliotheek aanroept die niet bestaat of je maakt een typfout: import maths ipv import math bijvoorbeeld. Het kan ook zijn dat het niet geinstalleerd is, dan moet je even meer moeite doen.

i=1
j=3
    k=4

i=5,4
j=2.0
k=i+j
print(i)

np.sqrt(2)
print(getalwaarde)

#In dit stukje zitten veel fouten, zoek ze allemaal. Er moet 1000 keer hoi geprint worden
N=1,000
for i in range(1,N))
    print(i:)
        print("Hoi)

Losse opdrachten#

Hieronder vind je wat losse opdrachten, probeer er een aantal te maken met de kennis die je nu hebt geleerd, er wordt geen nieuwe modules of wiskunde van je verwacht. De opdracht staat in de opmerking van elke nieuwe code. Kom je er niet uit: chat is je vriend. De eerste opdrachten kan je de priemlijst generator gebruiken eerder in deze les. Kopieer plak en dan er mee verder werken.

# Genereer een lijst van de eerste 100 priemtweelingen. Een priemtweeling is een paar priemen (a,b) met de eigenschap dat a en b twee van elkaar verschillen.
#Bijvoorbeeld (2,3) (3,5) (5,7) (11,13) zijn priemtweelingen. Het is een open probleem of er oneindig veel priemtweelingen zijn

#Goldbach vermoeden: Elk even getal N groter dan 2 is te schrijven als de som van twee priemgetallen p en q: N = p+q, bijvoorbeeld 24 = 17+7
#Het vermoeden is dat dit waar is, maar er is geen bewijs. Een tegenvoorbeeld zou het vermoeden ontkrachten. Ga voor een willekeurig getal N na of het inderdaad de som van twee priemgetallen is, door expliciet die som te vinden
#de output is dan iets als "N = p + q" 
#Hulp: genereer een lijst van priemgetallen, en gebruik twee for loops slim

#Perfecte getallen: Een getal is volmaakt als de som van zijn echte delers (dus het getal zelf niet meegerekend) gelijk is aan het getal zelf.
# Voorbeeld 6 is volmaakt: Delers zijn 1, 2 en 3. Som: 1 + 2 + 3 = 6
# Voorbeeld 8 is niet volmaakt: de delers zijn 1, 2, 4 en som is 1+2+4 = 7
#merk op dat 1 dus altijd een deler is
#Opdracht, genereer een lijst van alle volmaakte getallen onder de 10.000: spoiler, het zijn er maar 4

#Collatz vermoeden, ofwel het 3n+1 probleem.
#Neem een getal N, is deze even halveer deze dan. Is het Oneven, doe dan 3N+1. 
#Herhaal deze regel voor het nieuwe getal.
#Vermoeden: na een tijdje kom je altijd op 1 uit. Daar stop je dan.

#Opdracht: genereer van een willekeurig getal de collatzlijst uit, samen met het aantal stappen om tot 1 te komen. Bijvoorbeeld, voor N=6 krijg je dan de volgende output
# De Collatz-reeks voor 6:
# [6, 3, 10, 5, 16, 8, 4, 2, 1]
# Aantal stappen: 8

#bonus opdracht, welk getal onder de 100 heeft de langste stappen nodig?

#Maak een lijst van 1 tot en met 100. Tel dan het aantal keer dat je het cijfer 5 tegenkomt. 55 telt dus als twee vijfen