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

Door , , 134 reacties

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.

Moderatie-faq Wijzig weergave

Reacties (134)

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]

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.
Dit begrijp ik al niet, deze kansen zouden toch gelijk moeten zijn?
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.
Goede onder woorden gebracht. Ik kwam er niet helemaal uit.

Kun je uitleggen waarom Alice *gemiddeld* 4 keer moet tossen en Bob 6 keer? Dat lijkt me erg vaak voor een gemiddelde
Voordat je dit in de praktijk brengt in het casino...

Bedenk dat Bob de enige is die twee keer achter elkaar kan winnen, bij 3x tossen.

Mogelijkheid 1 is goed voor Bob, want hij wint 2 keer, maw ze winnen even veel, als ze 1 euro per winst krijgen uitgekeerd.
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]

Ik ben geen natuurkundige of wiskundige, maar volgens mij staat dit uit met iets wat Satyendra Bose begin 20e eeuw ontdekte. Stel, je hebt twee munten, en gaat die een hele tijd opgooien. Volgens de wet van de grote getallen zou dan 1/4 van de keren kop en kop zijn, 1/4 kop en munt, 1/4 munt en kop en 1/4 munt en munt moeten zijn.
Bose stelde echter dat 1/3 van de gevallen kop en kop moeten zijn, 1/3 van de gevallen kop en munt moeten zijn en 1/3 van de gevallen munt en munt.

Toen hij een paper ter publicatie aanbood, dacht iedereen dat hij een grove rekenfout had gemaakt, en werd de paper geweigerd. Maar toen hij daarop Einstein aanschreef, reageerde die dat de berekeningen wel degelijk klopten, maar dat Bose ook een nieuwe statistiek had gevonden.

(ik hoor graag als ik iets verkeerds zeg ;) )
Stel, je hebt twee munten, en gaat die een hele tijd opgooien. Volgens de wet van de grote getallen zou dan 1/4 van de keren kop en kop zijn, 1/4 kop en munt, 1/4 munt en kop en 1/4 munt en munt moeten zijn.
Bose stelde echter dat 1/3 van de gevallen kop en kop moeten zijn, 1/3 van de gevallen kop en munt moeten zijn en 1/3 van de gevallen munt en munt.
In het eerste geval maak je onderscheid tussen 'kop en munt' versus 'munt en kop', in het tweede geval noem je alleen kop en munt. Maar evengoed komt die uitkomst dan ongeveer in de ½ van de gevallen voor, en de andere twee elk ¼.
Gezien Satyendra Bose's achtergrond in de kwantumfysica zal die ⅓ wel te maken hebben gehad met het substitueren van munten voor deeltjes die niet onafhankelijk waren.
Zie mijn reactie op Sam 57
Uiteraard is dit zo?! Dit is toch alleen maar een logisch gevolg van de theorie achter Wheel Factorization: https://en.wikipedia.org/wiki/Wheel_factorization
Als je een willekeurig getal modulo 30 doet (30 = 2 * 3 * 5), en je houdt geen 1, 7, 11, 13, 17, 19, 23 of 29 (en het getal is boven de 5), dan is het sowieso geen priemgetal en is het getal deelbaar dan wel door 2, 3 of 5 en die wetenschap is reuze handig!
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.
Maar als ik kijk naar een primewheel van 30, dus: [1, 7, 11, 13, 17, 19, 23, 29]
Dan is het logisch dat 3 vaker gevolgd wordt door een 9 dan een door 7 en dat een 1 (of een 3) nog wat minder snel volgt. Die liggen immers verder van 13 en 23 vandaan...

Overigens hebben de priemgetallen tot en met 29 al een wiel (herhaalpatroon) met een omvang van 6.469.693.230, dus dan is het bekijken van de eerste 100 miljoen priemgetallen (2 t/m 2.038.074.743) niet heel representatief om grote patronen te zien, aangezien bij de volgende 4 miljard getallen de invloed van alleen al "29" op hele andere plekken ligt en het priemgetallen-landschap er dus compleet anders uitziet.

[Reactie gewijzigd door Elijan9 op 15 maart 2016 21:10]

Inderdaad, dit geeft alleen maar aan hoe snel de media op elk bericht springen wat ze niet meteen snappen maar wel aannemelijk klinkt en geen moeilijke woorden gebruikt. Voor een meer gedetaillerde ontkrachting: http://security.stackexchange.com/a/117450/2684

Simpel gezegd: als X geen priemgetal is omdat het deelbaar is door 3, dan kunnen X+2 en/of X+4 wél priemgetallen zijn, maar X+6 is dan ook deelbaar door 3. Hetzelfde geldt voor X en X+10 in het geval dat X een veelvoud is van 5.

Omgekeerd volgt dat X en X+2 wel allebei priemgetallen kunnen zijn, maar dan kan X+4 het niet meer zijn: X+4 is dan deelbaar door 3.
Omgekeerd volgt dat X en X+2 wel allebei priemgetallen kunnen zijn, maar dan kan X+4 het niet meer zijn: X+4 is dan deelbaar door 3.
Deze laatste snap ik niet.

