Hans Walser, [20250727]

100 Punkte

1 Worum es geht

Verschiedene Methoden zur Lösung eines zahlentheoretischen Problems.

2 Problemstellung

Wie viele Punkte mit ganzzahligen Koordinaten gibt es auf der durch die Gleichung

xyz = 1000, x > 0, y > 0, z > 0

definierten Fläche?

Kommentare:

(1) Vermutlich steht im Titel die Lösung. Hat das Ganze mit dem Dezimalsystem zu tun?

(2) Die Abbildung 1 zeigt die durch die Gleichung xyz = 1000, x > 0, y > 0, z > 0 definierte Fläche.

Abb. 1: Fläche

Eine naheliegende Lösung ist [10, 10, 10]. Der zugehörige Punkt liegt in der „Mitte“ (Abb. 2, 3, 4).

Ebenfalls naheliegend ist zum Beispiel die Lösung [1000, 1, 1]. Der zugehörige Punkt liegt janz weit außen.

Das zugehörige zahlentheoretische Problem ist:

Gesucht sind ganzzahligen Lösungen [x, y, z], x ∈ ℕ, y ∈ ℕ, z ∈ ℕ der diophantischen Gleichung:

xyz = 1000

3 Lösungsmethoden

3.1 Brute force

Wir gehen alle Tripel [x, y, z], x ∈ {1, ... , 1000}, y ∈ {1, ... , 1000}, z ∈ {1, ... , 1000} durch und schauen, ob sie der diophantischen Gleichung xyz = 1000 genügen.

Der Rechenweg kann etwa so aussehen:

n := 1000:

m := 0:

for x from 1 to n do

for y from 1 to n do

for z from 1 to n do

if x*y*z = n then

m := m+1:

print(m, [x,y,z]):

end:

end:

end:

end:

Die Tabelle 1 zeigt die tatsächlich 100 Lösungen.

m	Lösung	m	Lösung	m	Lösung	m	Lösung
1	[1, 1, 1000]	26	[2, 125, 4]	51	[8, 25, 5]	76	[40, 1, 25]
2	[1, 2, 500]	27	[2, 250, 2]	52	[8, 125, 1]	77	[40, 5, 5]
3	[1, 4, 250]	28	[2, 500, 1]	53	[10, 1, 100]	78	[40, 25, 1]
4	[1, 5, 200]	29	[4, 1, 250]	54	[10, 2, 50]	79	[50, 1, 20]
5	[1, 8, 125]	30	[4, 2, 125]	55	[10, 4, 25]	80	[50, 2, 10]
6	[1, 10, 100]	31	[4, 5, 50]	56	[10, 5, 20]	81	[50, 4, 5]
7	[1, 20, 50]	32	[4, 10, 25]	57	[10, 10, 10]	82	[50, 5, 4]
8	[1, 25, 40]	33	[4, 25, 10]	58	[10, 20, 5]	83	[50, 10, 2]
9	[1, 40, 25]	34	[4, 50, 5]	59	[10, 25, 4]	84	[50, 20, 1]
10	[1, 50, 20]	35	[4, 125, 2]	60	[10, 50, 2]	85	[100, 1, 10]
11	[1, 100, 10]	36	[4, 250, 1]	61	[10, 100, 1]	86	[100, 2, 5]
12	[1, 125, 8]	37	[5, 1, 200]	62	[20, 1, 50]	87	[100, 5, 2]
13	[1, 200, 5]	38	[5, 2, 100]	63	[20, 2, 25]	88	[100, 10, 1]
14	[1, 250, 4]	39	[5, 4, 50]	64	[20, 5, 10]	89	[125, 1, 8]
15	[1, 500, 2]	40	[5, 5, 40]	65	[20, 10, 5]	90	[125, 2, 4]
16	[1, 1000, 1]	41	[5, 8, 25]	66	[20, 25, 2]	91	[125, 4, 2]
17	[2, 1, 500]	42	[5, 10, 20]	67	[20, 50, 1]	92	[125, 8, 1]
18	[2, 2, 250]	43	[5, 20, 10]	68	[25, 1, 40]	93	[200, 1, 5]
19	[2, 4, 125]	44	[5, 25, 8]	69	[25, 2, 20]	94	[200, 5, 1]
20	[2, 5, 100]	45	[5, 40, 5]	70	[25, 4, 10]	95	[250, 1, 4]
21	[2, 10, 50]	46	[5, 50, 4]	71	[25, 5, 8]	96	[250, 2, 2]
22	[2, 20, 25]	47	[5, 100, 2]	72	[25, 8, 5]	97	[250, 4, 1]
23	[2, 25, 20]	48	[5, 200, 1]	73	[25, 10, 4]	98	[500, 1, 2]
24	[2, 50, 10]	49	[8, 1, 125]	74	[25, 20, 2]	99	[500, 2, 1]
25	[2, 100, 5]	50	[8, 5, 25]	75	[25, 40, 1]	100	[1000, 1, 1]

