Lösungen einer Diophantische Gleichung in N

01.10.2008, 22:34

lostgeek

Lösungen einer Diophantische Gleichung in N

Hi,

Ich hänge gerade bei Problem 108 bei Project Euler.

Es geht um folgende Diophantische Gleichung:

$\begin{eqnarray*} \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \end{eqnarray*}$

Gesucht ist das n, bei dem die Anzahl der Lösungen das erste Mal über 1000 steigt.

Ich habe nach y aufgelöst und kam auf $\begin{eqnarray*} y = \frac{x}{\frac{x}{n}-1} \end{eqnarray*}$

Ich habe gemerkt, dass y für $\begin{eqnarray*} x > n \end{eqnarray*}$ gegen n konvergiert.

Also dacht ich mir, dass ich für x, anfangend bei n+1, soweit Werte einsetzen muss, bis $\begin{eqnarray*} n \leq x \leq n+1 \end{eqnarray*}$ , weil es danach keine ganzzahligen y Werte mehr geben kann.

Wenn ich für n = 1260 die Anzahl der Lösungen berechne komme ich auf 108 Lösungen.
Bei Aufgabe 110 steht aber (zur selben Gleichung): "It can be verified that when n = 1260 there are 113 distinct solutions"
Seht ihr den Fehler?

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	double y = n+1; // Um die Anfangsbedingung der For-Schleife zu erfüllen. for(double x = n+1; y >= n+1 ; x++) { y = x/((x/n)-1); if(y == (int)y) { count++; } }

02.10.2008, 00:13

Auf diesen Beitrag antworten »

Umgestellt bedeutet diese Gleichung $\begin{eqnarray*} (x-n)(y-n) = n^2 \end{eqnarray*}$ , für $\begin{eqnarray*} n=1260=2^2\cdot 3^2\cdot 5\cdot 7 \end{eqnarray*}$ heißt das dann

$\begin{eqnarray*} (x-1260)(y-1260) = 2^4\cdot 3^4\cdot 5^2\cdot 7^2 \end{eqnarray*}$ ,

diese Gleichung hat genau $\begin{eqnarray*} 2\cdot 5\cdot 5\cdot 3\cdot 3 = 450 \end{eqnarray*}$ ganzzahlige Lösungen $\begin{eqnarray*} (x,y) \end{eqnarray*}$ . Abzüglich der Lösung $\begin{eqnarray*} (x,y)=(0,0) \end{eqnarray*}$ , die ja keine Lösung der Ausgangsgleichung ist, macht das genau 449 Lösungen $\begin{eqnarray*} (x,y) \end{eqnarray*}$ von

$\begin{eqnarray*} \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \end{eqnarray*}$ .

Betrachtet man nun nur geordnete Lösungen mit O.B.d.A. $\begin{eqnarray*} x\geq y \end{eqnarray*}$ , so bleiben davon immer noch 225 Lösungen übrig.

Oder interessieren dich nur positive Lösungen? In dem Fall wären die Anzahl $\begin{eqnarray*} \frac{225+1}{2} = 113 \end{eqnarray*}$ Lösungen richtig.

P.S.: Dein Programm ist wegen numerischer Instabilitäten höchst fragwürdig. Vermutlich deswegen entgehen dir ein paar Lösungen. Schreib es mal um, dass alles rein auf Integerbasis handhabbar ist!

02.10.2008, 01:26

lostgeek

Auf diesen Beitrag antworten »

Ich schätze ich bin auf ein Thema gestoßen, was sehr viel schwerer ist, als ich dachte.
Ich kann dir in so ziemlich keinem der Schritte wirklich folgen.

Gibt es vielleicht irgendetwas, das man sich dazu durchlesen könnte? Durch Google bin ich leider auf nichts Verständliches gestoßen.

Ich werde mich morgen/heute noch einmal stärker damit beschäftigen. Mir fallen gerade die Augen zu.

02.10.2008, 07:50

Auf diesen Beitrag antworten »

Dann heißt das ziemlich sicher, dass du noch nicht reif bist für das Nachfolgeproblem 110. Wie dort richtig steht, kommt man da mit einfachem Bruteforce (wie es dein Programm darstellt) nicht sehr weit - da wirst du schon meine Schritte nachvollziehen müssen, wenn du da weiterkommen willst.