Stel X = 3
X en X+2 kunnen beide priemgetal zijn: 3 en 5 => OK
X+4 is dan deelbaar door 3 maar 7 => niet deelbaar door 3?

Of interpreteer ik iets fout?
Het ging over het geval dat X-2 deelbaar was door 3. Als je met 5 zou beginnen komt het wel uit.
We hebben het hier over priemgetallen tot 8 cijfers lang. De 3-regel klopt niet voor X=3 en de 5-regel niet voor X=5. Maar neem X=17: X+2=19 is ook een priemgetal, en dus moet X+4=21 wel deelbaar zijn door 3.
Ik neem aan dat ze hier rekening mee gehouden hebben.

Het hele punt is dat je zou zeggen dat "ik heb priemgetal [X], we gaan ervan uit dat [X+1]%10 wordt gegeven door een stochast die onafhankelijk is van [X]" blijkt dus niet te kloppen. Dat er rekening gehouden dient te worden met dat de getallen sowieso niet evenveel voorkomen naarmate je verder komt in de reeks is nogal logisch neem je mee in het opstellen van je stochast.

Verder hebben we het hier over een erg grote dataset en dit is een statistische uitspraak. Nu is het aan andere wetenschappers om aan te tonen waar dit allemaal vandaan kan komen. Als de mensen van stackexchange dusdanig grote waarden inderdaad kunnen verklaren (wat nog niet is gebeurd; maak hier een simulatie van en publiceer het) met dit principe dan is het probleem/idee de wereld uit.

Waar dit precies vandaan komt is een leuk vraagstuk.

Edit; zie ook de quote van Jaahp.

[Reactie gewijzigd door Denni op 15 maart 2016 19:46]

Want tweakers en het internet ontkrachten wel even direct een 16-pagina-tellend paper van een stanford postdoc en prof... binnen een uur... gewoon... omdat het overduidelijk niet zo is. Daar zullen ze de dus allemaal wel aan gedacht hebben... :P
Wat een zinloze reactie.
Inderdaad, dit geeft alleen maar aan hoe snel de media op elk bericht springen wat ze niet meteen snappen maar wel aannemelijk klinkt en geen moeilijke woorden gebruikt. Voor een meer gedetaillerde ontkrachting: http://security.stackexchange.com/a/117450/2684
Staat ook in de Tweakers post.
Simpel gezegd: als X geen priemgetal is omdat het deelbaar is door 3, dan kunnen X+2 en/of X+4 wél priemgetallen zijn, maar X+6 is dan ook deelbaar door 3. Hetzelfde geldt voor X en X+10 in het geval dat X een veelvoud is van 5.

Omgekeerd volgt dat X en X+2 wel allebei priemgetallen kunnen zijn, maar dan kan X+4 het niet meer zijn: X+4 is dan deelbaar door 3.
Is een herhaling van @Elijan9 waardoor je keer verwarring zaait, omdat je het onnodig complex opschrijft.

Mede Tweakers: vanwaar de +2?
Het gaat om de procenten het petcentage is niet gelijk voor de eindnummers. Dit zou je kunnen gebruiken bij het zoeken van een volgend priemgetal door eerst getallen die eindigen op een getal met een hoog percentage te controleren kan je efficiënter zoeken door de kans te vergroten.
in de paper staat blijkbaar dat hun resultaat andere waarden geeft ten aanzien van de kansen dan je zou verwachten volgens Hardy en Littlewood (ook @MSalters)
Ik zeg niet dat je ongelijk hebt (integendeel, het klopt natuurlijk inhoudelijk), maar hoe kan het dat twee wetenschappers van Stanford zeggen een ontdekking te hebben gedaan en jij zegt dat dit "uiteraard" zo is? Ik ben geen wiskundige, maar ik vermoed hier zomaar dat jij iets anders bedoelt dan de wetenschappers hier ontdekt hebben? :)
Eerlijk gezegd, überhaupt het idee hebben dat de distributie van priemgetallen willekeurig zou zijn, vind ik al totaal niet Stanford waardig. Priemgetallen zijn het logisch gevolg van alle voorgaande getallen en elk veelvoud van elk priemgetal is géén priemgetal. Priemgetallen zijn alles behalve willekeurig, maar je moet wel veel doorrekenen voordat je met zekerheid kunt zeggen dat "iets" een priemgetal is. "Moeilijk uitrekenen" en "willekeurig" zijn niet hetzelfde. :)

Uit het artikel:
Two mathematicians have found a strange pattern in prime numbers — showing that the numbers are not distributed as randomly as theorists often assume.

[Reactie gewijzigd door Elijan9 op 16 maart 2016 14:17]

