staging.inyokaproject.org

Hi ich hätt nen Vorschlag für ne neue Aufgabe:

Das Programm soll alle Lychrel-Zahlen zwischen 0 - 100000 ausgeben. Pro Zahl sollten ca. 100 Iterationen ausgeführt werden(je mehr, desto besser ☺ )

Was haltet ihr davon?

So ich habe mal diese Seite erstellt: Baustelle/Code_Gala . Was haltet ihr davon?

Sieht schonma net schlecht aus... Soll für jede Aufgabe eine neue Seite angelegt werden oder alle Aufgaben in eine, bei letzteren hätte ich Angst das die Seite absolut unübersichtlich wird.

Quick and dirty python:

#!/usr/bin/python

import sys

def mirror(s):
  new = ""
  for i in range(len(s)):
    new+=s[(i+1)*-1]
  return new

def is_palindrom(n):
  s = str(n)
  if s==mirror(s):
    return True
  return False

def iterate(n):
  return n+int(mirror(str(n)))

def is_lychrel(n,niter):
  for i in range(niter+1):
    if is_palindrom(n):
      return False,i
    n = iterate(n)
  return True,niter

for n in range(int(sys.argv[1]),int(sys.argv[2])):
  if is_lychrel(n,int(sys.argv[3]))[0]:
    print n

Quick und nicht ganz so dirty Python: 😛

#!/usr/bin/env python

def is_palindrome(number):
    number_as_string = str(number)
    return number_as_string == number_as_string[::-1]

def is_lychrel(number, iterations):
    for dummy in xrange(iterations):
        number = number + int(str(number)[::-1])
        if is_palindrome(number):
            return False
    return True

def main():
    first = 1
    last = 100000
    iterations = 100
    for number in xrange(first, last + 1):
        if is_lychrel(number, 100):
            print number

if __name__ == '__main__':
    main()

So etwas habe ich früher mal in BASIC und Assembler auf'm C64 geschrieben. ☺

Marc 'BlackJack' Rintsch hat geschrieben:

[::-1]

Genau das hab ich gesucht. Danke.

Marc 'BlackJack' Rintsch hat geschrieben:

def is_lychrel(number, iterations):
    for dummy in xrange(iterations):
        number = number + int(str(number)[::-1])
        if is_palindrome(number):
            return False
    return True

Wenn ich da richtig durchblicke, dann überprüfst Du nicht, ob "number" schon ein Palindrome ist (z.B. 0,1,2, .., 11, ..).

'⇒ Quick und noch weniger dirty Python: 😛

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#!/usr/bin/env python

import sys

def is_palindrom(n):
  s = str(n)
  return s==s[::-1]

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

def is_lychrel(n,niter):
  for i in range(niter+1):
    if is_palindrom(n):
      return False,i,n
    n = iterate(n)
  return True,niter,n

for n in range(int(sys.argv[1]),int(sys.argv[2])):
  if is_lychrel(n,int(sys.argv[3]))[0]:
    print n

Das eine Zahl ein Palindrom ist, heisst nicht, dass sie keine Lychrel-Zahl sein kann!

Marc 'BlackJack' Rintsch hat geschrieben:

Das eine Zahl ein Palindrom ist, heisst nicht, dass sie keine Lychrel-Zahl sein kann!

Du hast wohl recht. Laut Wikipedia ist die kleinste Lychrel-Zahl 196. D.h. der Algorithmus (die Iteration) muß in jedem Fall einmal durchgeführt werden. Sorry, mein Fehler.

Obwohl ich meine Definition irgendwie intuitiver finde: Wieso soll ich eine Zahl mit einem Algorithmus behandeln, um diese Zahl in etwas zu verwandeln, was sie sowieso schon ist?

Die Fragestellung ist ja, gibt es Zahlen, die mit diesem Algorithmus behandelt nicht zu Palindromen führen. Das es Zahlen gibt, die einfach so ein Palindrom sind, weiss ich auch ohne Algorithmus. Umso interessanter ist es doch, das Palindrome als Ausgangszahl nichts besonderes sind, auch die könnten selbst Lychrel-Zahlen sein.

Einmal in Java ☺ Ich wette meine Spiegel Methode ist zu umständlich aber was solls ☺

import java.math.BigInteger;

public class Lychrel {
	
	public static boolean isPalindrom(BigInteger x) {
		if(spiegel(x).compareTo(x) == 0) return true;
		return false;
	}
	
	static BigInteger spiegel(BigInteger x) {
		char[] cl = x.toString().toCharArray();
		char[] neu = new char[cl.length];
		
		for(int i = 0; i < cl.length;i++) {
			neu[i] = cl[cl.length-1 - i];
		}
		return new BigInteger(String.valueOf(neu));
	}
	
