staging.inyokaproject.org

Und hier noch mal ne verbesserte C++ Variante...ebenfalls mit 20 Iterationen.
Wenn man sich aber nen eigenen Datentyp für Zahlen bastelt, dann ist auch noch mehr drin. 😉

#include <iostream>
#include <sstream>
using namespace std;

unsigned long long int revers(unsigned long long int zahl);
bool is_palin(unsigned long long int zahl);

int main(int argc, char** argv) {

	unsigned long long int zahl;

	for (int i = 1; i <= 100000; i++) {
		zahl = i;

		for (int j = 1; j <= 20; j++) {
			zahl += revers(zahl);
			if (is_palin(zahl)) {
				break;
			}

			if (j == 20) {
				cout << i << " könnte eine Lychrel-Zahl sein\n";
			}
		}
	}

	return EXIT_SUCCESS;
}

unsigned long long int revers(unsigned long long int zahl) {
	stringstream buf;
	
	while (zahl != 0) {
		buf << zahl % 10;
		zahl /= 10;
	}

	buf >> zahl;

	return zahl;
}

bool is_palin(unsigned long long int zahl) {
	if (zahl == revers(zahl)) {
		return true;
	} else {
		return false;
	}
} 

...
99979 könnte eine Lychrel-Zahl sein
99990 könnte eine Lychrel-Zahl sein
99999 könnte eine Lychrel-Zahl sein

real    0m2.887s
user    0m2.076s
sys     0m0.032s

Und eine C-Lösung. Ist nicht besonders hübsch, da auf Geschwindigkeit getrimmt: Test der Zahlen 1 bis 10000 dauert auf dem C64 damit nur 14 Minuten. ☺

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

#define FROM        1
#define TO          100000
#define TO_DIGITS   10
#define ITERATIONS  100
#define MAX_DIGITS  (TO_DIGITS + ITERATIONS)

static unsigned int n_length, length;
static char n[TO_DIGITS], a[MAX_DIGITS], b[MAX_DIGITS];

static void reverse_add(void)
{
    unsigned int i, carry, tmp;
    
    for (i = 0, carry = 0; i < length; i++) {
        tmp = a[i] + a[length - 1 - i] + carry;
        if (tmp >= 10) {
            tmp = tmp - 10;
            carry = 1;
        } else {
            carry = 0;
        }
        b[i] = tmp;
    }
    if (carry) {
        b[i] = carry;
        length++;
    }
}

static int is_palindrome(void)
{
    char *x, *y;
    
    x = b;
    y = b + length - 1;
    while (x < y) {
        if (*x++ != *y--) return 0;
    }
    return 1;
}

static int is_lychrel()
{
    unsigned int i;
    
    memcpy(a, n, n_length);
    length = n_length;
    for (i = 0; i < ITERATIONS; i++) {
        reverse_add();
        if (is_palindrome()) return 0;
        memcpy(a, b, length);
    }
    return 1;
}

static void print_n(void)
{
    int i;
    for (i = n_length - 1; i >= 0; i--) {
        printf("%c", n[i] + '0');
    }
    printf("\n");
}

static void increase_n(void)
{
    char *x = n;
    
    while ((*x)++ == 9) {
        *x++ = 0;
    }
    if (x - n == n_length) n_length++;
}

int main(void)
{
    unsigned int i;
    
    n_length = sprintf(a, "%d", FROM);
    for (i = 0; i < n_length; i++) {
        n[i] = a[n_length - 1 - i] - '0';
    }

    for (i = FROM; i <= TO; i ++) {
        if (is_lychrel()) {
            print_n();
        }
        increase_n();
    }
    return 0;
} 

real    0m0.386s
user    0m0.384s
sys     0m0.000s

wahahahaha.....
ich hab das ganze ma in ruby gemacht (orientiert an der c++ lösung von BlackJack)

def reverse(zahl)
  zahl.to_s.reverse.to_i
end

def is_palin zahl
  zahl == zahl.to_s.reverse.to_i
end

1.upto(100000) { |i|
  zahl = i
  1.upto(20) { |j|
    zahl += reverse(zahl)
    break if is_palin(zahl)
    #endzahl << i
    print i, " könnte eine Lychrel-Zahl sein\n" if j = 20
  }
} 

ich hab auch ma weiter versucht es ruby-like zu machen mit:

class Integer
  def palin?
    self == self.to_s.reverse.to_i
  end

  def reverse
    self.to_s.reverse.to_i
  end
end

aber das war langsamer...

naja...deshalb hab auch ma das ganze bissel weiter getestet, hier meine ergebnisse:
(1. C++ Variante, 2. ruby1.9, 3. ruby1.8 )

