Hoppa till innehållet

196-algoritmen

Från Wikipedia
(Omdirigerad från Lychreltal)

196-algoritmen är en metod inom talteorin, som för ett givet startvärde, ett heltal, genererar en sekvens av heltal. För alla startvärden N=1…195 visar det sig att den genererade sekvensen innehåller ett palindromtal mycket tidigt. Ett av de olösta problemen inom talteorin är att bevisa (eller refutera) att 196-algoritmen aldrig ger ett palindromtal för startvärdet 196. Eftersom detta är ett relativt välkänt, och än så länge icke-löst, problem så kallas algoritmen i sig ofta för 196-algoritmen. Algoritmen används inte för att beräkna något utan utgör bara grunden till det ovan nämnda problemet.

Algoritmen är mycket enkel. Antag att startvärdet är N, detta blir då första talet i den resulterande sekvensen. Vänd nu på ordningen bland siffrorna i N för att bilda ett nytt tal, summan av detta tal och N blir sen nästa tal i sekvensen.

Exempel:

411 är inte ett palindromtal. 411+114=525 som är ett palindromtal.

För startvärdet 198 får vi alltså sekvensen 198, 1089, 10890, 20691, 40293, 79497, … där 79497 är ett palindromtal medan vi exempelvis för startvärdet 19 enbart får 19, 110, 121, ….

Att många startvärden snabbt leder till palindrom är naturligt. Varje addition av två tal där det inte uppstår någon minnessiffra ger direkt en palindrom, till exempel 71+17=88. En minnessiffra skapar en asymmetri eftersom den påverkar resultatsiffran till vänster men inte till höger, exempelvis vid addering av 7:orna i 30700+00703=31403. Dock leder det ofta till låga siffror i det nya talet som i nästa steg har chans att adderas utan minnessiffra.

Externa länkar

[redigera | redigera wikitext]