	static boolean lychrel(int x) {
		BigInteger a = new BigInteger(String.valueOf(x));
		
		for(int i = 0;i < 100;i++) {
			if(isPalindrom(a=a.add(spiegel(a)))) return false;
			//System.out.println(a.toString());
		}
		return true;
	}
	
	public static void main(String[] args) {
		int erg = 0;
		long start = System.currentTimeMillis();
		for(int i = 1;i <= 100000;i++) {
			if(lychrel(i)) {
				System.out.println(i);
				erg++;
			}
		}
		long stop = System.currentTimeMillis();
		System.out.println("Anzahl: " + erg);
		System.out.println("Zeit: " + (stop - start) + "ms");
	}
}

Mit Ausgabe der Zahlen siehts ungefähr so aus:

[...]
99973
99974
99979
99990
99999
Anzahl: 6091
Zeit: 10103ms

ohne Ausgabe brauch das Programm nur 7sec...

Einmal in Haskell.
Aber Achtung, das ist ziemlich umständlich und braucht extrem lange

module Main where
{-
Integer - die zu testende Zahl
Bool - True wenn es ein Palindrom ist
-}
isPalindrom :: Integer -> Bool
isPalindrom x	| show x == reverse (show x) = True
				| otherwise = False

{-
Integer(1) - die zu testende Zahl
Integer(2) - Anzahl der Iterationen
Bool - True wenn es eine Lychrel-Zahl ist
-}
isLychrel :: Integer -> Integer -> Bool
isLychrel x y	| isPalindrom x = False
				| not (isPalindrom x) && y > 0 = isLychrel (x+(read(reverse(show x))::Integer)) (y-1)
				| not (isPalindrom x) && y <= 0 = True

{-
Integer(1) - Letzte zu testende Zahl
Integer(2) - Aktuell zu testende Zahl
Integer(3) - Anzahl der Iterationen Pro Zahl
[Integer] - Liste der Lychrel-Zahlen
-}
lychrelTest :: Integer -> Integer -> Integer -> [Integer] -> [Integer]
lychrelTest x y z xs	| y>x = xs
						| y<=x && isLychrel y z = lychrelTest x (y+1) z xs++y:[]
						| y<=x && not (isLychrel y z) = lychrelTest x (y+1) z xs
lychrelTest x y z []	| y>x = []
						| y<=x && isLychrel y z = lychrelTest x (y+1) z (y:[])
						| y<=x && not (isLychrel y z) = lychrelTest x (y+1) z []


{-
Integer(1) - Zu testende Zahlen
Integer(2) - Iterationen pro Zahl
[Integer] - Liste der Lychrel-Zahlen
-}
main :: Integer -> Integer -> [Integer]
main x y = lychrelTest x 1 y []

Marc 'BlackJack' Rintsch hat geschrieben:

Die Fragestellung ist ja, gibt es Zahlen, die mit diesem Algorithmus behandelt nicht zu Palindromen führen. Das es Zahlen gibt, die einfach so ein Palindrom sind, weiss ich auch ohne Algorithmus. Umso interessanter ist es doch, das Palindrome als Ausgangszahl nichts besonderes sind, auch die könnten selbst Lychrel-Zahlen sein.

Wenn ich mal Wikipedia Zitieren darf:
Wikipedia hat geschrieben:

Jede natürliche Zahl n, die nicht durch eine endliche Anzahl von Inversionen und Additionen zu einem Zahlen-Palindrom führt wird als Lychrel-Zahl bezeichnet. Als Inversion versteht man hier das Bilden der spiegelverkehrten Zahl m. Führt die Addition n + m dabei zu einem Zahlen-Palindrom, ist der Algorithmus beendet. Falls nicht, wird durch erneute Inversion und Addition dieser Vorgang solange ausgeführt, bis das Ergebnis ein Palindrom ist.

(hervorhebung von mir)
Ist 0 (null) jetzt auch schon endlich oder nicht?
Die Zahl 99 bildet nach genau 0 (null) Inversionen und Additionen ein Palindrom, ist also nach meinem Verständnis keine Lychrel-Zahl.

Ist 0 (null) jetzt auch schon endlich oder nicht?
Die Zahl 99 bildet nach genau 0 (null) Inversionen und Additionen ein Palindrom, ist also nach meinem Verständnis keine Lychrel-Zahl.

Gleich der erste Satz in Wikipedia bringt die Lösung...