$ time ./clychrel >/dev/null
real 0m3.733s
user 0m3.472s
sys 0m0.012s

$ time ruby1.9 lychrel > /dev/null
real 0m3.331s
user 0m2.148s
sys 0m0.040s

$ time ruby1.8 lychrel > /dev/null
real 0m5.123s
user 0m4.412s
sys 0m0.200s

yeha! 😀

Ok, dann erhöhe ich den Counter der funktionalen Ansätze um eine Lösung in Erlang. Ich habs mal übersichtlich gehalten, man kann das noch etwas eindampfen wenn man will.
Kommt hier auf ~7 Sekunden Laufzeit, wobei der Shutdown des Laufzeitsystems wie üblich mit ca. 1,5 Sekunden mitgezählt wird.

-module(lychrel).
-export( [is_palindrom/1, inversion/1, lychrel/3, start/0]).

%-- is_palindrom
is_palindrom(AnInteger)   ->
    L = integer_to_list(AnInteger), 
    R = lists:reverse(L),
    ZipWithFun = fun( E1, E2 ) -> E1 == E2 end,
    Zipped = lists:zipwith(ZipWithFun, L, R),
    %% lists:any here returns true if L is *not* a palindrom, so negate it.
    false == lists:any( fun(X) -> X == false end, Zipped);

%-- inversion
inversion(AnInteger) ->
    list_to_integer (lists:reverse( integer_to_list(AnInteger))).

%-- find_lychrel    
find_lychrel(OriginalStart, Current, 0) ->
    case is_palindrom(Current) of 
        true -> ok;
        false -> io:format("~w~n", [OriginalStart])
    end;

find_lychrel(OriginalStart, Current, CurrentIter) ->
    case is_palindrom(Current) of
        true -> ok;
        false -> find_lychrel(OriginalStart, Current + inversion(Current), CurrentIter -1 )
    end.

%-- lychrel
lychrel(End,End,_) ->
    ok;

lychrel(Start,End,MaxIter) ->
    find_lychrel(Start, Start, MaxIter),
    lychrel(Start+1, End, MaxIter).
    
%for convenience, assume Start=1,End=N,MaxIter=100
lychrel(N) ->	     
    lychrel(1,N,100).
					  
%-- for calling this as "erl -noshell lychrel start"
start() ->
    lychrel(100000),
    init:stop().

Ich hab mal Code_Gala aktualisiert. Is es möglich das eine Codebox neben den Inhaltsverzeichnis erscheint und nicht erst darunter? So wie es jetzt aussieht ist da ne hässliche Lücke 😢

Und dann nochmal eine Frage an die Mods:
Könnte man die Threads hierzu nich in etwas wiedererkennbares umbennen? Z.b. Anstatt "Zeigt her eure Codes" "Code Gala: Fibonacci" und diesen Thread in "Code Gala: Lychrel" und alle zukünftigen dann nach den gleichen Schema.

from itertools import ifilter, imap

def mirror(n):
    return int(
                str(n)[::-1])

def is_lychrel(n, tries=100):
    rev = mirror(n)
    for dummy in xrange(tries):
        n += rev 
        rev = mirror(n)
        if n == rev:
            return False
    return True

def main():
    print '\n'.join(imap(str, ifilter(is_lychrel, xrange(100000))))

if __name__ == '__main__':
    main()

An mirror() geht natürlich alle Rechenzeit verloren, das ist einfach viel zu langsam...
Aber das Problem ist ja bekannt 😀

noch mal eine andere Bash-Lösung:

#!/bin/bash

i=1
last=1000
iterations=100
x=0

isPalindrom ()
{
	if [[ "$x" == "$(echo $x | rev)" ]]
	then
		return 0
	else
		return 1
	fi
}

isLychrel ()
{
	j=0
	x=$i
	while [ "$j" -lt "$iterations" ]
	do
		x=$(echo "$x + $(echo $x | rev)" | bc)
		if isPalindrom
		then
			return 1
		fi
		(( j += 1 ))
	done
	return 0
}

while [ "$i" -lt "$last" ] 
do
	if isLychrel
	then
		echo "-------------> Found Lychrel: $i"
	fi
	(( i += 1 ))
done
echo
exit 0

Eine Lösung in D. Basiert auf meiner C-Lösung, implementiert die Integer-Klasse aber als Wert-Typ, es wird also viel "unnötig" umher kopiert. Dafür ist es wesentlich sauberer und wohl auch nachvollziehbarer.

import std.stdio;
import std.string;

static const uint ITERATIONS = 100;


class Integer
{
    ubyte[] digits;
    
