project euler

[lukas (Gast)]

hallo,

kennt ihr projecteuler.net?

ich find die seite recht gut (soweit ich das beurteilen kann, bin erst 
beim lösen von problem 4 also noch nicht weit)

und bei eben diesen bin ich dann auch schon auf ein problem gestoßen, 
nämlich das prüfen ob eine zahl ein palindrome ist oder nicht.

ich wollte mir "einfach" eine kleine funktion schreiben, aber diese 
funktioniert leider irgendwie noch nicht.

also falls ihr auch etwas mitprogrammieren wollt und eure lösungen 
präsentieren wollt könnt ihr dass ja hier machen ;)
und wer mir einen tipp geben kann warum meine funktion nicht dass tut 
wass sie soll, der kann dass auch gerne tun.

viel spass beim lösen der probleme!

lg lukas

int is_palindrome(int x) {
  //Prüft max 10 Stellige zahlen ob sie palindrom sind.
  //gibt 99 zurück wenn x nicht erlaubt ist
  //gibt 1 zurück wenn x ein palindrom ist
  //gibt 0 zurück wenn x kein palindrom ist
  char n = 0;
  do {  //Anzahl der stellen feststellen
    if(x<10) return 1;
    if(x>999999999)  n=10; break;
    if(x>99999999)  n=9; break;
    if(x>9999999)  n=8; break;
    if(x>999999)  n=7; break;
    if(x>99999)  n=6; break;
    if(x>9999)  n=5; break;
    if(x>999)  n=4; break;
    if(x>99)  n=3; break;
    if(x>9)  n=2; break;
    return 99;
  } while( true );
  char a[n];
  char b[n];
  int tmp;
  for(int i=0; i<n; i++) {  //arrays initialisieren
    a[i] = 0; b[i] = 0;
  }
  for(int i = 0; i<n; i++) {  //einer, zehner,... feststellen
    tmp = 0;
    for(int j = 0; j<i; j++) {
      tmp += a[j];
    }
    tmp = x - tmp;
    a[i] = tmp % int(pow(10,i));
  }
  for(int i = 0; i<n; i++) {  //Zahlenfolge umdrehen
    b[i] = a[n-i];
  }
  for(int i = 0; i<n; i++) {  //auf gleichheit prüfen
    if( a[i] != b[i] ) return 0;
  }
  return 1;
}

[Vlad T. (vlad_tepesch)]

mein ansatz war ganz einfach:

Zahl in String umwandeln
String umdrehen
Strings vergleichen
;)

bool isPalindromNumber(uint64_t n)
{
  ostringstream ostr;
  ostr << n;
  string st;
  string t =  ostr.str();
  reverse(t.begin(), t.end());
  return ostr.str() == t;
}

dann einfach zwei verschachtelte Schleifen, die alle Kombinationen 
durchtesten.

Da es keine Laufzeitanforderungen gibt und je schleife nur 900 
iterationen sind, geht das trotzdem fix

[DirkB (Gast)]

Ich hätte die Zahl neu zusammengesetzt. (ungetestet)

int is_palindrome(uint64_t zahl) {
  uint64_t z, gedreht=0;

  for(z=zahl;z>0;z/=10) 
    gedreht = gedreht * 10 + (z%10);
  
  return (gedreht==zahl);
}

Ein 32-Bit int kann Werte bis knapp 2 Milliarden aufnehmen. Das ist zwar 
10-stellig, aber nicht so ganz :-)

[anon (Gast)]

If you can't solve it, then you can't solve it. ;)

Ich habe schon viele tage mit project euler vebracht. Das helfen 
untereinander ist dort auf jeden fall nicht gerne gesehen.

[D. I. (Gast)]

Hatten wir vor einiger Zeit schonmal. Die Project Euler Probleme sind 
relativ langweilig und unanspruchsvoll, da keine Laufzeitbeschränkung 
und man daher nicht bemüht sein muss sich was schlaues auszudenken.

Ich finde

http://www.spoj.pl/

deutlich besser, aber das dürfte den meisten Ings wohl zu hoch sein 
duck und weg

[lukas (Gast)]

anon schrieb:
> If you can't solve it, then you can't solve it. ;)
>
> Ich habe schon viele tage mit project euler vebracht. Das helfen
> untereinander ist dort auf jeden fall nicht gerne gesehen.

hallo, ich habe ja nicht nach einem Code zum copy-pasten gefragt... ich 
werde auch weiter an meiner Lösung arbeiten,... obwohl mir die 
umwandlung in string sehr gut gefällt ;)

danke für eure bisherigen Kommentare!

die andere Seite werden ich mir heute Abend mal anschauen. klingt schon 
mal intressant, auch wenns schwer sein soll, oder sogar deswegen. man 
wächst ja anscheinend mit der herausforderung :)

lg lukas

[Karl H. (kbuchegg)]

lukas schrieb:


> und wer mir einen tipp geben kann warum meine funktion nicht dass tut
> wass sie soll, der kann dass auch gerne tun.

>     a[i] = tmp % int(pow(10,i));

Das dürfte nicht das machen, was du denkst was da rauskommen sollte.
Aber dein Code ist so verworren, dass das schwer zu sagen ist ohne ihn 
in Aktion zu sehen.

Lass dir halt die Arrays ausgeben, dann siehst du was rauskommt und 
kannst weiter überlegen.



Ich kanns nicht lassen.
wenn du eine Zahl in Einer, Zehner etc. zerlegen willst dann geht das so

  i = 0;
  while( x > 0 ) {
    a[i] = x % 10;
    x = x / 10;
    ++i;
  }