Dreh- und Angelpunkt bei der Bestimmung der Anzahl der Lösungen ist die Anzahl der $\begin{eqnarray*} d(n^2) \end{eqnarray*}$ der positiven Teiler von $\begin{eqnarray*} n^2 \end{eqnarray*}$ , dabei ist $\begin{eqnarray*} d \end{eqnarray*}$ die sogenannte Teileranzahlfunktion:

Denn jedem Teiler $\begin{eqnarray*} t \end{eqnarray*}$ von $\begin{eqnarray*} n^2 \end{eqnarray*}$ kann man über die Produktdarstellung $\begin{eqnarray*} (x-n)(y-n)=n^2 \end{eqnarray*}$ die Lösung

$\begin{eqnarray*} x-n = t, \quad y-n = \frac{n^2}{t} \end{eqnarray*}$

zuordnen, und umgekehrt (!).

02.10.2008, 12:40

lostgeek

Auf diesen Beitrag antworten »

Selber könnte ich die Schritte zwar nicht machen, aber ich kann sie jetzt nachvollziehen.
Ich muss nur noch einen guten Algorithmus für die Primfaktorzerlegung implementieren, um die Teileranzahlfunktion ausführen zu können. Die stupide Methode braucht zu viel Rechenzeit.

Danke dir smile

02.10.2008, 13:23

Auf diesen Beitrag antworten »

Zitat:

Original von lostgeek
Ich muss nur noch einen guten Algorithmus für die Primfaktorzerlegung implementieren, um die Teileranzahlfunktion ausführen zu können.

Ich wüsste jetzt nicht, wozu dieser Algorithmus konkret beim vorliegenden Problem nützlich sein könnte. Generell kriegt man nämlich folgendes schnell raus:

Sucht man zu gegegebenen, festen Wert $\begin{eqnarray*} t \end{eqnarray*}$ die kleinste positive ganze Zahl $\begin{eqnarray*} n \end{eqnarray*}$ mit $\begin{eqnarray*} d(n)=t \end{eqnarray*}$ , dann besitzt dieses $\begin{eqnarray*} n \end{eqnarray*}$ die Gestalt

$\begin{eqnarray*} n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_m^{e_m}\qquad (*) \end{eqnarray*}$

mit $\begin{eqnarray*} e_1\geq e_2\geq \ldots \geq e_m \end{eqnarray*}$ , wobei $\begin{eqnarray*} (p_k)_{k=1,2,\ldots} \end{eqnarray*}$ die Folge aller Primzahlen ist, also beginnend mit $\begin{eqnarray*} p_1=2,p_2=3,p_3=5 \end{eqnarray*}$ .

Der Nachweis ist sehr einfach, denn die Annahme $\begin{eqnarray*} e_i < e_j \end{eqnarray*}$ für irgendein Paar $\begin{eqnarray*} i<j \end{eqnarray*}$ führt zum Widerspruch der Minimalität, da dann für die durch Austausch der Exponenten kleinere Zahl

$\begin{eqnarray*} n' = p_1^{e_1} \cdot \ldots \cdot p_i^{e_j} \cdot \ldots \cdot p_j^{e_i} \cdot \ldots \cdot p_m^{e_m} \end{eqnarray*}$

