Was macht man, wenn man im Zug von Paris nach Aachen sitzt und plötzlich das Bedürfnis verspürt, ein Problem, das einen schon länger beschäftigt, weil es so spannend ist, effizient zu lösen? Hier die Antwort: man hört Musik und hangelt sich von Version zu Version, bis nichts Verständliches mehr übrig bleibt:
#include <iostream>
include <map>
using namespace std;typedef size_t T;typedef map<T, T>M;T sn(T n){T s=0;while(n>0){s+=(n%10)(n%10);n/= 10;}return s;}int main(int argc,char argv[]){T a=1 ,b=100;if(argc>1){a=atoi(argv[1]);b=a;}if(argc>2){b =atoi(argv[2]);}T x=a;M l,e;while(x<b+1){M si;T c=x ;T eq=0;while(1){T s=sn(c); if(c==x){if(e.find(s)!= e.end()){l[e[s]]++;break;}eq=s;}if(si.find(s)!=si.\ end() ){if(l.find(s)!=l.end())l[s]++;else l[s]=1;e[ eq]=s;break;}else{si[s]=1;c=s;}}++x;}for(M::const_\ iterator i=l.begin();i!=l.end(); ++i)cout<<i->first <<" "<<i->second<<endl;return 0;}
Und hier eure Preise (Susanne darf leider nur beim 2. Punkt mitmachen): 😉
- 1 Getränk eurer Wahl in der Pontstraße, wenn ihr mir sagt, was das Programm löst.
- 1 Essen eurer Wahl in der Pontstraße, wenn ihr eine Version schreibt, die schneller ist.
Einsendeschluss ist Donnerstag, der 28.06.2007. Danach bin ich nämlich weg. Viel Erfolg!
Ach, einen Hinweis gebe ich euch (copy-paste in eine Datei, z.B. bretzel.cc):
$ g++ -O3 -o bretzel bretzel.cc
$ ./bretzel 1 10000000
Def. Querquadratsumme Sei n eine natürliche Zahl, dann heißt die Summe der Quadrate aller Ziffern aus n Querquadratsumme (qqd).
Def. Querquadratsummenreihe Sei n eine natürliche Zahl und a0 = qqd(n) und a[i] = qqd(a[i-1]) für i > 0. Wir nennen die Folge a[i] Querquadratsummenreihe von n.
Def. Querquadratsummenreihenkreis Gilt für eine Querquadratsummenreihe a[i] und zwei Indizes i != j: a[i] = a[j] und alle Elemente zwischen a[i] und a[j] paarweise unterschiedlich, nennen wir a[i] bis a[j-1] einen Querquadratsummenreihenkreis, wenn i mit dieser Eigenschaft minimal ist. Das a[i] dieses Querquadratsummenreihenkreises nennen wir Querquadratsummenreihenkreisanfang. Es gibt also (bis auf rotation) äquivalente Querquadratsummenreihenkreise mit unterschiedlichen Querquadratsummenreihenkreisanfängen.
Korollar Existiert in der Querquadratsummenreihe einer Zahl ein Querquadratsummenreihenkreis, so gibt es in der Querquadratsummenreihe nur endlich viele unterschiedliche Elemente.
Theorem von Hasan (vielleicht tu ich da jemandem unrecht, ich habe nicht recherchiert) Für jede natürliche Zahl n gilt, dass ihre Querquadratsummenreihe einen Kreis besitzt. Weiter gilt, dass alle Zahl n und m, wenn sie einen äquivalenten Querquadratsummenreihenkreis besitzen, auch der Querquadratsummenreihenkreisanfang der gleiche ist. Fasst man solche Zahlen n und m in Äquivalenzklassen, so fällt auf, dass es davon erstaunlich wenig gibt. Eine Abschätzung dieser Anzahl von Äquivalenzklassen von Zahlen, die unter n liegen, ist bislang nicht bekannt, ebenfalls nicht, ob es vielleicht nur endlich viele gibt.
Further investigation would be beyond the scope of this paper.
Du sollst arbeiten und nicht Pontstraßengetränkegutscheine sammeln. 😉 Oh Mann, du bist irre.