Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Patroon ontdekt in priemgetallen

Priemgetallen blijken minder willekeurig dan gedacht en laten zelfs een patroon zien. Dat ontdekten twee wiskundigen van Stanford University in de Verenigde Staten. Het blijkt zo te zijn dat priemgetallen die elkaar opvolgen, minder vaak hetzelfde nummer aan het eind hebben.

Dit laatste betekent dat een priemgetal dat op 1 eindigt minder vaak wordt gevolgd door een ander priemgetal eindigend op 1. Als priemgetallen willekeurig zouden zijn, zou dit niet het geval zijn. Nu zijn priemgetallen ook niet willekeurig, maar gedragen zich wel in veel opzichten zo. Wetenschappers beschouwen de opeenvolgende reeks priemgetallen als pseudowillekeurig omdat geen structuur aan te geven is waar in de reeks een priemgetal voorkomt. De onderzoekers Kannan Soundararajan en Robert Lemke Oliver ontdekten echter een afwijking in de willekeur, in eerste instantie bij het getal 1. Priemgetallen eindigen na 2 en 5 altijd op 1, 3, 7 of 9. Een priemgetal is een natuurlijk getal en alleen deelbaar door 1 en zichzelf.

De onderzoekers ontdekten dat in de eerste 100 miljoen priemgetallen een priemgetal eindigend op 1 in slechts 18,5 procent van de gevallen werd gevolgd door een ander priemgetal eindigend op 1. Als priemgetallen echt willekeurig zijn, zou het volgende getal in 25 procent van de gevallen op 1 moeten eindigen. Priemgetallen met een 9 op het eind volgden in 22 procent van de gevallen een priemgetal met een 1 op het eind op. Priemgetallen die eindigen met een 7 of 3 komen ieder 30 procent voor.

Eenzelfde patroon bleek voor priemgetallen eindigend op 3, 7 en 9 te gelden: die werden eveneens het minst vaak opgevolgd door een priemgetal eindigend op hetzelfde cijfer. Ondanks dat het patroon minder sterk wordt bij hogere priemgetallen - de onderzoekers checkten getallen tot een paar biljoen - bleef de afwijking zichtbaar.

Soundararajan kreeg het idee dit te onderzoeken na een lezing over tossen. In de lezing werd gesteld dat als Alice een munt tost totdat ze een kop door een munt gevolgd ziet, en Bob een munt tost totdat hij twee koppen achter elkaar ziet, Alice dan gemiddeld vier keer zal moeten tossen, tegen zes keer tossen voor Bob.

Soundararajan vroeg zich af of dit vreemde fenomeen zich ook op andere terreinen voordoet. Omdat hij al jaren met priemgetallen bezig is, besloot hij te kijken of hier hetzelfde aan de hand is. Dat bleek inderdaad het geval. Hij keek naar priemgetallen met grondtal 3, waarbij grofweg de helft van de priemgetallen op 1 en de helft op 2 eindigt. Priemgetallen onder 1000 in base 3 die eindigden op 1 werden meer dan twee keer zo veel gevolgd door een priemgetal eindigend op 2, en vice versa.

Nadat Soundararajan zijn bevindingen liet zien aan Oliver, schreef die een programma om veel verder langs de lijn van priemgetallen te kunnen zoeken; namelijk door de eerste 400 miljard priemgetallen. Dat toonde hetzelfde aan. Ook bleek dit niet alleen het geval te zijn voor grondtal 3 en 10, maar ook voor andere grondtallen.

Waarom het laatste cijfer van een priemgetal niet willekeurig verdeeld lijkt te zijn, is niet helemaal duidelijk. De onderzoekers vermoeden dat het te doen heeft met hoe vaak paren, groepen van drie en grotere groepen van priemgetallen voorkomen, zoals voorspeld door het k-tuple-vermoeden.

Volgens de onderzoekers lijkt hun vinding geen invloed te hebben op praktisch gebruik van priemgetallen, zoals voor cryptografie.

De paper is te vinden op de arXiv-server.

Door Krijn Soeteman

Freelanceredacteur

15-03-2016 • 18:15

134 Linkedin Google+

Reacties (134)

Wijzig sortering
Zoals al aangegeven wordt in het artikel "lijkt" hun vinding geen praktisch invloed te hebben op de priemgetallen bij cryptografie.

Dit even vertaald:
Bijvoorbeeld RSA Encryptie maakt gebruikt van grote machtsverheffing getallen, waarbij de basis (start getal y) vele male groter is dan 100 miljoen. Om de inverse te berekenen van dit getal (om te decrypten) dient het congruent te zijn aan 1. (getal y modulus n ≡ y-1). Dit betekend dus dat getal Y altijd een priemgetal is, echter komen deze ver boven de 100 miljoen uit.

