i i “1483-Juvan-Pozabljena” — 2010/8/25 — 9:30 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 29 (2001/2002) Številka 5 Strani 290–291 Martin Juvan: POZABLJENA NALOGA Ključne besede: računalništvo, praštevila, odmetavanje števk. Elektronska verzija: http://www.presek.si/29/1483-Juvan.pdf c© 2002 Društvo matematikov, fizikov in astronomov Slovenije c© 2010 DMFA – založništvo Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovo- ljeno. Računalništvo - Naloge I POZABLJENA NALOGA Večji del januarja in v začetku februarja imam o na uni verzi zimske počit­ nice. To sicer ne pomeni , da počivamo, ni pa predavanj in vaj za št udente, še vedno pa moramo poskrbeti za kolokvije in izpite, govorilne ure ipd. No, to zimo sem si vzel nekaj časa in pregledal enega od kupov, kam or odlagam zadeve, ki se mi sicer zdijo zanimive, a ne zahtevajo takojšnje obravnave . Tako sem naletel tudi na kopijo naslednjega e-pisma, ki mi ga je že jeseni let a 1995 iz Amerike pos lal kolega Ma rko Petkovšek. Takole prav i: Za Presek pa tale naloga: Se spomniš tiste z S-mestnimi praštevili, kjer odmetavaš cifre in imaš ves čas sama praštevila? No, če ne zahtevaš, da so vse cifre različne, lahko dobiš precej daljše prim er(k )e. Vprašanje je, kolikšno j e maksimalno število cifer? (Domnevam, da ne moreš imeti polj ubno dolgih rešitev, čeprav tega ne znam dokazati .) Z Mm a sem ugotovil, da je največja dolžina S, če odmetavaš cifre le na koncu; 23, če jih odmetavaš le na začetku . Ko sem dovolil odmetavanje na obeh koncih, sem (prek noči) dobil primer dolžine 30. Ko pa sem pognal iskanje v globino na celotnem drevesu in pustil teči prek noči, se j e Macintosh sesul. Mm a je seveda zelo počasna, po drugi strani pa bi bilo treba v C-j u ali pascalu napisati dolgo aritmetiko in testiranje praštevil. Kaj praviš na to? Nekaj časa sem potreboval , da sem razvozlal , katera naloga je "t ista z S-mestnimi praštevili" . Gre za Uga nko gospoda Kukrike v reviji Monito r, in sicer iz oktobrske številke letnika 1994. V pismu je uporabljena tudi kratica Mma, ki označuje programski paket Mathernatica. To je zmogljiv program, ki med drugim omogoča udobno računanje z velikimi števili. V pismu so torej omenjene t ri vrste prašt evil: taka, pri katerih lahko s konca po vrsti odmetavamo števke, doblj ena števila pa so vseskozi pr aštevila (npr. 7333, sa j so števila 7333, 733, 73 in 3 praštevila) , taka , pri katerih odmetavamo števke na začetku (npr. 2137, ker so 2137, 137, 37 in 7 praš tevila), in taka, pri katerih na posameznem koraku dovolim o odstranitev števke na začetku ali na koncu (npr. 7229, saj so 7229, 229, 29 in 2 praštevila). Seveda nas zanimajo čim daljša pr aštevila z omenjenimi lastnostmi. Ne spomnim se, kaj sem odgovoril na pismo, očitno pa sem kasneje na nalogo pozabil. Leta so minila, zamenjalo se je kar nekaj generacij procesorjev, pa nekaj različic Oken in tudi Mathematica je doživela nekaj poso dobitev. Računalniki so tako postali pr ecej zmoglivejš i in iskanj e odgovora na vpra šanje iz pisma danes ne bi smelo več biti pretežko. Z nekaj sreEe bom uspel nagmriti Marka, da ZB nasldujo 6tmQko P& nap* odgwor in krath razlago trditev iz pisma. Vam pa m d a ni treba Wati do wlednje &e6h. & a radwedni in mdi prenretavate Wevila, la$ko pusbite poiskati odgmre tudi s d . Martan Jawan