[ZT] Praktische Zahlen

23.07.2019, 18:03

Hosenschlange

[ZT] Praktische Zahlen

Es geht um Praktische Zahlen. Eine Praktische Zahl n ist eine solche, wenn sich alle Zahlen 1 <= m <= n aus der Summe verschiedener Teiler von n oder durch einen Teiler selbst darstellen lassen.
Zum Beispiel n = 12; die Teiler sind 1, 2, 3, 4, 6, 12. Mit diesen Teilern lassen sich alle Zahlen von 1 bis 12 darstellen:
m = 1 = 1
m = 2 = 2
m = 3 = 3 = 1 + 2
m = 4 = 4 = 1 + 3
m = 5 = 2 + 3
m = 6 = 6 = 2 + 4
m = 7 = 1 + 6
m = 8 = 2 + 6
m = 9 = 3 + 6
m = 10 = 1 + 2 + 3 + 4
m = 11 = 2 + 3 + 6
m = 12 = 12 = 2 + 4 + 6

Die Zahl 10 ist nicht Praktisch, weil aus den Teilern 1, 2, 5, 10 bspw. die Zahl m = 4 nicht gebildet werden kann.

Um nun zu bestimmen, ob eine Zahl n Praktisch ist, müsste man ziemlich viele Kombinationen der Teiler von n durchgehen und die Summe bilden. Was mich zu einer -wahrscheinlich haarsträubenden- Anfängerfrage führt: Kann ich allein aus der Primfaktorisierung ablesen, ob eine Zahl n Praktisch ist? Und zwar in der Form, dass ich rausfinde, wie viele Teiler t eine Zahl hat. Damit schaue ich, ob $\begin{eqnarray*} 2^{t-1} \lt n-1 \end{eqnarray*}$ gilt. Falls ja, dann ist n keine Praktische Zahl. Als bisher Gedankenexperiment habe ich noch kein Gegenbeispiel gefunden.

Könnte mir damit jemand weiterhelfen?

23.07.2019, 18:27

HAL 9000

Auf diesen Beitrag antworten »

$\begin{eqnarray*} n = p_1^{r_1}\cdot \ldots p_s^{r_s} \end{eqnarray*}$ hat genau $\begin{eqnarray*} t=(r_1+1)\cdot \ldots\cdot (r_s+1) \end{eqnarray*}$ positive Teiler.

Und ja, die Teilermenge bestehend aus den $\begin{eqnarray*} t-1 \end{eqnarray*}$ echten Teilern von $\begin{eqnarray*} n \end{eqnarray*}$ (also alle außer $\begin{eqnarray*} n \end{eqnarray*}$ selbst) hat insgesamt $\begin{eqnarray*} 2^{t-1}-1 \end{eqnarray*}$ nichtleere Teilmengen. Selbst wenn die alle zu verschiedenen Summen führen und auch kleiner als $\begin{eqnarray*} n \end{eqnarray*}$ sind, so können sie doch im Fall $\begin{eqnarray*} 2^{t-1}-1 < n-1 \end{eqnarray*}$ nicht alle Werte $\begin{eqnarray*} 1\ldots (n-1) \end{eqnarray*}$ abdecken. Insofern ist $\begin{eqnarray*} 2^{t-1}<n \end{eqnarray*}$ ein hinreichendes Kriterium dafür, dass $\begin{eqnarray*} n \end{eqnarray*}$ keine praktische Zahl ist. Notwendig ist es natürlich nicht. Insofern muss man

Zitat:

Original von Hosenschlange
Kann ich allein aus der Primfaktorisierung ablesen, ob eine Zahl n Praktisch ist?

verneinen, kann aber feststellen: In gewissen Fällen kann man bereits anhand der Primfaktorzerlegung ausschließen, dass $\begin{eqnarray*} n \end{eqnarray*}$ eine praktische Zahl ist.

23.07.2019, 18:34

Hosenschlange

Auf diesen Beitrag antworten »

Danke, HAL Freude

vielleicht fällt mir ja noch was ein, um den ganzen Prozess zu beschleunigen

23.07.2019, 19:14

HAL 9000

Auf diesen Beitrag antworten »

Es gibt aber auch ausgewählte Zahlen, wo das Kriterium ausgesprochen "scharf" ist:

Nämlich die Zweierpotenzen $\begin{eqnarray*} n=2^m \end{eqnarray*}$ : Die sind alle praktisch, und dieses $\begin{eqnarray*} n \end{eqnarray*}$ hat genau $\begin{eqnarray*} t=m+1 \end{eqnarray*}$ positive Teiler. Es ergibt sich $\begin{eqnarray*} 2^{t-1} = 2^m = n \end{eqnarray*}$ , d.h., das hinreichende Kriterium $\begin{eqnarray*} 2^{t-1} < n \end{eqnarray*}$ für nichtpraktische Zahlen wird auch nur ganz knapp gerissen. Augenzwinkern