Het onderzoek stelt toch niet dat priemgetallen willekeurig waren? Het onderzoek stelt een nieuw patroon te hebben gevonden. Nature noemt het ook "Peculiar pattern found in ‘random’ prime numbers". Nergens wordt beweerd dat priemgetallen willekeurig -zijn-.
...en dat is nu een drogreden op basis van autoriteit ;)
Waarom zou ik hem niet in twijfel mogen trekken?
Lees m'n bericht nog eens zou ik zeggen. Ik veronderstel niets. Ik stel een vraag, wat niet vreemd is als iemand hardop een onderzoek van Stanford in twijfel trekt.

[Reactie gewijzigd door mOrPhie op 15 maart 2016 22:40]

Dit gaat niet om de reputatie van de media, maar van Stanford, die erg hoog staat aangeschreven en meer geloofwaardigheid heeft dan media.
Als Rambam (of een andere club) een verhaal verzint en niemand controleert het voor ze het publiceren, controleren ze dus ook niet of het echt van Stanford komt..
Ik stel alleen een vraag. Er wordt hardop getwijfeld aan een onderzoek van twee wetenschappers die zijn aangesloten aan stanford. Dat vind ik opmerkelijk. Ik zeg niet dat de ene of de andere gelijk heeft, ik merk alleen op dat het opmerkelijk is en dat ik dan wat uitleg zou willen. :)
Ik denk dat Elijan9 een veronderstelling doet die niet klopt (nl: alsof priemgetallen willekeurig begonnen en na dit onderzoek een patroon hebben, wat niet zo gesteld wordt in het onderzoek).

[Reactie gewijzigd door mOrPhie op 15 maart 2016 22:41]

En zo tegen eind maart moet toch al, al het nieuws met een korrel zout worden genomen.
Sorry hoor, maar is dit niet puur en alleen omdat er binnen een '10-tal' vaak meer dan 1 priemgetal is?

Waarschijnlijk wordt de 1 het minst vaak gevolgd door een 9, dan de 7 en dan de 3. De 3 het minst vaak door de 1, dan de 9 enzovoorts.

Zou ik geen patroon durven noemen

Edit: aan het artikel te zien is dit voor de 1 inderdaad het geval.

[Reactie gewijzigd door Pepper92 op 15 maart 2016 18:51]

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.
Thanks! Het zal dus een deel verklaren, maar niet alles.
Het wetenschappelijke artikel is een stuk wiskundiger, dan dit artikel laat vermoeden. Ze hebben een aantal eigenschappen van priemgetallen aangetoond in een k-tallig stelsel met k > 2.
Misschien komt mijn reactie iets fel over, maar ik vroeg het me oprecht af. Hierboven is gelukkig meer duidelijkheid gegeven; ze hebben er zelf (gelukkig) ook aan gedacht.
Ze zouden jou moeten aannemen, want jij denkt aan dingen waar wiskundigen van Stanford University misschien niet aan denken.
Het is anders wel iets waar naar mijn idee meer mensen aan denken, en het zou naar mijn idee dus goed zijn als het hierboven gequote stuk terug zou komen in het nieuwsbericht.
Als priemgetallen echt willekeurig zijn, zou het volgende getal in 25 procent van de gevallen op 1 moeten eindig
Moet dat niet 10% zijn? Of kan iemand die 25% uitleggen?
Komt omdat niet alle getallen tussen 1 en 10 priemgetallen zijn, alleen 2, 3, 5 en 7 zijn dat.
(4 = 2 x 2
6 = 2 x 3
8 = 2 x 2 x 2
9 = 3 x 3)
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%
Zie ook het artikel : "Priemgetallen eindigen na 2 en 5 altijd op 1, 3, 7 of 9."
Dat zijn dus 4 keuzes, vandaar de 25%. Al wordt er dan ook de aanname gedaan dat elk van deze 4 eindcijfers even vaak voor komt. Ik weet niet of dat inderdaad zo is.
Elk van deze 4 eindcijfers komt even vaak voor: namelijk oneindig. Aangezien er een oneindige hoeveelheid priemgetallen bestaat (Stelling van Euclides), komen de 4 eindcijfers per definitie allemaal oneindig vaak voor.

* Edit: en ik wordt gedownmod omdat ... ? Dit lijkt me niet echt off-topic, en zeker geen trolling.

[Reactie gewijzigd door Amanush op 15 maart 2016 19:18]

Oei! Oneindig, dat heeft een paar bijzondere eigenschappen. Oneindig is namelijk ongelijk aan oneindig. Neem nou eens de Reële getallen. Dus tussen elke twee reële getallen zitten oneindig veel reële getallen. Dus zitten er tussen 0 en 10 oneindig veel getallen, en tussen 0 en 1 ook. Maar toch zijn ze verschillend.
Oei! Oneindig, dat heeft een paar bijzondere eigenschappen. Oneindig is namelijk ongelijk aan oneindig. Neem nou eens de Reële getallen. Dus tussen elke twee reële getallen zitten oneindig veel reële getallen. Dus zitten er tussen 0 en 10 oneindig veel getallen, en tussen 0 en 1 ook. Maar toch zijn ze verschillend.
Die twee oneindigheden zijn wel hetzelfde, tussen 0 en 10 zitten precies evenveel reële getallen als tussen 0 en 1 (namelijk 2ℵ₀ info).