Tab. 1: 100 Lösungen

Kommentare

(1) Die Lösungen sind lexikografisch geordnet.

(2) Es müssen 1000³ = 1 000 000 000 Fälle untersucht werden. Der Computer braucht auch entsprechend lange (acht Minuten). Die Hälfte der Arbeitszeit wird für den letzten Schritt von der 99. Lösung zur 100. Lösung verbraucht.

3.2 Defensiv

Wegen 1000 = 2³•5³ dürfen auch die Lösungen nur die Primfaktoren 2 und/oder 5 enthalten.

Wir können also unsere Suche auf Vielfache von 2 und/oder 5 beschränken. Dabei darf die 1 nicht vergessen werden. Da es zwischen 1 und 1000 genau 500 gerade Zahlen, 100 ungerade durch 5 teilbare Zahlen und eine 1 gibt, haben wir noch 601³ = 217 081 801 Fälle zu untersuchen. Also weniger als ein Viertel im Vergleich zur brute-force-Methode.

Der Rechenweg kann etwa so aussehen:

n := 1000:

m := 0:

for x from 1 to n do

if modp(x,2) = 0 or modp(x,5) = 0 or x = 1 then

for y from 1 to n do

if modp(y,2) = 0 or modp(y,5) = 0 or y = 1 then

for z from 1 to n do

if modp(z,2) = 0 or modp(z,5) = 0 or z = 1 then

if x*y*z = n then

m := m+1:

print(m, [x,y,z]):

end:

end:

end:

end:

end:

end:

end:

Wir erhalten wiederum die Lösungen der Tabelle 1, und dies in derselben Anordnung. Die Rechenzeit ist immer noch groß (sechs Minuten).

3.3 Aktives Auswählen

Wegen der Primfaktorzerlegung 1000 = 2³•5³ können in den drei Faktoren x, y und z nur insgesamt die sechs Primfaktoren aus {2, 2, 2, 5, 5, 5} vorkommen. Wir müssen also sowohl die drei Primfaktoren 2 wie auch die drei Primfaktoren 5 auf die drei Zahlen x, y und z verteilen. Die Aufteilung braucht nicht gleichmäßig zu sein (sonst gäbe es nur die Lösung x = 2•5 = 10, y = 2•5 = 10 und z = 2•5 = 10). Wenn eine der die Zahlen x, y und z bei der Primfaktorzuteilung leer ausgeht, erhält sie den Faktor 1.

Was speziell die drei Primfaktoren 2 angeht, müssen wir also drei Elemente auf die drei Zahlen x, y und z verteilen. Dazu gibt es

Möglichkeiten. Vorstellung: auf 5 Plätze müssen wir drei Elemente und zwei Trennstriche setzen. Also aus fünf Plätzen zwei für die Trennstriche auswählen.

Ebenso gibt es 10 mögliche Aufteilung der drei Primfaktoren 5 auf die drei Zahlen x, y und z. Somit gibt es insgesamt 10•10 = 100 Möglichkeiten der Aufteilung der sechs Primfaktoren auf die drei Zahlen x, y und z. Wir sehen, dass die Anzahl 100 der möglichen Lösungen nicht unmittelbar aus dem Dezimalsystem folgt.

Nachfolgend ein möglicher Rechenweg zur Bestimmung der 100 Lösungen. Bei diesem Rechenweg ist die Testrechnung xyz nicht erforderlich.

p1 := 2; # erster Primfaktor

p2 := 5; # zweiter Primfaktor

m := 0:

for lax from 0 to 3 do

for lay from 0 to 3 - lax do

laz := 3 - lax - lay:

for mux from 0 to 3 do

