Wszyscy znamy zagadk臋 z drabink膮 liter: 呕eby przej艣膰 od KOT do WAR mo偶emy zrobi膰 na przyk艂ad tak: KOT->KAT->WAT->WAR. W ka偶dym kroku zamieniamy jedn膮 liter臋 na inn膮, zawsze tak, 偶eby uzyskane litery tworzy艂y poprawne s艂owo.
A co je偶eli s艂owa zamienimy na liczby pierwsze?
Okazuje si臋, 偶e tu te偶 s膮 takie drabinki. Na przyk艂ad 偶eby przej艣膰 z 23 do 31 mo偶emy zrobi膰 to w ten spos贸b: 23->13->11->31. Czytelnikowi pozostawiam do sprawdzenia, 偶e jest to para dwucyfrowych liczb pierwszych z najd艂u偶sz膮 minimaln膮 drabink膮 (cho膰 s膮 te偶 inne takie pary, na przyk艂ad 97->53).
Minimalna drabinka to najkr贸tsza liczba krok贸w wymaganych do przekszta艂cenia jednej liczby w drug膮 (spe艂niaj膮c zasady drabinki a wi臋c zawsze zamieniamy dok艂adnie jedn膮 cyfr臋 na inn膮, a ka偶da liczba po艣rednia musi te偶 by膰 liczb膮 pierwsz膮). Dla r贸偶nych par liczb dwucyfrowych d艂ugo艣ci tych minimalnych drabinek b臋d膮 r贸偶ne. Na przyk艂ad dla 13, 37 minimalna drabinka ma trzy elementy: 13->17->37 (s膮 te偶 ine trzyelementowe). Kr贸cej si臋 nie da. A dla 23->31 minimalna drabinka ma cztery elementy - i w艣r贸d liczb pierwszych dwucyfrowych nie da si臋 znale藕膰 pary z d艂u偶sz膮 (na przyk艂ad pi臋cioelementow膮) minimaln膮 drabink膮. Jest to wi臋c najd艂u偶sza minimalna drabinka.
Czas na zagadk臋 w艂a艣ciw膮: ile element贸w ma najd艂u偶sza minimalna drabinka dla liczb pierwszych trzycyfrowych? Prosz臋 poda膰 przyk艂adowe liczby z takiej drabinki.
Pytanie bonusowe: a dla czterocyfrowych?
Rozwi膮zanie zagadki tutaj.