Anders dan bijvoorbeeld het aantal rationale getallen (breuken), dat zijn er veel minder, alhoewel nog steeds oneindig (namelijk ℵ₀ info).
Elk van deze 4 eindcijfers komt even vaak voor: namelijk oneindig. Aangezien er een oneindige hoeveelheid priemgetallen bestaat (Stelling van Euclides), komen de 4 eindcijfers per definitie allemaal oneindig vaak voor.
1. Dat er oneindig veel priemgetallen zijn, impliceert nog niet automatisch dat er voor alle vier die cijfers ook oneindig veel priemgetallen zijn die eindigen op dat eindcijfer. Je kunt bijvoorbeeld niet zomaar uitsluiten dat er voorbij een bepaalde bovengrens geen priemgetallen meer voorkomen die eindigen op een 3.
(overigens is het wel zo, sterker nog, voor ieder getal x dat eindigt op 1,3,7 of 9 bestaan er zelfs oneindig veel priemgetallen die eindigen met x; dit is een gevolg van de stelling van Dirichlet)

2. Ook al zijn er voor alle vier de eindcijfers oneindig veel priemgetallen die daarmee eindigen, impliceert dat nog niet automatisch dat ze alle vier even veel voorkomen. Je kunt bijvoorbeeld niet zomaar uitsluiten dat voorbij een bepaalde bovengrens de dichtheid van priemgetallen die eindigen op een 7 twee keer zo hoog is als eindigend op een 9.
[...]

1.
2.
Spreek je in 1. jezelf niet tegen?

Stelling van Dirichlet > Voor elk getal x eindigen oneindig aantal priemgetallen met x -> dus ook voor getallen 1,3,7,9 --> oneindig aantal priemgetallen die eindigen op 1,3,7,9.
Nee, 1. zegt inderdaad dat er oneindig veel priemgetallen zijn die op 1 eindigen, en ook oneindig veel die op 3 eindigen, en idem dito voor 7 en 9. Alleen dat volgt niet vanzelfsprekend uit enkel het feit dat er oneindig veel priemgetallen zijn (zoals Amanush concludeerde).