du gehst das ziemlich kompliziert und unübersichtlich an.

[http://www. (Gast)]

anon schrieb:
> Ich habe schon viele tage mit project euler vebracht.
Ich auch, leider nur 40(??) Rätsel gelöst.

> Das helfen
> untereinander ist dort auf jeden fall nicht gerne gesehen.
Psst, einfach nicht weitersagen (oder weiter sagen?).

Was Problem 4 betrifft, ich hab perl genommen, Vorsicht 
Programmieranfänger (in Perl):

use strict;
use warnings;

my $z1;
my $z2;
my $val;
my $valr;
my $max=1;

for $z1(100..999)
{
  for $z2($z1..999)
  {
    $val=$z1*$z2;
    $valr=reverse $val;
    if($val eq $valr)
    {
      $max=$val if($val>$max);
    }
  }
}

print $max;

Braucht unter einer Sekunde auf meiner Kiste.

[Mark B. (markbrandis)]

anon schrieb:
> If you can't solve it, then you can't solve it. ;)
>
> Ich habe schon viele tage mit project euler vebracht. Das helfen
> untereinander ist dort auf jeden fall nicht gerne gesehen.

Ist doch Bullshit. Ob einem jemand hilft oder nicht kann sowieso nicht 
kontrolliert werden. Man könnte ja auch einen Freund fragen, oder einen 
Kommilitonen, oder einen Arbeitskollegen, ...

[lukas (Gast)]

so, ich hab jetzt eine funktionierende, nicht sehr effiziente, aber auf 
den meisten rechner sicher in unter 5sec ausführbare lösung gefunden.

was bekommt ihr denn für eine lösung heraus?

ich bekomme 90909 heraus, müsste doch stimmen, oder???

lg lukas

ps spoj.pl schaut auch sehr intressant aus, und die erste aufgabe macht 
auf jeden fall lust auf mehr :)

[Johann L. (gjlayde)]

Vlad Tepesch schrieb:
> mein ansatz war ganz einfach:
>
> Zahl in String umwandeln
> String umdrehen
> Strings vergleichen

Ist aber leider falsch:

#4: Find the largest palindrome made from the product of two 3-digit 
numbers.

Zudem: Selbst wenn du die Zahl über Computergeklimper findest, ist die 
Aufgabe nicht gelöst, weil der Nachweis fehlt, daß die gefundene Zahl 
die geforderten Eigenschaften hat.

[lukas (Gast)]

Johann L. schrieb:
> Vlad Tepesch schrieb:
>> mein ansatz war ganz einfach:
>>
>> Zahl in String umwandeln
>> String umdrehen
>> Strings vergleichen
>
> Ist aber leider falsch:
>
> #4: Find the largest palindrome made from the product of two 3-digit
> numbers.
>
> Zudem: Selbst wenn du die Zahl über Computergeklimper findest, ist die
> Aufgabe nicht gelöst, weil der Nachweis fehlt, daß die gefundene Zahl
> die geforderten Eigenschaften hat.

es ging ja hier nur um die abfrage ob eine zahl ein palindrome ist oder 
nicht, dass diese funktion dann noch in das eigentliche programm zur 
lösung des problems eingebaut werden muss ist doch klar.

lg lukas

[lukas (Gast)]

und weil ich grad dabei bin, was bekommt ihr bei problem 8 raus?

40824 ist meine lösung. könnte doch stimmen, oder?

lg lukas

[Vlad T. (vlad_tepesch)]

Johann L. schrieb:
> Ist aber leider falsch:
>
> #4: Find the largest palindrome made from the product of two 3-digit
> numbers.

cih seh da kein widerspruch.

ich iteriere quadratisch über die Zahlen 100..999, teste mit oben 
genanntem Ansatz auf Palindrom und merke mir die größte bisherige 
Palindromzahl.