Voor mensen die van leesvoer houden over het duo Rijndael(Belgie), zij hebben in het jaar 2000 de Advanced Encryption Standard gezet. Hoe de berekeningen daar werken is leesbaar opgeschreven in dit document: http://www.cs.uu.nl/docs/vakken/b3crp/Symp1001/AES.pdf

[Reactie gewijzigd door nickko op 15 maart 2016 19:25]

Als Alice op een bepaald moment kop gooit, kan ze de worp daarna direct winnen door munt te gooien. Als ze dan niet wint is dat omdat ze weer kop gooit, en kan ze de worp dáárna weer gelijk winnen.

Als Bob op een bepaald moment kop gooit, kan hij de worp daarna direct winnen door weer kop te gooien. Als hij dan niet wint is dat omdat hij munt gooit, maar dan kan hij niet de worp daarna gelijk winnen (omdat hij nou eenmaal pas wint als hij 2x kop achter elkaar gooit).

Intuïtief is het dus wel logisch dat Bob vaker moet gooien om te winnen dan Alice moet gooien om te winnen.
De exacte uitleg weet ik ook niet, maar de kansen zijn niet gelijk.

Als je 2 keert tost, dan heb je 4 mogelijkheden:
* kop - kop
* kop - munt
* munt - kop
* munt - munt

Al je 3 keer tost heb je
1. kop - kop - kop
2. kop - kop - munt
3. kop - munt - kop
4. kop - munt - munt
5. munt - kop - kop
6. munt - kop - munt
7. munt - munt - kop
8. munt - munt - munt

De mogelijkheden 1, 2 en 5 zijn goed voor Bob
De mogelijkheden 2, 3, 4 en 6 zijn goed voor Alice


Mijn lessen kansrekening liggen alweer 2 decennia achter mij, dus aan 4x of 6x tossen ga ik me niet wagen, maar bovenstaand voorbeeldje toont hopelijk wel aan dat kansen voor Alice beter liggen dan die voor Bob.

[Reactie gewijzigd door tc-t op 15 maart 2016 19:06]

Dat is waar, maar dit effect is kleiner dan het effect dat in de paper is aangetoond.
Lemke Oliver and Soundararajan’s first guess for why this bias occurs was a simple one: Maybe a prime ending in 3, say, is more likely to be followed by a prime ending in 7, 9 or 1 merely because it encounters numbers with those endings before it reaches another number ending in 3. For example, 43 is followed by 47, 49 and 51 before it hits 53, and one of those numbers, 47, is prime.

But the pair of mathematicians soon realized that this potential explanation couldn’t account for the magnitude of the biases they found. Nor could it explain why, as the pair found, primes ending in 3 seem to like being followed by primes ending in 9 more than 1 or 7. To explain these and other preferences, Lemke Oliver and Soundararajan had to delve into the deepest model mathematicians have for random behavior in the primes.
Hier is rekening mee gehouden.
Lemke Oliver and Soundararajan’s first guess for why this bias occurs was a simple one: Maybe a prime ending in 3, say, is more likely to be followed by a prime ending in 7, 9 or 1 merely because it encounters numbers with those endings before it reaches another number ending in 3. For example, 43 is followed by 47, 49 and 51 before it hits 53, and one of those numbers, 47, is prime.

But the pair of mathematicians soon realized that this potential explanation couldn’t account for the magnitude of the biases they found. Nor could it explain why, as the pair found, primes ending in 3 seem to like being followed by primes ending in 9 more than 1 or 7. To explain these and other preferences, Lemke Oliver and Soundararajan had to delve into the deepest model mathematicians have for random behavior in the primes.
Het komt vooral omdat (buiten de getallen tussen 0 en 10) alleen getallen eindigend op 1, 3, 7 of 9 priemgetallen kunnen zijn.

0,2,4,6,8 -> alles wat op een even cijfer eindigt is per definitie deelbaar door 2
5 -> alles wat op een 5 eindigt is per definitie deelbaar door 5.

Schiet over: 1, 3, 7, 9
=> 1 kans op 4 of 25%

Op dit item kan niet meer gereageerd worden.


OnePlus 7 Pro (8GB intern) Microsoft Xbox One S All-Digital Edition LG OLED C9 Google Pixel 3a XL FIFA 19 Samsung Galaxy S10 Sony PlayStation 5 Games

Tweakers vormt samen met Tweakers Elect, Hardware.Info, Autotrack, Nationale Vacaturebank, Intermediair en Independer de Persgroep Online Services B.V.
Alle rechten voorbehouden © 1998 - 2019 Hosting door True