ebenfalls $\begin{eqnarray*} d(n')=d(n)=t \end{eqnarray*}$ gelten würde.

Du kannst dich also bei der Suche auf Zahlen der Form (*) beschränken, was den Suchraum erheblich eingrenzt. Selbstverständlich weist die genannte Zahl 1260 auch diese Eigenschaft auf:

$\begin{eqnarray*} n=1260=2^2\cdot 3^2\cdot 5^1\cdot 7^1 \end{eqnarray*}$ .

02.10.2008, 14:59

lostgeek

Auf diesen Beitrag antworten »

Die Fragestellung lautet: "What is the least value of n for which the number of distinct solutions exceeds one-thousand?"

Sprich es wird das n gesucht, wo t zum ersten mal über 1000 liegt.

Deine Form (*) gilt aber nur für ein festes t, was hier aber nicht gegeben ist.

Soweit ich es verstanden hab, suche ich nämlich nach dem kleinsten positiven n mit $\begin{eqnarray*} \frac{d(n^2)}{2} > t \end{eqnarray*}$ und $\begin{eqnarray*} t = 1000 \end{eqnarray*}$ .

Und wenn $\begin{eqnarray*} \frac{d(n^2)}{2} = t \end{eqnarray*}$ ist, kann bei $\begin{eqnarray*} \frac{d({n'}^2)}{2} = t+1 \end{eqnarray*}$
$\begin{eqnarray*} n' < n \end{eqnarray*}$ sein, oder vertue ich mich da?

02.10.2008, 15:10

Auf diesen Beitrag antworten »

Zitat:

Original von lostgeek
Deine Form (*) gilt aber nur für ein festes t, was hier aber nicht gegeben ist.

Denk nochmal genauer nach, ob das nicht auch für deine Fragestellung von Belang ist. Forum Kloppe

02.10.2008, 15:31

lostgeek

Auf diesen Beitrag antworten »

Wenn ich z.B. nach mehr als 3 Lösungen suche, dann such ich erstmal für t = 4 und komme auf n = 8. Aber bei t = 5 ist n = 6, sprich bei t = 5 ist das n niedriger als bei t = 4.
Und könnte es nicht sein, dass ich bei t = 6 vielleicht sogar etwas noch niedrigeres finde?

Mein Problem ist, dass ich nicht sagen kann, ab wo an das Erhöhen von t zum Finden von niedrigerem n sinnlos wird.

02.10.2008, 15:34

tmo

Auf diesen Beitrag antworten »

Ich habe das Problem gelöst, indem ich einfach mal mit $\begin{eqnarray*} n = 2 \cdot 3 \cdot 5 \end{eqnarray*}$ angefangen habe und dann immer überlegt habe, ob es nun besser ist die nächste Primzahl dranzuhängen oder ob man vorne einen Exponenten erhöhen sollte.

Dabei auch beachten, dass es um $\begin{eqnarray*} d(n^2) \end{eqnarray*}$ und nicht um $\begin{eqnarray*} d(n) \end{eqnarray*}$ geht.

02.10.2008, 15:35

Auf diesen Beitrag antworten »

Zitat:

Original von lostgeek
Soweit ich es verstanden hab, suche ich nämlich nach dem kleinsten positiven n mit $\begin{eqnarray*} \frac{d(n^2)}{2} > t \end{eqnarray*}$ und $\begin{eqnarray*} t = 1000 \end{eqnarray*}$ .

Richtig - nennen wir den zu diesem minimalen $\begin{eqnarray*} n \end{eqnarray*}$ zugehörigen Wert $\begin{eqnarray*} t^* \end{eqnarray*}$ . Die Annahme, dass $\begin{eqnarray*} n \end{eqnarray*}$ nicht die Form (*) hat, führt auch wie oben zum Widerspruch!!!

02.10.2008, 15:38

lostgeek

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Die Annahme, dass $\begin{eqnarray*} n \end{eqnarray*}$ nicht die Form (*) hat, führt auch wie oben zum Widerspruch!!!

Ok stimmt. Meine Formulierung war falsch. Mein Problem ist das, was ich vor ein paar Posts geschrieben habe.

02.10.2008, 15:39

Auf diesen Beitrag antworten »

Eben: Kein Mensch behauptet, dass die Folge der zu $\begin{eqnarray*} t \end{eqnarray*}$ gehörigen minimalen $\begin{eqnarray*} n \end{eqnarray*}$ mit $\begin{eqnarray*} d(n)=t \end{eqnarray*}$ monoton bzgl. $\begin{eqnarray*} t \end{eqnarray*}$ ist - das ist tatsächlich falsch. Aber darum geht es hier doch gar nicht. unglücklich

EDIT: Ein Nachtrag noch zu

code:
1: 2: 3: 4: 5: 6: 7: 8:	double y = n+1; // Um die Anfangsbedingung der For-Schleife zu erfüllen. for(double x = n+1; y >= n+1 ; x++) { y = x/((x/n)-1); if(y == (int)y) { count++; } }

Da erhalte ich (mit MS Visual Express 2008) auch den Wert 108. Die mathematisch äquivalente, aber numerisch robustere Integervariante

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

int y = n+1; // Um die Anfangsbedingung der For-Schleife zu erfüllen.
for (int x = n+1; y >= n+1 ; x++) {
  double fy = (double)x/(((double)x/(double)n)-1.0);
  int y = (int)(fy+0.5);
  if (x*y == n*(x+y))
  {
    count++;
  }
}

liefert den tatsächlichen richtigen Wert 225. Dir sind durch die numerische Schlamperei also sage und schreibe 117 Lösungen verlorengegangen. Augenzwinkern

02.10.2008, 18:08

lostgeek

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Da erhalte ich (mit MS Visual Express 2008) auch den Wert 108. Die mathematisch äquivalente, aber numerisch robustere Integervariante

liefert den tatsächlichen richtigen Wert 225. Dir sind durch die numerische Schlamperei also sage und schreibe 117 Lösungen verlorengegangen. Augenzwinkern

Hui. Da hast du wohl recht. Dauert trotzdem eine halbe Ewigkeit, bis der mal die t > 100 findet. Geschweige denn die t > 1000 in der Aufgabe.

(Und eigentlich war das Java und kein C#. Scheint aber fast 1:1 der selbe Code zu sein.)

Zitat:

Original von tmo
Ich habe das Problem gelöst, indem ich einfach mal mit $\begin{eqnarray*} n = 2 \cdot 3 \cdot 5 \end{eqnarray*}$ angefangen habe und dann immer überlegt habe, ob es nun besser ist die nächste Primzahl dranzuhängen oder ob man vorne einen Exponenten erhöhen sollte.

Dabei auch beachten, dass es um $\begin{eqnarray*} d(n^2) \end{eqnarray*}$ und nicht um $\begin{eqnarray*} d(n) \end{eqnarray*}$ geht.

Ich hab das mal bis zu dem Punkt in Code gegossen, wo man die Entscheidung treffen muss.

Die Frage ist nur, was man da als sicheren Indikator nehmen kann, welche Entscheidung die richtige ist. Ich konnte keinen finden.

02.10.2008, 18:55

Auf diesen Beitrag antworten »

Zitat:

Genau hast du hier aber nicht erklärt, welchen Exponenten du nun genau erhöhst in jedem Schritt. Und ob man auf diese Weise immer für jede vorgebene untere Schranke $\begin{eqnarray*} L \end{eqnarray*}$ das kleinste $\begin{eqnarray*} n \end{eqnarray*}$ mit $\begin{eqnarray*} d(n^2) \geq L \end{eqnarray*}$ findet, wage ich zu bezweifeln.

Ich kann mir gut vorstellen, dass deine iterierten $\begin{eqnarray*} n \end{eqnarray*}$ die Eigenschaft

$\begin{eqnarray*} d(n^2) \geq d(m^2) \end{eqnarray*}$ für alle $\begin{eqnarray*} m\leq n \end{eqnarray*}$

erfüllen, aber das ist nicht genug für die vorliegende Problemstellung.

03.10.2008, 16:42

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Und ob man auf diese Weise immer für jede vorgebene untere Schranke $\begin{eqnarray*} L \end{eqnarray*}$ das kleinste $\begin{eqnarray*} n \end{eqnarray*}$ mit $\begin{eqnarray*} d(n^2) \geq L \end{eqnarray*}$ findet, wage ich zu bezweifeln.

Ich auch, aber bei der Aufgabe hat es geklappt Augenzwinkern

03.10.2008, 20:44

lostgeek

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Ich auch, aber bei der Aufgabe hat es geklappt Augenzwinkern

Schummler! Big Laugh

Mir ist aber auch kein Algorithmus eingefallen, mit dem ich 100%ig sicher das kleinste n finden kann und unter Jahrzehnten an Laufzeit bleiben kann.

Ich werde einfach mal für $\begin{eqnarray*} 1000 \leq t \leq 1100 \end{eqnarray*}$ die niedrigstmöglichen n suchen. Ich denk das sollte dann auch relativ sicher das niedrigste sein.

06.10.2008, 16:45

Auf diesen Beitrag antworten »

@tmo

Ich lass mal nicht locker, da du die genaue Vorgehensweise bei der Auswahl des nächsten Exponenten nach wie vor im Dunkeln gelassen hast:

Was ergibt dein Verfahren beispielsweise für $\begin{eqnarray*} L=10^8 \end{eqnarray*}$ ? Oder falls dir das zu groß ist, für $\begin{eqnarray*} L=10^5 \end{eqnarray*}$ ?

(Ich will nur ein wenig von den Werten $\begin{eqnarray*} L=1\,000 \end{eqnarray*}$ bzw. $\begin{eqnarray*} L=4\,000\,000 \end{eqnarray*}$ aus diesem Projekt Euler fernbleiben, um lostgeek nicht zuviel zu verraten. Big Laugh

)

Wohlgemerkt, es geht nur um positiven Lösungen $\begin{eqnarray*} (x,y) \end{eqnarray*}$ mit o.B.d.A. $\begin{eqnarray*} x\geq y \end{eqnarray*}$ , oder anders gesprochen: ungeordnete Paare, der Symmetrie des Problems wegen.

EDIT: Sorry, meinte natürlich L statt n - korrigiert.

06.10.2008, 17:29

tmo

Auf diesen Beitrag antworten »

Einen präzisen Algorithmus dazu habe ich nicht.

Ich habe mir einfach überlegt, dass man die Teileranzahl von $\begin{eqnarray*} n^2 \end{eqnarray*}$

- mit 3 multipliziert, wenn man einen neuen Primfaktor dranhängt
- mit 5/3 multipliziert, wenn man aus einer 1 im Exponent eine 2 macht.
etc...

Für L = 2000 hat das wunderbar geklappt (einfach mal gucken wie man nur mit 3en und 5en schnell auf über 2000 kommt), ich habe aber nie behauptet, dass es für höhere L auch klappt.

06.10.2008, 18:32

Auf diesen Beitrag antworten »

Ich will dir ja auch nicht den Kopf abreißen. Augenzwinkern

Sondern nur einen Vergleichswert haben, um meinen schnell zusammengehauenen Bruteforce-Algorithmus zu prüfen. Natürlich Bruteforce im Bereich der oben eingegrenzten Zahlen.

06.10.2008, 19:25

Airblader

Auf diesen Beitrag antworten »

Ich habe hier mal ein paar spontane Überlegungen. Wäre nett, wenn die jemand überprüft, da sie, wie gesagt, sehr spontan waren und ich grade mal weg muss Augenzwinkern

$\begin{eqnarray*} y = \frac{1}{\frac{1}{n}-\frac{1}{x}} \end{eqnarray*}$

$\begin{eqnarray*} y = \frac{1}{\frac{x-n}{nx}} \end{eqnarray*}$

$\begin{eqnarray*} y = \frac{nx}{x-n} = \frac{n}{1-\frac{n}{x}} \end{eqnarray*}$

Für welche x(n) ist n/x also ein Bruch mit abbrechender Dezimaldarstellung (denn nur dann ist der Zähler ein Vielfaches vom Nenner und y damit ganzzahlig)?
bzw. anders formuliert:
Für welche ganze k ist 1/k ein Bruch mit abbrechender Dezimaldarstellung (wenn man x(n) in Vielfachen k von n angibt)?

Genau dann, wenn k sich nicht ausschließlich durch die Primfaktoren 2 und 5 erzeugen lässt. Kommt also in der Primfaktorzerlegung von k eine Primzahl ungleich 2 und 5 raus, so kann man diesen x-Wert als Lösung vergessen.

Und noch besser: Kommen nur 2 und 5 raus, so ist dieser x-Wert eine Lösung und nach obiger Gleichung errechnet sich direkt y.

air

06.10.2008, 20:14

Auf diesen Beitrag antworten »

Ich kann den meisten Schlüssen deiner Logik nicht folgen, z.B. dem nicht: unglücklich

Zitat:

Original von Airblader
Für welche x(n) ist n/x also ein Bruch mit abbrechender Dezimaldarstellung (denn nur dann ist der Zähler ein Vielfaches vom Nenner und y damit ganzzahlig)?

Oder das:

Zitat:

Original von Airblader
Genau dann, wenn k sich nicht ausschließlich durch die Primfaktoren 2 und 5 erzeugen lässt. Kommt also in der Primfaktorzerlegung von k eine Primzahl ungleich 2 und 5 raus, so kann man diesen x-Wert als Lösung vergessen.

Und wenn du die Gleichung im Hexadezimalsystem betrachtest, bekommst du andere Kriterien? Kann schon von daher nicht stimmen.

06.10.2008, 20:31

Airblader

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Ich kann den meisten Schlüssen deiner Logik nicht folgen, z.B. dem nicht: unglücklich

Zitat:

Original von Airblader
Für welche x(n) ist n/x also ein Bruch mit abbrechender Dezimaldarstellung (denn nur dann ist der Zähler ein Vielfaches vom Nenner und y damit ganzzahlig)?

Hm. Stimmt. Da habe ich wohl viel zu schnell und zu falsch gedacht. Naja, es war ja auch nur ein spontaner Gedanke Augenzwinkern

Zitat:

Oder das:

Zitat:

Und wenn du die Gleichung im Hexadezimalsystem betrachtest, bekommst du andere Kriterien? Kann schon von daher nicht stimmen.

Das interessiert mich nun aber. Ich habe das in der Eile mal schlicht von wikipedia übernommen: http://de.wikipedia.org/wiki/Dezimalsystem#Periode
Zweiter Satz nach den Beispielen.

air

06.10.2008, 20:39

Auf diesen Beitrag antworten »

Zitat:

Original von Airblader
Ich habe das in der Eile mal schlicht von wikipedia übernommen: http://de.wikipedia.org/wiki/Dezimalsystem#Periode

Das bezweifle ich gar nicht. Nur: Was hat das Dezimalsystem mit den Lösungen von

$\begin{eqnarray*} \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \end{eqnarray*}$

zu tun? Nichts.

06.10.2008, 20:44

Airblader

Auf diesen Beitrag antworten »

Ja, das mag natürlich sein, weil meine vorausgehende Überlegung schon Unsinn war. Ich dachte nur, das 'Argument' sei an und für sich schon falsch.

Einfach nicht mein Tag heute. Erst will ich was bauen und mir fehlt sämtliches Werkzeug und dann das. böse

air

06.10.2008, 22:45

Auf diesen Beitrag antworten »

Naja, selbstverständlich ist es keine Pflicht, so wie hier an die Sache ranzugehen. Aber wie auch immer man vorgeht, am Ende müssen natürlich dieselben Lösungen

$\begin{eqnarray*} x = n+t, \quad y = n+\frac{n^2}{t} \end{eqnarray*}$

herauskommen, wobei $\begin{eqnarray*} t \end{eqnarray*}$ die positiven Teiler von $\begin{eqnarray*} n^2 \end{eqnarray*}$ durchläuft.

06.10.2008, 22:50

Airblader

Auf diesen Beitrag antworten »

Ich hatte das Thema bisher, um ehrlich zu sein, gar nicht wirklich detailliert verfolgt Augenzwinkern

air

07.10.2008, 11:17

tmo

Auf diesen Beitrag antworten »

Nur um kurz zu sagen, wie ich an die Sache rangegangen bin:

Zitat:

Original von Airblader
$\begin{eqnarray*} y = \frac{nx}{x-n} \end{eqnarray*}$

Ab hier hab ich jetzt Polynomdivision gemacht. Dann erkennt man auch schnell, dass es um die Teiler von $\begin{eqnarray*} n^2 \end{eqnarray*}$ geht.

07.10.2008, 16:16

Auf diesen Beitrag antworten »

Aber leider keine Antwort auf

Zitat:

Original von Arthur Dent
Was ergibt dein Verfahren beispielsweise für $\begin{eqnarray*} L=10^8 \end{eqnarray*}$ ? Oder falls dir das zu groß ist, für $\begin{eqnarray*} L=10^5 \end{eqnarray*}$ ?

Dann muss ich wohl mal vorlegen: Es ist

$\begin{eqnarray*} n_1 = \min\Big\{ n \Bigm| d(n^2) \geq 10^5 \Big\} = 2^3 \cdot 3^3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 = 8\,031\,343\,320 \end{eqnarray*}$

mit $\begin{eqnarray*} d(n_1^2) = 107\,163 \end{eqnarray*}$ , sowie

$\begin{eqnarray*} n_2 = \min\Big\{ n \Bigm| d(n^2) \geq 10^8 \Big\} = 2^4 \cdot 3^3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47 = 44\,272\,064\,346\,371\,381\,520 \end{eqnarray*}$

mit $\begin{eqnarray*} d(n_2^2) = 100\,442\,349 \end{eqnarray*}$ . Wäre interessant zu erfahren, ob dein einfacheres, heuristisches Verfahren diese Minima erfasst, oder doch zumindest "suboptimal" nicht so weit weg ist.

Neue Frage »

Antworten »

Lösungen einer Diophantische Gleichung in N

Verwandte Themen