Optimering af kode

Den kan du nemt gøre hurtigere du skal bruge en metode der hedder erastotenes si (jeg garanterer ikke for stavemåden)

Hvis du vil finde alle primtal imellem 1 og 100 gør du følgende.

lav et array med 100 pladser (gerne bits) sæt dem alle til 1.

Start med 2, er plads 2=1 ja det er den, godt, fjern nu alle multiplummer af 2 op til , altså nulstil plads 4,6,8,10....
Kig på næste plads altså nummer 3 er den =1 yep, fjern så alle multiplummer af 3, altså 6,9,12,15....
Er plads 4=1 nej den fjernede vi jo ved multiplum af 2. så kig på plads nummer 5, fjern så alle multiplummer af 5, altså 10,15,20,25....
dette gør du så indtil du har gjort det op til kvadratroden af antal elementer altså op til talle 10.

Alle pladser i dette array der er =1 er primtal.

Kan optimeres hvis at springe alle lige tal over.

Ulempe du skal starte ved 1 og opefter

Det må jeg lige lege lidt med. Har du evt. noget dokumentation på det? En anden begrænsning der er, er at det ikke må brugere mere dn 16Mb hukommelse. Så hvis jeg skal have et array med 100000000 elementer, som hver kan indeholde meget store tal, bliver det så ikke problematisk?

en bit er nok per tal, men det fylder.

et eksempel
http://www.math.niu.edu/~rusin/known-math/95/sieve
Hvordan du kan memory optimere den kan jeg ikke lige svare på

Nej, det skal jo ikke indeholde tallene!
Du kan nøjes med én bit per tal, indexet til den enkelte bit er så selve tallet.

Så med 16 MB plads kan du klare op til 16*1024*1024*8 og hvis du er smart ved du alle lige tal ikke er primtal, så gange du lige antallet med 2 igen :)

Oki, det lyder alt fint, jeg kigger på det. Jeg accepterer lige når jeg har afprøvet det.

Det er bare fint :)

Hvis jeg erklærer et array bool[100000000], så tager den 98Mb hukommelse. Er der en anden variabel jeg burde bruge?

Nu har jeg næsten fået det til at køre, har dog lige en sidste flaskehals.

For at tjekke for om tallene er palindromer, så skal jeg have det over i en char[9], hvor jeg tjekker fra begge ender indtil et tal ikke passer sammen.

Problemet er konverteringen. Da det skal være Gnu++ kompatibelt, så er itoa ikke en mulighed. sprintf er alt for langsom her, jeg har testet at det er flaskehalsen. Så hvad har jeg af muligheder? (fart er altbetydende).

Jeg har også lige forsøgt med med en stringstream:

    ostringstream strStream;

    for (i=intLowRange; i<=intHighRange; i+=2)
    {
          ... kode ...
      //strStream << i;
      //strTest=strStream.str();
      //intLength=strTest.length();
          ... kode ...

Men det er også for langsomt, igen opstår flaskehalsen her, helt specifikt opstår den ved linien:
  strStream << i;

Nogen forslag?

Selvom en bool kun kan havde 2 værdier, er den alligevel 1 byte stor i hukommelsen.

Hvordan du laver udskrivningen til GUI kan jeg ikke svare på, jeg har faktisk aldrig programmet C++ til Linux.

disky >> en bool er ikke nødvendigvis 1 byte stor, det afhænger af flere ting...
Fx var en bool i tidligere versioner af VC++ samme størrelse som en int.

disky -> Jeg udskriver ikke noget til GUI, jeg udskriver til en fil, så jeg har stadig brug for at konvertere en integer til en char.

Hukommelsesforbruget har jeg fået ned, jeg mangler altså bare at konvertere mine tal til chars i ekstrem hastighed. Jeg bruger VS.NET.

Da det tidligere var ret normalt med typedef int BOOL, så tror
jeg at der er mange bool der er 4 byte.

Bit arrays er ikke særligt almindelige i programmerings sprog.

Pascal packed array of boolean plejer dog at blive til et
bit array.

Så orca du bliver nødt til selv at pakke og udpakke bits.

orca>

Jeg tror at du skal undgå at konvertere direkte til ascii text, men
nøjes med at konvertere til decimale cifre.

Altså:

int prime;
char dig[9];
int tmp = prime;
for(int i=0;i<9;i++) {
  dig[8-i]=tmp%10;
  tmp=tmp/10;
}

og så sammenligne:
dig[0] - dig[8]
dig[1] - dig[7]
dig[2] - dig[6]
dig[3] - dig[5]

Det er iøvrigt muligt at:

int prime;
char dig[9];
int tmp = prime;
int oldtmp;
for(int i=0;i<9;i++) {
  oldtmp=tmp;
  tmp=tmp/10;
  dig[8-i]=oldtmp-10*tmp;
}

er hurtigere.

Det allerhurtigste ville være hvis x86 instruktions-sættet havde
en instruktion som lavede både mod og div i en enkelt instruktion
og vi kunne kalde den med asm.

En lille tilføjelse til diskys oprindelige svar omkring Erathostenes sigte (jeg garanterer HELLER ikke for stavningen...)

Det er rigtigt, at man kun behøver at fjerne multipla af allerede fundne primtal op til kvadratroden af maksimum, i eksemplet 10. Men man behøver rent faktisk ikke at fjerne multipla af et primtal "helt nedefra", man kan nøjes med at starte med kvadratet af primtallet. Når man i diskys eksempel når til primtallet 5, er det altså ikke nødvendigt at fjerne 10, 15 og 20 (de er nemlig allerede fjernet!) man skal bare starte med 25, 30, osv...

Jeg har ikke lige nogle forslag til konverteringen til decimal... Må jeg spørge, HVAD skal du bruge dette her til, og hvorfor skal det absolut køre under 5 sekunder? Løsningen ændrer sig jo ikke fra gang til gang, så det skulle jo være nok at køre bare en enkelt gang, og hvad betyder så nogle sekunder fra eller til? ;-)