[http://www. (Gast)]

lukas schrieb:
> so, ich hab jetzt eine funktionierende, nicht sehr effiziente, aber auf
> den meisten rechner sicher in unter 5sec ausführbare lösung gefunden.
>
> was bekommt ihr denn für eine lösung heraus?
>
> ich bekomme 90909 heraus, müsste doch stimmen, oder???
falsch.

lukas schrieb:
> und weil ich grad dabei bin, was bekommt ihr bei problem 8 raus?
>
> 40824 ist meine lösung. könnte doch stimmen, oder?
passt.

[DirkB (Gast)]

lukas schrieb:
> ich bekomme 90909 heraus, müsste doch stimmen, oder???

Ist um ca. Faktor 10 falsch.

[Vlad T. (vlad_tepesch)]

http://www. schrieb im Beitrag #2486546:
> lukas schrieb:
>> 40824 ist meine lösung. könnte doch stimmen, oder?
> passt.
häh?
40824 ist doch nicht mal ein palindrom

das ganze ist doch nahezu trivial

prinzipiell gibts doch 2 Ansätze:
1. Brutforce einfach alles durchprobieren.
Ist aufgrund der geringen Datenmenge rechenzeitmäßig kein Problem und 
der am schnellsten hinprogrammiert.
2. ich erzeuge kombinatorisch alle möglichen Palindromzahlen zwischen 
10000 und 998001 und teste, jeweils, ob sie sich ohne rest in zwei 
3-Stellige Zahlen zerlegen lassen. Dies wiederum lässt sich auch auf 
verschiedene Wege bewerkstelligen, wobei auch hier bruteforce der 
einfachere ist.

[http://www. (Gast)]

Vlad Tepesch schrieb:
> http://www. schrieb im Beitrag #2486546:
>> lukas schrieb:
>>> 40824 ist meine lösung. könnte doch stimmen, oder?
>> passt.
> häh?
> 40824 ist doch nicht mal ein palindrom
Er spricht von einer anderen Aufgabe.

zu Aufgabe 4:
> das ganze ist doch nahezu trivial
Stimmt, s. meinen Perlcode.

[Johann L. (gjlayde)]

Vlad Tepesch schrieb:
> Johann L. schrieb:
>> Ist aber leider falsch:
>>
>> #4: Find the largest palindrome made from the product of two 3-digit
>> numbers.
>
> cih seh da kein widerspruch.
>
> ich iteriere quadratisch über die Zahlen 100..999, teste mit oben
> genanntem Ansatz auf Palindrom und merke mir die größte bisherige
> Palindromzahl.

Das ist aber nur ein hirntotes Durchprobieren und nicht das Lösen einer 
Mathe-Aufgabe. Stell dir einfach vor, es ist eine Klausuraufgabe die du 
lösen sollst. Und zwar so, daß andere die Lösung nachvollziehen können. 
Ich denke nicht, daß jemand 810000 Rechnungen nachkontrollieren will. 
Dein Rechner spuckt eine Zahl aus. Na und? Wieso sollte das die Lösung 
sein? In einer Klausur gäbe es dafür 0 Punkte, egal wie "richtig" die 
Zahl ist.

Bei der Seite handelt es sich um eine Mathe-Seite, wo man durch das 
Lösen der Aufgaben was über Mathe lernt. Nimm zum Beispiel Aufgabe #24 
oder #25:

Aufgabe #24
> What is the millionth lexicographic permutation of the
> digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Aufgabe #25
> What is the first term in the Fibonacci sequence to
> contain 1000 digits?

Zur Lösung braucht man bestenfalls nen Taschenrechner und mit was Übung 
im Rechnen noch nichtmal den (für #25 evtl. ne Logarithmentafel).

Das in einen Computer reinzuhacken bringt dir nix. Das ist nämlich nicht 
nur ausnehmend hässlich und das Ergebnis nicht nachvollziehbar (es sei 
denn, man ist selbst ein fehlloser Computer), sondern du lernst dadurch 
auch absolut nichts über Mathemetik.

Nochmals zurück zu Aufgabe #4: Ein Faktor ist zum Beispiel durch 11 
teilbar (warum?)

[http://www. (Gast)]

Johann L. schrieb:
> Das in einen Computer reinzuhacken bringt dir nix. Das ist nämlich nicht
> nur ausnehmend hässlich und das Ergebnis nicht nachvollziehbar (es sei
> denn, man ist selbst ein fehlloser Computer), sondern du lernst dadurch
> auch absolut nichts über Mathemetik.
Naja, die Aufgaben der Seite sollen ja mittels Computer gelöst werden 
und wenn man das Forum dursucht finden sich viele die wo möglich Brute 
Force anwenden...

[lukas (Gast)]

ok, bin auf meinen fehler drauf gekommen, 90909 kann ja garnicht stimmen 
:S
aber 906609 sollte jetzt passen :)

ich seh das ganze so:
ich mache dort nicht im forum mit oder will viel mathe lernen, sondern 
programmieren üben, und mir ist klar dass die aufgaben wenn sie alle nur 
durch brutforcen gelöst werden bald langweilig werden. aber es ist 
dennnoch für einen programmieranfänger fein wenn man ein paar aufgaben 
zum abarbeiten hat.

lg lukas

[Karl H. (kbuchegg)]

lukas schrieb:

> ich mache dort nicht im forum mit oder will viel mathe lernen, sondern
> programmieren üben, und mir ist klar dass die aufgaben wenn sie alle nur
> durch brutforcen gelöst werden bald langweilig werden. aber es ist
> dennnoch für einen programmieranfänger fein wenn man ein paar aufgaben
> zum abarbeiten hat.

Um erst mal in die Gänge zu kommen, finde ich Brute Force schon ok. Aber 
irgendwann kommt der Zeitpunkt, an dem man das Handwerk 'Programmieren' 
soweit beherrscht, dass das Finden einer Lösungsstrategie der weitaus 
interessantere Teil ist. Das Coden in ein Programm ist dann eher mehr 
der "lästige", aber auch interessante Part, der einem dann aufzeigt ob 
die Gedankengänge richtig waren oder nicht.

[lukas (Gast)]

Karl Heinz Buchegger schrieb:
>
> Um erst mal in die Gänge zu kommen, finde ich Brute Force schon ok. Aber
> irgendwann kommt der Zeitpunkt, an dem man das Handwerk 'Programmieren'
> soweit beherrscht, dass das Finden einer Lösungsstrategie der weitaus
> interessantere Teil ist. Das Coden in ein Programm ist dann eher mehr
> der "lästige", aber auch interessante Part, der einem dann aufzeigt ob
> die Gedankengänge richtig waren oder nicht.

genau so seh ich das!

[MaWin (Gast)]

> Ob einem jemand hilft oder nicht kann sowieso nicht
> kontrolliert werden.

Man hat sich halt nur selbst beschissen.

Manche Leute lernen in der Schule auch abschreiben
statt selberdenken.

Zumal die Aufgaben offenbar wiklich Kinderlevel haben.

[Yalu X. (yalu) (Moderator)]

Auch wenn die Webseite "Euler" im Namen trägt, tritt der mathematische
Aspekt bei den Aufgaben leider etwas in den Hintergrund. Zumindest die
leichteren Aufgaben lassen sich deswegen ohne viel Nachzudenken meist in
1 bis 10 Zeilen herunterprogrammieren. Die Lösungssuchraum ist meist so
klein, dass auch mit VHLL-Sprachen wie Python akzeptable Laufzeiten
erreicht werden, was die Sache zusätzlich erleichtert.

Zudem wiederholen sich die Aufgaben immer wieder in ähnlicher Weise.
Wenn man sich einmal eine Handvoll Lösungsschemata zurechtgelegt hat,
kann man einen Großteil der Aufgaben mit viel Copy-Paste lösen.

Es gibt auch harte Nüsse unter den Aufgaben. Aber diejenigen, die sowohl
anspruchsvoll als auch irgendwie ein Bisschen pfiffig sind, muss man
erst einmal finden.

lukas schrieb:
> ich mache dort nicht im forum mit oder will viel mathe lernen, sondern
> programmieren üben,

Dafür sind die Aufgaben in Ordnung. Man sollte sich allerdings im Klaren
darüber sein, dass viele Probleme aus dem realen Programmiererleben
durch die Aufgaben nicht abgedeckt sind.

[Karl H. (kbuchegg)]

Das zb

  do {  //Anzahl der stellen feststellen
    if(x<10) return 1;
    if(x>999999999)  n=10; break;
    if(x>99999999)  n=9; break;
    if(x>9999999)  n=8; break;
    if(x>999999)  n=7; break;
    if(x>99999)  n=6; break;
    if(x>9999)  n=5; break;
    if(x>999)  n=4; break;
    if(x>99)  n=3; break;
    if(x>9)  n=2; break;
    return 99;
  } while( true );
  char a[n];
  char b[n];

ist .... ekelig.

* die do - while Schleife braucht kein Mensch. Wozu soll die gut sein?
* die Ausstiege mittels break sind ... scheuslich. Abgesehen davon,
  dass sie sowieso nicht so funktionieren, wie du dir das vorstellst.
  Jedes einzelne break gehört NICHT zum if, mit dem es in einer Zeile
  steht. Und genau darum hasse ich es, wenn man nach einem if die
  abhängige Anweisung in dieselbe Zeile steht. Man ist dann nämlich
  verführt zu denken, die gehören die irgendwie auch ohne { } dazu.
  Mach es dir zur Regel:
    Eine Zeile - eine Anweisung. Nur in ganz seltenen Fällen gibt es
    dazu eine Ausnahme!

  Warum nicht einfach

    if( x > 999999999 )
      n = 10;
    else if( x > 99999999 )
      n = 9;
    else if( x > 9999999 )
      n = 8;
    else if( x > 999999 )
      n = 7;
    else if( x > 99999 )
      n = 6;
    ...

   Da das ganze ein Matheforum ist, kann man sich auch mal überlegen,
   welche Aussagekraft eigentlich der 10-er Logarithmus über die
   Anzahl der Stellen einer Zahl hat.
   der log von 10     ist 1
   der log von 100    ist 2
   der log von 1000   ist 3
   ....

* Allerdings: Wozu das Ganze? Du hast die Zusicherung, dass die Zahlen
  nicht mehr als 10 Stellen haben werden. Mit größeren Zahlen kann
  dein Code sowieso nicht umgehen. Es ist daher absolut kein Beinbruch
  wenn du ganz einfach annimmst

  char a[10];
  char b[10];

  und damit glücklich wirst. Die tatsächliche Stellenzahl ergibt sich
  dann sowieso automatisch bei der Zerlegung mittels fortgesetzter
  Division durch 10.

[Mark B. (markbrandis)]

MaWin schrieb:
> Man hat sich halt nur selbst beschissen.
>
> Manche Leute lernen in der Schule auch abschreiben
> statt selberdenken.

Seltsam freilich, dass man im Berufsleben ständig kooperiert und das so 
richtig sein soll, und beim Lösen von anderen Aufgaben soll es auf 
einmal falsch sein.

[Vlad T. (vlad_tepesch)]

wenn wir hier grad beim Thema sind:

Ich hab ein Verständnisproblem bei AUfgabe 361:
http://projecteuler.net/problem=361

Es wird eine Sequenz {T_n} definiert - die ist mir klar.

Dann wird die Sequenz {A_n} definiert, die alle Ganzzahlen enzhält, 
deren Binärrepresentation in Sequenz {T_n} vorkommt - auch klar

The first several terms of A_n are given as follows
n    0  1  2  3  4  5  6  7   8   9  10  11  12  …
A_n  0  1  2  3  4  5  6  9  10  11  12  13  18  …

was meint A_n jetzt?
Ich dachte erst an die Länge der Sequenz {A_n}, also wie viele Elemente 
enthalten sind? Das funktioniert aber nicht.

[Vlad T. (vlad_tepesch)]

Nür für den Fall, dass mir die Sequenz doch nicht so klar ist, wie ich 
dachte:

hier mal ein Beispiel:

{T_5}:
011010

{A_5} = 0       0
        1       1
        2      10
        3      11
        5     101
        6     110
       13    1101
       26   11010

[Yalu X. (yalu) (Moderator)]

Vlad Tepesch schrieb:
> {A_5} = 0       0
>         1       1
>         2      10
>         3      11
>         5     101
>         6     110
>        13    1101
>        26   11010

Die 10 fehlt noch ;-)

Aber so ist das nicht gemeint {T_n} ist eine unendlich Folge, {A_n}
ebenso.Eine Zahl ist also auch dann in {A_n} enthalten, wenn ihre
Binärdarstellung erst beim zigmillionsten Element von {T_n} auftaucht.

Ah, sollte das vielleicht eine Aufgabe sein, die man wegen der
Unendlichkeit nicht mit Brute Force lösen kann?

[Johann L. (gjlayde)]

MaWin schrieb:

> Zumal die Aufgaben offenbar wiklich Kinderlevel haben.

Nein, das ist alles andere als Kinderkram. Zumindest wenn man die 
Aufgaben im Sinne der Seite löst.

Yalu X. schrieb:
> Auch wenn die Webseite "Euler" im Namen trägt, tritt der mathematische
> Aspekt bei den Aufgaben leider etwas in den Hintergrund.

Das kommt ganz auf den Ansetz an. Mit Brute Force ist der mathematische 
Aspekt perdu und der Schwierigkeitsgtrad darauf reduziert, eine 
Textaufgabe in eine Formel zu bekommen und ein paar Zeilen Code zu 
schreiben.

Nochmal anhand #24:

Die Lösungen kann man natürlich mit Brute Force rausprügeln, aber für 
#24 leitet man aus der rekursiven Darstellung die explizite Darstellung 
her:

Die Werte der Folge ergeben sich als Linearkombination der Potenzen der 
Eigenwerte der Matrix, die durch die Rekursion gegeben ist. Weil ein 
Eigenwert > 1 ist und der andere betragsmäßig < 1, kann man die Näherung 
für die Größe von F_n angeben. Die Anzahl der Stellen erhält man 
trivial; es verbleibt lediglich den Logarithmus der Eigenwerte zu 
berechnen (und evtl. der Linearfaktoren).

Mehr als ein Taschenrechner für den einen Logarithmus braucht man nicht, 
und einen Computer schon garnicht. Das Computerergebnis ist zudem 
unbrauchbar solange man nicht eine Fehlerabschätzung macht, aber selbst 
damit ist der erste Ansatz deutlich elegenter und weitreichender.

Und so einen Ansatz als Kinderkram hinzustellen braucht schon einiges an 
Ignoranz und Überheblichkeit...

[Yalu X. (yalu) (Moderator)]

Johann L. schrieb:
> Yalu X. schrieb:
>> Auch wenn die Webseite "Euler" im Namen trägt, tritt der mathematische
>> Aspekt bei den Aufgaben leider etwas in den Hintergrund.
>
> Das kommt ganz auf den Ansetz an. Mit Brute Force ist der mathematische
> Aspekt perdu und der Schwierigkeitsgtrad darauf reduziert, eine
> Textaufgabe in eine Formel zu bekommen und ein paar Zeilen Code zu
> schreiben.

Das ist halt wie bei einem Berg: Ein Bergsteiger kann mit viel Geschick
den Berg manuell erklimmen, ein Ungeübter in Sandalen nimmt stattdessen
die Seilbahn. Ich glaube, die meisten Bergsteiger mögen lieber Berge
ohne Seilbahn, um auf dem Gipfel nicht Leuten mit Sandalen begegnen zu
müssen.

Bei vielen der Aufgaben in Project Euler führt ebenfalls eine Seilbahn
(in Form des Computers) den Berg hinauf. Bei Aufgabe 24 hätten die
Aufgabensteller die Seilbahn dadurch stilllegen können, dass sie statt
der millionsten Permutation aus 10 Symbolen nach der billionsten
Permutation aus 15 Symbolen gefragt hätten. Dass sie das nicht getan
haben, lässt vermuten, dass sie von den Teilnehmern erwarten, dass sie
ihren Computer benutzen.

Johann L. schrieb:
> Nochmals zurück zu Aufgabe #4: Ein Faktor ist zum Beispiel durch 11
> teilbar (warum?)

Sicher ist das aber nur, wenn man bereits herausgefunden hat, dass die
Lösung eine gerade Anzahl von Stellen hat.

P.S: Was hat Aufgabe 24 eigentlich mit Matrizen zu tun? Ich habe das
anders gelöst.

[Vlad T. (vlad_tepesch)]

Yalu X. schrieb:
> Die 10 fehlt noch ;-)
stimmt

>
> Aber so ist das nicht gemeint {T_n} ist eine unendlich Folge, {A_n}
> ebenso.Eine Zahl ist also auch dann in {A_n} enthalten, wenn ihre
> Binärdarstellung erst beim zigmillionsten Element von {T_n} auftaucht.

dann ist die Übersicht mit n und A_n aber irreführend, da die Variable n 
hier für zwei verschiedene Sachen steht.
Einmal nämlich als Platzhalter für eine quasi beliebige  grße Zahl und 
dann als konkreter Index für die sortierte Liste A_n

[Johann L. (gjlayde)]

Yalu X. schrieb:
> P.S: Was hat Aufgabe 24 eigentlich mit Matrizen zu tun? Ich habe das
> anders gelöst.

Upps, verwechselt mit Numero 25.

[Yalu X. (yalu) (Moderator)]

Vlad Tepesch schrieb:
> dann ist die Übersicht mit n und A_n aber irreführend, da die Variable n
> hier für zwei verschiedene Sachen steht.

Finde ich nicht. Das ist das Gleiche wie wenn du schreibst:

$$\sum_{i=0}^{n-1} a_i\quad\text{mit }a_i=2^i$$

Da kommt i ebenfalls zweimal vor, einmal als Laufvariable in der Summe,
das andere mal bei der Definition von a_i. Die Laufvariable ist sozusa-
gen lokal.

[Yalu X. (yalu) (Moderator)]

Johann L. schrieb:
> Die Werte der Folge ergeben sich als Linearkombination der Potenzen der
> Eigenwerte der Matrix, die durch die Rekursion gegeben ist. Weil ein
> Eigenwert > 1 ist und der andere betragsmäßig < 1, kann man die Näherung
> für die Größe von F_n angeben.

Du wirst aber zugeben, dass die Herleitung der nichtrekursiven Formel
die Fähigkeiten eines Nichtmathematikers leicht übersteigen könnte. Ich
kannte die Formel auswendig, somit hätte ich die Aufgabe schnell lösen
können. Hätte ich sie nicht gekannt und auch nirgends nachschlagen
können, wäre ich sicher stundenlang daran gesessen.

Ein ganz primitives Python-Skript hingegen ist in weniger als einer
Minute runtergehackt und braucht auf meinem Uralt-PC keine 0,3s:

a = 0
b = 1
n = 1
while len(str(b)) < 1000:
  a, b = b, a+b
  n += 1
print n

Auch hier die Frage: Warum haben die Aufgabensteller nicht nach der
ersten Fibonacci-Zahl gefragt, die mindestens eine Million Stellen 
hat?

[Mike M. (mikeii)]

public class prog {
  

  public static void main(String[] args) {
    
    
    int Zahl1,Zahl2;
    int product,biggest = 0;
    
      
      String a,b;

      for(Zahl1 = 100; Zahl1 < 1000; Zahl1++)
      {
          for(Zahl2 = 100; Zahl2 < 1000; Zahl2++)
          {
              product = Zahl1 * Zahl2;
              a = Long.toString(product);
              b = new StringBuffer(a).reverse().toString();
              if (a.equals(b))
              {
                if (product > biggest)
                {
                  biggest = product;
                }
              }              
          }
      }  
      System.out.println(biggest);
    

  }

}

[Johann L. (gjlayde)]

Yalu X. schrieb:
> Johann L. schrieb:
>> Die Werte der Folge ergeben sich als Linearkombination der Potenzen der
>> Eigenwerte der Matrix, die durch die Rekursion gegeben ist. Weil ein
>> Eigenwert > 1 ist und der andere betragsmäßig < 1, kann man die Näherung
>> für die Größe von F_n angeben.
>
> Du wirst aber zugeben, dass die Herleitung der nichtrekursiven Formel
> die Fähigkeiten eines Nichtmathematikers leicht übersteigen könnte.

Da steht:

> The motivation for starting Project Euler [...] is to provide
> a platform for the inquiring mind to delve into unfamiliar areas
> and learn new concepts [...].

Gegenfrage: Was hat man über Mathe gelernt, wenn man die paar Zeilen 
Python-oder-Perl-oder-was-auch-immer-Code hingeschrieben hat?

Lernen ist Arbeit, und auf eine Aufgabe wirklich einzusteigen und sich 
damit auseinander zu setzen brauch Zeit und Muße, die heutzutage kaum 
mehr jemand bereit aufzubringen bereit ist. Wenn man auf diese Aufgabe 
wirklich einsteigt, kann man Tage oder gar Wochen damit verbringen um 
seinen Bildungshorizont zu erweitern, ohne daß es je langweilig wird 
oder man am Ende der mathematischen Fahnenstange ankäme.

Ein paar Zeilen hinklatschen ist dagegen ziemlich fad und neue Einblicke 
gibt es keine — es sei denn, man möchte die Aufgaben wirklich hernehmen 
um eine neue Sprache zu erlernen.

Ich zumindest würde mit einen brute-force Ansatz recht bald die Lust 
verlieren, damit sind alle Aufgaben ziemlich flach und gleich...

[D. I. (Gast)]

Deswegen sucht man sich Aufgaben bei denen man gezwungen wird sich 
Gedanken zu machen ;) Und naja Project Euler ist halt schon sehr 
mathematisch, da ist mir persönlich die Aufgabenvariation zu einseitig, 
deswegen ist mir auch spoj.pl oder TopCoder lieber