23.07.2019, 19:26

Hosenschlange

Auf diesen Beitrag antworten »

ich hatte mich schon ein klein wenig belesen und rausgefunden, dass alle Praktischen Zahlen (PZ) durch 4 und/oder 6 teilbar sind, abgesehen von 1 und 2. Aber das sind ja grundsätzlich auch Zweierpotenzen. Ungerade Zahlen gehen gar nicht, außer 1. Fakultäten und Primfakultäten sind immer dabei. Und wenn n eine PZ ist, dann ist das Produkt von n und einem Teiler von n ebenfalls wieder eine PZ.... etc.

Die Frage bleibt, ob mir das helfen kann, einen fixen Weg zu finden, um feststellen zu können, ob n eine PZ ist verwirrt

23.07.2019, 19:41

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hosenschlange
dass alle Praktischen Zahlen (PZ) durch 4 und/oder 6 teilbar sind

Da lässt sich sicher noch mehr rausfinden von dieser Struktur: Ist beispielsweise 2 mit Exponent $\begin{eqnarray*} r \end{eqnarray*}$ in $\begin{eqnarray*} n \end{eqnarray*}$ vertreten (d.h. $\begin{eqnarray*} 2^r\mid n \end{eqnarray*}$ aber $\begin{eqnarray*} 2^{r+1}\nmid n \end{eqnarray*}$ ), dann muss für den zweitkleinsten in $\begin{eqnarray*} n \end{eqnarray*}$ vorhandene Primfaktor $\begin{eqnarray*} p \end{eqnarray*}$ (soweit vorhanden) die Bedingung $\begin{eqnarray*} p < 2^{r+1} \end{eqnarray*}$ gelten.

D.h., $\begin{eqnarray*} n = 2^2\cdot 11\cdot 13 \end{eqnarray*}$ ist nicht praktisch.

23.07.2019, 20:20

Hosenschlange

Auf diesen Beitrag antworten »

Wikipedia listet ein paar auf... ich werde mal versuchen, gerade bei einer größeren Anzahl, die Bestimmung über ein Sieb zu lösen

26.07.2019, 08:43

Hosenschlange

Auf diesen Beitrag antworten »

Noch eine gedankliche Experimentalschraube......
Gegeben sei eine Zahl n und deren Faktorisierung $\begin{eqnarray*} p_{1}^{e_{1}}*p_{2}^{e_{2}}*...*p_{n}^{e_{n}} \end{eqnarray*}$ . Wir hatten ja schon festgestellt, dass Zweierpotenzen Praktisch sind. Daraus folgt, dass jede andere gültige Praktische Zahl wenigstens zwei Primfaktoren hat, wobei 2 die erste ist.
Mir kam nun die Idee, die Kette der Primfaktoren und ihrer Potenzen zu durchlaufen, zu multiplizieren und den nächsten Primfaktor zu betrachten. Wie folgt:
(1) Variable S = 1
(2) durchlaufe die Primfaktoren/-exponenten vom kleinsten bis zum zweitgrößten
(3) multipliziere $\begin{eqnarray*} S = S * p_{i}^{e_{i}} \end{eqnarray*}$
(4) prüfe ob $\begin{eqnarray*} S * p_{i} \lt p_{i+1} \end{eqnarray*}$
(5) wenn das letzte Produkt aus (4) kleiner ist, dann liegt keine praktische Zahl vor, ansonsten weiter bei Schritt (3)
(6) wenn kein Abbruch erfolgt war, dann ist n Praktisch

Beispiel n = 78 (2 * 3 * 13):
- S = 1
- $\begin{eqnarray*} p_{1} = 2 \Rightarrow S = 2 \end{eqnarray*}$
- $\begin{eqnarray*} p_{2} = 3, S * p_{1} = 4 \gt 3 \end{eqnarray*}$ ... also weiter
- $\begin{eqnarray*} p_{2} = 3 \Rightarrow S = 6 \end{eqnarray*}$
- $\begin{eqnarray*} p_{3} = 13, S * p_{2} = 18 \gt 13 \end{eqnarray*}$
Fertig. n = 78 ist also Praktisch.

Ist das evtl ein Holzweg, oder kann man das durchgehen lassen?

Neue Frage »

Antworten »

[ZT] Praktische Zahlen

Verwandte Themen