orca>

Du behøver jo iøvrigt kun checke halvdelen af de fundne primtal.

Da primtal der starter med et lige tal ikke kan være et palindrom.

Jeg kan iøvrigt se, at dine tal kun er 8 lange, så du skal selvfølgelig
kun loope til 8 i mit lille stykke kode ovenfor.

Og vis 119 ikke skal opfattes som 00000119, så skal du selvfølgelig stoppe
når tmp er nul.

Altså:

int ispalindrome(int prime)
{
char dig[8];
int tmp = prime;
for(int i=0;i<8;i++) {
  dig[7-i]=tmp%10;
  tmp=tmp/10;
  if(tmp==0) {
    for(int j=0;j<=i/2;j++) {
        if(dig[j]!= dig[i-j]) return 0
    }
    return 1;
  }
}

Og så kalde den funktion for 1,3,7,9,10-19,30-39,70-79,90-99,... !

[advarsel: kode ikke testet]

Jeg prøvede lige at teste og selvfølgelig var der fejl.

Men følgende ser ud til at virke:

int ispalindrome(int prime)
{
  char dig[8];
  int tmp = prime;
  for(int i=0;i<8;i++) {
      dig[i]=tmp%10;
      tmp=tmp/10;
      if(tmp==0) {
        switch(i+1) {
            case 1:
              return 1;
            case 2:
              return (dig[0]==dig[1]);
            case 3:
              return (dig[0]==dig[2]);
            case 4:
              return (dig[0]==dig[3] && dig[1]==dig[2]);
            case 5:
              return (dig[0]==dig[4] && dig[1]==dig[3]);
            case 6:
              return (dig[0]==dig[5] && dig[1]==dig[4] && dig[2]==dig[3]);
            case 7:
              return (dig[0]==dig[6] && dig[1]==dig[5] && dig[2]==dig[4]);
            case 8:
              return (dig[0]==dig[7] && dig[1]==dig[6] && dig[2]==dig[5] && dig[3]==dig[4]);
        }
      }
  }
}

Hmm, det er jo meget godt med disse løsninger, men kan vi ikke
reducere problemet med 99,995% sådan uden videre.

fx. ved tal 100000X, X er 0-9 er der jo kun 1 der dur, nemlig 1,
lige så med de øvrige tal på første position, hermed er talmængden
reduceret 90%, ligeledes med cifre nr. 2 og 7, 3 og 6 samt 4 og 5,
hermed reduceret til 99,99% og vi behøver ikke teste lige tal så
vi kan reducere med 50% igen, for en samlet reduktion på 99,995%

Palindrom ligger meget op til en rekursiv løsning...

segmose>

Skriver du ikke lige koden ?

Jeg synes nemlig ikke din logik er lige nem at følge !

Udgangspunkt er at du har Z prim-tal mellem 5 og 100000000
som binære 32 bit ints og du skal finde dem der er palindromer.

Et eller andet ovenfor må betragtes som et svar.

arne_v skriver: Udgangspunkt er at du har Z prim-tal mellem 5 og 100000000

Det kan jeg ikke se af orca's program, der jo netop finder primtal og
derefter undersøger om de er palindromer.

pseudo kode:
char dig[8];  // egentlig byte
memset(dig, 0, sizeof(dig));

int JegErEtPalindrom(char *dig, int len) {
  if (!len) {
    CheckPrimtal(dig); // hele dig skal være prim
    gør hvad man nu skal bruge det til hvis prim
    return noget
  }

  for (int i = 0; i <= 9; ++i) {
    dig[0] = i;
    dig[len-1] = i;
    JegErEtPalindrom(&dig[1], len-2);
  }
  return noget;
}

ok?

segmose>

1)  Primtallene er allerede fundet med Sieve of E.