[Yalu X. (yalu) (Moderator)]

Johann L. schrieb:
> Gegenfrage: Was hat man über Mathe gelernt, wenn man die paar Zeilen
> Python-oder-Perl-oder-was-auch-immer-Code hingeschrieben hat?

Nichts, aber der eine oder andere lernt auf diese Weise Programmieren,
wie es auch die Intention des Thread-Eröffners ist.

> Lernen ist Arbeit, und auf eine Aufgabe wirklich einzusteigen und sich
> damit auseinander zu setzen brauch Zeit und Muße, die heutzutage kaum
> mehr jemand bereit aufzubringen bereit ist. Wenn man auf diese Aufgabe
> wirklich einsteigt, kann man Tage oder gar Wochen damit verbringen um
> seinen Bildungshorizont zu erweitern, ohne daß es je langweilig wird
> oder man am Ende der mathematischen Fahnenstange ankäme.

Da stimme ich dir vollkommen zu. Ich ertappe mich oft genug dabei, dass
ich irgendwo eine Aufgabe sehe — sei es im täglichen Leben, in einem
Rätselbuch oder in einem Forum wie diesem —, die mir stunden-, tage-
oder wochenlang (dann aber mit Unterbrechungen :)) keine Ruhe lässt, bis
ich sie gelöst habe. Und fast immer kommt auch ein Erkenntnisgewinn
dabei heraus, weil man bspw. den Lösungsweg auch für andere Probleme
gewinnbringend einetzen kann.