for muy from 0 to 3-mux do

muz := 3 - mux - muy:

m := m+1:

x := p1^lax*p2^mux:

y := p1^lay*p2^muy:

z := p1^laz*p2^muz:

print(m, [x, y, z]):

end:

end:

end:

end:

Dies führt auf die Lösungen der Tabelle 2. Inhaltlich stimmt sie mit der Tabelle 1 überein, hat aber eine andere Anordnung.

m	Lösung	m	Lösung	m	Lösung	m	Lösung
1	[1, 1, 1000]	26	[5, 20, 10]	51	[2, 2, 250]	76	[20, 5, 10]
2	[1, 5, 200]	27	[5, 100, 2]	52	[2, 10, 50]	77	[20, 25, 2]
3	[1, 25, 40]	28	[25, 4, 10]	53	[2, 50, 10]	78	[100, 1, 10]
4	[1, 125, 8]	29	[25, 20, 2]	54	[2, 250, 2]	79	[100, 5, 2]
5	[5, 1, 200]	30	[125, 4, 2]	55	[10, 2, 50]	80	[500, 1, 2]
6	[5, 5, 40]	31	[1, 8, 125]	56	[10, 10, 10]	81	[4, 2, 125]
7	[5, 25, 8]	32	[1, 40, 25]	57	[10, 50, 2]	82	[4, 10, 25]
8	[25, 1, 40]	33	[1, 200, 5]	58	[50, 2, 10]	83	[4, 50, 5]
9	[25, 5, 8]	34	[1, 1000, 1]	59	[50, 10, 2]	84	[4, 250, 1]
10	[125, 1, 8]	35	[5, 8, 25]	60	[250, 2, 2]	85	[20, 2, 25]
11	[1, 2, 500]	36	[5, 40, 5]	61	[2, 4, 125]	86	[20, 10, 5]
12	[1, 10, 100]	37	[5, 200, 1]	62	[2, 20, 25]	87	[20, 50, 1]
13	[1, 50, 20]	38	[25, 8, 5]	63	[2, 100, 5]	88	[100, 2, 5]
14	[1, 250, 4]	39	[25, 40, 1]	64	[2, 500, 1]	89	[100, 10, 1]
15	[5, 2, 100]	40	[125, 8, 1]	65	[10, 4, 25]	90	[500, 2, 1]
16	[5, 10, 20]	41	[2, 1, 500]	66	[10, 20, 5]	91	[8, 1, 125]
17	[5, 50, 4]	42	[2, 5, 100]	67	[10, 100, 1]	92	[8, 5, 25]
18	[25, 2, 20]	43	[2, 25, 20]	68	[50, 4, 5]	93	[8, 25, 5]
19	[25, 10, 4]	44	[2, 125, 4]	69	[50, 20, 1]	94	[8, 125, 1]
20	[125, 2, 4]	45	[10, 1, 100]	70	[250, 4, 1]	95	[40, 1, 25]
21	[1, 4, 250]	46	[10, 5, 20]	71	[4, 1, 250]	96	[40, 5, 5]
22	[1, 20, 50]	47	[10, 25, 4]	72	[4, 5, 50]	97	[40, 25, 1]
23	[1, 100, 10]	48	[50, 1, 20]	73	[4, 25, 10]	98	[200, 1, 5]
24	[1, 500, 2]	49	[50, 5, 4]	74	[4, 125, 2]	99	[200, 5, 1]
25	[5, 4, 50]	50	[250, 1, 4]	75	[20, 1, 50]	100	[1000, 1, 1]

Tab. 2: Andere Anordnung

4 Produkt = 216

Die Anzahl der Lösungen hängt offenbar nur von der Struktur der Primzahlzerlegung des geforderten Produktes xyz ab, nicht von der Zahl oder ihren Primfaktoren selber.

Die Zahl 216 = 2³•3³ hat dieselbe Struktur der Primzahlzerlegung wie die Zahl 1000. Daher gibt es auch in diesem Fall genau 100 Lösungen. Wir brauchen im obigen Rechenweg lediglich den zweiten Primfaktor auf 3 abzuändern. Dies führt auf die Tabelle 3.