2)  Din funktion erstatter jo kun switch statementen
    i min kode og jeg kan ikke tro at en løkke og et
    rekursivt kald er hurtigere end 1 jump og 1-4 int comparisons.

Jeg accepterer. Løsningen som arne_v er kommet med er dog heller ikke hurtig nok. Såvidt jeg ved er division af integers noget af det langsomte integer behandling man kan komme i nærheden af. Så jeg må nok lige kigge lidt mere på hvordan jeg kan tjekke for palindromer. Tak for alle forslagene indtil videre.

Integer division er langsomt, men det er vist nødvendigt når man skal konvertere
fra binært til decimalt.

Men jeg har en alternativt ide.

Hvor svært vil det være at lave et program som genererer alle
palindromer i intervallet ?

Altså have et bit array hvor du med Sieve of E finder alle
primtal og et andet bit array hvor du genererer alle palindromer.

Så skal du bare finde alle tal hvor begge bits er sat.

Og palindromer må kunne genereres kun med multiplikation og addition.

for(int i=0;i<10;i++) {
  // 1 digit
  pal[i] = 1;
  // 2 digit
  pal[i*10+i] = 1;
  for(int j=0;j<10;j++) {
      // 3 digit
      pal[i*100+j*10+i]=1;
      // 4 digit
      pal[i*1000+j*100+j*10+i] = 1;
      for(int k=0;k<10;k++) {
          // 5 digit
          pal[i*10000+j*1000+k*100+j*10+i] = 1;
          // 6 digit
          pal[i*100000+j*10000+k*1000+k*100+j*10+i] = 1;
          for(int l=0;l<10;l++) {
              // 7 digit
              pal[i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i] = 1;
              // 8 digit
              pal[i*10000000+j*1000000+k*100000+l*10000+l*1000+k*100+j*10+i] = 1;
          }
  }
}

[check lige for typos - det er bare tastet ind]

Jeg testede lige og det ser meget lovende ud.

Men et char array tager det <1 sekund.

Med lidt held kan du også gøre det hurtigt med et bit array.

Test kode:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>


int main()
{
time_t t1 = time(NULL);
char *pal = (char *)malloc(100000000);
memset(pal,0,sizeof(pal));
for(int i=0;i<10;i++) {
  // 1 digit
  pal[i] = 1;
  // 2 digit
  pal[i*10+i] = 1;
  for(int j=0;j<10;j++) {
      // 3 digit
      pal[i*100+j*10+i]=1;
      // 4 digit
      pal[i*1000+j*100+j*10+i] = 1;
      for(int k=0;k<10;k++) {
          // 5 digit
          pal[i*10000+j*1000+k*100+j*10+i] = 1;
          // 6 digit
          pal[i*100000+j*10000+k*1000+k*100+j*10+i] = 1;
          for(int l=0;l<10;l++) {
              // 7 digit
              pal[i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i] = 1;
              // 8 digit
              pal[i*10000000+j*1000000+k*100000+l*10000+l*1000+k*100+j*10+i] = 1;
          }
      }
  }
}
time_t t2 = time(NULL);
for(int i=0;i<250;i++) {
printf("%d %d\n",i,pal[i]);
}
printf("sec = %d\n",t2-t1);
}

erstat lige:
memset(pal,0,sizeof(pal));
med:
memset(pal,0,100000000);
hvis nogen vil køre det !

Det var løsningen arne_v! Nu klarer den det på ca. et halvt sekund på min maskine. Jeg vil gerne give dig +50 point hvis du vil have dem? :) Jeg har lige et andet problem. Programmet skal køre på en linux maskine, kompileret med Gnu++ compileren. Jeg får beskeden at programmet er quittet med besked #6 - abort med det samme. Hvad kan det være? Jeg har ikke selv forstand på linux.