Nur: Die Aufgaben in Project Euler entstammen weder aus dem täglichen
Leben noch steht von vorne herein fest, ob sie überhaupt mit akzeptablem
Aufwand ohne Computer lösbar sind.

Ein extremer (wenn auch etwas gestellter) Fall wäre nämlich folgender:

<hypothetischer_fall>
Angenommen, eine der Aufgaben wäre genauso schwer wie der Beweis der
Goldbachschen Vermutung. Aber natürlich weiß ich nichts über den Schwie-
rigkeitsgrad der Aufgabe.

Nach vielen Monaten intensiver Arbeit gelingt es mir tatsächlich, die
Lösung zu finden. Was wäre mein Gewinn? Zum einen ist da die Gewissheit,
nach langer Zeit eine Aufgabe gelöst zu haben. Aber möglicherweise war
sie in Wirklichkeit ja trivial, und ein anderer hätte sie in einer
Stunde gelöst. Ich kann nicht einmal meinen Lösungsweg mit anderen
diskutieren, weil diese ja alle stumpfsinnigerweise den Computer zu
Hilfe genommen haben.

Eine andere Form des Gewinns wäre der Unterhaltungswert während der
Lösungsfindung und ein großer Aha-Effekt am Ende. So etwas ist bspw. oft
in guten Rätselbüchern gegeben. Aber woher weiß ich im Voraus, dass das
auch bei den Project-Euler-Aufgaben der Fall ist? Es hat sich zumindest
keiner bemüht, die Ausgaben nach diesem Gesichtspunkt auszuwählen.