2. zegt dat er bijvoorbeeld niet per se evenveel priemgetallen hoeven te zijn die op 3 eindigen als op 7. Het zou best zo kunnen zijn, maar dat kunnen we niet zomaar concluderen uit het feit dat er van allebei oneindig veel zijn.
Ja, maar het gaat hier om de verhouding waarin ze voorkomen en die is nu voor de eerste 400 miljard priemgetallen vastgesteld.
Maar dat geldt niet voor de onderzochte set van bekende priemgetallen. Dat is een eindige verzameling. En er kan alleen maar onderzoek worden gedaan op bekende priemgetallen. Ben wel benieuwd naar de frequentie van die 4 'eindgetallen'.
Het gaat ook niet om de verhouding tussen de eindcijfers in de volledige set priemgetallen, maar enkel om de eindcijfers van de priemgetallen die elkaar opvolgen.
Sommige getallen kunnen oneindiger zijn dan andere getallen. Als je bijvoorbeeld naar het rijtje (1,0,1,1,0,1,1,0,...) kijkt dan is het duidelijk dat 1 vaker voorkomt dan 0: er is een N, zodat in ieder deel rijtje (de eerste n elementen) van lengte > N 1 vaker voorkomt dan 0. Als dus voor ieder (voldoende lange) deel rijtje geldt dat 1 vaker voorkomt dan 0, dan is het niet vreemd (afhankelijk van je definities en axioma's) om te concluderen dat de 1 ook in het oneindige rijtje vaker voorkomt dan 0.
Die aanname is nou juist waar het om gaat. Als iets compleet willekeurig is heb je 25% kans dat het volgende cijfer een 1 wordt, 25% kans dat het een 3 wordt, enzovoorts. Er is ontdekt dat de kans dat na een eindcijfer 1, het volgende eindcijfer weer 1 is, lager is dan 25%. Dit gegeven maakt dat priemgetallen minder willekeurig zijn dan gedacht en dat er misschien zelfs een patroon in te vinden is.
Niet helemaal. Alle eindcijfers kunnen best even vaak voorkomen (dat is de aanname waar ik het over had), maar het nieuwsbericht gaat hier specifiek om het de kans waarbij het eindcijfer van twee opeenvolgende priemgetallen gelijk is. Een klein nuance verschil, maar wel een andere aanname.
Natuurlijk is er een patroon.. Het priemgetallenpatroon
De priemgetallen zijn oneven, omdat alle even getallen (met uitzondering van 2) deelbaar zijn door 2. Dan hou je er 5 over, namelijk 1, 3, 5, 7 en 9.
Wat geldt voor 2, geldt ook voor 5. Alle getallen die eindigen op een 5 zijn deelbaar door 5, met uitzondering van 5 zelf. Dan hou je dus 4 cijfers over, en als de kans evengroot is, zou de kans 25% zijn.
Je bedoelt uiteraard: dat alle even getallen ook deelbaar zijn door 2 (naast 1 en zichzelf); en dat voor 2 geldt: ENKEL 1 en zichzelf

Zelfde verhaaltje voor 5.

Zoals het er nu staat klinkt het nogal ongelukkig:
* omdat alle even getallen (met uitzondering van 2) deelbaar zijn door 2 => eigenlijk zeg je dat 2 niet deelbaar is door 2
* Alle getallen die eindigen op een 5 zijn deelbaar door 5, met uitzondering van 5 zelf => ditto

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

Omdat getallen eindigend op een even getal geen priemgetallen kunnen zijn.
Hogere priemgetallen kunnen alleen eindigen op 1, 3, 7 en 9, zoals ook in het artikel staat. 5 en 0 zijn uitgesloten als veelvouden van 5 en 2,4,6 en 8 als veelvouden van 2. Blijven er slechts vier over, vandaar 25%.
Getallen die eindigen op een 2 of een meervoud van 2 (4, 6, 8 of 10 (ofwel 0)) zijn geen priemgetallen, want ze zijn deelbaar door 2 en dus geen priemgetal.
Boven de 5 zijn alleen cijfers eindigend op 1,3,7,9 nog priemgetallen, omdat 2,4,6,8 even zijn en 0 en 5 deelbaar zijn door 5.
Andere cijfers hebben bij vermenigvuldigen niet altijd hetzelfde cijfers. Zo heeft 3 de getallen 3,6,9 onder de tien, maar in de tien-reeks zijn het 2,5, en 8, en in de twintig reeks 1,4,7.


Omdat 1,3,7,9 de enige mogelijkheden blijven, en bij een normale verdeling elk getal even vaak voor kan komen, is er dus normaal een 25% kans op een specifiek eindcijfer na het gekozene.
En ik altijd maar denken dat 0 ook een even getal was?

Boven de 5 zijn alleen cijfers eindigend op 1,3,7,9 nog priemgetallen, omdat 0,2,4,6,8 even zijn en 5 deelbaar is door 5
Uit het artikel

"Priemgetallen eindigen na 2 en 5 altijd op 1, 3, 7 of 9"
Even getallen vallen af omdat het getal daardoor deelbaar wordt door 2 en dus geen priemgetal meer is.
Zodoende blijven 1, 3 ,5 en 7 over.
9 valt ook af, want deelbaar door 3
9 zelf wel, maar een groter getal zoals 19 is weer een priemgetal.
5 valt juist af omdat elk getal groter dan 5 dat eindigt op 5, sowieso deelbaar is door 5.
Getallen 2, 4, 6, 8 en 0 (vanaf de 10 natuurlijk) zijn altijd deelbaar door 2. Deze getallen zullen dus nooit een priemgetal zijn. het getal 5 is altjid deelbaar door 5 wat dus ook op 5 zelf na nooit een priemgetal kan zijn. hierdoor resteren de getallen 1,3,7 en 9, en dus een 25% kans dat je een van deze getallen willekeurig pakt

[Reactie gewijzigd door Rushed op 15 maart 2016 18:35]

Wat is de wiskunde achter het tossen? Zowel Bob als alice moeten 1 bepaalde uitkomst krijgen voor de eerste munt en een bepaalde uitkomst voor hun daaropvolgende munt. Telkens met een kans van 1 op 2. Hoe leidt dit toch tot een ander gemiddeld aantal worpen?
Ik denk:
Als Alice kop gooit, heeft hij daarna 50% kans op munt. Gooit ze kop, dan heeft ze de volgende worp weer 50% kans.

Maar: Gooit Bob kop, dan heeft hij 50% kans op weer kop. Gooit hij munt, dan moet hij eerst weer kop gooien voor een nieuwe 50% kans op (2x) kop.
Inderdaad. Goed te zien als je de mogelijkheden van vier keer gooien op een rijtje zet. Stel kop = 0 en munt = 1 dan zijn de mogelijkheden als volgt:

0000 kop-kop
0001 kop-kop & kop-munt
0010 kop-kop & kop-munt
0100 kop-kop & kop-munt
1000 kop-kop
0011 kop-kop & kop-munt
0110 kop-munt
1100 kop-kop
1001 kop-kop & kop-munt
0101 kop-munt
1010 kop-munt
0111 kop-munt
1110
1011 kop-munt
1101 kop-munt
1111
Bij 4 keer gooien komt er bij 8 reeksen twee keer kop voor, terwijl er in 11 reeksen een combinatie kop-munt voorkomt binnen 4 keer gooien.

[Reactie gewijzigd door rick77 op 15 maart 2016 19:10]

Nee dat klopt , denk ik met alle respect , niet ;) . Beste Rick 77 aangezien 1 munt is en 0 kop. Ga je uit van 4x gooien

=1100=munt-kop
=1111=munt-munt
=1001=munt-kop-kop-munt
=0111=kop-munt,munt,munt
enz.
0000 is dan kop -kop ,dat klopt wel.
en 0001 =,kop,kop,kop,munt ,dat klopt ook.

