Enkel priemgetallen in priem

Opgave - reeks 1 2015 dag 1 vraag 2

Wat is het grootste natuurlijke getal zodat elke opeenvolging van cijfers die in dat getal
voorkomt, een priemgetal vormt? (Bv. 23 voldoet aan de voorwaarde, want 2, 3 en 23
zijn priem. Het getal 253 voldoet niet, want 25 is niet priem.)

Oplossing

We kunnen opbouwend te werk gaan. We starten van alle mogelijkheden die bestaan uit één cijfer. We gebruiken die cijfers als bouwstenen om nieuwe getallen te maken en eisen dat die getallen voldoen aan de gevraagde eigenschap. Die getallen (van twee cijfers) kunnen we gebruiken, samen met de priemgetallen van 1 cijfer, om getallen van drie cijfers te construeren die voldoen enzoverder.

GETALLEN VAN 1 CIJFER
Priemgetallen die bestaan uit één cijfer zijn: 2, 3, 5 en 7. Dit zijn dus tevens alle getallen van 1 cijfer die voldoen aan de eigenschap. Steek deze in de verzameling A = {2,3,5,7}.

GETALLEN VAN 2 CIJFERS
We maken een getal van twee cijfers dat voldoet, noteer dit als ab met a en b cijfers. Dan geldt dus a, b in A.

De eigenschap vereist dat ab priem moet zijn. Dit betekent dat 2 en 5 nooit het laatste cijfer mogen zijn (b in {3,7}). Verder is duidelijk dat de cijfers met zichzelf geen priemgetal vormen (aa is niet priem), dit is namelijk deelbaar door 11. De resterende opties (zeer beperkt ondertussen) kunnen we expliciet checken.

  • 23: priem, dus oké!
  • 27: deelbaar door drie, niet oké.
  • 37: priem, dus oké!
  • 53: priem, dus oké!
  • 57: deelbaar door drie, niet oké.
  • 73: priem, dus oké!

Alle getallen van twee cijfers die voldoen aan de eigenschap zijn dus 23, 37, 53 en 73.
Steek deze in een verzameling B = {23,37,53,73}.

GETALLEN VAN 3 CIJFERS
Noteer dit getal als abc met a, b en c cijfers. Dan moet gelden: a,b,c in A en ab, bc in B.
Hierdoor ligt er een beperking op het cijfer b (het moet het begincijfer van een getal in B én eindcijfer van een ander getal in B zijn). Er zijn maar vier mogelijkheden daarvoor:

  • 237: dit is deelbaar door 3, niet oké.
  • 537: dit is deelbaar door 3, niet oké.
  • 373: priem, oké!
  • 737: dit is deelbaar door 11, niet oké.

Enkel 373 blijft overeind, in een verzameling C = {373}.

GETALLEN VAN 4 CIJFERS EN MEER
Noteer dit getal als abcd met a, b, c en d cijfers. Dan moet gelden a, b, c, d in A maar ook ab, bc, cd in B en abc, bcd in C. Maar dan moet abc = bcd = 373 zijn, want dit is het enige getal in C. Dit is niet mogelijk (bc kan niet tegelijk 73 en 37 zijn), dus een getal van vier cijfers dat aan de eigenschap voldoet, bestaat niet en bijgevolg ook geen getal met meer cijfers.

ANTWOORD
Bijgevolg moeten we kijken naar het grootste getal van 3 cijfers dat voldoet en dat is 373 (tevens het enige getal van 3 cijfers).