Das hammerharte Zahlenrätsel - Die Lösung

Worum geht es hier? Wir müssen verstehen, was die Gespräche uns für Hinweise geben. Wir müssen aus der Gesamtmenge der Zahlenpaare zwischen 1 und 1000 mit jedem neuen Hinweis diejenigen entfernen, die den Anforderungen nicht mehr genügen.

Wen dieser ganze SQL-Quatsch nicht interessiert, der kann sich natürlich auch einfach nur die gesuchten Zahlen ansehen.

Vorbereitung: die Liste der Zahlenpaare

Wir erzeugen eine Tabelle mit Zahlen von 1 bis 1000. Der Feldtyp identity sorgt dafür, dass SQL mit jeder Zeile, die es in der Tabelle anlegt, einen Wert weiterzählt. Was wir also als "Nutzwert" in die Tabelle schreiben, ist für uns ein nutzloser Nutzwert, deswegen nehmen wir immer Null. Könnte auch 42 sein :-)
Wir kopieren so lange den Tabelleninhalt in die Tabelle, bis durch diese Verdopplungen der Anzahl von Zeilen die Gesamtzahl mindestens 1000 ist. Was zuviel ist, also größer 1000, wird abgeschnitten.

create table Zahl (zahl int identity, nutzlos int)
insert into Zahl (nutzlos) values (0)
while (select count(1) from Zahl) < 1000
	insert into Zahl (nutzlos) select nutzlos from Zahl
delete Zahl where zahl > 1000

Man möge mir verzeihen, dass ich SQL-Keywords klein schreibe. Ein ANSI SQL Parser verzeiht mir das. Unter echten Datenbank-Programmieren ist es freilich verpönt, aber wir wollen hier ja in erster Linie ein Rätsel lösen und nicht programmieren.

Jetzt haben wir eine Tabelle mit Zahlen. Wir wollen eine Tabelle mit Faktoren Schrägstrich Summanden, nämlich eine Tabelle mit Zahlenpaaren. Sowohl die Multiplikation als auch die Addition sind kommutativ - das Zahlenpaar (X, Y) ist für unsere Lösung identisch zu (Y, X). Zwar ist die Subtraktion nicht kommutativ, doch wenn man die Angaben studiert, dann wird nirgends erwähnt, welche der beiden Differenzen der zwei Zahlen (die Positive oder die Negative) Daniel verraten wird. Deswegen ist offensichtlich nur der Betrag der Differenz interessant. Wir nehmen also nicht alle Zahlenpaare in unsere Tabelle auf, sondern nur diejenigen, bei denen die zweite Zahl größer oder gleich der ersten Zahl ist.
Dieses Statement kann durchaus ein paar Minütchen brauchen ...

create table Paar (X int, Y int, produkt int, summe int, differenz int)
insert into Paar
select X.zahl, Y.zahl,
	X.zahl * Y.zahl,
	X.zahl + Y.zahl,
	Y.zahl - X.zahl
from Zahl as X
inner join Zahl as Y on Y.zahl >= X.zahl

Warum wir jetzt genau 500500 Zeilen in der Tabelle Paar haben, kann man unter dem Stichwort Der kleine Gauß nachlesen :-)

Peter sagt zu den anderen: "ich kann die Lösung nicht nennen".

Peter kennt das Produkt zweier Zahlen zwischen 1 und 1000. Er könnte die Lösung nennen, wenn es eine Primzahl wäre, denn dann wäre das Produkt gleich dem einen Faktor und der andere wäre 1. Er könnte die Lösung ebenfalls nennen, wenn es das Produkt zweier Primzahlen und es zugleich größer 1000 wäre, denn in dem Fall würde die Lösung mit der 1 nicht funktionieren.
Allgemein formuliert, hat es mit Primzahlen wenig zu tun. Die Information, die Peter uns gibt, wenn er sagt, dass er die Lösung nicht nennen kann, ist lediglich, dass seine Zahl sich auf mehr als eine Art als das Produkt aus zwei Zahlen zwischen 1 und 1000 ausdrücken lässt. Die Zahl 5055 zum Beispiel ist in der Primfaktorenzerlegung 3 x 5 x 337. Sie kann aber nur als 15 x 337 durch zwei Zahlen zwischen 1 und 1000 ausgedrückt werden, denn sowohl bei 3 x 1685 als auch bei 5 * 1011 ist der zweite Faktor größer als 1000.
Wir verwenden bei dieser Überlegungen zwar die Primfaktorzerlegung, aber wir sehen dadurch auch, dass es keine offensichtliche Ableitung gibt, die uns entscheidende Informationen über die Eigenschaften der gesuchten Zahlen gibt. Alles, was wir bis jetzt erkennen, sind Eigenschaften der Lösungsmenge als Ganzem.

Wir suchen nach der Menge der Produkte, die in der Auflistung aller Produkte aus zwei Zahlen zwischen 1 und 1000 mehrfach auftauchen. Wir erzeugen dazu eine Tabelle der Produkte und zählen, wie viele Faktorenpaare jedes Produkt ergeben.

create table Produkt (produkt int, anzahl int)
insert into Produkt
select produkt, count(1)
from Paar
group by produkt

Die gute Nachricht: es gibt jetzt nur noch 103360 mögliche Produkte mit lumpigen 355777 denkbaren Kombinationen von Faktoren. Hurra!

select count(distinct produkt) as Produkte,
	count(1) as Kombinationen
from Paar
where produkt in (select produkt
	from Produkt
	where anzahl > 1)

Zurück zum Rätsel - Weiter zu Schritt 2