0011,is geen kop,kop,kop,munt ,maar kop, munt.
0110 is dan weer wel kop,munt.
m.a.w 0011 is fout ,0111 is fout ,1011 is fout ,1101 is fout

1110 = munt,munt,munt,kop .Want je zegt 0001=, kop ,kop kop,munt en dat klopt.

Ik ga uit van het binaire* stelsel ,niet van het trinaire stelsel omdat muntje gooien maar 2 argumenten kent n.l kop & munt. Het aantal worpen is een Ariteit.(=Plaatsigheid)

Maar dan nog ,is het een vorm van kansberekening die afhangt ,(a)van de persoon die gooit,(B)de snelheid waarmee,(c)het gewicht v/ munt,(d)de snelheid en richting v.d wind (e) andere externe factoren o.a het draaien v/d aarde,magnetisch veld en nog een paar anderen.
Men gaat uit van vaste factoren ,terwijl die er bij echt muntje gooien alleen in de meest ideale omstandigheden zo zijn.Maar er is een kans van slagen als de reeks ,in 3 maal , zo loopt;

1=0101,1100,1110,0000,
2=1100,0101,0101,1110,
3=0011,1000,0110,1100
dat de volgende gooi ; munt zal zijn.

n.b Ik had de cijfers random neergezet ,dus niet gemanipuleerd maar toch blijkt uit de 3 reeksen 50% -50%. Frappant :D
mijn aanname in deze is in de volgorde waarin de kop of munt kant gevallen is , bepaald de uitkomst van de voorspelde volgende gooi

*binair

[Reactie gewijzigd door tweaker1971 op 16 maart 2016 10:12]

Ik heb achter alle 16 mogelijke reeksen die gegooid kunnen worden met 4 keer achter elkaar een munt gooien gezet of de gevraagde combinaties (kop-kop of kop-munt achter elkaar) er in voorkomen. Dit om te laten zien dat de kans op kop-munt achter elkaar (11 keer) groter is dan de kans op kop-kop (8 keer), zoals Pepper92 intuitief ook al uitlegt.
Klopt :) ,je hebt niets anders dan gelijk met deze voorwaarde " 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.

Ik dacht op een gehele andere lijn ,zoals ik al zei ,alleen kop of munt en niet 2 koppen achter elkaar in die verhouding .Thanx Rick , en mijn excuus voor dat ik je fout noemde :)

[Reactie gewijzigd door tweaker1971 op 16 maart 2016 07:54]

Ik vond dat inderdaad het interessantste van het hele artikel. Daar moet ik even wat meer over opzoeken...Dat met die priemgetallen zal wel...Lijkt mij nog steeds random. Klinkt me een beetje als Nostradamus in mijn oren. Zoekt en gij zult vinden..

edit: ik snap hem al:

Als Bob de tweede poging mis tost ( Munt ipv kop ) moet hij bij voorbaat opnieuw beginnen

Als Alice de tweede poging mis tost ( dus weer kop, geen munt ) dan kan zij deze gelijk voor de volgende poging gebruiken ( eerst kop ) en gelijk een tweede poging wagen..

Vandaar ook de verhouding 3 op 2

edit 2: ik ga eens wat munten achter houden voor in de kroeg :)

edit 3: deed me trouwens sterk denken aan het "drie deuren probleem" uit een oude spelshow van Willem ruis, waar dit trucje werd gebruikt om spelers te misleiden, het was de taak van de spelhost om de kandidaten de verkeerde deur te laten kiezen.

http://www.sybrandjissink.nl/3deuren/

[Reactie gewijzigd door micla op 15 maart 2016 19:27]

"Vervolgens maakte de alwetende assistent een lege deur open" Dan heb je automatisch nog maar 2 keuze`s 2 uit 2 .Het is dan 50/50 geworden en geen 33 % kans uit /100 meer .
In de link draaien ze het om en zeggen dat je een kans hebt uit 2 op 3 maar 1 deur is toch al weg,dus die telt niet meer en dus is het 1 op 2 ipv 2 op 3 geworden.

Maar met deze 2 regels ; (maar dan moet ik de regels ook weten)
1. Zij zal nooit aan de deur komen van jouw keuze, die kans blijft dan ook altijd hetzelfde
2. Zij zal nooit aan de deur komen waar de prijs achter zit.


Stel je voor ,ik sta in de studio met Hans Kazan en assistente .Ik kies deur nummer 1 .Hans zegt ,"we gaan nu een deur open maken waar die in ieder geval niet achter zit ",en de assistente maakt deur nummer drie open. Dan zou ik goed hebben gekozen,de prijs zit achter deur nr 1 ,omdat de assistente nooit aan de deur met de prijs zou komen ,dus 2 zou ze nooit open doen.De enigste die open gaat,over blijft is is 1 .

Maar dit > Het misconcept bij dit probleem is eenvoudig. Velen denken namelijk dat er een 1:1 kansverdeling is en dat dus de kans op een prijs bij beide deuren 50% is. Dit is niet waar! De kans dat de kandidaat een prijs wint als hij/zij vasthoudt aan zijn/haar eerste keuze, is 1/3 (33%) en de kans op een prijs bij wisselen is 2/3 (67%).< klopt dan niet want ik hield vast aan mijn 1st keuze

Off topic; Ik had gehoord dat er snel verschoven werd,de prijzen stonden meestal op plateau`s met wielen eronder,zodat de kandidaat soms als nog wel de gesponsorde prijs kreeg ,die dan uitgebreid in beeld kwam.Een vorm van reclame .

