ubuntuusers.de

[Code-Gala] Lychrel-Zahlen

Status: Ungelöst | Ubuntu-Version: Nicht spezifiziert
Antworten |
Dieses Thema ist die Diskussion des Artikels Projekte/Code_Gala.

MrKanister

Anmeldungsdatum:
13. Oktober 2007

Beiträge: 2105

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

Marc_BlackJack_Rintsch Team-Icon

Ehemalige
Avatar von Marc_BlackJack_Rintsch

Anmeldungsdatum:
16. Juni 2006

Beiträge: 4650

Wohnort: Berlin

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

BadBoy

Avatar von BadBoy

Anmeldungsdatum:
25. Oktober 2007

Beiträge: 479

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! 😀

radoe2

Anmeldungsdatum:
30. November 2006

Beiträge: 243

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().

kart0ffelsack

(Themenstarter)

Anmeldungsdatum:
16. Oktober 2007

Beiträge: 102

Wohnort: Kaiserslautern

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.

audax

Avatar von audax

Anmeldungsdatum:
15. September 2006

Beiträge: 1253

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 😀

rocco_storm Team-Icon

Avatar von rocco_storm

Anmeldungsdatum:
3. November 2005

Beiträge: 1811

Wohnort: Ruhrpott

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

Marc_BlackJack_Rintsch Team-Icon

Ehemalige
Avatar von Marc_BlackJack_Rintsch

Anmeldungsdatum:
16. Juni 2006

Beiträge: 4650

Wohnort: Berlin

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);
    }
} 

rocco_storm Team-Icon

Avatar von rocco_storm

Anmeldungsdatum:
3. November 2005

Beiträge: 1811

Wohnort: Ruhrpott

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


😲

rocco_storm Team-Icon

Avatar von rocco_storm

Anmeldungsdatum:
3. November 2005

Beiträge: 1811

Wohnort: Ruhrpott

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");
	   }
}

Hello_World

Anmeldungsdatum:
13. Juni 2006

Beiträge: 3620

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';
    }
}

sxfreak

Avatar von sxfreak

Anmeldungsdatum:
27. Juni 2006

Beiträge: 436

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.

e1bart0 Team-Icon

Avatar von e1bart0

Anmeldungsdatum:
12. Mai 2007

Beiträge: 927

Wohnort: München

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

Hello_World

Anmeldungsdatum:
13. Juni 2006

Beiträge: 3620

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 ☺

coxran

Anmeldungsdatum:
4. März 2008

Beiträge: 11

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?