[...], die sich der Palindrombildung durch einen bestimmten Algorithmus widersetzen.

Um sich den Algoritmus wiedersetzen zu können muss er mindestens einmal angewendet werden... Ansonsten kann man keine Aussage darüber machen ob der Algorithmus nun erfolgreich war(keine Lychrel) oder nicht(ist eine Lychrel)...

Eine IMHO recht flotte Haskell-Lösung (ca. 4 Sekunden bei mir):

import Char (ord)

type Digits = [Int]

intToDigits :: Int -> Digits
intToDigits n = reverse [ord(c) - ord('0') | c <- show n]

add :: Digits -> Digits -> Digits
add xs ys = add' xs ys 0
    where
        add' [] [] 0 = []
        add' [] [] 1 = [1]
        add' (a:as) (b:bs) c =
            let s = a + b + c in
                (s `mod` 10) : add' as bs (s `div` 10)

reverseAndAdd :: Digits -> Digits
reverseAndAdd ds = add ds (reverse ds)

isPalindrome :: Digits -> Bool
isPalindrome ds = ds == (reverse ds)

isLychrel :: Int -> Int -> Bool
isLychrel i n = not . any isPalindrome . take i . tail
    $ iterate reverseAndAdd (intToDigits n)

lychrelNumbers :: Int -> Int -> Int -> [Int]
lychrelNumbers a b m = filter (isLychrel m) [a..b]

main :: IO ()
main = putStr . unlines . map show $ lychrelNumbers 1 100000 100

Hier mal in c++. Allerdings sind viel mehr als 20 Iterationen bei 100000 in c++ durch die Begrenzung von unsigned long long nicht möglich...

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

/* Gibt alle Lychrel-Zahlen zwischen 11 und 100000 aus */

unsigned long long reverse( unsigned long long zahl) //Dreht die Zahl um
{
      stringstream stream, s;
      string asstring, reverse;
      unsigned long long rev = 0;
      stream << zahl;
      stream >> asstring;
      stream.flush();

      for( int i = (asstring.length()-1); i >= 0 ; i-- ) {
	  s << asstring.at(i);
      }
      s >> rev;
    
      return rev;
}

bool is_palin( unsigned long long zahl )  //Überprüft, ob zahl ein Palindrom ist
{
      if( reverse(zahl) == zahl ) return true;
      return false;
}

int main()
{
      bool is_lychrel = true;
      unsigned long long zahl = 0;

      for( int z = 11; z <= 100000; z++ ) {
	  is_lychrel = true;
	  zahl = z;
	  for( int i = 0; i <= 20; i++ ) {
	      zahl = zahl + reverse(zahl);
	      if( is_palin(zahl) ) {
		  is_lychrel = false;
		  break;
	      }
	  }
      
	  if( is_lychrel ) cout << z << " könnte eine Lychrel-Zahl sein!" << endl;

      }
      return 0;
}

und sicherlich ist dieser Code noch verbesserungsfähig... 😉

Hier mal in der bash:

#!/bin/bash

for (( i = 1; i <= 1000; i++ ))
do
	zahl=$i

	for (( j = 1; j <= 100; j++ ))
	do
		zahl=$(echo "$zahl + $(echo $zahl | rev)" | bc)

		[[ "$zahl" == "$(echo $zahl | rev)" ]] && break

		(( j == 100 )) && echo $i
	done
done

Dauert aber bis 1000 schon viel zu lange 😛

martin@martin-desktop:~$ time example
196
295
394
493
592
689
691
788
790
879
887
978
986

real    0m42.851s
user    0m17.945s
sys     0m24.134s

Gruß Martin

So das ganze in SML:

fun revhelp x = IntInf.fromString(implode(rev(explode(IntInf.toString(x)))));

fun revhelp2(SOME(x)) = x;

fun revInt x = revhelp2(revhelp(x));

fun isPalindrom x = revInt(x) = x;

fun isLychrel (x,0) = true
|    isLychrel (x,y) =    
let
     val erg = x + revInt(x)
in
     if isPalindrom(erg) 
     then false
     else isLychrel(erg,y-1)
end;

fun test 0 = []
|	 test x =
if isLychrel(x,100) then x::test(x-1) else test(x-1);

test 100000;

Ausgabe:

val it = [99999,99990,99979,99974,99973,99961,99958,99953,99947,99923,99898,99892,...] : IntInf.int list

Zeit konnte ich leider nicht messen, sind aber so gefühlte 5-6 sec

fun revhelp x = IntInf.fromString(implode(rev(explode(IntInf.toString(x)))));

Genau wegen solchen Dingen mag ich SML so ☺