Da die Aufgabe aber (ohne es zu wissen) wirklich extrem schwer war, muss
ich extrem gut gewesen sein, um die Lösung zu finden. Folglich hätte ich
mit dem gleichen Aufwand vielleicht auch die Goldbachsche Vermutung
beweisen können. Der Gewinn hier: Das Gefühl, etwas wirklich Großes
geleistet zu haben und wissenschaftliches Renommee.

Warum sollte ich also meine Zeit mit Project-Euler-Aufgaben verplempern?
</hypothetischer_fall>

> Ein paar Zeilen hinklatschen ist dagegen ziemlich fad und neue Einblicke
> gibt es keine —

So ist es. Deswegen bin ich damals nach 63 durch Hinklatschen gelösten
Aufgaben auch aus der Sache ausgestiegen. Es kam einfach zu wenig Neues.

> Ich zumindest würde mit einen brute-force Ansatz recht bald die Lust
> verlieren, damit sind alle Aufgaben ziemlich flach und gleich...

Löst du denn regelmäßig ein paar von diesen Aufgaben mit mathematischen
Ansätzen? Diese Frage ist nicht etwa rhetorisch, sondern: Wenn du
wirklich interessante und lösbare Aufgaben darunter gefunden hast,
könntest du ein paar Links dahin posten. Das wären dann sicher Aufgaben
mit sehr hohem Unterhaltungswert.