    invariant {
        foreach (ubyte d; digits) {
            assert(0 <= d && d < 10);
        }
    }
    
    this(uint n)
    out { assert(this.toInt == n); }
    body
    {
        char[] d = std.string.toString(n);
        this.digits = new ubyte[d.length];
        foreach (uint i, char c; d) {
            this.digits[$-1-i] = c - '0';
        }
    }
    
    this(Integer i)
    out { assert(this.digits !is i.digits);  }
    body
    {
        this.digits = new ubyte[i.length];
        this.digits[] = i.digits;
    }
    
    Integer opAdd(Integer other)
    {
        auto result = new Integer(this);
        uint carry = 0;
        foreach (uint i, inout ubyte b; result.digits) {
            b = b + other.digits[i] + carry;
            if (b >= 10) {
                b -= 10;
                carry = 1;
            } else {
                carry = 0;
            }
        }
        if (carry) {
            result.digits.length = result.digits.length + 1;
            result.digits[$-1] = carry;
        }
        return result;
    }
    
    uint length() { return this.digits.length; }
    
    bool isPalindrome()
    {
        for (uint i = 0; i < this.length / 2; i++) {
            if (this.digits[i] != this.digits[$-1-i]) return false;
        }
        return true;
    }
    
    Integer reversed()
    {
        auto result = new Integer(this);
        for (uint i = 0; i < result.length / 2; i++) {
            auto tmp = result.digits[i];
            result.digits[i] = result.digits[$-1-i];
            result.digits[$-1-i] = tmp;
        }
        return result;
    }
    
    char[] toString()
    {
        auto result = new char[this.length];
        foreach (uint i, ubyte b; this.digits) {
            result[i] = this.digits[$-1-i] + '0';
        }
        return result;
    }
    
    uint toInt()
    {
        uint result = 0;
        foreach_reverse (ubyte b; this.digits) {
            result = result * 10 + b;
        }
        return result;
    }
}

bool isLychrel(Integer n, uint iterations = ITERATIONS)
{
    for (uint i = 0; i < iterations; i++) {
        n = n + n.reversed;
        if (n.isPalindrome) return false;
    }
    return true;
}

void main()
{
    for (uint n = 1; n <= 100_000; n++) {
        auto i = new Integer(n);
        if (isLychrel(i)) writef("%s\n", i);
    }
} 

Hm, ich habe gerade versucht das in php (shame on me) um zu setzten (frei nach der Bash-Verision von Mr. Kanister), aber irgendwie findet der Zahlen die nicht gefunden gehören, ich habe jetzt aber auch keine Zeit bzw. Lust mehr, vielleicht findet ja jemand den Fehler:

<?php
$last = 100000;
$iter = 100;
$anz = 0;
$start = time();
for ( $i=1; $i<=$last; $i++ ) {
	$z = $i;
	for ( $j=1; $j<=$iter; $j++ ) {
		$z += intval(strrev($z));
		if ( $z == intval(strrev($z)) ) break;
		if ( $j == $iter ) {$anz++;echo $i . ' ';}
	}
}
echo '<br/>anz: ' . $anz . '<br/>time: ' . (time()-$start);
?>

89 98 177 187 196 276
...
99988 99990 99995 99997 99998 99999
anz: 13620
time: 8

😲

Na gut, der Vollständigkeit halber hier noch mal der gleiche Algorithmus in Java:

import java.math.BigInteger;

public class lychrel3 {

	public static void main(String[] args) {
	      int anz = 0;
	      int last = 100000;
	      int iter = 100;
	      long start = System.currentTimeMillis();
	      for(int i = 1;i <= last;i++) {
	          BigInteger z = new BigInteger(String.valueOf(i));
	    	  for (int j=1;j<=iter;j++) {
	    		  z=z.add(new BigInteger(String.valueOf(new StringBuffer(z.toString()).reverse().toString())));
	    		  if(new BigInteger(String.valueOf(new StringBuffer(z.toString()).reverse().toString())).compareTo(z) == 0) break;
	    		  if (j==iter) {
	    			  System.out.println(i);
	    			  anz++;
	    		}
	         }
	      }
	      long stop = System.currentTimeMillis();
	      System.out.println("anz:  " + anz);
	      System.out.println("time: " + (stop - start) + "ms");
	   }
}

In C++, ohne Beschränkung auf 20 Iterationen. Benötigt libgmpxx4ldbl und den Compilerswitch -lgmpxx