Point modtages altid med taknemmelighed.

Jeg er ikke skrap til Linux.

Har du brugt arrays eller malloc/new ?

Jeg har ofte haft problemer med at lave et meget stort array
i GCC mens jeg sagtens kan malloc/new den samme mængde memory !

Æh, tror jeg ved det nu. Der er som sagt 16Mb hukommelsesgrænse. Min kode er her: http://nopaste.php-q.net/5336. Hvis jeg fjerner alt efter linie 47, så er forbruget på omkring en halv mb. Hvis jeg lader palindromfindingsalgoritmen stå, så kommer den op omkring 43Mb. Og de sidste tre linier (79-81) får hukommelsesforbruget op på omkring 196(!!!)Mb... Hmmm... bummer.

http://www.eksperten.dk/spm/317166 <-- arne_v

Prøv lige og lav pal om til en bool * og brug new ligesom med arrPrimes.

Hmm - det er nok ikke helt nok.

2*100M*1 bit = 2*12.5 MB = 25 MB

Hvis du skal under 16 MB skal du have smidt alle de "uinteressante"
lige tal ud af arrayet.

Så bør programmet kunne være i 16 MB.

Men det vil kræve lidt ekstra kode.

http://nopaste.php-q.net/5338 100% samme resultat. Jeg forstår det ikke rigtig. Første bool[megetstorttal] fylder <1Mb, næste fylder 40Mb. Og til sidst kommer jeg op på næsten 200Mb når jeg vil udskrive resultatet, hvilket jeg _slet_ ikke kan forstå?

Jeg har lige fået mine arrays ned på det halve (100000000), men den bruger stadig 98Mb :(... Jeg må lige lede lidt videre efter besparelser.

Argh, har lige fundet ud af en bug i min primtals algoritme, så mange tal der ikke var primtal blev behandlet som primtal :/. Efter at have rettet den er performance igen for lav.

Min primtalsalgoritme ser således ud:

    while (intCount<intCut)
    {
        intTest=intCount*intCount;
        while (intTest<=intHighRange)
        {
            arrPrimes[intTest]=true;
            intTest+=intCount*2;
        }
        intCount+=2;
        for (intCount=intCount; intCount<intCut; intCount+=2)
            if (!arrPrimes[intCount])
                break;
    }

Et åbenlyst problem som md7jt også pointerer, er at 3 f.eks fjerner tallene 9, 15, 21, 27, 33, 39 osv, mens at tallet 11 også fjerne tallet 33 f.eks. Sådan går det igen mange gange, og en masse tal som allerede er udelukket bliver kørt igennem igen. Jeg kan dog ikke lige se hvordan jeg kan undgå det...

Selve genereringen af *pal tager ingen tid, ligeledes tager testen af arrPrimes&&pal heller ingen tid. Altså er det ovenstående algoritme som humlen skal findes i. Først og fremmest vil jeg have performance i orden, så må jeg fikse hukommelsesproblemet bagefter.

Igen, hvis i har forslag så er i velkomne :)


Ps. md7jt, det er en opgave jeg er blevet stillet, og kravene er at den skal kunne generere alle primtalspalindromer mellem 5 og 100 mill på under 5 sekunder, og hukommelsesforbruget må ikke overstige 16mb.