[Mike M. (mikeii)]

Sorry, aber folgende Sachen konnte ich nicht ohne PC lösen:

http://projecteuler.net/problem=5
http://projecteuler.net/problem=7
http://projecteuler.net/problem=59
http://projecteuler.net/problem=67


Soviel Papier hab ich nicht da :(

[Vlad T. (vlad_tepesch)]

Mike Mike schrieb:
> Sorry, aber folgende Sachen konnte ich nicht ohne PC lösen:

soll man imho auch gar nicht.
wenn man die Aufgaben der Reihe nach löst baut man sich eine kleine 
Beibliothek auf.
Die erste Lösung zur Ermittlung von Primzahlen kann durchaus aus 
Brutforce bestehen. Aber meist ist dann bei der nächsten entsprechenden 
Aufgabe dieser Ansatz nicht mehr zielführend, so dass man sich weitere 
Gedanken machen muss, wie man das optimiert. nach der Lösung einer 
Aufgabe, gibts ja manchmal auch noch ein PDF oder einen Forenthread 
durch den man weiter an das Thema rankommt und die Lösung verbessern 
kann.

[Yalu X. (yalu) (Moderator)]

Mike Mike schrieb:
> Sorry, aber folgende Sachen konnte ich nicht ohne PC lösen:

Für Problem 5 sollte aber doch ein Taschenrechner genügen, es sei denn,
du gehst noch in die Grundschule. Früher war das im Gymnasium Stoff der
5. oder 6. Klasse, wenn ich mich recht erinnere.

Bei den drei anderen Problemen hast du aber recht. Bei Problem 59 und 67
muss man größere Datenmengen schaufeln, was man besser nicht von Hand
tut. Bei Problem 7 warten wir noch darauf, dass die Mathematiker eine
geschlossene Formel finden, die für ein beliebiges n die n-te Primzahl
liefert.

Es gibt noch viele Aufgaben von dieser Sorte. Manchen (wie bei 7, 59 und
67) sieht man es sofort an, dass man ohne Computer nicht viel weiter
kommt, anderen erst, nachdem man ein paar Stunden herumprobiert hat :)

[Mark B. (markbrandis)]

Yalu X. schrieb:
> Bei den drei anderen Problemen hast du aber recht. Bei Problem 59 und 67
> muss man größere Datenmengen schaufeln, was man besser nicht von Hand
> tut. Bei Problem 7 warten wir noch darauf, dass die Mathematiker eine
> geschlossene Formel finden, die für ein beliebiges n die n-te Primzahl
> liefert.
>
> Es gibt noch viele Aufgaben von dieser Sorte. Manchen (wie bei 7, 59 und
> 67) sieht man es sofort an, dass man ohne Computer nicht viel weiter
> kommt, anderen erst, nachdem man ein paar Stunden herumprobiert hat :)

Aber das kann ja nicht sein: Laut unseres Experten Johann L. muss man 
doch alle Aufgaben durch Nachdenken und maximal mit Bleistift und Papier 
lösen können. Denn sonst hat man ja nichts gelernt und der edlen 
Mathematik nicht genüge getan. Code schreiben? Teufelszeug!

