Parasittallene er et kjent fenomen og de kan finnes på forskjellige måter og i forskjellige former. Når jeg har tatt med dette som en algoritmisk øvelse er det fordi det er et godt eksempel på hvordan man kan bruke papir og blyant for å finne en generell metode som kan programmeres. Der også basert på litt notstalgi fra min tid som student.
For lenge siden, tror det var 1966, lange før internettet og før datamaskiner var allment tilgjengelige fikk jeg en utfordring av en medstudent. Hun vikarierte som lærer i ungdomsskolen og hadde fått en oppgave fra en elev (jeg gjetter på at det sto en matematikkkyndig forelder bak). Utfordringen var kort og godt slik:
Finn et naturlig tall som er slik at dersom det siste sifferet flyttes foran så blir tallet dobbelt så stort
Jeg hadde bare papir og blyant tilgjengelig og kjente, så vidt jeg husker, verken begrepet parasittall eller for den saks skyld algoritme. Jeg tok utfordringen og tilbrakte mesteparten av en dag på lesesalen for finne et slikt tall, og fant omsider en metode som fungerte. Det var den første gangen jeg arbeidet systematisk og bevisst for å finne en ikke-triviell algoritme. Jeg må innrømme at i løpet av prosessen dukket det opp en mistanke om at jeg var lurt opp i noe som ikke var mulig, men det gikk bra til slutt.
Mange år senere dukket denne anstrengelsen opp i hukommelsen og jeg forsøkte å rekonstruere dagen på lesesalen for å implementere algoritmen i Python og i Javascript. Det er denne rekonstruksjonen du finner nedenfor.
Vi starter med det bakerste sifferet (det som skal flyttes til å bli det første i summen). Vi velger et 2-tall. Det betyr altså at vi vil lete mot venstre etter et 2-tall som er det dobbelte av sifferet til høyre for seg.
| Det neste blir 4 (2+2) | 42 |
| Det neste blir 8 (4+4) | 842 |
| Det neste blir 6 (8+8=16) Vi må ta med oss menta (1) | 6842 |
| Det neste blir 3 (6+6+1=13) Vi må ta med oss menta | 36842 |
| Det neste blir 7 (3+3+1)=7. Ingen mente | 736842 |
| .. | .. |
| og slik fortsetter vi inntil vi får | 2105263157894736842 |
| Resultatet | 105263157894736842 |
Altså:
105263157894736842 + 105263157894736842 --------------------- = 210526315789473684 ====================
Det et par ting å merke seg:
- Hvis du ser på resultatet så ser du at vi har et 2-tall underveis. Dette kan ikke avslutte vår leting fordi det er resultatet av en addisjon som gir mente. Konkret: 6+6=12
- Det gir ingen mening å begynne med tallet 0, siden vi aldri får noe annet enn 0 i addisjoner
- Vi kan heller ikke begynne med tallet 1 siden 1 i starten av summen må bety at vi har en menteoverføring i siste addisjon.
- Vi vil ikke finne flere løsninger som slutter på samme tall med den algoritmen vi har beskrevet. (Vi kan imidlertid, viser det seg, få lengre tall der 18-siffers sekvenser gjentar seg. Se Python-løsningen nedenfor.)
Vi har altså med håndarbeid funnet et parasittall med 18 siffere. Så er utfordringen å programmere denne strategien (algoritmen) slik at vi kan finne flere tall.
Javascript
Vi ser først på en Javascript løsning. Denne er laget ved ganske slavisk å følge resonnementet over:
// finn en løsning med et gitt siste tall
function findIt(start){
var siffere=new Array(); // tallrekka
var ferdig = false; // ferdig ?
var mente=0; // mente (0 eller 1)
siffere.push(start);
while (!ferdig){
var sisteIx=siffere.length-1; // det siste vi la til
var t=siffere[sisteIx]*2+mente; // neste tall
// vi er ferdig hvis:
// vi har flere enn to siffere og
// vi ikke har noen mente og
// det siste sifferet er det samme som vi startet med
if((sisteIx > 2) &&
(mente == 0 ) &&
(siffere[sisteIx] == siffere[0])){
ferdig=true;
}
else{ // legg til sifferet og husk mente
if(t >9){
mente=1;
siffere.push(t-10);
}
else{
mente=0
siffere.push(t);
}
}
}
siffere.pop(); // ta bort det siste vi la til
siffere.reverse(); // omvendt rekkefølge
return siffere.join("");
}
Finn tall som slutter på
Python
Pythonkoden er litt mer omfattende. Her søker vi å finne alle parasittall som er som er kortere enn et gitt antall siffer.
#----------------------
# Produce numbers that is such that
# If you move the last digits in front it doubles
#---------------------------------------------
# Observe that for n+1 digits:
#
# Dn-1 = 2*Dn % 10, M = 2 * Dn / 10
# ...
# Di = (2 * Di+1 + M) % 10, M = (2 * Di+1 + M)/10
# ...
# Dn = (2 * D0 + M) % 10, M = 0
#
# where M carries 0 or 1 to next digit addition
#-------------------------------------------------
# what we find
result=""
def CheckAndRemember(digits):
# check the aritmetic, update result
global result
a=digits[0]
for i in range(1,len(digits)):
a=a*10+digits[i]
b=digits[len(digits)-1]
for i in range(0,len(digits)-1):
b=b*10+digits[i]
if 2*a == b:
# it is ok, remember the number
result=result+str(a)+"\n"
def makeDigits(n):
# assume n digits in the soulution
for d0 in range(1,5):
# there are two possible last digits, dn
for dn in range(2*d0,2*d0+2):
D=[dn]
M=0
# calculate the others systematically right to left
for i in range(1,n):
v=2*D[0]+M
D.insert(0,v%10)
M=v/10
CheckAndRemember(D)
def find(limit):
# search for numbers smaller than limit
for i in range(0,limit):
makeDigits(i)
find(37)
# show what we found
print(result)
Hvis du (kopierer) og kjører denne koden kan du endre parameteren til find-funksjonen og du vil se at du finner ingen tall kortere enn 18 siffer og du vil se at hvis setter grensen til mer en 36 vil du se at siffersekvensene gjentar seg. F.eks slik med limit på 37:
105263157894736842 157894736842105263 210526315789473684 263157894736842105 315789473684210526 368421052631578947 421052631578947368 473684210526315789 105263157894736842105263157894736842 157894736842105263157894736842105263 210526315789473684210526315789473684 263157894736842105263157894736842105 315789473684210526315789473684210526 368421052631578947368421052631578947 421052631578947368421052631578947368 473684210526315789473684210526315789
Kanskje ikke så rart siden det første sifferet i en 18-sekvens ikke genererer noen mente.
Du vil finne stoff om parasittall på nettet og du vil se andre og smartere måter å beregne dem på. (parasitic numbers)