[Reactie gewijzigd door tweaker1971 op 16 maart 2016 08:10]

Dat vroeg ik me ook al af! Wie weet het antwoord?
Is het niet gewoon zo dat als je maar hard genoeg zoekt/kijkt, je altijd wel ergens een patroon in denkt te herkennen, ondanks dat het nog prima toeval kan zijn?
Het omgekeerde kan natuurlijk ook,
de dusdanige overtuiging dat het random is waardoor er niet neer naar patronen wordt gezocht.
Iedereen wist dat het niet kon, totdat er iemand kwam die dat niet wist - aldus Epictetus.
Lekker cliché :P
Daarom onderzoek je natuurlijk of het effect statistisch significant is. Dat moet met 400 miljard getallen wel lukken...

Maar in het algemeen moet je niveau van statische significantie wel in lijn zijn met het aantal hypotheses wat je probeert. Als je maar genoeg hypotheses test, zonder daarbij je criteria voor statistische significantie aan te scherpen, vindt je inderdaad verbanden zoals deze. Een groot probleem in de minder exacte wetenschappen, waar moeilijk aan data te komen is of waarin verbanden vaag zijn. Daar valt de wiskunde niet bepaald onder.

[Reactie gewijzigd door bwerg op 15 maart 2016 19:01]

Een patroon kenmerkt zich door het ogenschijnlijk terugkerend patroon. In het geval van toeval zou dit voor een bepaalde reeks mogelijk zijn maar in een reeks van 400 miljard priemgetallen is dat dan wel heel veel "toeval".

Uiteindelijk is alles om ons heen gebonden aan wiskundige / natuurkundige wetten. Dat iets met "toeval"gebeurd heeft meer te maken met het feit dat wij het (nog) niet hebben/ hadden kunnen voorspellen.
maar wat kunnen we ermee ? :/
Priem getallen zijn "pseudorandom" en om die reden veel gebruikt in encryptie waar "random" nodig is, als er nu een patroon in die priemgetallen zit wordt encryptie in bepaalde gevallen te kraken
Nee, priemgetallen zijn helemaal niet pseudo-random. Het zijn gewoon getallen op een getallenlijn die niet deelbaar zijn door de voorafgaande getallen, ze hebben een hele duidelijke definitie en ze hebben een sterk repetitief karakter (elk veelvoud van een priemgetal p is géén priemgetal). Het is alleen wel rekenintensief om te controleren of iets een priemgetal is.
Met een priemgetal kun je wel gemakkelijk pseudo-random getallen genereren.
Getallen die worden gegenereerd door middel van een algoritme, maar waarvan niet makkelijk (zonder kennis van het algoritme) te achterhalen is wat het volgende getal zal zijn, zijn per definitie pseudo-random getallen. Hier voldoen priemgetallen prima aan.

Als er een patroon in de pseudo random getallen te vinden is, ben je over het algemeen niet blij met je algoritme als je random getallen wilt simuleren.

[Reactie gewijzigd door Denni op 15 maart 2016 19:52]

Ja, maar bij priemgetallen is héél goed te zeggen dat p+1 geen priemgetal is, en dat als p - 2 óók een priemgetal is, dat p + 2 dat dan niet is e.d. Bij priemgetallen is redelijk goed te achterhalen wat niet het volgende getal zal zijn.

Voor p > 5 natuurlijk ;)

[Reactie gewijzigd door Elijan9 op 15 maart 2016 20:22]

dat klopt toch niet?
5=priem
5-2=3->priem
5-2=7->priem
Het punt is vooral dat als ik je priemgetal nr 25 tm 50 geef je moeilijk het volgende getal kunt voorspellen zonder kennis over hoe ik de getallen genereer.
Als we priem getal xxxxxx1 gevonden hebben dan kunnen we bij de berekening voor het volgende priem getal alles wat eindigt op 1 al uitsluiten.

En als je je afvraagt waarom wil je in godsnaam priem getallen weten.
Encryptie encryptie encryptie ;)

cilph; sssssh.... :) dan is het mss een goede keuze om de resources niet te spenderen daaraan. Dat is wat ze eigenlijk zeggen

[Reactie gewijzigd door Icekiller2k6 op 15 maart 2016 18:24]