Ok, E's sieve skal bruge 12,5 MB hvis der bruges 1 bit/tal
og der er ca. 20000 palindromer, (pseudo bevis se min eller
arne_v's kode, 4 loops med hver 10 gennemløb med 2 tal i hver).

1. optimering, hvorfor vil du lave et nyt array til palindromerne?
du kan lige så godt lave checket omgående hvor du genere palindromerne.

2. Du er kan skære de lige palindromer fra i koden, hvilket efterlader
ca. 10000.

3. lav primtals check på dem.

4. man kan forsøge at undgå E's sieve men det bliver lidt snævert med tid :)
Der er mindre end 2000 primtal under 10000.
så man skal lave mindre end 10000(palindromer)*2000(primtal<10000) divisioner
for at checke dette (efter at man har lavet de første primtal) 200.000.000
divs a ca. 40 cycles = 8.000.000.000 cycles du har 800MHz *5 = 4.000.000.000

orca, din algoritme tager så vidt jeg kan se også højde for den detalje, jeg havde pointeret:
intTest=intCount*intCount;
Her sikrer du dig jo netop, at du først starter ved 121, når du når frem til primtallet 11.

Men du kan følge det råd, som disky gav tidligere: Lad dit array repræsentere alle ULIGE tal. Dermed halverer du memoryforbruget (hvilket dog ikke er nok...), og du kan fjerne en *2 i din primtalsløkke. Koden bliver alt andet lige lidt vanskeligere at skrive, men det er nu ikke så slemt.

segmose har ret.

Hvis du erstatter pal[index]=1 med et om primarr[index] også er sat
og agerer på det, så behøver du slet ikke noget pal array.

segmose/arne_v -> Grunden til pal arrayet er også at jeg så får et sorteret output (krævet). Ellers skal jeg bruge kræfter på at sortere mit output bagefter, og det tror jeg bliver for langsomt.

Jeg har fået mit primtalsarray ned på størrelsen 50000001, ved at skære de lige tal fra, det hjælper på hukommelsesforbruget (49mb), så jeg må lige se om ikke også jeg kan gøre det samme med pal arrayet.

Jeg kan ikke se nogen grund til at lave primtalscheck på mit pal array mens jeg gemmer værdierne, for da jeg vil have sorteret output, så kan jeg ligeså godt gøre det hele til sidst.

Jeg har lige eksperimenteret lidt.

Og de 2 hurtigste varianter jeg har kunnet komme op med er:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

int main()
{
  time_t t1 = time(NULL);
  char *prime = (char *)malloc(100000000/2);
  memset(prime,1,100000000/2);
  for(int i=3;i<=10000; i+=2) {
      if(prime[i/2]) {
        for(int j=i*i;j<100000000;j+=2*i) {
            prime[j/2]=0;
        }
      }
  }
  time_t t2 = time(NULL);
  int nprime = 0;
  for(int i=0;i<100000000/2;i++) {
    if(prime[i]) nprime++;
  }
  printf("%d\n",5761457);
  printf("%d\n",nprime);
  printf("sec = %d\n",t2-t1);
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

int main()
{
  time_t t1 = time(NULL);
  char *prime = (char *)malloc(100000000+30*10000);
  memset(prime,1,100000000);
  for(int j=4;j<100000000;j+=2) {
      prime[j] = 0;
  }
  for(int j=9;j<100000000;j+=6) {
      prime[j]=0;
  }
  prime[25]=0;
  for(int j=30;j<100000000;j+=30) {
      prime[j+5]=0;
      prime[j+25]=0;
  }
  for(int i=7;i<=10000; i++) {
      if(prime[i]) {
        prime[7*i]=0;
        prime[11*i]=0;
        prime[13*i]=0;
        prime[17*i]=0;
        prime[19*i]=0;
        prime[23*i]=0;
        prime[29*i]=0;
        for(int j=30*i;j<100000000;j+=30*i) {
            prime[j+i]=0;
            prime[j+7*i]=0;
            prime[j+11*i]=0;
            prime[j+13*i]=0;
            prime[j+17*i]=0;
            prime[j+19*i]=0;
            prime[j+23*i]=0;
            prime[j+29*i]=0;
        }
      }
  }
  time_t t2 = time(NULL);
  int nprime = 0;
  for(int i=0;i<100000000;i++) {
    if(prime[i]) nprime++;
  }
  printf("%d\n",5761457);
  printf("%d\n",nprime);
  printf("sec = %d\n",t2-t1);
}

Men de er stadig ikke god enok.

Men så arbejdede jeg lidt videre på segmoses ide.

Og det ser endda meget lovende ud !

Og sortering tager ikke lang tid.

Prøv med følgende:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

int nprim10000;
int prim10000[4000];
int nprimpal;
int primpal[10000];

void genprim()
{
  char *temp = (char *)malloc(10000);
  memset(temp,1,10000);
  for(int i=2;i<=100;i++) {
      if(temp[i]) {
        for(int j=2*i;j<10000;j+=i) {
            temp[j]=0;
        }
      }
  }
  nprim10000=0;
  for(int j=2;j<10000;j++) {
      if(temp[j]) {
          prim10000[nprim10000]=j;
          nprim10000++;
      }
  }
  return;
}

void check(int v)
{
  if(v<2) return;
  int ix = 0;
  while((prim10000[ix]*prim10000[ix])<=v) {
      if((v % prim10000[ix])==0) return;
      ix++;
  }
  primpal[nprimpal]=v;
  nprimpal++;
  return;
}

void qsint_help(int n1,int n2,int *ia)
{
  int tmp;
  int l=n1;
  int r=n2;
  int pivot=ia[(n1+n2)/2];
  do {
      while(ia[l]<pivot) l++;
      while(ia[r]>pivot) r--;
      if(l<=r) {
        tmp=ia[l];
        ia[l]=ia[r];
        ia[r]=tmp;
        l++;
        r--;
      }
  } while(l<=r);
  if(n1<r) qsint_help(n1,r,ia);
  if(l<n2) qsint_help(l,n2,ia);
  return;
}

void qsint(int n,int *ia) {
  qsint_help(0,n-1,ia);
  return;
}

void sort()
{
  qsint(nprimpal,primpal);
  return;
}

void genpal()
{
  primpal[0]=2;
  nprimpal=1;
  for(int i=1;i<10;i++) {
      if((i==1) || (i==3) || (i==5) || (i==7) || (i==9)) {
        // 1 digit
        check(i);
        // 2 digit
        check(i*10+i);
        for(int j=0;j<10;j++) {
            // 3 digit
            check(i*100+j*10+i);
            // 4 digit
            check(i*1000+j*100+j*10+i);
            for(int k=0;k<10;k++) {
              // 5 digit
              check(i*10000+j*1000+k*100+j*10+i);
              // 6 digit
              check(i*100000+j*10000+k*1000+k*100+j*10+i);
              for(int l=0;l<10;l++) {
                  // 7 digit
                  check(i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i);
                  // 8 digit
                  check(i*10000000+j*1000000+k*100000+l*10000+l*1000+k*100+j*10+i);
              }
            }
        }
      }
  }
  return;
}


int main()
{
  // start timer
  time_t t1 = time(NULL);
  // generate all primes up to 10000
  genprim();
  // generate all palindromes and check for prime
  genpal();
  // sort palindrome primes
  sort();
  // stop timer
  time_t t2 = time(NULL);
  // print
  printf("sec = %d\n",t2-t1);
  //for(int i=0;i<nprimpal;i++) printf("%d\n",primpal[i]);
  printf("found = %d\n",nprimpal);
}

Under 1 sekund på en 750 MHz compilet med GCC 3.1 !

found = 781
Det var ikke mange, og der er ikke noget 8 cifrede, underligt da de
ellers skulle være de fleste.

Antal '%' udført
checks = 324078
Forbavsende lille tal, det må være fordi de fleste tal falder fra
tidligt.

palins = 11109
Nogenlunde det forudsagte antal.

Der er heller ingen 4 eller 6 cifrede. Enten så er der en eller anden
matematisk sammenhæng eller så er der fejl i min kode !

Hele hemmeligheden i det stykek kode er at få så mange tal som muligt smidt
væk så hurtigt som muligt..

Ja, der er en matematisk sammenhæng: Palindromer med et lige antal cifre kan altid divideres med 11. Man kan let overbevise sig om, at palindromer med et lige antal cifre kan opløses i summer af følgende led: 11, 1001, 100001,... altså med et lige antal 0'er i "midten". F.eks. er 36577563 = 3*10000001+60*100001+500*1001+7000*11. Derefter skal vi bare "bevise", at 11 går op i 10..01, og det er også let at "se": Beregn differencen mellem 1001 (med n nuller) og 11 (med n-2 nuller), den er 990 (altså 99 med ned n-1 nuller), det vil gælde for hele rækken. 11 går selvfølgelig op i 11 og også op i 990, 99000, osv. altså går 11 op i hele rækken, og dermed også i alle palindromer med et lige antal cifre. (Kan naturligvis formuleres pænt som et rigtigt induktionsbevis).

Tak for forklaringen.

Så kunne man faktisk speede algoritmen yderligere op ved at skippe
4, 6 og 8 cifrede tal (ikke 2 da 11 selv lige skal med).