m	Lösung	m	Lösung	m	Lösung	m	Lösung
1	[1, 1, 216]	26	[3, 12, 6]	51	[2, 2, 54]	76	[12, 3, 6]
2	[1, 3, 72]	27	[3, 36, 2]	52	[2, 6, 18]	77	[12, 9, 2]
3	[1, 9, 24]	28	[9, 4, 6]	53	[2, 18, 6]	78	[36, 1, 6]
4	[1, 27, 8]	29	[9, 12, 2]	54	[2, 54, 2]	79	[36, 3, 2]
5	[3, 1, 72]	30	[27, 4, 2]	55	[6, 2, 18]	80	[108, 1, 2]
6	[3, 3, 24]	31	[1, 8, 27]	56	[6, 6, 6]	81	[4, 2, 27]
7	[3, 9, 8]	32	[1, 24, 9]	57	[6, 18, 2]	82	[4, 6, 9]
8	[9, 1, 24]	33	[1, 72, 3]	58	[18, 2, 6]	83	[4, 18, 3]
9	[9, 3, 8]	34	[1, 216, 1]	59	[18, 6, 2]	84	[4, 54, 1]
10	[27, 1, 8]	35	[3, 8, 9]	60	[54, 2, 2]	85	[12, 2, 9]
11	[1, 2, 108]	36	[3, 24, 3]	61	[2, 4, 27]	86	[12, 6, 3]
12	[1, 6, 36]	37	[3, 72, 1]	62	[2, 12, 9]	87	[12, 18, 1]
13	[1, 18, 12]	38	[9, 8, 3]	63	[2, 36, 3]	88	[36, 2, 3]
14	[1, 54, 4]	39	[9, 24, 1]	64	[2, 108, 1]	89	[36, 6, 1]
15	[3, 2, 36]	40	[27, 8, 1]	65	[6, 4, 9]	90	[108, 2, 1]
16	[3, 6, 12]	41	[2, 1, 108]	66	[6, 12, 3]	91	[8, 1, 27]
17	[3, 18, 4]	42	[2, 3, 36]	67	[6, 36, 1]	92	[8, 3, 9]
18	[9, 2, 12]	43	[2, 9, 12]	68	[18, 4, 3]	93	[8, 9, 3]
19	[9, 6, 4]	44	[2, 27, 4]	69	[18, 12, 1]	94	[8, 27, 1]
20	[27, 2, 4]	45	[6, 1, 36]	70	[54, 4, 1]	95	[24, 1, 9]
21	[1, 4, 54]	46	[6, 3, 12]	71	[4, 1, 54]	96	[24, 3, 3]
22	[1, 12, 18]	47	[6, 9, 4]	72	[4, 3, 18]	97	[24, 9, 1]
23	[1, 36, 6]	48	[18, 1, 12]	73	[4, 9, 6]	98	[72, 1, 3]
24	[1, 108, 2]	49	[18, 3, 4]	74	[4, 27, 2]	99	[72, 3, 1]
25	[3, 4, 18]	50	[54, 1, 4]	75	[12, 1, 18]	100	[216, 1, 1]

Tab. 3: Anderes Beispiel

5 Zurück zur Geometrie

In der Abbildung 2 sind einige der 100 Punkte eingezeichnet. Ausreißer mit Werten > 30 sind nicht auf dem Bild.

Abb. 2: Punkte

Die Punkte liegen auf Niveaulinien (Abb. 3). Die Niveaus 2, 4, 5, 8, 10, ... , 500 sind die Teiler von 1000. Die Niveaulinien für Niveaus > 30 liegen außerhalb des Bildes.

Die Niveaulinien sind Hyperbeln.

Abb. 3: Niveaulinien

Die Niveaulinien in der Abbildung 3 beziehen sich auf die z-Richtung. Aus Symmetriegründen gibt es entsprechende Niveaulinien für die x- und die y-Richtung (Abb. 4).

Abb. 4: Drei Scharen von Niveaulinien

Weblinks

Hans Walser: Konstantes Produkt

https://walser-h-m.ch/hans/Miniaturen/K/Konstantes_Produkt/Konstantes_Produkt.html

Hans Walser: Summe = Produkt

https://walser-h-m.ch/hans/Miniaturen/S/Summe=Produkt3/Summe=Produkt3.html

Hans Walser: Summe = Produkt

https://walser-h-m.ch/hans/Miniaturen/S/Summe=Produkt4/Summe=Produkt4.html