#include <gmpxx.h>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
bool is_palindrome(const mpz_class& x) {
    stringstream ss;
    ss << x;
    string s = ss.str();
    int i1 = s.length()-1, i2=0;
    while (i1 >= i2) {
        if (s[i1] != s[i2])
            return false;
        i1--;
        i2++;
    }
    return true;
}
mpz_class reverse(const mpz_class& x) {
    stringstream ss;
    mpz_class rv;
    ss << x;
    string s = ss.str();
    reverse(s.begin(),s.end());
    ss.str(s);
    ss >> rv;
    return rv;
}
bool is_lychrel(const mpz_class& x, int iterations) {
    mpz_class y = x;
    for (int i=0;i<iterations;++i) {
        y+=reverse(y);
        if (is_palindrome(y))
            return false;
    }
    return true;
}
int main() {
    cout.sync_with_stdio(false);
    for (int i=0;i<100000;++i) {
        if (is_lychrel(i,100))
            cout << i << '\n';
    }
}

So ich hab dann auch mal schnell etwas gebastelt:
Die Ergebnisse sind noch etwas komisch, liegt das vielleicht an der Anzahl der Itterationen oder hab ich was falsch gemacht? 😀

unsigned long invertNumber(unsigned long number, unsigned int base)
{
   unsigned long invertedNumber = 0;

   // Die aktuelle Stelle der invertieren Zahl
   unsigned int currentNumPos = 0;

   unsigned int lastNumPos;

   {
      unsigned long temp = number;

      // Anzahl Stellen herausfinden
      while (temp != 0)
      {
         currentNumPos++;
         temp /= base;
      }
   }

   while (number != 0)
   {
       currentNumPos--;

       lastNumPos = (number - ((number / base) * base));

       invertedNumber += lastNumPos * pow(base, currentNumPos);
       number /= base;
   }

   return invertedNumber;
};

bool isPalindrom(unsigned long number, unsigned int base = 10)
{
   return invertNumber(number, base) == number;
};

int main(int arg_count, char **arg_list)
{
   if (arg_count == 1 || arg_count > 4)
   {
      return 1;
   }

   unsigned int start = (unsigned int)atoi(arg_list[1]);
   unsigned int end = (unsigned int)atoi(arg_list[2]);
   unsigned int base = (unsigned int)atoi(arg_list[3]);

   if (start > end)
   {
      unsigned int temp = start;
      start = end;
      end = start;
   }

   unsigned int count = 0;

   clock_t start_time, end_time;
   start_time = clock();


   for (unsigned int run = start; run < end; run++)
   {

      unsigned int currentNum = run;

      for (int iter = 1; iter < 21; iter++)
      {

         if (isPalindrom(currentNum, base))
         {
            break;
         }

         currentNum += invertNumber(currentNum, base);

         if (iter == 20)
         {
            std::cout << run << " könnte eine Lychrel-Zahl sein." << std::endl;
            count++;
         }

      }
   }

   end_time = clock();

   std::cout.precision(10);

   std::cout << count << " mögliche Lychrel-Zahlen in " << (double)(end_time - start_time) / (double)CLOCKS_PER_SEC << " Sekunden gefunden." << std::endl;

   return 0;

};

Ach ja: 😉

11669 mögliche Lychrel-Zahlen in 0.62 Sekunden gefunden.

Dann werfe ich auch mal meine Lösung in die Runde: http://paste.pocoo.org/show/31710

e1bart0 hat geschrieben:

Dann werfe ich auch mal meine Lösung in die Runde: http://paste.pocoo.org/show/31710

Diese Lösung ist aber IMHO nicht korrekt. Meine Lösung, die Java-Lösung und audax' Python-Lösung spucken 6091 Zahlen aus, Deine dagegen 7444.
Hier die Zahlen, die bei Dir zu viel sind:
http://paste.pocoo.org/show/31787/

Und außerdem finde ich es ungerecht, dass sowohl die Python-Lösung schneller ist als C++. Zumal ich nicht so recht weiß, wie ich es optimieren soll. Der Profiler sagt, dass satte 54% der Laufzeit in std::reverse verbracht werden. Eine selbst geschriebene Reverse-Funktion für die Strings ist aber nur wenig schneller :/.
Bei Java seh ich ja noch ein, dass da mittels Laufzeitoptimierung noch einiges herausgeholt werden kann. Da kann man schön erkennen, wie der JIT so optimiert ☺

Meine C++ Version, die ich momentan aber leider nicht posten kann (evtl. heut Abend), findet meiner Ansicht nach auch zuviele Zahlen. Zum Beispiel die 89 und die 98, obwohl laut Wikipedia (Lychrel-Zahl) 196 die kleinste Lychrel Zahl ist. Oder sind 100 Iterationen einfach noch nicht genug?

Was sind eure ersten Lychrel Zahlen?