Minder kans, niet nul kans, op een priemgetal eindigend op 1.
priemgetallen worden gebruikt in computer beveiliging. In het geval ze er achter komen dat er een duidelijk patroon in priemgetallen zit zouden bepaalde beveiligingen makkelijker te kraken zijn.
Dit is in eerste instantie natuurlijk gewoon een stukje getaltheorie; pure wetenschap dat niet direct een toepassing kent in de praktijk.

Zoals aangegeven zijn priemgetallen erg belangrijk in onze digitale wereld. RSA, een assymetrisch encryptiealgortitme, maakt gebruik van priemgetallen. RSA wordt voornamelijk gebruikt voor het tot stand brengen van beveiligde verbindingen en identificatie. RSA maakt gebruik van het feit dat er geen efficiënte methode bestaat om grote semipriemgetallen te factoriseren. Wanneer er een bepaalde systematiek van priemgetallen bekend is, zou deze factorisatie wellicht veel makkelijker plaats kunnen vinden. Overigens is de wetenschappelijke vaak zijn tijd vooruit. Doorgaans duurt het even voordat het zijn weg vindt in de natuurkunde en vervolgens engineering. Een leuk feitje is bijvoorbeeld dat aan RSA de kleine stelling van Fermat ten grondslag ligt, die dateert uit de 17de eeuw. Ruim 350 jaar oude wiskunde zorgt er dus voor dat jij veilig kan internetbankieren ;)

Overigens is het helemaal niet nieuw dat regelmatigheden gevonden worden in priemgetallen. Hierbij kan bijvoorbeeld gedacht worden aan de distributie van priemgetallen, waar verrassend accurate benaderingen voor zijn.

[Reactie gewijzigd door DEVoTi0N op 15 maart 2016 18:44]

Het is wel weer een stap opweg naar het kraken van encryptie die vaak gebaseerd is op het gebruik van een tweetal priemgetallen.
Jou dat jezelf af laten vragen tot je er gek van wordt. ;)
kun je dit niet veel beter onderzoeken in base2 in plaats van base10?
Priemgetallen zijn niet afhankelijk van welk talstelsel je gebruikt.

In binair (base2) eindigen priemgetallen (behalve de eerste) overigens altijd op een 1, want oneven.
en ik vermoed dat er een computer bij aan de pas is gekomen om dit uit te rekenen, die rekenen doorgaans in binaire
Intern wel, maar verder rekent een computer natuurlijk hoe je wil. Geloof het of niet, maar ik doe zo nu en dan ook wel eens een decimale berekening.

Bij dit soort problemen lukt het veel mensen niet om representatie los te zien van de theorie zelf. Genoeg mensen die denken dat 10 zo'n mooi getal is, omdat als je 10x10 uitrekent, daar wéér zo'n mooi rond getal uitkomt.
Intern wel, maar verder rekent een computer natuurlijk hoe je wil. Geloof het of niet, maar ik doe zo nu en dan ook wel eens een decimale berekening.

Bij dit soort problemen lukt het veel mensen niet om representatie los te zien van de theorie zelf. Genoeg mensen die denken dat 10 zo'n mooi getal is, omdat als je 10x10 uitrekent, daar wéér zo'n mooi rond getal uitkomt.
Ja maar dat is ook wel waar, 10 is altijd een mooi rond getal.
In de context van natuurlijke text bedoel ik natuurlijk 10 met decimale betekenis en niet in elk mogelijke representatie die je kunt bedenken, net zoals deze comment niet als Engels gelezen moet worden, ook al hebben Engels en Nederlands toevallig hetzelfde alfabet. :+

Dus wederom: lastig, representatie en betekenis gescheiden houden. We zouden standaard het subscript dec in moeten voeren. Neem je 8dec eieren mee van de supermarkt? Dit artikel zou er in ieder geval duidelijker van worden.

[Reactie gewijzigd door bwerg op 16 maart 2016 09:07]

In welk stelsel representeert 8stelsel een ander aantal eieren dan? :+
Elke base is base10 ;)
als je naar het eindcijfer kijkt, dan is de base wel degelijk van belang, want je bekijkt een eigenschap van de symbolische representatie van het priemgetal (dat zelf onafhankelijk is van de base). Maar door een andere representatie geeft iedere base andere resultaten.
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.
Waarom is dit pas nu ontdekt? Klinkt vrij makkelijk dit te onderzoeken toch?

[Reactie gewijzigd door pelt op 15 maart 2016 18:25]

Omdat niemand ooit eerder de moeite heeft genomen om het A te onderzoeken, of B te publiceren.

In de wetenschap wordt nooit de "waarom" vraag gesteld, omdat die "zin" impliceert. De vraag is altijd: Hoe?

[Reactie gewijzigd door LarBor op 15 maart 2016 18:35]

Op dit item kan niet meer gereageerd worden.



Nintendo Switch Google Pixel Sony PlayStation VR Samsung Galaxy S8 Apple iPhone 7 Dishonored 2 Google Android 7.x Watch_Dogs 2

© 1998 - 2016 de Persgroep Online Services B.V. Tweakers vormt samen met o.a. Autotrack en Carsom.nl de Persgroep Online Services B.V. Hosting door True