] >
Tot nu toe hebben we getallen tientallig genoteerd. Van deze notatie hebben we echter geen gebruik gemaakt bij het rekenen: we hebben alles teruggebracht tot het nemen van de opvolger. We zullen nu zien hoe de notatie samenhangt met delen met rest. Voor deze paragraaf gaan we uit van een vast natuurlijk getal met . We gaan getallen -tallig noteren. Het getal heet het grondtal van deze notatie.
Zij . We delen door , het quotiënt van bij deling door delen we vervolgens door , etc. Met delen bedoelen we hier steeds delen met rest. We krijgen dan na keer:
We hebben dan
Voor de rij geldt
M.a.w. de rij is het verloop van onder de transformatie van .
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Deze notatie ligt ook vast door
Dus bijvoorbeeld . Let op de volgorde: . De notatie wordt een notatie voor .
De keten (6.1) van gelijkheden is dus ook zo te schrijven:
Als , dan .
6.10 Definitie. Zij een natuurlijk getal. Bestaat er een rijtje van natuurlijke getallen met voor en als zo dat
dan zeggen we dat -tallig kan worden geschreven. We noemen de uitdrukking ‘’ de -tallige schrijfwijze van .
Uit het bovenstaande volgt:
6.12 Notatie. Zij een verzameling en . De verzameling rijen in hebben we genoteerd als . De deelverzameling bestaande uit rijen waarvoor er een is met voor alle geven we aan met . Het zijn de repeterende rijen van de vorm
We zeggen dat zulke rijen een -staart hebben.
We hebben de afbeelding
(6.2) |
waarbij bij iedere rij een is gekozen zodat voor alle . Voor zullen we ook schrijven omdat de keuze van er niet toe doet. De verzameling is de deelverzameling van bestaande uit rijen in met een -staart. Beperken we de afbeelding (6.2) tot deze deelverzameling dan krijgen we de afbeelding
(6.3) |
Omdat ieder natuurlijk getal -tallig kan worden geschreven, is de afbeelding (6.3) surjectief. We zullen zien dat hij ook injectief is, m.a.w. dat de -tallige schrijfwijze uniek is. Dat de afbeelding (6.2) surjectief is was al meteen duidelijk: . Injectief is hij niet: en .
We laten zien dat de afbeelding (6.3) een inverse heeft (en dus bijectief is). Die inverse is de afbeelding
(6.4) |
waarbij, als de rij het verloop van onder de transformatie van is, voor alle . We hebben al gezien dat . Nog aan te tonen dat, als , de getallen gelijk zijn aan . Uit volgt dat en . Dus ook , ofwel , en dus inderdaad . We hebben aangetoond:
6.13 Stelling. Ieder natuurlijk getal kan -tallig worden geschreven en deze schrijfwijze is uniek. □
Het bepalen van de -tallige notatie van een natuurlijk getal komt neer op herhaald delen met rest. Voor de -tallige notatie van wordt herhaald door gedeeld:
Dus . Je kunt de berekening ook zo noteren:
Of in een tabel die van rechts naar links wordt gemaakt:
0 | 1 | 13 | 106 | 851 |
1 | 5 | 2 | 3
| |
Bij een getal in de bovenste rij wordt links ervan het quotiënt bij deling door geplaatst en de rest eronder. De onderste rij is de -tallige schrijfwijze.
In Python kan de -tallige schrijfwijze bepaald worden door delen met rest, waarbij de resten in een lijst worden geplaatst. We gebruiken hierbij het datatype list. De termen in zo’n lijst hebben een index, en dat is een natuurlijk getal. Omdat we hier juist met natuurlijke getallen bezig zijn zullen we daar niet echt gebruik van maken. We beperken ons daarom in dit hoofdstuk tot een paar simpele operaties met lijsten.
De functie repres(a,g) geeft de -tallige schrijfwijze van als een list:
Het terugrekenen gebeurt in omgekeerde volgorde:
Bij het grondtal spreken we van de binaire schrijfwijze. Gebruikelijk is om woorden van -en en -en te schrijven: in plaats van schrijven we kortweg . Het moet dan natuurlijk wel duidelijk zijn dat we de binaire notatie bedoelen.
Delen door geeft alleen de getallen t/m als mogelijke resten. De achttallige (=octale) schrijfwijze van een getal is een rijtje van deze getallen. De -tallige schrijfwijze van is en we schrijven het ook korter als . In de octale notatie zijn getallen woorden in de cijfers t/m .
De -tallige (= hexadecimale) schrijfwijze van een getal is een rijtje bestaande uit getallen van t/m :
Om getallen compact hexadecimaal te kunnen noteren heb je ook symbolen nodig voor de getallen t/m . Daarvoor worden gewoonlijk de letters A t/m F gebruikt. De hexadecimale notatie van is dan .