[Bartli (Gast)]

Ach, lesen wir uns doch einfach nochmals durch, was die Nasen auf ihrer 
Website so schreiben: http://projecteuler.net.

"Project Euler is a series of challenging mathematical/computer 
programming problems that will require more than just mathematical 
insights to solve. Although mathematics will help you arrive at elegant 
and efficient methods, the use of a computer and programming skills will 
be required to solve most problems."

Alles klar?

[Mike M. (mikeii)]

BUSTED!

Jedes Problem hat seine eigenen Problemlösungen

[Johann L. (gjlayde)]

Yalu X. schrieb:
> Johann L. schrieb:
>> Lernen ist Arbeit, und auf eine Aufgabe wirklich einzusteigen und sich
>> damit auseinander zu setzen brauch Zeit und Muße, die heutzutage kaum
>> mehr jemand bereit aufzubringen bereit ist. Wenn man auf diese Aufgabe
>> wirklich einsteigt, kann man Tage oder gar Wochen damit verbringen um
>> seinen Bildungshorizont zu erweitern, ohne daß es je langweilig wird
>> oder man am Ende der mathematischen Fahnenstange ankäme.
>
> Da stimme ich dir vollkommen zu. Ich ertappe mich oft genug dabei, dass
> ich irgendwo eine Aufgabe sehe — sei es im täglichen Leben, in einem
> Rätselbuch oder in einem Forum wie diesem —, die mir stunden-, tage-
> oder wochenlang (dann aber mit Unterbrechungen :)) keine Ruhe lässt, bis
> ich sie gelöst habe. Und fast immer kommt auch ein Erkenntnisgewinn
> dabei heraus, weil man bspw. den Lösungsweg auch für andere Probleme
> gewinnbringend einetzen kann.

Geht mir auch so, und manchmal schreib ich auch was dazu wie in
http://gjlay.de/pub/von-punkt-zu-punkt.pdf
Beitrag "Wie Parametrisierung für Kurve finden?"
Ohne Rechner wäre da auch nix zu wollen.

> Nur: Die Aufgaben in Project Euler entstammen weder aus dem täglichen
> Leben noch steht von vorne herein fest, ob sie überhaupt mit akzeptablem
> Aufwand ohne Computer lösbar sind.
> [...]
> Eine andere Form des Gewinns wäre der Unterhaltungswert während der
> Lösungsfindung und ein großer Aha-Effekt am Ende. So etwas ist bspw. oft
> in guten Rätselbüchern gegeben. Aber woher weiß ich im Voraus, dass das
> auch bei den Project-Euler-Aufgaben der Fall ist? Es hat sich zumindest
> keiner bemüht, die Ausgaben nach diesem Gesichtspunkt auszuwählen.

Leider sieht man den Aufgaben nicht an, was da an mathematischer 
Substanz drin steckt. Auch wenn man die Mathe nicht direkt zur Lösung 
verwenden kann, wäre ein Ausblick auf die mathematische Landschaft nicht 
fehl am Platze. Leider gibt es weder sowas wie ein Tutor, der einen 
darauf hinweisen könnte, und Nachfragen ist offenbar verpönt. Zudem 
verstellt die Allverfügbarkeit von Rechnern allzu oft die Bereitschaft, 
die grauen Zellen anzukurbeln.

>> Ich zumindest würde mit einen brute-force Ansatz recht bald die Lust
>> verlieren, damit sind alle Aufgaben ziemlich flach und gleich...
>
> Löst du denn regelmäßig ein paar von diesen Aufgaben mit mathematischen
> Ansätzen? Diese Frage ist nicht etwa rhetorisch, sondern: Wenn du
> wirklich interessante und lösbare Aufgaben darunter gefunden hast,
> könntest du ein paar Links dahin posten. Das wären dann sicher Aufgaben
> mit sehr hohem Unterhaltungswert.

Die Seite war mir bislang unbekannt.  An zu lösenden Aufgaben mangelt es 
mir nicht, von daher min ich auf so eine Seite nicht angewiesen :o)

Beim Überfliegen der Aufgaben ist mir nur aufgefallen, daß einige sich 
sehr elegant lösen lassen, stattdessen aber lieber die Rechnerkeule 
geschwungen wird.

Mike Mike schrieb:
> Sorry, aber folgende Sachen konnte ich nicht ohne PC lösen:
>
> http://projecteuler.net/problem=5

Die gesuchte Zahl kann man so hinschreiben:

$$m = \operatorname{kgV}(1, \ldots, 20)$$

also

$$m = \prod p_i^{n_i} \quad\text{mit}\quad n_i = \max \{n\in\N_0 \;|\; p_i^n \leqslant 20\}$$

> http://projecteuler.net/problem=7

Meines Wissens ist bislang keine geschlossene Formel zur Darstellung der 
n-ten Primzahl bekannt, Mittel der Wahl ist ein Sieb. Um eine 
Vorstellung von der Größenordnung von p_10001 zu bekommen, würd ich mir 
p(n) abschauen bzw. eine Näherung für p wie n/ln(n).

> http://projecteuler.net/problem=59

Kryptanalyse oder Datamining sind aufwändig, ohne Computer kommt man oft 
nicht weiter. Aber ohne Idee wird einem auch ein Superrechner nicht 
weiterhelfen.

> http://projecteuler.net/problem=67

Hier wird schon darauf hingewiesen, daß es um einen geschickten 
Algorithmus geht (Algorithmus = Computer) und daß man mit brute-force 
keinen Stich macht.

Mark Brandis schrieb:

Was für'n Quark...