N mit mindestens T Teilern < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Für jede (positive) natürliche Zahl T definieren wir:
$\ [mm] N_1(T)\ [/mm] =\ [mm] min\,(\,\{\,n\in\IN\ \ |\ \ \tau(n)\ =\ T\,\}\,)$
[/mm]
$\ [mm] N_2(T)\ [/mm] =\ [mm] min\,(\,\{\,n\in\IN\ \ |\ \ \tau(n)\ \ge\ T\,\}\,)$
[/mm]
Gesucht sind möglichst einfache Verfahren, allenfalls
geschlossene Formeln zur Berechnung von
[mm] N_1(T) [/mm] und [mm] N_2(T) [/mm] zu gegebenem T . |
Erläuterung:
[mm] \tau(n) [/mm] steht für die Anzahl aller Teiler (inkl. 1 und n)
einer natürlichen Zahl n .
Gesucht sind also zu gegebener Zahl T die kleinsten
Zahlen n , deren Teileranzahl exakt gleich T oder aber
mindestens gleich T ist.
Hallo zusammen
ich bin auf eine entsprechende Frage in einem anderen
Forum gestoßen, wo allerdings nicht viel brauchbares
rausschaute. Ich habe dann versucht, mir das Ganze mal
etwas näher anzuschauen, bin aber leider bisher auch
noch nicht zu einem "einfachen" Rezept gelangt.
Es ist zwar nicht besonders schwer, z.B. obere Schranken
für die gesuchten Werte zu finden. Um in jedem Fall die
wirklich minimalen Werte zu bestimmen, bräuchte ich
aber wohl noch eine Idee, auf die ich bisher noch nicht
gekommen bin.
Deshalb stelle ich dies mal hier als Frage rein und hoffe,
einige unter Euch zur Suche nach praktikablen Lösungs-
verfahren (natürlich möglichst ohne "brute force" - Methoden)
anzuregen.
Gute neue Woche !
Al-Chwarizmi
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:12 Mo 29.09.2014 | | Autor: | leduart |
Hallo
ich habe die Konstruktion der N(T) nicht ganz kapiert, kannst du es für kleine Zahlen T mal Beispiele geben?
ist N1(1)=1 und N2(1)=1
existieren die N1(3) da ja keine Zahl 3 Teiler haben kann?
Gruß leduart
|
|
|
| |
|
> Hallo
> ich habe die Konstruktion der N(T) nicht ganz kapiert,
> kannst du es für kleine Zahlen T mal Beispiele geben?
> ist N1(1)=1 und N2(1)=1
> existieren die N1(3) da ja keine Zahl 3 Teiler haben
> kann?
> Gruß leduart
Hallo leduart,
hier eine Tabelle mit den ersten paar Werten:
[mm] \begin{tabular}{c | c c c c c c c c c c c}
T & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline\\
N_1(T) & 1 & 2 & 4 & 6 & 16 & 12 & 64 & 24 & 36\\ \\
N_2(T) & 1 & 2 & 4 & 6 & 12 & 12 & 24 & 24 & 36\\
\end{tabular}
[/mm]
Die Zahl 4 hat genau 3 Teiler. Eine Zahl der Form [mm] p^{k-1} [/mm] mit
p prim und [mm] k\in\IN [/mm] hat genau k Teiler. [mm] N_1(T) [/mm] muss also für
jede natürliche Zahl T existieren, und dann natürlich auch [mm] N_2(T) [/mm] .
Man kann sich also klar machen, dass stets [mm] N_2(T)\le N_1(T)\le 2^{T-1}
[/mm]
gelten muss.
LG , Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:01 Mo 29.09.2014 | | Autor: | Marcel |
Hallo,
> > Hallo
> > ich habe die Konstruktion der N(T) nicht ganz kapiert,
> > kannst du es für kleine Zahlen T mal Beispiele geben?
> > ist N1(1)=1 und N2(1)=1
> > existieren die N1(3) da ja keine Zahl 3 Teiler haben
> > kann?
> > Gruß leduart
>
>
>
> Hallo leduart,
>
> hier eine Tabelle mit den ersten paar Werten:
>
> [mm]\begin{tabular}{c | c c c c c c c c c c c}
T & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline\\
N_1(T) & 1 & 2 & 4 & 6 & 16 & 12 & 64 & 24 & 36\\ \\
N_2(T) & 1 & 2 & 4 & 6 & 12 & 12 & 24 & 24 & 36\\
\end{tabular}[/mm]
>
> Die Zahl 4 hat genau 3 Teiler. Eine Zahl der Form [mm]p^{k-1}[/mm]
> mit
> p prim und [mm]k\in\IN[/mm] hat genau k Teiler. [mm]N_1(T)[/mm] muss also
> für
> jede natürliche Zahl T existieren, und dann natürlich
> auch [mm]N_2(T)[/mm] .
ah, das ist eine gute Überlegung für die Existenz von [mm] $N_1(T)\,.$ [/mm] Die Existenz
von [mm] $N_2(T)$ [/mm] hätte man auch anders hinbekommen:
Multiplikation der ersten [mm] $T\,$ [/mm] Primzahlen etwa.
> Man kann sich also klar machen, dass stets [mm]N_2(T)\le N_1(T)\le 2^{T-1}[/mm]
>
> gelten muss.
Durchaus interessante Erkenntnisse. 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:44 Mo 29.09.2014 | | Autor: | Marcel |
Hallo Al,
> Für jede (positive) natürliche Zahl T definieren wir:
>
> [mm]\ N_1(T)\ =\ min\,(\,\{\,n\in\IN\ \ |\ \ \tau(n)\ =\ T\,\}\,)[/mm]
ich muss mir das jetzt jedenfalls so hinschreiben, dass ich direkt sehe,
was da stehe soll:
$\ [mm] N_1(T)=\min\{n \in \IN:\;\; |\{t \in \IN:\;\; t \mid n\}|=T\}\,.$
[/mm]
Also ohne jetzt auf Deinen untenstehenden Text zu schielen sag' ich es
mal mit meinen Worten:
$\ [mm] N_1(T)$ [/mm] ist die kleinste natürliche Zahl, die genau [mm] $T\,$ [/mm] Teiler hat.
> [mm]\ N_2(T)\ =\ min\,(\,\{\,n\in\IN\ \ |\ \ \tau(n)\ \ge\ T\,\}\,)[/mm]
$\ [mm] N_2(T)=\min\{n \in \IN:\;\; |\{t \in \IN:\;\; t \mid n\}|\;\ge\;T\}\,.$
[/mm]
$\ [mm] N_2(T)$ [/mm] ist die kleinste natürliche Zahl, die mindestens [mm] $T\,$ [/mm] Teiler hat.
> Gesucht sind möglichst einfache Verfahren, allenfalls
> geschlossene Formeln zur Berechnung von
> [mm]N_1(T)[/mm] und [mm]N_2(T)[/mm] zu gegebenem T .
>
> Erläuterung:
> [mm]\tau(n)[/mm] steht für die Anzahl aller Teiler (inkl. 1 und
> n)
> einer natürlichen Zahl n .
> Gesucht sind also zu gegebener Zahl T die kleinsten
> Zahlen n , deren Teileranzahl exakt gleich T oder aber
> mindestens gleich T ist.
Wenn Du exakt =T hast, dann hast Du auch [mm] [nomm]$\ge T\,.$[/nomm] [/mm] Daher wird doch in
diesem Falle [mm] [nomm]$\, N_1(T)=\ N_2(T)$[/nomm] [/mm] gelten?
(Edit: Das war ein logisches Missgeschick, was passieren kann, wenn man
die Minimalität unterschlägt...)
Allerdings sehe ich die Existenz von $\ [mm] N_1(T)$ [/mm] nicht so direkt ein - die Existenz
von $\ [mm] N_2(T)$ [/mm] sollte leicht zu begründen sein.
Hilft Dir natürlich bei Deiner Frage nicht direkt. Aber ich muss da auch erst
mal kapieren, um was es geht. 
Bsp.:
Wenn ich [mm] $T=5\,$ [/mm] habe, dann hat
[mm] $1\,$ [/mm] nur einen Teiler: [mm] $1\,$
[/mm]
[mm] $2\,$ [/mm] hat 2 Teiler: [mm] $1,\,2$
[/mm]
[mm] $3\,$ [/mm] hat 2 Teiler (bei Primzahlen brauchen wir eh nicht groß zu überlegen)
[mm] $4\,$ [/mm] hat 3 Teiler: [mm] $1,\,2,\,4$
[/mm]
[mm] $5\,$ [/mm] wieder 2 Teiler
[mm] $6\,$ [/mm] hat 4 Teiler: [mm] $1,\,2,\,3,\,6$
[/mm]
[mm] $7\,$ [/mm] hat 2 Teiler
[mm] $8\,$ [/mm] hat 4 Teiler: [mm] $1,\,2,\,4,\,8$
[/mm]
[mm] $9\,$ [/mm] hat 3 Teiler: [mm] $1,\,3,\,9$
[/mm]
[mm] $10\,$ [/mm] hat 4 Teiler: [mm] $1,\,2,\,5,\,10$
[/mm]
[mm] $11\,,13$ [/mm] haben 2 Teiler
[mm] $12\,$ [/mm] hat 6 Teiler: [mm] $1,\,2,\,3,\,4,6\,12$
[/mm]
[mm] $14\,$ [/mm] hat 4 Teiler: [mm] $1,\,2,\,7,\,14$
[/mm]
[mm] $15\,$ [/mm] hat 4 Teiler: [mm] $1,\,3,\,5\,15$
[/mm]
[mm] $16\,$ [/mm] hat 5 Teiler: [mm] $1,\,2,\,4,\,8,\,16$
[/mm]
Sieht man hier nicht irgendwie, dass es generell reicht, die Teiler bis zur
Zahl
[mm] $\lfloor T/2\rfloor$
[/mm]
zu zählen? Danach kann ja nur noch einer hinzukommen [mm] ($T\,$ [/mm] selbst)...
Ob das was bringt (außer Testersparnis)?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:08 Mo 29.09.2014 | | Autor: | Marcel |
Hallo Al,
> Für jede (positive) natürliche Zahl T definieren wir:
>
> [mm]\ N_1(T)\ =\ min\,(\,\{\,n\in\IN\ \ |\ \ \tau(n)\ =\ T\,\}\,)[/mm]
>
> [mm]\ N_2(T)\ =\ min\,(\,\{\,n\in\IN\ \ |\ \ \tau(n)\ \ge\ T\,\}\,)[/mm]
>
> Gesucht sind möglichst einfache Verfahren, allenfalls
> geschlossene Formeln zur Berechnung von
> [mm]N_1(T)[/mm] und [mm]N_2(T)[/mm] zu gegebenem T .
>
> Erläuterung:
> [mm]\tau(n)[/mm] steht für die Anzahl aller Teiler (inkl. 1 und
> n)
> einer natürlichen Zahl n .
> Gesucht sind also zu gegebener Zahl T die kleinsten
> Zahlen n , deren Teileranzahl exakt gleich T oder aber
> mindestens gleich T ist.
>
>
>
>
> Hallo zusammen
>
> ich bin auf eine entsprechende Frage in einem anderen
> Forum gestoßen, wo allerdings nicht viel brauchbares
> rausschaute. Ich habe dann versucht, mir das Ganze mal
> etwas näher anzuschauen, bin aber leider bisher auch
> noch nicht zu einem "einfachen" Rezept gelangt.
> Es ist zwar nicht besonders schwer, z.B. obere Schranken
> für die gesuchten Werte zu finden. Um in jedem Fall die
> wirklich minimalen Werte zu bestimmen, bräuchte ich
> aber wohl noch eine Idee, auf die ich bisher noch nicht
> gekommen bin.
>
> Deshalb stelle ich dies mal hier als Frage rein und hoffe,
> einige unter Euch zur Suche nach praktikablen Lösungs-
> verfahren (natürlich möglichst ohne "brute force" -
> Methoden)
> anzuregen.
kann man nicht mit einer Primfaktorzerlegung die Anzahl der Teiler einer
Zahl berechnen?
Z.B.:
$6=2*3$
Dann hat 6 die Teiler
[mm] $2^0*3^0,$ $2^0*3^1,$ $2^1*3^0,$ $2^1*3^1\,.$
[/mm]
Die Zahl [mm] $40=5*2^3$ [/mm] hat die Teiler
[mm] $5^0*2^0=1,$ $5^0*2^1=2,$ $5^0*2^2=4,$ $5^0*2^3=8$
[/mm]
[mm] $5^1*2^0=5,$ $5^1*2^1=10,$ $5^1*2^2=20,$ $5^1*2^3=40$
[/mm]
Das sieht doch schonmal sehr kombinatorisch aus! Denn bei
[mm] $2^3*7=7*2^3=7*8=56$
[/mm]
greift das gleiche Verfahren. (2 Primteiler -> 2 Stellen
Für die eine der beiden Stellen gibt es 2=1+1 Möglichkeiten, für die andere
der beiden Stellen gibt es 4=3+1 Möglichkeiten: Also 8 Teiler!
Mit dieser Idee sollte man doch wenigstens einen Algorithmus für $\ [mm] N_2(T)$
[/mm]
hinbekommen, oder? Wobei es auch da noch eine knifflige Stelle gibt, glaube
ich...)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:32 Mo 29.09.2014 | | Autor: | Marcel |
Hallo,
also hier die Ansatzidee für einen Algorithmus an einem Beispiel verdeutlicht:
Es sei etwa
[mm] $T=3*2^3=24\,.$
[/mm]
Dann setze
[mm] $Z=Z(T)=2^{2^3-1}*3^{3-1}\,.$
[/mm]
Dann ist [mm] $Z(T)\,$ [/mm] eine Zahl, die genau [mm] $2^3*3=24$ [/mm] Teiler hat.
Es ist noch zu beweisen, dass es auch die kleinste ist.
Wie gesagt: Ich muss gerade noch überlegen, ob ich da nichts übersehe.
Vor allen Dingen werde ich das gerade mal mit Deiner Tabelle abgleichen,
ob das da analog steht ^^
Gruß,
Marcel
Gerade bemerkt: Irgendwie passt das noch nicht...
Bemerkenswert ist aber, dass (ich habe mir einen Algorithmus geschrieben)
[mm] $360=2^\red{3}*3^\blue{2}*5^\green{1}$
[/mm]
die gesuchte Zahl ist. Und es ist auch
[mm] $24=(\red{3}+1)*(\blue{2}+1)*(\green{1}+1)$
[/mm]
Das war die Tücke, an der ich eben scheiterte...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:38 Mo 29.09.2014 | | Autor: | Marcel |
Hallo,
für alle interessierten Entwickler dann wenigstens eine abgeschwächte
Brute-Force-Methode, mit der man seine Ergebnisse vergleichen kann.
Wie gesagt: Ich denke, dass man eigentlich nur eine Faktorisierung der
Zahl [mm] $T\,$ [/mm] vornehmen muss. Und dann muss man die *günstigste Verteilung
der "Faktoren-1" auf die Exponenten der ersten Primzahlen* finden.
Im Beispiel eben:
[mm] $24=2^3*3=4*3*2$
[/mm]
Aber
[mm] $2^{2^3-1}*3^{3-1}$
[/mm]
ist eine Zahl, die größer ist als
[mm] $2^{4-1}*3^{3-1}*5^{2-1}\,.$
[/mm]
Auch testbar wäre etwa gewesen
[mm] $2^{2-1}*3^{2-1}*5^{2-1}*7^{3-1}\,.$
[/mm]
Aber das nur nebenbei. Im Anhang der Code für Octave!
![[a]](/images/paperclip.gif "Dateianhänge") Octave-Code von: KleinsteZahl_k_mit_genau_AT_Teilern.m
Gruß,
Marcel
Dateianhänge:
Anhang Nr. 1 (Typ: m) [nicht öffentlich]
|
|
|
| |
|
Hallo Marcel,
ich habe gesehen, dass du mittlerweile eine ganze Reihe
von Mitteilungen eingereicht hast.
Dazu kann ich eigentlich nur sagen, dass ich mir das alles
eigentlich auch schon überlegt habe. Nur wollte ich diejenigen,
die sich mit dem Thema beschäftigen wollen, nicht schon durch
eine ganze Serie von einleitenden Überlegungen davon
abhalten, sich alles Schritt für Schritt selber zurechtzulegen.
Also hier mal eine Grundüberlegung: Wenn eine Zahl n
vorgegeben ist, kann man die Teileranzahl [mm] \tau(n) [/mm] (gemäß
![[]](/images/popup.gif) Wikipedia so bezeichnet) berechnen als
[mm] $\tau(n)\ [/mm] =\ [mm] \prod_{i=1}^{k}(\alpha_i\,+\,1)$
[/mm]
wenn $\ n\ =\ [mm] \prod_{i=1}^{k}p_i^{\alpha_i}$ [/mm] die Primfaktorzerlegung von $\ n$ ist.
Dabei sei [mm] [/mm] = <2,3,5,7,11,13,17, ... > die Folge der Primzahlen.
Zur Existenz der Minima [mm] N_1(T) [/mm] und [mm] N_2(T) [/mm] zu beliebigem gegebenem
[mm] T\in\IN [/mm] muss ich mich wohl kaum weiter auslassen.
Als obere Schranke für [mm] N_1(T) [/mm] und damit auch für [mm] N_2(T) [/mm] hatte ich
oben schon angegeben:
$ [mm] N_2(T)\le N_1(T)\le 2^{T-1} [/mm] $
Es ist auch nicht schwer, eine im Allgemeinen deutlich schärfere
obere Schranke für [mm] N_2(T) [/mm] anzugeben, nämlich:
$ [mm] N_2(T)\ \le\ \prod_{i=1}^{i_{max}}p_i$
[/mm]
wobei $\ [mm] i_{max}\ [/mm] =\ [mm] \left \lceil\, lb(T)\, \right \rceil\ [/mm] =\ [mm] \left \lceil\, \frac{ln(T)}{ln(2)}\, \right \rceil\ [/mm] $
Dazu ein kleines Beispiel: Nehmen wir etwa T=1000 , so ist T
knapp kleiner als 1024 = [mm] 2^{10} [/mm] , d.h. [mm] $\left \lceil\, lb(T)\, \right \rceil\ [/mm] =\ 10$
Das Produkt [mm] $\prod_{i=1}^{10}p_i\ [/mm] =\ 2*3*5*7*11*13*17*19*23*29\ \ [mm] \approx\ 6.47*10^9$
[/mm]
der ersten 10 Primzahlen hat exakt 1024, also auch mehr
als T=1000 Teiler und kann darum als obere Schranke für
[mm] N_2(1000) [/mm] dienen. Diese ist natürlich sehr klein im Vergleich
zur ersten angegebenen oberen Schranke $\ [mm] 2^{T-1}\ [/mm] =\ [mm] 2^{999}\ \approx 5.36*10^{300}$
[/mm]
Allerdings ist auch die neue Schranke noch sehr weit weg
von den wahren Werten der [mm] N_1 [/mm] und [mm] N_2 [/mm] für T=1000.
So wie ich sehe, ist nämlich vermutlich
$\ [mm] N_1(1000)\ [/mm] =\ 810'810'000\ [mm] \approx\ 8.1*10^8$
[/mm]
Dabei kann ich allerdings anstelle des Gleichheitszeichens erst
ein [mm] "\le" [/mm] garantieren ...
[mm] N_2(1000) [/mm] ist dann ziemlich sicher noch kleiner als [mm] N_1(1000) [/mm] .
Um die Problematik auch nur bei der Bestimmung von [mm] N_1(T)
[/mm]
zu illustrieren, habe ich ein nettes Beispiel mit kleineren
Zahlen. Es sei z.B. $\ T\ =\ 96\ =\ [mm] 2^5*3^1$
[/mm]
Man kann leicht einsehen, dass die Zahl $\ 60'060\ =\ [mm] 2^2*3^1*5^1*7^1*11^1*13^1$
[/mm]
exakt 96 Teiler besitzt.
Allerdings zeigt dann eine etwas nähere Untersuchung, dass
es auch noch kleinere Zahlen mit exakt ebenso vielen Teilern
gibt, nämlich zum Beispiel:
$\ 40'320\ =\ [mm] 2^7*3^2*5^1*7^1$
[/mm]
aber auch schon
$\ 30'240\ =\ [mm] 2^5*3^3*5^1*7^1$
[/mm]
Um diese Zerlegungen zu finden, habe ich mich natürlich an die
oben angegebene Formel
[mm] $\tau(n)\ [/mm] =\ [mm] \prod_{i=1}^{k}(\alpha_i\,+\,1)$
[/mm]
gehalten, für die linke Seite den Wert 96 eingesetzt und dann
mit den möglichen Faktorzerlegungen von 96 etwas rumgespielt -
aber noch ohne definitives System, um mit Sicherheit das
kleinste mögliche n (also [mm] N_1(96)) [/mm] herauszufinden. Genau
für diesen Schritt, also genaugenommen für das damit verbundene
Optimierungsproblem, fehlt mir noch der ganz systematische
Ansatz.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:12 Di 30.09.2014 | | Autor: | Marcel |
Hi Al,
> Hallo Marcel,
>
> ich habe gesehen, dass du mittlerweile eine ganze Reihe
> von Mitteilungen eingereicht hast.
> Dazu kann ich eigentlich nur sagen, dass ich mir das alles
> eigentlich auch schon überlegt habe. Nur wollte ich
> diejenigen,
> die sich mit dem Thema beschäftigen wollen, nicht schon
> durch
> eine ganze Serie von einleitenden Überlegungen davon
> abhalten, sich alles Schritt für Schritt selber
> zurechtzulegen.
>
> Also hier mal eine Grundüberlegung: Wenn eine Zahl n
> vorgegeben ist, kann man die Teileranzahl [mm]\tau(n)[/mm]
> (gemäß
>
> Wikipedia
> so bezeichnet) berechnen als
>
> [mm]\tau(n)\ =\ \prod_{i=1}^{k}(\alpha_i\,+\,1)[/mm]
>
> wenn [mm]\ n\ =\ \prod_{i=1}^{k}p_i^{\alpha_i}[/mm] die
> Primfaktorzerlegung von [mm]\ n[/mm] ist.
genau - ich kannte die Formel zwar nicht, aber ich habe sie mir neulich
wegen einer Aufgabe aus der Kryptographie selbst hergeleitet und
erklärt.
> Dabei sei [mm][/mm] = <2,3,5,7,11,13,17, ... > die Folge der
> Primzahlen.
Genau. Da brauchen wir ja auch noch einen Algorithmus, der die uns
schnell baut. Wenn Du einen brauchst: Ich habe mir gerade erst das
Sieb des Eratosthenes selbst in Octave geschrieben. Müsste man minimal
verifizieren (es berechnet die Primzahlen bis zu einer gewissen Zahl). Aber
zum einen denke ich, dass Du das eh irgendwo rumliegen hast, zum
anderen gibt es da vielleicht auch bessere Algorithmen. Algorithmisch
kenne ich mich da (noch) nicht so aus.
Und ich glaube, Du benutzt auch eher nicht Matlab/Octave?!
> Zur Existenz der Minima [mm]N_1(T)[/mm] und [mm]N_2(T)[/mm] zu beliebigem
> gegebenem
> [mm]T\in\IN[/mm] muss ich mich wohl kaum weiter auslassen.
Ne, das habe ich eingesehen (wenn es doch noch jemand hören will:
Nichtleere Teilmengen der natürlichen Zahlen haben ein Minimum). Wie
gesagt: Da hatte ich einen Gedankenfehler.
> Als obere Schranke für [mm]N_1(T)[/mm] und damit auch für [mm]N_2(T)[/mm]
> hatte ich
> oben schon angegeben:
Ja.
> [mm]N_2(T)\le N_1(T)\le 2^{T-1}[/mm]
>
> Es ist auch nicht schwer, eine im Allgemeinen deutlich
> schärfere
> obere Schranke für [mm]N_2(T)[/mm] anzugeben, nämlich:
>
> [mm]N_2(T)\ \le\ \prod_{i=1}^{i_{max}}p_i[/mm]
>
> wobei [mm]\ i_{max}\ =\ \left \lceil\, lb(T)\, \right \rceil\ =\ \left \lceil\, \frac{ln(T)}{ln(2)}\, \right \rceil\[/mm]
>
> Dazu ein kleines Beispiel: Nehmen wir etwa T=1000 , so ist
> T
> knapp kleiner als 1024 = [mm]2^{10}[/mm] , d.h. [mm]\left \lceil\, lb(T)\, \right \rceil\ =\ 10[/mm]
>
> Das Produkt [mm]\prod_{i=1}^{10}p_i\ =\ 2*3*5*7*11*13*17*19*23*29\ \ \approx\ 6.47*10^9[/mm]
>
> der ersten 10 Primzahlen hat exakt 1024, also auch mehr
> als T=1000 Teiler und kann darum als obere Schranke für
> [mm]N_2(1000)[/mm] dienen. Diese ist natürlich sehr klein im
> Vergleich
> zur ersten angegebenen oberen Schranke [mm]\ 2^{T-1}\ =\ 2^{999}\ \approx 5.36*10^{300}[/mm]
Das überlege ich mir noch.
> Allerdings ist auch die neue Schranke noch sehr weit weg
> von den wahren Werten der [mm]N_1[/mm] und [mm]N_2[/mm] für T=1000.
> So wie ich sehe, ist nämlich vermutlich
>
> [mm]\ N_1(1000)\ =\ 810'810'000\ \approx\ 8.1*10^8[/mm]
ich lasse mal gerade Octave laufen - aber ob das heute noch fertig wird?
> Dabei kann ich allerdings anstelle des Gleichheitszeichens
> erst
> ein [mm]"\le"[/mm] garantieren ...
> [mm]N_2(1000)[/mm] ist dann ziemlich sicher noch kleiner als
> [mm]N_1(1000)[/mm] .
>
> Um die Problematik auch nur bei der Bestimmung von [mm]N_1(T)[/mm]
> zu illustrieren, habe ich ein nettes Beispiel mit
> kleineren
> Zahlen. Es sei z.B. [mm]\ T\ =\ 96\ =\ 2^5*3^1[/mm]
>
> Man kann leicht einsehen, dass die Zahl [mm]\ 60'060\ =\ 2^2*3^1*5^1*7^1*11^1*13^1[/mm]
>
> exakt 96 Teiler besitzt.
>
> Allerdings zeigt dann eine etwas nähere Untersuchung,
> dass
> es auch noch kleinere Zahlen mit exakt ebenso vielen
> Teilern
> gibt, nämlich zum Beispiel:
>
> [mm]\ 40'320\ =\ 2^7*3^2*5^1*7^1[/mm]
>
> aber auch schon
>
> [mm]\ 30'240\ =\ 2^5*3^3*5^1*7^1[/mm]
Hast Du einfach mal die größeren durch die kleineren geteilt? Ich meine,
irgendein System müßte man da doch sehen, warum die größer sind bei
dieser "Verteilung an die Primzahlexponenten".
> Um diese Zerlegungen zu finden, habe ich mich natürlich an
> die
> oben angegebene Formel
>
> [mm]\tau(n)\ =\ \prod_{i=1}^{k}(\alpha_i\,+\,1)[/mm]
>
> gehalten, für die linke Seite den Wert 96 eingesetzt und
> dann
> mit den möglichen Faktorzerlegungen von 96 etwas
> rumgespielt -
> aber noch ohne definitives System, um mit Sicherheit das
> kleinste mögliche n (also [mm]N_1(96))[/mm] herauszufinden.
>
> Genau
> für diesen Schritt, also genaugenommen für das damit
> verbundene
> Optimierungsproblem, fehlt mir noch der ganz
> systematische
> Ansatz.
Ja. Ich hab' zwar da durchaus eine gedankliche Idee, aber das wird dauern
bis ich die Zeit hab', das auf's Papier zu schreiben bzw. gar
runterzuprogrammieren.
Im ersten Schritt würde ich da auch gar nicht versuchen, direkt die *optimale*
Verteilung zu finden, sondern erstmal alle relevanten Verteilungen. Ich
meine, nehmen wir mal
[mm] $20=2*2*5=2^\red{2}*5^{\blue{1}}\,.$
[/mm]
Dann weißt Du ja, dass Du maximal die ersten [mm] $\red{2}+\blue{1}=3$ [/mm] Primzahlen benutzen wirst:
[mm] $2^1*3^1*5^4\,.$
[/mm]
Und diese Zahl würdest Du schon gar nicht testen, sondern die Exponenten
absteigend sortieren:
[mm] $2^4*3^1*5^1\,.$
[/mm]
Und jetzt kannst Du aus den 3 Faktoren
$2*2*5$
ja auch [mm] $2\,$ [/mm] machen:
Entweder [mm] $4*5\,$ [/mm] oder $2*10$ schreiben.
(Dann berechnen wir für den Test
[mm] $2^{5-1}*3^{4-1}$ [/mm] und [mm] $2^{10-1}*3^{2-1}\,.$)
[/mm]
Etc. pp.
Wir brauchen so also erheblich weniger Testfälle durchzuspielen. Das ganze
wird sicher etwas *kombinatorisch* werden. In Matlab/Octave kann ich
da durchaus mit Schleifen arbeiten. Mit Befehlen wie
nchoosek([1:3],2)
bekommt eine wunderbare Matrix, deren Zeilen man durchlaufen kann. Und
wie gesagt: da braucht man eigentlich auch *weniger*, weil man natürlich
sieht, dass die Exponenten der Größe nach abfallen müssen. Man weiß halt
nur nicht wirklich, welche Primfaktorenanzahl betrachtet werden soll.
Und bei
> $ \ 40'320\ =\ [mm] 2^7\cdot{}3^2\cdot{}5^1\cdot{}7^1 [/mm] $
>
> aber auch schon
>
> $ \ 30'240\ =\ [mm] 2^5\cdot{}3^3\cdot{}5^1\cdot{}7^1 [/mm] $
sieht man wunderbar, dass hier [mm] $2^2=4 [/mm] > 3$ zum Tragen kommt. Also
ganz zufällig ist das ja nicht. Man muss sich nur mal ganz genau klar machen,
und dann auch versuchen, hinzuschreiben, was der entscheidende Punkt
hier ist.
Aber das wäre dann meiner Meinung nach erst der nächste Optimierungs-
schritt. Am besten erstmal einen Algorithmus bauen, der nur das oben
Gesagte macht.
Gruß,
Marcel
|
|
|
| |
|
> > Also hier mal eine Grundüberlegung: Wenn eine Zahl n
> > vorgegeben ist, kann man die Teileranzahl [mm]\tau(n)[/mm]
> > (gemäß
> >
> > Wikipedia
> > so bezeichnet) berechnen als
> >
> > [mm]\tau(n)\ =\ \prod_{i=1}^{k}(\alpha_i\,+\,1)[/mm]
> >
> > wenn [mm]\ n\ =\ \prod_{i=1}^{k}p_i^{\alpha_i}[/mm] die
> > Primfaktorzerlegung von [mm]\ n[/mm] ist.
>
> genau - ich kannte die Formel zwar nicht, aber ich habe sie
> mir neulich wegen einer Aufgabe aus der Kryptographie selbst
> hergeleitet und erklärt.
Habe ich ebenfalls so gemacht - ob ich die Formel früher schon
mal "wusste" , weiß ich nicht mal ...
> > Dabei sei [mm][/mm] = <2,3,5,7,11,13,17, ... > die Folge der
> > Primzahlen.
>
> Genau. Da brauchen wir ja auch noch einen Algorithmus, der
> die uns
> schnell baut. Wenn Du einen brauchst: Ich habe mir gerade
> erst das
> Sieb des Eratosthenes selbst in Octave geschrieben. Müsste
> man minimal
> verifizieren (es berechnet die Primzahlen bis zu einer
> gewissen Zahl). Aber
> zum einen denke ich, dass Du das eh irgendwo rumliegen
> hast, zum
> anderen gibt es da vielleicht auch bessere Algorithmen.
> Algorithmisch
> kenne ich mich da (noch) nicht so aus.
> Und ich glaube, Du benutzt auch eher nicht
> Matlab/Octave?!
So ist es. Und ich habe auch nicht die Idee, das Problem auf
rein algorithmischem Weg zu bearbeiten. Ein rechnerischer
Algorithmus zur praktischen Bestätigung an konkreten Beispielen
könnte allenfalls am Ende stehen.
> > Zur Existenz der Minima [mm]N_1(T)[/mm] und [mm]N_2(T)[/mm] zu beliebigem
> > gegebenem
> > [mm]T\in\IN[/mm] muss ich mich wohl kaum weiter auslassen.
>
> Ne, das habe ich eingesehen (wenn es doch noch jemand
> hören will:
> Nichtleere Teilmengen der natürlichen Zahlen haben ein
> Minimum).
Genau.
> > Als obere Schranke für [mm]N_1(T)[/mm] und damit auch für [mm]N_2(T)[/mm]
> > hatte ich
> > oben schon angegeben:
> > [mm]N_2(T)\le N_1(T)\le 2^{T-1}[/mm]
> >
> > Es ist auch nicht schwer, eine im Allgemeinen deutlich
> > schärfere
> > obere Schranke für [mm]N_2(T)[/mm] anzugeben, nämlich:
> >
> > [mm]N_2(T)\ \le\ \prod_{i=1}^{i_{max}}p_i[/mm]
> >
> > wobei [mm]\ i_{max}\ =\ \left \lceil\, lb(T)\, \right \rceil\ =\ \left \lceil\, \frac{ln(T)}{ln(2)}\, \right \rceil\[/mm]
>
> >
> > Dazu ein kleines Beispiel: Nehmen wir etwa T=1000 , so ist T
> > knapp kleiner als 1024 = [mm]2^{10}[/mm] , d.h. [mm]\left \lceil\, lb(T)\, \right \rceil\ =\ 10[/mm]
>
> >
> > Das Produkt [mm]\prod_{i=1}^{10}p_i\ =\ 2*3*5*7*11*13*17*19*23*29\ \ \approx\ 6.47*10^9[/mm]
>
> >
> > der ersten 10 Primzahlen hat exakt 1024, also auch mehr
> > als T=1000 Teiler und kann darum als obere Schranke für
> > [mm]N_2(1000)[/mm] dienen. Diese ist natürlich sehr klein im
> > Vergleich
> > zur ersten angegebenen oberen Schranke [mm]\ 2^{T-1}\ =\ 2^{999}\ \approx 5.36*10^{300}[/mm]
>
> Das überlege ich mir noch.
>
> > Allerdings ist auch die neue Schranke noch weit weg
> > von den wahren Werten der [mm]N_1[/mm] und [mm]N_2[/mm] für T=1000.
> > So wie ich sehe, ist nämlich vermutlich
> >
> > [mm]\ N_1(1000)\ =\ 810'810'000\ \approx\ 8.1*10^8[/mm]
>
> ich lasse mal gerade Octave laufen - aber ob das heute noch
> fertig wird?
Die Zahl habe ich (sogar ohne TR ... ) so berechnet:
$\ 1000\ =\ [mm] 5^3*2^3 [/mm] \ =\ [mm] (4+1)^3*(1+1)^3$
[/mm]
$\ [mm] 2^4*3^4*5^4*7^1*11^1*13^1\ [/mm] =\ [mm] 10^4*81*\underbrace{(7*11*13)}_{1001}\ [/mm] =\ 810810000$
> > Dabei kann ich allerdings anstelle des Gleichheitszeichens
> > erst
> > ein [mm]"\le"[/mm] garantieren ...
>
> > [mm]N_2(1000)[/mm] ist dann ziemlich sicher noch kleiner als
> > [mm]N_1(1000)[/mm] .
> >
> > Um die Problematik auch nur bei der Bestimmung von [mm]N_1(T)[/mm]
> > zu illustrieren, habe ich ein nettes Beispiel mit
> > kleineren
> > Zahlen. Es sei z.B. [mm]\ T\ =\ 96\ =\ 2^5*3^1[/mm]
> >
> > Man kann leicht einsehen, dass die Zahl [mm]\ 60'060\ =\ 2^2*3^1*5^1*7^1*11^1*13^1[/mm]
> > exakt 96 Teiler besitzt.
> > Allerdings zeigt dann eine etwas nähere Untersuchung,
> > dass es auch noch kleinere Zahlen mit exakt ebenso vielen
> > Teilern gibt, nämlich zum Beispiel:
> >
> > [mm]\ 40'320\ =\ 2^7*3^2*5^1*7^1[/mm]
> >
> > aber auch schon
> >
> > [mm]\ 30'240\ =\ 2^5*3^3*5^1*7^1[/mm]
>
> Hast Du einfach mal die größeren durch die kleineren
> geteilt? Ich meine,
> irgendein System müßte man da doch sehen, warum die
> größer sind bei
> dieser "Verteilung an die Primzahlexponenten".
> > Um diese Zerlegungen zu finden, habe ich mich natürlich an
> > die oben angegebene Formel
> >
> > [mm]\tau(n)\ =\ \prod_{i=1}^{k}(\alpha_i\,+\,1)[/mm]
> >
> > gehalten, für die linke Seite den Wert 96 eingesetzt und
> > dann
> > mit den möglichen Faktorzerlegungen von 96 etwas
> > rumgespielt -
> > aber noch ohne definitives System, um mit Sicherheit
> das
> > kleinste mögliche n (also [mm]N_1(96))[/mm] herauszufinden.
> >
> > Genau
> > für diesen Schritt, also genaugenommen für das damit
> > verbundene
> > Optimierungsproblem, fehlt mir noch der ganz
> > systematische
> > Ansatz.
>
> Ja. Ich hab' zwar da durchaus eine gedankliche Idee, aber
> das wird dauern
> bis ich die Zeit hab', das auf's Papier zu schreiben bzw.
> gar
> runterzuprogrammieren.
>
> Im ersten Schritt würde ich da auch gar nicht versuchen,
> direkt die *optimale*
> Verteilung zu finden, sondern erstmal alle relevanten
> Verteilungen. Ich
> meine, nehmen wir mal
>
> [mm]20=2*2*5=2^\red{2}*5^{\blue{1}}\,.[/mm]
>
> Dann weißt Du ja, dass Du maximal die ersten
> [mm]\red{2}+\blue{1}=3[/mm] Primzahlen benutzen wirst:
>
> [mm]2^1*3^1*5^4\,.[/mm]
>
> Und diese Zahl würdest Du schon gar nicht testen, sondern
> die Exponenten
> absteigend sortieren:
>
> [mm]2^4*3^1*5^1\,.[/mm]
>
> Und jetzt kannst Du aus den 3 Faktoren
>
> [mm]2*2*5[/mm]
>
> ja auch [mm]2\,[/mm] machen:
>
> Entweder [mm]4*5\,[/mm] oder [mm]2*10[/mm] schreiben.
> (Dann berechnen wir für den Test
>
> [mm]2^{5-1}*3^{4-1}[/mm] und [mm]2^{10-1}*3^{2-1}\,.[/mm])
>
> Etc. pp.
>
> Wir brauchen so also erheblich weniger Testfälle
> durchzuspielen. Das ganze
> wird sicher etwas *kombinatorisch* werden. In
> Matlab/Octave kann ich
> da durchaus mit Schleifen arbeiten. Mit Befehlen wie
>
> nchoosek([1:3],2)
>
> bekommt eine wunderbare Matrix, deren Zeilen man
> durchlaufen kann. Und
> wie gesagt: da braucht man eigentlich auch *weniger*, weil
> man natürlich
> sieht, dass die Exponenten der Größe nach abfallen
> müssen. Man weiß halt
> nur nicht wirklich, welche Primfaktorenanzahl betrachtet
> werden soll.
>
> Und bei
>
> > [mm]\ 40'320\ =\ 2^7\cdot{}3^2\cdot{}5^1\cdot{}7^1[/mm]
> >
> > aber auch schon
> >
> > [mm]\ 30'240\ =\ 2^5\cdot{}3^3\cdot{}5^1\cdot{}7^1[/mm]
>
> sieht man wunderbar, dass hier [mm]2^2=4 > 3[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
zum Tragen kommt.
> Also
> ganz zufällig ist das ja nicht. Man muss sich nur mal
> ganz genau klar machen,
> und dann auch versuchen, hinzuschreiben, was der
> entscheidende Punkt
> hier ist.
> Aber das wäre dann meiner Meinung nach erst der nächste
> Optimierungsschritt. Am besten erstmal einen Algorithmus
> bauen, der nur das oben Gesagte macht.
>
> Gruß,
> Marcel
Hallo Marcel,
auch hier erwähnst du einige Gedankengänge, die ich mir in
den letzten paar Tagen schon erarbeitet habe. Für alle, die
sich auch ein wenig in das Thema reinknien wollen, ist es
bestimmt ebenfalls nützlich, sich einiges davon ebenfalls
selber zu "erkämpfen". Dazu habe ich auch Dutzende von
Zetteln mit diversen Notizen und Beispielen etc. geschrieben.
Dabei wurde mir klar, dass sich die beiden Aufgaben,
zu gegebenem T entweder N_1(T) oder aber N_2(T) zu
finden, im Detail doch erheblich voneinander unterscheiden.
Meine Idee ist vor allem, möglichst ohne viel Computereinsatz,
Suchalgorithmen und "brute force" auszukommen, sondern
möglichst geschlossene Ausdrücke zu finden. Programmiert
habe ich demzufolge noch gar nichts !
Für die Bestimmung von N_2(T) kann man sich etwa klar
machen, dass man von der kompletten Primzerlegung
einer Zahl mit mindestens T Teilern ausgehen kann.
In einem zweiten Schritt geht es dann darum, daraus
durch geeignete Zusammenfassungen
eine (schwach monoton) abfallende Folge von Faktoren
der Form (\alpha_i+1) zu erzeugen, wobei dann die \alpha_i
als Primzahlexponenten in der Faktorisierung von
$\ N\ =\ \prod_{i=1}^{k}p_i^{\alpha_i}$
bilden. Das Ziel ist, diese Zerlegung so zu gestalten, dass
das resultierende N minimal wird. Nun könnte man anstatt N
dessen Logarithmus minimieren, also
$\ ln(N)\ =\ \summe_{i=1}^{k}{\alpha_i*ln(p_i)}$
Eine halbwegs ausgereifte Idee dazu war, dass die Folge der
Exponenten vielleicht entstehen könnte, indem man von
der Folge $\ <\frac{1}{ln{2}}\,,\frac{1}{ln{3}}\,,\frac{1}{ln{5}}\,,\frac{1}{ln{7}}\,,\frac{1}{ln(11)}\,,\,....\,}$
ausgeht, die Glieder mit einem passend gewählten Faktor f
multipliziert und dann auf ganzzahlige Werte rundet.
In einigen Beispielen hat das so ungefähr gepasst, aber
eben nur so "in etwa" und ohne exakte Begründung.
Das Optimierungsproblem, das hier auftritt, ist eher von
ungewohnter Getalt, da man nicht einmal eine von
vornherein bekannte Anzahl von Variablen hat ...
LG , Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:50 Di 30.09.2014 | | Autor: | Marcel |
Hallo Al,
> > > Also hier mal eine Grundüberlegung: Wenn eine Zahl n
> > > vorgegeben ist, kann man die Teileranzahl [mm]\tau(n)[/mm]
> > > (gemäß
> > >
> > > Wikipedia
> > > so bezeichnet) berechnen als
> > >
> > > [mm]\tau(n)\ =\ \prod_{i=1}^{k}(\alpha_i\,+\,1)[/mm]
> > >
> > > wenn [mm]\ n\ =\ \prod_{i=1}^{k}p_i^{\alpha_i}[/mm] die
> > > Primfaktorzerlegung von [mm]\ n[/mm] ist.
> >
> > genau - ich kannte die Formel zwar nicht, aber ich habe sie
> > mir neulich wegen einer Aufgabe aus der Kryptographie
> selbst
> > hergeleitet und erklärt.
>
> Habe ich ebenfalls so gemacht - ob ich die Formel früher
> schon
> mal "wusste" , weiß ich nicht mal ...
>
> > > Dabei sei [mm][/mm] = <2,3,5,7,11,13,17, ... > die Folge der
> > > Primzahlen.
> >
> > Genau. Da brauchen wir ja auch noch einen Algorithmus, der
> > die uns
> > schnell baut. Wenn Du einen brauchst: Ich habe mir gerade
> > erst das
> > Sieb des Eratosthenes selbst in Octave geschrieben. Müsste
> > man minimal
> > verifizieren (es berechnet die Primzahlen bis zu einer
> > gewissen Zahl). Aber
> > zum einen denke ich, dass Du das eh irgendwo rumliegen
> > hast, zum
> > anderen gibt es da vielleicht auch bessere Algorithmen.
> > Algorithmisch
> > kenne ich mich da (noch) nicht so aus.
> > Und ich glaube, Du benutzt auch eher nicht
> > Matlab/Octave?!
>
> So ist es. Und ich habe auch nicht die Idee, das Problem
> auf
> rein algorithmischem Weg zu bearbeiten. Ein rechnerischer
> Algorithmus zur praktischen Bestätigung an konkreten
> Beispielen
> könnte allenfalls am Ende stehen.
>
> > > Zur Existenz der Minima [mm]N_1(T)[/mm] und [mm]N_2(T)[/mm] zu beliebigem
> > > gegebenem
> > > [mm]T\in\IN[/mm] muss ich mich wohl kaum weiter auslassen.
> >
> > Ne, das habe ich eingesehen (wenn es doch noch jemand
> > hören will:
> > Nichtleere Teilmengen der natürlichen Zahlen haben ein
> > Minimum).
>
> Genau.
>
> > > Als obere Schranke für [mm]N_1(T)[/mm] und damit auch für [mm]N_2(T)[/mm]
> > > hatte ich
> > > oben schon angegeben:
>
> > > [mm]N_2(T)\le N_1(T)\le 2^{T-1}[/mm]
> > >
> > > Es ist auch nicht schwer, eine im Allgemeinen deutlich
> > > schärfere
> > > obere Schranke für [mm]N_2(T)[/mm] anzugeben, nämlich:
> > >
> > > [mm]N_2(T)\ \le\ \prod_{i=1}^{i_{max}}p_i[/mm]
> > >
> > > wobei [mm]\ i_{max}\ =\ \left \lceil\, lb(T)\, \right \rceil\ =\ \left \lceil\, \frac{ln(T)}{ln(2)}\, \right \rceil\[/mm]
>
> >
> > >
> > > Dazu ein kleines Beispiel: Nehmen wir etwa T=1000 , so ist
> T
> > > knapp kleiner als 1024 = [mm]2^{10}[/mm] , d.h. [mm]\left \lceil\, lb(T)\, \right \rceil\ =\ 10[/mm]
>
> >
> > >
> > > Das Produkt [mm]\prod_{i=1}^{10}p_i\ =\ 2*3*5*7*11*13*17*19*23*29\ \ \approx\ 6.47*10^9[/mm]
>
> >
> > >
> > > der ersten 10 Primzahlen hat exakt 1024, also auch mehr
> > > als T=1000 Teiler und kann darum als obere Schranke für
> > > [mm]N_2(1000)[/mm] dienen. Diese ist natürlich sehr klein
> im
> > > Vergleich
> > > zur ersten angegebenen oberen Schranke [mm]\ 2^{T-1}\ =\ 2^{999}\ \approx 5.36*10^{300}[/mm]
>
> >
> > Das überlege ich mir noch.
> >
> > > Allerdings ist auch die neue Schranke noch weit weg
> > > von den wahren Werten der [mm]N_1[/mm] und [mm]N_2[/mm] für T=1000.
> > > So wie ich sehe, ist nämlich vermutlich
> > >
> > > [mm]\ N_1(1000)\ =\ 810'810'000\ \approx\ 8.1*10^8[/mm]
> >
> > ich lasse mal gerade Octave laufen - aber ob das heute noch
> > fertig wird?
>
> Die Zahl habe ich (sogar ohne TR ... ) so berechnet:
>
> [mm]\ 1000\ =\ 5^3*2^3 \ =\ (4+1)^3*(1+1)^3[/mm]
>
> [mm]\ 2^4*3^4*5^4*7^1*11^1*13^1\ =\ 10^4*81*\underbrace{(7*11*13)}_{1001}\ =\ 810810000[/mm]
Na, ich wollte meinen Code mal drüberlaufen lassen, ob der nicht doch eine
kleinere Zahl findet. ^^
>
> > > Dabei kann ich allerdings anstelle des Gleichheitszeichens
> > > erst
> > > ein [mm]"\le"[/mm] garantieren ...
> >
> > > [mm]N_2(1000)[/mm] ist dann ziemlich sicher noch kleiner als
> > > [mm]N_1(1000)[/mm] .
> > >
> > > Um die Problematik auch nur bei der Bestimmung von [mm]N_1(T)[/mm]
> > > zu illustrieren, habe ich ein nettes Beispiel mit
> > > kleineren
> > > Zahlen. Es sei z.B. [mm]\ T\ =\ 96\ =\ 2^5*3^1[/mm]
> > >
> > > Man kann leicht einsehen, dass die Zahl [mm]\ 60'060\ =\ 2^2*3^1*5^1*7^1*11^1*13^1[/mm]
>
> > > exakt 96 Teiler besitzt.
> > > Allerdings zeigt dann eine etwas nähere Untersuchung,
> > > dass es auch noch kleinere Zahlen mit exakt ebenso vielen
> > > Teilern gibt, nämlich zum Beispiel:
> > >
> > > [mm]\ 40'320\ =\ 2^7*3^2*5^1*7^1[/mm]
> > >
> > > aber auch schon
> > >
> > > [mm]\ 30'240\ =\ 2^5*3^3*5^1*7^1[/mm]
> >
> > Hast Du einfach mal die größeren durch die kleineren
> > geteilt? Ich meine,
> > irgendein System müßte man da doch sehen, warum die
> > größer sind bei
> > dieser "Verteilung an die Primzahlexponenten".
>
> > > Um diese Zerlegungen zu finden, habe ich mich natürlich an
> > > die oben angegebene Formel
> > >
> > > [mm]\tau(n)\ =\ \prod_{i=1}^{k}(\alpha_i\,+\,1)[/mm]
> > >
> > > gehalten, für die linke Seite den Wert 96 eingesetzt und
> > > dann
> > > mit den möglichen Faktorzerlegungen von 96 etwas
> > > rumgespielt -
> > > aber noch ohne definitives System, um mit Sicherheit
> > das
> > > kleinste mögliche n (also [mm]N_1(96))[/mm]
> herauszufinden.
> > >
> > > Genau
> > > für diesen Schritt, also genaugenommen für das
> damit
> > > verbundene
> > > Optimierungsproblem, fehlt mir noch der ganz
> > > systematische
> > > Ansatz.
> >
> > Ja. Ich hab' zwar da durchaus eine gedankliche Idee, aber
> > das wird dauern
> > bis ich die Zeit hab', das auf's Papier zu schreiben
> bzw.
> > gar
> > runterzuprogrammieren.
> >
> > Im ersten Schritt würde ich da auch gar nicht versuchen,
> > direkt die *optimale*
> > Verteilung zu finden, sondern erstmal alle relevanten
> > Verteilungen. Ich
> > meine, nehmen wir mal
> >
> > [mm]20=2*2*5=2^\red{2}*5^{\blue{1}}\,.[/mm]
> >
> > Dann weißt Du ja, dass Du maximal die ersten
> > [mm]\red{2}+\blue{1}=3[/mm] Primzahlen benutzen wirst:
> >
> > [mm]2^1*3^1*5^4\,.[/mm]
> >
> > Und diese Zahl würdest Du schon gar nicht testen, sondern
> > die Exponenten
> > absteigend sortieren:
> >
> > [mm]2^4*3^1*5^1\,.[/mm]
> >
> > Und jetzt kannst Du aus den 3 Faktoren
> >
> > [mm]2*2*5[/mm]
> >
> > ja auch [mm]2\,[/mm] machen:
> >
> > Entweder [mm]4*5\,[/mm] oder [mm]2*10[/mm] schreiben.
> > (Dann berechnen wir für den Test
> >
> > [mm]2^{5-1}*3^{4-1}[/mm] und [mm]2^{10-1}*3^{2-1}\,.[/mm])
> >
> > Etc. pp.
> >
> > Wir brauchen so also erheblich weniger Testfälle
> > durchzuspielen. Das ganze
> > wird sicher etwas *kombinatorisch* werden. In
> > Matlab/Octave kann ich
> > da durchaus mit Schleifen arbeiten. Mit Befehlen wie
> >
> > nchoosek([1:3],2)
> >
> > bekommt eine wunderbare Matrix, deren Zeilen man
> > durchlaufen kann. Und
> > wie gesagt: da braucht man eigentlich auch *weniger*,
> weil
> > man natürlich
> > sieht, dass die Exponenten der Größe nach abfallen
> > müssen. Man weiß halt
> > nur nicht wirklich, welche Primfaktorenanzahl
> betrachtet
> > werden soll.
> >
> > Und bei
> >
> > > [mm]\ 40'320\ =\ 2^7\cdot{}3^2\cdot{}5^1\cdot{}7^1[/mm]
> > >
> > > aber auch schon
> > >
> > > [mm]\ 30'240\ =\ 2^5\cdot{}3^3\cdot{}5^1\cdot{}7^1[/mm]
> >
> > sieht man wunderbar, dass hier [mm]2^2=4 > 3[/mm] zum Tragen kommt.
> > Also
> > ganz zufällig ist das ja nicht. Man muss sich nur mal
> > ganz genau klar machen,
> > und dann auch versuchen, hinzuschreiben, was der
> > entscheidende Punkt
> > hier ist.
> > Aber das wäre dann meiner Meinung nach erst der
> nächste
> > Optimierungsschritt. Am besten erstmal einen Algorithmus
> > bauen, der nur das oben Gesagte macht.
> >
> > Gruß,
> > Marcel
>
>
> Hallo Marcel,
>
> auch hier erwähnst du einige Gedankengänge, die ich mir
> in
> den letzten paar Tagen schon erarbeitet habe. Für alle,
> die
> sich auch ein wenig in das Thema reinknien wollen, ist es
> bestimmt ebenfalls nützlich, sich einiges davon
> ebenfalls
> selber zu "erkämpfen". Dazu habe ich auch Dutzende von
> Zetteln mit diversen Notizen und Beispielen etc.
> geschrieben.
> Dabei wurde mir klar, dass sich die beiden Aufgaben,
> zu gegebenem T entweder [mm]N_1(T)[/mm] oder aber [mm]N_2(T)[/mm] zu
> finden, im Detail doch erheblich voneinander
> unterscheiden.
Vom Gefühl her würde ich sagen, dass wir eher eine Lösung zur Berechnung
von [mm] $N_1(T)$ [/mm] bekommen.
> Meine Idee ist vor allem, möglichst ohne viel
> Computereinsatz,
> Suchalgorithmen und "brute force" auszukommen, sondern
> möglichst geschlossene Ausdrücke zu finden.
> Programmiert
> habe ich demzufolge noch gar nichts !
Klar. Aber manche Aufgaben haben keine solche Lösung. Wobei ich das hier
nicht so pessimistisch sehe. Ich würde aber dennoch auch solch' einen
Algorithmus benutzen, denn manchmal hilft sowas dabei, ein Schema zu
erkennen, was man sonst nicht vermutet hätte.
> Für die Bestimmung von [mm]N_2(T)[/mm] kann man sich etwa klar
> machen, dass man von der kompletten Primzerlegung
> einer Zahl mit mindestens T Teilern ausgehen kann.
> In einem zweiten Schritt geht es dann darum, daraus
> durch geeignete Zusammenfassungen
> eine (schwach monoton) abfallende Folge von Faktoren
> der Form [mm](\alpha_i+1)[/mm] zu erzeugen, wobei dann die
> [mm]\alpha_i[/mm]
> als Primzahlexponenten in der Faktorisierung von
>
> [mm]\ N\ =\ \prod_{i=1}^{k}p_i^{\alpha_i}[/mm]
>
> bilden. Das Ziel ist, diese Zerlegung so zu gestalten,
> dass
> das resultierende N minimal wird. Nun könnte man anstatt
> N
> dessen Logarithmus minimieren, also
>
> [mm]\ ln(N)\ =\ \summe_{i=1}^{k}{\alpha_i*ln(p_i)}[/mm]
>
> Eine halbwegs ausgereifte Idee dazu war, dass die Folge
> der
> Exponenten vielleicht entstehen könnte, indem man von
> der Folge [mm]\ <\frac{1}{ln{2}}\,,\frac{1}{ln{3}}\,,\frac{1}{ln{5}}\,,\frac{1}{ln{7}}\,,\frac{1}{ln(11)}\,,\,....\,}[/mm]
>
> ausgeht, die Glieder mit einem passend gewählten Faktor f
> multipliziert und dann auf ganzzahlige Werte rundet.
> In einigen Beispielen hat das so ungefähr gepasst, aber
> eben nur so "in etwa" und ohne exakte Begründung.
> Das Optimierungsproblem, das hier auftritt, ist eher von
> ungewohnter Getalt, da man nicht einmal eine von
> vornherein bekannte Anzahl von Variablen hat ...
Das sehe ich als das größte Problem dabei an. Denn wenn man etwa
naiv denkt, könnte man denken, dass man vielleicht die Summe der
benutzten Exponenten minimal halten sollte. Du hast aber oben gerade
ein Beispiel stehen, das deutlich zeigt, dass diese Idee zu verwerfen
ist - was daran liegt, dass wir eine andere Zahl an Primteiler haben.
Wie gesagt: Ich würde gerne weiterhin erstmal einen "schnellen" Algorithmus
zu bauen versuchen, der uns (wesentlich schneller als der jetzige hier)
die Zahlen [mm] $N_1(T)$ [/mm] liefert. Und wenn wir die haben, dann würde ich
weitergucken, ob da ein "System" erkennbar ist, wie es etwa mit der
günstigten Anzahl der mitzunehmenden Primteiler ist.
Ob sich dann was findet, ist schonmal die eine Sache. Und wenn man dann
eine Vermutung hat, auch noch zu beweisen, dass diese korrekt ist, ist
eine weitere.
Aber die Aufgabe finde ich, wie Du vielleicht merkst, durchaus interessant,
es ist nur schwer, weil ich mich gerade auf 3 weiteren Gebieten meist
mit anderen Sachen beschäftige, mich da wirklich *reinzuhängen*. Wenn
ich Zeit habe und mir noch was einfällt, melde ich mich aber. Und manchmal
hat man ja auch die besten Ideen, wenn man mal gerade nicht an ein zu
lösendes Problem denkt.
Gruß,
Marcel
|
|
|
| |
|
Hallo,
ich konnte meine oben geäußerte Vermutung, dass die
Folge der Exponenten in der Darstellung von [mm] N_2(T) [/mm] in
etwa proportional zur Folge der reziproken Werte der
Logarithmen der Primzahlen (die als Basen vorkommen)
sein könnte, durch eine etwas ungewohnte Überlegung
bestätigen.
Dabei habe ich einfach mal auf die Forderung verzichtet,
dass sich alles in [mm] \IN [/mm] , also auch nur mit ganzzahligen
Exponenten abspielen solle. Das heißt, ich lasse für die
Exponenten [mm] \alpha_i [/mm] in der Zerlegung
$\ N\ =\ [mm] \prod_{i=1}^{i_{max}}p_i^{\alpha_i}$
[/mm]
beliebige [mm] \alpha_i\in\IR^+ [/mm] zu. Um ein konkretes Problem
zu bekommen, habe ich wieder das Beispiel mit T=1000
genommen, zu welchem ich ja schon vermutete Werte
für [mm] N_1 [/mm] und [mm] N_2 [/mm] hatte, nämlich:
$\ [mm] N_1\ [/mm] =\ [mm] 2^4*3^4*5^4*7^1*11^1*13^1\ [/mm] =\ 810'810'000$ (mit genau 1000 Teilern)
$\ [mm] N_2\ [/mm] =\ [mm] 2^6*3^5*5^2*7^1*11^1*13^1\ [/mm] =\ 389'188'800$ (mit 1008 Teilern)
Man sieht schon, dass die Exponentenfolge für [mm] N_2 [/mm] in
gewisser Weise "schöner abfallend" ist als die für [mm] N_1.
[/mm]
Das liegt natürlich daran, dass die strenge Forderung
T=1000 (exakt !) im ersten Fall deutlich einschränkender
ist als im zweiten, wo T auch "etwas größer" als 1000
sein darf. Ein noch "schöneres" Verhalten der Exponenten-
folge ergibt sich nun bestimmt, wenn wir einmal ganz auf
die Forderung der Ganzzahligkeit der Exponenten verzichten.
Allerdings verliert das Ganze dann auch den eigentlich im
Reich der natürlichen Zahlen liegenden Sinn, der ganz
wesentlich mit Teilbarkeit und Primzahlen zu tun hat.
Die Erweiterung, die wir hier machen, soll aber nur einem
Zweck dienen, der nicht direkt mit Zahlentheorie zu tun hat.
Es soll nur darum gehen, eine bestimmte Extremalaufgabe
mit den gewohnten und sehr praktischen Mitteln der Analysis
lösen zu können.
Da sich in den angegebenen Beispielen für [mm] N_1(1000) [/mm] und
[mm] N_2(1000) [/mm] zeigt, dass hier jeweils nur genau die ersten 6
Primzahlen von 2 bis und mit 13 wirklich gebraucht werden,
betrachten wir nun folgende
| Aufgabe | Gesucht sind die Exponenten p,q,r,s,t,u [mm] \in\IR^+ [/mm] , für welche
die Gleichung
$\ (p+1)*(q+1)*(r+1)*(s+1)*(t+1)*(u+1)\ =\ [mm] 1000\quad (\,=\ T\,)$
[/mm]
gilt und der Term
$\ N\ =\ [mm] 2^p*3^q*5^r*7^s*11^t*13^{u}$
[/mm]
seinen kleinstmöglichen Wert annimmt. |
Die Lösung, in welcher sich z.B. noch die Bezeichnungen
a:=p+1 , b:=q+1 , c:=r+1 , d:=s+1 , e:=t+1 , f:=u+1
als hilfreich erwiesen, will ich hier nicht vorführen. Durch
Elimination der Variablen p (bzw. a) und Betrachtung der
partiellen Ableitungen nach den übrigen 5 Variablen kommt
man auf ein Gleichungssystem mit 5 Unbekannten, das
zwar zunächst ungewohnt erscheint aber doch ganz
leicht zu lösen ist. Ich empfehle die Durchführung der
Rechnung jedem, der bis hierher gefolgt ist. Erfolgserlebnis
beinahe garantiert !
Das Ergebnis der Rechnung kann man so formulieren, dass
$\ a:b:c:d:e:f\ =\ [mm] \frac{1}{ln(2)}:\frac{1}{ln(3)}:\frac{1}{ln(5)}:\frac{1}{ln(7)}:\frac{1}{ln(11)}:\frac{1}{ln(13)}$
[/mm]
gelten muss. Zusammen mit der weiteren Gleichung
$\ a*b*c*d*e*f\ =\ T\ =\ 1000$
kann man daraus die Werte von a,b,c,d,e,f und damit
natürlich auch p,q,r,s,t,u berechnen.
Das Ergebnis, das ich erhalten habe, kann man dann
so notieren:
$\ N\ [mm] \approx\ 2^{6.138}*3^{3.504}*5^{2.074}*7^{1.543}*11^{1.063}*13^{0.929}\ \approx\ 2.60*10^8$
[/mm]
Dies ist nun natürlich auch eine untere Schranke für [mm] N_2(1000)
[/mm]
und wegen $\ [mm] N_2(T)\le\ N_1(T)$ [/mm] auch untere Schranke für [mm] N_1(1000) [/mm] .
Eigenartigerweise entspricht der Wert [mm] 2.60*10^8 [/mm] fast genau
zwei Dritteln des oben angegebenen Wertes $\ [mm] N_2\approx\ 3.90*10^8$ [/mm] ...
Noch eine Vermutung zum Schluss: Das Beispiel mit
T=1000 bewegt sich eigentlich noch im Bereich sehr
kleiner natürlicher Zahlen. Da im Bereich viel größerer
Zahlen die Möglichkeiten der Faktorisierungen auch sehr
viel reichhaltiger und damit feiner abgestuft werden,
darf man wohl annehmen, dass die nach dem vorliegenden
"Rezept" bestimmte Unterschranke für [mm] N_2(T) [/mm] mit
wachsendem T und asymptotisch für $\ T\ [mm] \to\ \infty$
[/mm]
immer besser wird in dem Sinne, dass
[mm] $\limes_{T\to\infty}\,\frac{Unterschranke}{N_2}\,(T)\ [/mm] =\ 1$
Dafür einen hieb- und stichfesten Beweis zu liefern, überlasse
ich aber gerne Anderen ...
LG , Al-Chwarizmi
|
|
|
| |
|
Leider habe ich eine unangenehme Entdeckung machen müssen.
Jemand gab mir das Stichwort "superabundante Zahlen", das
vielleicht etwas mit dem Thema zu tun haben könnte.
Erstaunt sah ich dann im Netz, dass sich der berühmte
Ramanujan damit befasst hatte und dass es auch sogar
Verbindungen zur Riemannschen Vermutung geben soll.
Der Ablöscher kam dann aber, als ich in einer Tabelle in
einer von Ramanujan stammenden Arbeit
fand, dass die Zahl $\ [mm] 2^6*3^2*5^2*7*11*13*17\ \approx 2.45*10^8$
[/mm]
mehr als 1000 Teiler hat, nämlich deren 1008 .
Nun ist diese Zahl [mm] $\approx 2.45*10^8$ [/mm] (leider ...)
kleiner als die vermeintliche "untere Schranke", die ich
vorher berechnet hatte (dies allerdings unter der Annahme,
dass nur die ersten 6 Primzahlen bis und mit 13 verwendet
werden sollten).
Doch: Nachrechnen brachte die Erlösung ! Anzunehmen,
dass 6 Faktoren ausreichen würden, war ein Fehler. Für
den Fall, dass wir nur Zerlegungen nutzen, die auf den
Primzahlen 2,3,5,7,11,13 beruhen, war die Rechnung
schon korrekt. Allerdings gibt es für den Fall T=1000
(mindestens) auch eine Zerlegung der Zahl 1008 und ein
dazu gehöriges N, das kleiner ist als die errechnete
Unterschranke, wenn man auch noch die siebte Primzahl
17 für einen weiteren Faktor zulässt.
Berechnet man für die neue Situation (basierend auf
2,3,5,7,11,13,17) analog wie vorher eine untere Schranke
mit einem Wert von etwa [mm] 1.519*10^8 [/mm] .
Und damit sind wir wieder auf der "guten" Seite ...
Damit stellt sich natürlich auch wieder eine neue Frage:
Wie kann man, wenn T vorgegeben wird, herausfinden,
wie viele Primzahlen man als Basen grundsätzlich
zulassen sollte ?
Dazu hatten wir allerdings schon früher eine Abschätzung:
Wenn T gegeben ist, hat die Zahl $\ M\ =\ [mm] \prod_{i=1}^{i_{max}}p_i$
[/mm]
mit $\ [mm] i_{max}\ [/mm] =\ [mm] \left \lceil \frac{ln(T)}{ln(2)}\right \rceil$
[/mm]
wenigstens T Teiler. Das so berechnete [mm] i_{max} [/mm] gibt also
auch an, wieviele Primzahlen man allerhöchstens braucht.
Leider sind die aufgrund dieser Abschätzung erhaltenen
Unterschranken wohl im Allgemeinen wieder deutlich zu
klein und verlieren damit deutlich an praktischem Nutzen ...
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:43 Do 02.10.2014 | | Autor: | Marcel |
Hallo Al,
um Deine Überlegungen nochmal nachrechnen/nachvollziehen zu können,
wird es bei mir mit Sicherheit jetzt noch länger dauern.
> Leider habe ich eine unangenehme Entdeckung machen
> müssen.
> Jemand gab mir das Stichwort "superabundante Zahlen", das
> vielleicht etwas mit dem Thema zu tun haben könnte.
> Erstaunt sah ich dann im Netz, dass sich der berühmte
> Ramanujan damit befasst hatte und dass es auch sogar
> Verbindungen zur Riemannschen Vermutung geben soll.
> Der Ablöscher kam dann aber, als ich in einer Tabelle in
> einer
> von Ramanujan stammenden Arbeit
>
> fand, dass die Zahl [mm]\ 2^6*3^2*5^2*7*11*13*17\ \approx 2.45*10^8[/mm]
>
> mehr als 1000 Teiler hat, nämlich deren 1008 .
> Nun ist diese Zahl [mm]\approx 2.45*10^8[/mm] (leider ...)
> kleiner als die vermeintliche "untere Schranke", die ich
> vorher berechnet hatte (dies allerdings unter der
> Annahme,
> dass nur die ersten 6 Primzahlen bis und mit 13 verwendet
> werden sollten).
>
> Doch: Nachrechnen brachte die Erlösung ! Anzunehmen,
> dass 6 Faktoren ausreichen würden, war ein Fehler. Für
> den Fall, dass wir nur Zerlegungen nutzen, die auf den
> Primzahlen 2,3,5,7,11,13 beruhen, war die Rechnung
> schon korrekt. Allerdings gibt es für den Fall T=1000
> (mindestens) auch eine Zerlegung der Zahl 1008 und ein
> dazu gehöriges N, das kleiner ist als die errechnete
> Unterschranke, wenn man auch noch die siebte Primzahl
> 17 für einen weiteren Faktor zulässt.
> Berechnet man für die neue Situation (basierend auf
> 2,3,5,7,11,13,17) analog wie vorher eine untere Schranke
> mit einem Wert von etwa [mm]1.519*10^8[/mm] .
> Und damit sind wir wieder auf der "guten" Seite ...
>
>
> Damit stellt sich natürlich auch wieder eine neue Frage:
>
> Wie kann man, wenn T vorgegeben wird, herausfinden,
> wie viele Primzahlen man als Basen grundsätzlich
> zulassen sollte ?
Das war das Problem, was ich doch schon angesprochen habe. Und gerade
dieses Problem macht die Aufgabe so komplex.
Ich meine, etwa bei
[mm] $30=5*3*2=6*5=10*3=15*2\,.$
[/mm]
Da vergleicht man doch die Zahlen
[mm] $2^{29}=536'870'912$, $2^4*3^2*5^1=720$, $2^9*3^2=4608$, $2^{14}*3^{1}=49'152$ [/mm]
Meine Idee war es, "Faktoren" (inklusive Vielfachheiten) zu zählen. Hier
ist etwa
$29 > 14+1=15 > 9+2=11 > [mm] 4+2+1=7\,.$
[/mm]
Sowas funktioniert aber nicht immer, allerdings bin ich der Meinung, dass
man vielleicht doch irgendwas mit der kleinstmöglichen Summe anfangen
kann.
Oben zum Beispiel sieht man den Sprung von der 7 auf die 11. Und alleine
schon, weil
[mm] $2^4*3^2*5=720$
[/mm]
kleiner als [mm] $2^{11}$ [/mm] ist, können wir dann keine Verbesserung erwarten...
Wir bräuchten dann also gar nicht weiterrechnen.
Gruß,
Marcel
> Dazu hatten wir allerdings schon früher eine
> Abschätzung:
> Wenn T gegeben ist, hat die Zahl [mm]\ M\ =\ \prod_{i=1}^{i_{max}}p_i[/mm]
>
> mit [mm]\ i_{max}\ =\ \left \lceil \frac{ln(T)}{ln(2)}\right \rceil[/mm]
>
> wenigstens T Teiler. Das so berechnete [mm]i_{max}[/mm] gibt also
> auch an, wieviele Primzahlen man allerhöchstens braucht.
> Leider sind die aufgrund dieser Abschätzung erhaltenen
> Unterschranken wohl im Allgemeinen wieder deutlich zu
> klein und verlieren damit deutlich an praktischem Nutzen
> ...
>
> LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:02 Do 02.10.2014 | | Autor: | Marcel |
Hallo nochmal,
> Hallo Al,
>
> um Deine Überlegungen nochmal nachrechnen/nachvollziehen
> zu können,
> wird es bei mir mit Sicherheit jetzt noch länger dauern.
>
>
> > Leider habe ich eine unangenehme Entdeckung machen
> > müssen.
> > Jemand gab mir das Stichwort "superabundante Zahlen",
> das
> > vielleicht etwas mit dem Thema zu tun haben könnte.
> > Erstaunt sah ich dann im Netz, dass sich der berühmte
> > Ramanujan damit befasst hatte und dass es auch sogar
> > Verbindungen zur Riemannschen Vermutung geben soll.
> > Der Ablöscher kam dann aber, als ich in einer Tabelle
> in
> > einer
> >
> von Ramanujan stammenden Arbeit
>
> >
> > fand, dass die Zahl [mm]\ 2^6*3^2*5^2*7*11*13*17\ \approx 2.45*10^8[/mm]
>
> >
> > mehr als 1000 Teiler hat, nämlich deren 1008 .
> > Nun ist diese Zahl [mm]\approx 2.45*10^8[/mm] (leider ...)
> > kleiner als die vermeintliche "untere Schranke", die
> ich
> > vorher berechnet hatte (dies allerdings unter der
> > Annahme,
> > dass nur die ersten 6 Primzahlen bis und mit 13
> verwendet
> > werden sollten).
> >
> > Doch: Nachrechnen brachte die Erlösung ! Anzunehmen,
> > dass 6 Faktoren ausreichen würden, war ein Fehler.
> Für
> > den Fall, dass wir nur Zerlegungen nutzen, die auf den
> > Primzahlen 2,3,5,7,11,13 beruhen, war die Rechnung
> > schon korrekt. Allerdings gibt es für den Fall T=1000
> > (mindestens) auch eine Zerlegung der Zahl 1008 und ein
> > dazu gehöriges N, das kleiner ist als die errechnete
> > Unterschranke, wenn man auch noch die siebte Primzahl
> > 17 für einen weiteren Faktor zulässt.
> > Berechnet man für die neue Situation (basierend auf
> > 2,3,5,7,11,13,17) analog wie vorher eine untere
> Schranke
> > mit einem Wert von etwa [mm]1.519*10^8[/mm] .
> > Und damit sind wir wieder auf der "guten" Seite ...
> >
> >
> > Damit stellt sich natürlich auch wieder eine neue Frage:
> >
> > Wie kann man, wenn T vorgegeben wird, herausfinden,
> > wie viele Primzahlen man als Basen grundsätzlich
> > zulassen sollte ?
>
> Das war das Problem, was ich doch schon angesprochen habe.
> Und gerade
> dieses Problem macht die Aufgabe so komplex.
> Ich meine, etwa bei
>
> [mm]30=5*3*2=6*5=10*3=15*2\,.[/mm]
>
> Da vergleicht man doch die Zahlen
>
> [mm]2^{29}=536'870'912[/mm], [mm]2^4*3^2*5^1=720[/mm], [mm]2^9*3^2=4608[/mm],
> [mm]2^{14}*3^{1}=49'152[/mm]
>
> Meine Idee war es, "Faktoren" (inklusive Vielfachheiten) zu
> zählen. Hier
> ist etwa
>
> [mm]29 > 14+1=15 > 9+2=11 > 4+2+1=7\,.[/mm]
>
> Sowas funktioniert aber nicht immer, allerdings bin ich der
> Meinung, dass
> man vielleicht doch irgendwas mit der kleinstmöglichen
> Summe anfangen
> kann.
> Oben zum Beispiel sieht man den Sprung von der 7 auf die
> 11. Und alleine
> schon, weil
>
> [mm]2^4*3^2*5=720[/mm]
>
> kleiner als [mm]2^{11}[/mm] ist, können wir dann keine Verbesserung
> erwarten...
> Wir bräuchten dann also gar nicht weiterrechnen.
nur zur Ergänzung, und auch, wenn Du es nicht brauchst: Solche
Beobachtungen kann man durchaus auch in einem Algorithmus unterbringen.
Mit unseren bisherigen Erkenntnissen könnten wir also durchaus schon
schnelle Algorithmen zur Berechnung von [mm] $N_1(T)$ [/mm] schreiben.
Ich weiß, das ist nicht Dein Ziel, aber mich interessiert sowas nebenher
dennoch auch. Und wenn ich mal die Zeit finde, programmiere und teste
ich das mal (step by step).
Dann sieht man am Ende auch mal Geschwindigkeitsunterschiede zwischen
Brute Force (minimal optimiert)
Verwendung von Primteilern
Optimierte Verwendung von Primteilern (also inklusive einer weiteren
*Abbruchbedingung*)
Und vielleicht sieht das ja auch einer und sagt: "Ihr macht das doch viel
zu kompliziert..."
Gruß,
Marcel
|
|
|
| |
|
> Und vielleicht sieht das ja auch einer und sagt: "Ihr macht
> das doch viel zu kompliziert..."
Naja, sowas würde ich auf gewisse Weise sogar begrüßen -
denn leider ist dieser Thread bisher praktisch in unserem
Dialog "steckengeblieben", obwohl ich weiß, dass es
im Matheraum bestimmt noch weitere Leute gibt, die
an zahlentheoretischen Fragen interessiert sind ...
Zuerst hatte ich einfach gehofft, dass jemand gewisse
Quellenangaben machen könnte, wo man weiter suchen
könnte. Ich kann mir kaum vorstellen, dass derartige
Fragestellungen noch nicht in der mathematischen
Literatur vorkommen.
Einen wichtigen Hinweis (den mit den "superabundanten
Zahlen") habe ich auf dem Matheplaneten erhalten,
wo ich unsere Frage auch mal deponiert habe.
LG , Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:08 Do 02.10.2014 | | Autor: | hippias |
Ja, ich finde die Fragestellung auch sehr interessant, kann aber wenig beitragen. Um ein Gefuehl fuer das Problem zu bekommen, habe ich bisher aber nur das REELLE Optimierungsproblem [mm] $\prod_{i=1}^{k}p_{i}^{e_{i}}\to\text{ Max}$ [/mm] unter der Nebenbedingung [mm] $\prod_{i=1}^{k}(e_{i}+1)= [/mm] N$ mit festem $k$ geloest. Ein Ergebnis war, dass $k$ eher klein sein sollte, aber das trifft wohl nicht auf das urspruengliche Problem zu.
Sonst habe ich nur Vermutungen und wenig handfestes.
|
|
|
| |
|
> Ja, ich finde die Fragestellung auch sehr interessant, kann
> aber wenig beitragen. Um ein Gefuehl fuer das Problem zu
> bekommen, habe ich bisher aber nur das REELLE
> Optimierungsproblem [mm]\prod_{i=1}^{k}p_{i}^{e_{i}}\to\text{ Max}[/mm]
> unter der Nebenbedingung [mm]\prod_{i=1}^{k}(e_{i}+1)= N[/mm] mit
> festem [mm]k[/mm] geloest. Ein Ergebnis war, dass [mm]k[/mm] eher klein sein
> sollte, aber das trifft wohl nicht auf das urspruengliche
> Problem zu.
>
> Sonst habe ich nur Vermutungen und wenig handfestes.
hallo hippias,
dann hast du dich offenbar mit einer gewissen "Umkehrung"
des Problems beschäftigt, was wieder eine andere Sichtweise
wäre. Meine Frage war: T gegeben ---> minimales N gesucht.
Du fragst aber: N gegeben ---> maximales T gesucht.
Allerdings ist ja in [mm] \IN [/mm] zu jeder Zahl N die Anzahl T(N) der
Teiler aufgrund der Primzerlegung von N eindeutig
festgelegt - da gibt es gar nichts mehr zu optimieren.
Du kannst also mit deinem Ansatz allenfalls etwas
beitragen zur Lösung der Frage: Wie groß kann die Anzahl
der Teiler einer Zahl höchstens etwa werden, wenn die
Zahl in der Nähe einer vorgegebenen Zahl N liegt ?
Die Fragestellungen haben schon irgendwie miteinander
zu tun, aber ich denke nicht, dass man die eine Art der
Fragestellung beantwortet, indem man das "konträre"
Problem löst.
Danke aber jedenfalls für die Rückmeldung. Es freut mich,
wenn noch andere die Fragestellung interessant finden.
Im Moment habe ich gerade noch andere Obliegenheiten,
aber ich möchte jedenfalls dann auch noch etwas weiter
suchen, wenn ich wieder dazu komme.
Schönes Wochenende !
LG , Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:55 Do 09.10.2014 | | Autor: | wauwau |
In OEIS A005179 (http://OEIS.org/a005179/internal) findest du diese Folge mit einigen Literaturhinweisen und PARI-Programm
|
|
|
| |
|
> In OEIS A005179 (http://OEIS.org/a005179/internal) findest
> du diese Folge mit einigen Literaturhinweisen und
> PARI-Programm
Hallo wauwau,
dadurch, dass diese Folge der "Smallest number with exactly n divisors"
eine Katalognummer hat, ist natürlich noch nicht viel Wesentliches
gesagt. Ich werde aber schauen, ob mir die dort angegebenen
Literaturhinweise etwas bringen werden.
Hinweisen möchte ich aber insbesondere noch darauf, dass diese
Folge (auch falls Programme zu ihrer Berechnung vorliegen) noch
nicht sehr vieles bringt, wenn man auch nach der Folge der
"Smallest number with at least n divisors" fragt. Im Prinzip kann
man natürlich aus der ersten Folge auch die zweite logisch
ableiten - für einen praktikablen Algorithmus ist dies aber kaum
sehr nützlich.
LG , Al-Chwarizmi
|
|
|
|
