Eine besondere Zahl wird gesucht

25.08.2022, 02:53

Phenix

Auf diesen Beitrag antworten »

Eine besondere Zahl wird gesucht

Wenn man die Kuben der einzelnen Ziffern einer beliebigen durch 3 teilbaren natürlichen Zahl addiert und mit der entstandenen Zahl wieder so verfährt, landet man nach einer endlichen Anzahl von Schritten stets bei der gesuchten Zahl, die sich dann selbst reproduziert.

Wie heißt diese Zahl und kann jemand beweisen, dass dieser Zyklus mit jeder durch 3 teilbaren natürlichen Zahl auftritt.

25.08.2022, 08:54

HAL 9000

Auf diesen Beitrag antworten »

Bruteforce über alle durch 3 teilbaren maximal vierstelligen Zahlen zeigt, dass jede dieser Zahlen nach maximal 13 Operationen in Fixpunkt 153 von $\begin{eqnarray*} f \end{eqnarray*}$ mündet. Ein Beispiel für solch eine maximal lange Kette ist

177 , 687 , 1071 , 345 , 216 , 225 , 141 , 66 , 432 , 99 , 1458 , 702 , 351 , 153

Jetzt kann man sich noch überlegen, warum es ausreicht, sich auf diese durch 3 teilbaren maximal vierstelligen Zahlen zu beschränken - wie sieht es aus, Phenix, das wäre doch mal eine Beweisübung für dich?

25.08.2022, 09:33

Leopold

Auf diesen Beitrag antworten »

Das erinnert mich an die Kaprekar-Zahl, Huggys Lieblingsproblem.

25.08.2022, 09:47

HAL 9000

Auf diesen Beitrag antworten »

Jetzt kann man noch untersuchen, was für nicht durch 3 teilbare Zahlen geschieht. Dass dort auch einiges anders laufen kann, zeigt bereits Startwert 4:

4 , 64 , 280, 520, 133, 55, 250, und dann die rote Dreiersequenz als Periode.

25.08.2022, 11:01

Phenix

Auf diesen Beitrag antworten »

Es muss doch einen Grund dafür geben, weshalb der Rechen-Algorithmus (s.o.) immer bei $\begin{eqnarray*} 1^3 \end{eqnarray*}$ + $\begin{eqnarray*} 5^3 \end{eqnarray*}$ + $\begin{eqnarray*} 3^3 \end{eqnarray*}$ = 153 endet, wenn die Ziffern-Summe einer beliebigen Start-Zahl durch 3 teilbar ist. ich finde den Grund nicht! … wer findet ihn?

25.08.2022, 11:08

HAL 9000

Auf diesen Beitrag antworten »

Es steht dir offen, eine einfachere Begründung als Bruteforce anzugeben.

Dass es sich durchaus nicht zwingend nur aus dem Verfahren ergibt, zeigen die Beispiele von nicht durch 3 teilbaren Anfangswerten: Da gibt es sogar vier mögliche Fixpunkte 1, 370, 371, 407, in die die Folge hineinlaufen kann, oder aber auch in Zweier- bzw. Dreierzyklen (136,244), (919,1458), (55,250,133), (160,217,352).

Zitat:

Original von HAL 9000
Jetzt kann man sich noch überlegen, warum es ausreicht, sich auf diese durch 3 teilbaren maximal vierstelligen Zahlen zu beschränken - wie sieht es aus, Phenix, das wäre doch mal eine Beweisübung für dich?

Ist immer noch offen. Augenzwinkern

Augenzwinkern

Anzeige

25.08.2022, 11:18

Phenix

Auf diesen Beitrag antworten »

Schade, ich dachte es gäbe vielleicht einen Beweis für die Selbstreproduktion der Zahl 153 aus beliebigen Zahlen, die durch drei teilbar sind.

25.08.2022, 11:20

HAL 9000

Auf diesen Beitrag antworten »

Den gibt es doch, und er steht (zumindest als Skizze) oben - vielleicht geruhst du das zur Kenntnis zu nehmen.

25.08.2022, 11:25

Phenix

Auf diesen Beitrag antworten »

… und wie lautet der Beweis?

PS: es gibt ja insgesamt noch 3 andere dreistellige „Narzissen“, nämlich
370
371
407
aber die sind nicht selbstreproduzierend wie 153, oder?

25.08.2022, 11:30

HAL 9000

Auf diesen Beitrag antworten »

Er steht skizziert im Beítrag 8:54.

25.08.2022, 11:35

Phenix

Auf diesen Beitrag antworten »

Aber 8:53 beweist doch nicht, dass jede durch 3 teilbare Zahl auf 153 endet.

25.08.2022, 11:39

HAL 9000

Auf diesen Beitrag antworten »

Herrje, du drehst dich gern im Kreis und verschließt die Augen vor den Argumenten ... also nochmal deutlicher:

Nimm alle diese 3333 Zahlen - das sind 3, 6, 9, 12, ... , 9996, 9999 - und unterziehe sie jeweils 13mal iteriert dieser Operation, dann wirst du feststellen, dass jedesmal 153 herauskommt. Das kannst du in der Programmiersprache deiner Wahl tun - zur Not tut es auch ein entsprechend aufgebrezeltes Excel-Sheet.

Natürlich fehlt noch der kleine Beweis, dass die Betrachtung maximal vierstelliger Zahlen ausreicht - darüber solltest DU ja mal nachdenken. Aber anscheinend ist es zwecklos, dich mal zu so etwas zu motivieren, obgleich dieser Hilfsbeweis sehr einfach ist.

------------------------------------------------------------------------

Viele mathematische Beweise enthalten auch eine Bruteforce-Komponente, das ist nichts "ehrenrühriges":

a) So hatte es 1976 einiges Aufsehen erregt, dass ein Bestandteil des Beweises des Vier-Farben-Satzes darin bestand, dass 1936 Unterfälle automatisiert vom Computer geprüft wurden, auch eine Art Bruteforce.

b) Soweit ich weiß, ist die Klassifikation der endlichen einfachen Gruppen auch nicht ohne Computerunterstützung gelaufen.

25.08.2022, 11:52

Phenix

Auf diesen Beitrag antworten »

Nimm das Collatz-Problem bzw. die (3n+1)-Vermutung: Für über 12-stellige große Zahlen hat man bisher gezeigt, dass die Collatz-Folge (bisher) immer auf 4, 2, 1 endet. Das ist aber kein Beweis, denn es könnte ja Zahlen geben, die NICHT auf 4, 2, 1 enden.

Beim 153-Problem kann man das genau so sehen. Nur weil man für n-Zahlen gezeigt hat, dass sie bei 153 enden, beweist das doch nicht, dass ALLE durch 3 teilbare Zahlen bei 153 enden, außer es wurde bewiesen und diesen Beweis hätte ich gern …

25.08.2022, 12:42

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Natürlich fehlt noch der kleine Beweis, dass die Betrachtung maximal vierstelliger Zahlen ausreicht - darüber solltest DU ja mal nachdenken. Aber anscheinend ist es zwecklos, dich mal zu so etwas zu motivieren, obgleich dieser Hilfsbeweis sehr einfach ist.

Zum vierten und letzten mal - lerne endlich mal lesen! Forum Kloppe

Forum Kloppe

Forum Kloppe

Forum Kloppe

---------------------------------------------------

Also gut, dieser Beweis der Hilfsaussage, zu dem du ja anscheinend komplett unfähig bist:

Mit Dezimaldarstellung $\begin{eqnarray*} n = \sum_{k=0}^{m-1} z_k 10^k \end{eqnarray*}$ der $\begin{eqnarray*} m \end{eqnarray*}$ -stelligen natürlichen Zahl $\begin{eqnarray*} n \end{eqnarray*}$ ist $\begin{eqnarray*} f(n) = \sum_{k=0}^{m-1} z_k^3 \end{eqnarray*}$ das Ergebnis der im Text beschriebenen Operation.

1) Wegen $\begin{eqnarray*} z^3-z = (z-1)z(z+1)\equiv 0\bmod 3 \end{eqnarray*}$ für alle möglichen Ziffern $\begin{eqnarray*} z \end{eqnarray*}$ gilt $\begin{eqnarray*} f(n) \equiv \sum_{k=0}^{m-1} z_k\equiv n\bmod 3 \end{eqnarray*}$ , d.h., mit dieser Operation verbleibt man in der Menge der durch 3 teilbaren Zahlen.

2) Durch Vollständige Induktion kann man leicht $\begin{eqnarray*} 10^{m-1} > m\cdot 9^3 \end{eqnarray*}$ für alle natürlichen $\begin{eqnarray*} m\geq 5 \end{eqnarray*}$ nachweisen. Das bedeutet, dass $\begin{eqnarray*} f(n) \end{eqnarray*}$ auf eine mindestens fünfstellige Zahl angewandt garantiert die Stellenzahl um mindestens 1 verringert. Daraus kann man wiederum schließen, dass jede natürliche Zahl $\begin{eqnarray*} n \end{eqnarray*}$ nach einer endlichen Anzahl von Operationen in eine maximal vierstellige Zahl mündet. Und für die greift ja dann die obige Bruteforcebetrachtung.

Nun zum eigentlichen Beweis dieses $\begin{eqnarray*} 10^{m-1} > m\cdot 9^3 \end{eqnarray*}$ :

Induktionsanfang $\begin{eqnarray*} m=5 \end{eqnarray*}$ : Gilt wegen $\begin{eqnarray*} 10^{m-1} = 10000 > 3645 = m\cdot 9^3 \end{eqnarray*}$

Induktionsschritt $\begin{eqnarray*} m\to m+1 \end{eqnarray*}$ : Der gilt infolge

$\begin{eqnarray*} 10^m = 10\cdot 10^{m-1} \stackrel{IV}{>} 10m\cdot 9^3 > (m+1)\cdot 9^3 \end{eqnarray*}$ für alle $\begin{eqnarray*} m\geq 5 \end{eqnarray*}$ .

---------------------------------------------------

1) Es gibt Leute, die können solche Beweise selbst erstellen.

2) Dann gibt es Leute, die können solche Beweise lesen und nachvollziehen.

3) Weiter gibt es Leute, die verstehen, dass da ein Beweis vorliegt, haben aber Schwierigkeiten beim Verständnis.

4) Und schließlich gibt es Leute, die kriegen gar nicht mit, dass da ein Beweis vorgestellt wurde.

Du gehörst offenbar zu Kategorie 4.

25.08.2022, 13:23

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von Phenix
Nimm das Collatz-Problem bzw. die (3n+1)-Vermutung:

Beim Collatz-Problem ist ja auch die nächste Zahl der Folge nicht ab irgendeinem Grenzwert zwingend kleiner als die Ausgangszahl. Im Gegenteil, bei jeder zweiten ungeraden Zahl $\begin{eqnarray*} >1 \end{eqnarray*}$ ist die nächste Zahl größer als die Ausgangszahl. Man hat für ungerade Ausgangszahlen bisher nicht mal zeigen können, dass man irgendwann zwingend eine Zahl bekommt, die kleiner ist als die Ausgangszahl. Deshalb lässt sich das Collatz-Problem im Unterschied zu deinem Problem bisher nicht auf eine endliche Zahl zu überprüfender Fälle reduzieren.

25.08.2022, 13:27

Phenix

Auf diesen Beitrag antworten »

Vielen Dank für Ihre Bemühungen.
Ich gehöre nicht zur 4. Kategorie, sondern eher zur 3. Kategorie.

25.08.2022, 13:34

HAL 9000

Auf diesen Beitrag antworten »

Nein. Jemand der mitgekriegt hätte, dass das 8:54 eine Beweisskizze darstellt, hätte vielleicht nachgefragt:

"Ah, interessant. Aber wie beweist man diesen letzten Teil, dass es ausreicht vierstellige Zahlen zu betrachten?"

Nein, du hast stereotyp wiederholt

"Wie lautet der Beweis für die Selbstreproduktion der Zahl 153 aus beliebigen Zahlen, die durch drei teilbar sind?"

und machst bescheuerte Quervergleiche zu Collatz, so als hätte ich nicht kapiert, dass man das ganze auch für größere als vierstellige Zahlen beweisen muss - tust schlicht so, als hätte ich noch gar nichts zur Beweismethodik geschrieben. Dieses immer wieder An-den-Anfang-zurückkehren, obwohl doch schon erhebliche Fortschritte im Thread stehen, ist eine nervtötende Ignoranz von dir, die auch zeigt, dass dein Halbwissen wohl eher ein Viertel- oder gar nur Achtelwissen ist.

15.09.2022, 15:21

dalek

Auf diesen Beitrag antworten »

Collatz-Vermutung
Eine statistische Betrachtung der Collatz Folgen

Die Collatz Vermutung, eines von vielen ungelösten Problemen in der Mathematik, ist schon eine harte Nuss. Insbesondere dann, wenn man versucht, sie mit normalen Methoden aus der Zahlentheorie zu beweisen.

Terence Tao, der berühmte Fields Medaillen Preisträger, hat in 2019 den Beweis für "fast" alle natürlichen Zahlen größer als 1 geführt und dabei auf statistische Verfahren und auf die Tatsache, dass es sich bei den Collatz Folgen um „Random Walks“ handelt, zurückgegriffen. Dieser Beweis ist ziemlich komplex und dürfte für Nicht-Mathematiker ziemlich unverständlich sein.

Ich habe mal versucht mich der Lösung es Problems mit einfacheren Mitteln zu nähern und wäre sehr dankbar, wenn meine Argumentation kritisch hinterfragt und geprüft werden würde. Ich möchte noch erwähnen, dass diese Betrachtung der Collatz-Folge vielleicht nicht unbedingt den mathematischen Konventionen entspricht, ich bin ja auch kein Mathematiker, sondern Physiker.

Unter der Berücksichtigung, dass wir es bei der Collatz Folge mit einem „Random Walk“ zu tun haben, lässt sich folgendes Modell konstruieren:

Wir betrachten alle ungeraden Zahlen größer als 1 und ihr Verhalten unter Verwendung der Collatz Funktion, nachfolgend Col(u) genannt. Diese Zahlen lassen sich in folgende Teilmengen aufteilen:

Teilmenge 1:
Alle Zahlen, die unter Anwendung von Col(u) steigen: u = x * 4 + 3 mit x >= 0
Dies sind:
(3 * 3 + 1) / 2 = 5
(7 * 3 + 1) / 2 = 11
(11 * 3 + 1) / 2 = 17
…
Im Nenner steht immer 2 und die Collatz-Folge wächst im Folgeglied um den Faktor u * 3/2 + 1/2
Die Wahrscheinlichkeit P(T1) für das Auftreten dieser ungeraden Zahlen in N beträgt 1/2 = 50%.

Teilmenge 2:
Alle Zahlen, die unter Anwendung von Col(u) fallen: u = x * 8 + 1 mit x >= 0
Dies sind:
(1 * 3 + 1) / 4 = 1 -> endet in einem Loop
(9 * 3 + 1) / 4 = 7
(17 * 3 + 1) / 4 = 13
(25 * 3 + 1) / 4 = 19
…
Im Nenner steht immer 4 und die Collatz-Folge fällt im Folgeglied um den Faktor u * 3/4 + 1/4
Die Wahrscheinlichkeit P(T2) für das Auftreten dieser ungeraden Zahlen in N beträgt 1/4 = 25%.

Teilmenge 3:
Alle Zahlen, die unter Anwendung von Col(u) fallen: u = x * 8 + 5 mit x >= 0
Dies sind:
(5 * 3 + 1) / 16 = 1
(13 * 3 + 1) / 8 = 5
(21 * 3 + 1) / 64 = 1
(29 * 3 + 1) / 8 = 11
...
Im Nenner steht mindestens 8 und die Collatz Folge fällt im Folgeglied um den Faktor u * 3/8 + 1/8
Die Wahrscheinlichkeit P(T3) für das Auftreten dieser ungeraden Zahlen in N beträgt 1/4 oder 25%.
Genauer gesagt besteht die Teilmenge T3 aus ungeraden Zahlen mit den Wahrscheinlichkeiten
1/8 + 1/16 + 1/32 ... + 1/2**n = 1/4 = 25%

Satz 1:

Wenn wir col(u) mit einer beliebigen ungeraden Zahl u starten, so sind nur Zahlenfolgen mit Zahlen aus folgenden 3 Teilmengen möglich:

T1 mit P(T1) = 1/2
T2 mit P(T2) = 1/4
T3 mit P(T3) = 1/4

Jede Folge durchläuft einen „Random Walk“ mit den Wahrscheinlichkeiten

P(T1) = 1/2 für Anstiege (u * 3/2 + 1/2)
P(T2) = 1/4 für Abstiege (u * 3/4 + 1/4)
P(T3) = 1/4 (1/8, 1/16, 1/32 …) für Abstiege mindestens (u * 3/8 + 1/8)

P(T1) + P(T2) + P(T3) = 1 = 100%

Für die Nenner der An- und Abstiege schreiben wir in Kurzform:

2 2 4 8

Dies ist die minimale Bedingung, damit die Collatz-Folge unter den Startwert fällt.
Jede Folge, sei sie auch noch so groß, genügt mindestens immer dieser Wahrscheinlichkeit.
Es spielt dabei keine Rolle welcher Startwert gewählt wird, wieviele Folgeglieder es gibt oder welche Reihenfolge die Nenner haben.
___________________________________________________________________________
_______

Ein schönes Beispiel für eine derartige Folge ist

7 (2) 11 (2) 17 (4) 13 (8) 5

Wir können sagen, es gibt 2 Anstiege mit Nenner (2), einen Abstieg mit Nenner (4) und einen Abstieg mit Nenner (8).

Egal mit welchem Startwert wir beginnen, die Wahrscheinlichkeiten sind gemäß Satz 1 so gegeben, dass auf 2 Anstiege ein Abstieg mit dem Nenner 4 und ein Abstieg mindestens mit dem Nenner 8 folgt oder die Nenner einfach der Häufigkeitsverteilung genügen müssen.
Fällt der Wert eines Folgeglieds unter den Startwert, so ist das Kriterium für einen Abstieg auf 1 gegeben und das ist gemäß Satz 1 immer der Fall.

Wir können, unter Berücksichtigung der Häufigkeitsverteilung gemäß Satz 1, beliebige Folgen konstruieren. Egal mit welcher Zahl wir starten, die Folge fällt immer unter den Startwert.

Zum Beispiel:
x - (2 2 2 2 2 2 2 2 4 4 4 4 8 8 8 8) - y (y < x)
x - (2 2 4 4 4 4 2 2 2 2 2 2 8 8 8 8) - y (y < x)

In der Folge mit dem Startwert 27, die sehr viele Folgeglieder hat, wird dies besonders anschaulich. Dort ist das Verhältnis der Anstiege zu den Abstiegen annähernd 1.

Ich habe ein kleines Computerprogramm geschrieben und alle kumulierten Anstiege und Abstiege bis zur Zahl 44.600.001 berechnen lassen.

Hier das Ergebnis:

u=659344622 d=659278436 d4=318848842 d8=163968216 d16=105036167 d32=39534448 d64=16274006

Wie man sehen kann, nähert sich das Verhältnis der Anstiege u zu den Abstiegen d immer mehr der 1. Die Symbole d4, d8, d16 und so weiter veranschaulichen die oben genannten Häufigkeitsverteilungen und nähern sich den vorhergesagten Werten.

Meine Schlussfolgerung:

Unter den Bedingungen der Collatz-Folge, mit den auftretenden Häufigkeitsverteilungen für ungerade Zahlen, kann die Collatz-Folge 3 u + 1 nur fallen und muss letztendlich mit 1, in einem Loop, enden. Ob dies nun einen gültigen Beweis für die Collatz-Vermutung darstellt, kann ich noch nicht sagen und stelle diese Frage zur Diskussion.

16.09.2022, 14:04

Huggy

Auf diesen Beitrag antworten »

RE: Collatz-Vermutung

Zitat:

Original von dalek
Unter den Bedingungen der Collatz-Folge, mit den auftretenden Häufigkeitsverteilungen für ungerade Zahlen, kann die Collatz-Folge 3 u + 1 nur fallen und muss letztendlich mit 1, in einem Loop, enden. Ob dies nun einen gültigen Beweis für die Collatz-Vermutung darstellt, kann ich noch nicht sagen und stelle diese Frage zur Diskussion.

Das ist natürlich kein Beweis. Deine Überlegung, dass, wenn man sich auf die ungeraden Zahlen in der Folge beschränkt, die nächste Zahl der Folge im Mittel kleiner ist als die vorige Zahl, ist eine der ältesten Überlegungen zum Collatz-Problem. Man kann sie zu einem Beweis verdichten, das "fast alle" Folgen hinunter zur $\begin{eqnarray*} 1 \end{eqnarray*}$ gehen. Fast alle sind aber nun mal nicht alle. Lies dir mal diesen Vortrag von Tao durch:

https://terrytao.files.wordpress.com/2020/02/collatz.pdf

Deine Überlegung wird da auch erwähnt. Es wird da auch erwähnt, dass man bei $\begin{eqnarray*} 3n-1 \end{eqnarray*}$ statt $\begin{eqnarray*} 3n+1 \end{eqnarray*}$ im Bildungsgesetz der Folge noch zwei weitere Zyklen bekommt, nämlich

$\begin{eqnarray*} 5 \to 7 \to 5 \end{eqnarray*}$

$\begin{eqnarray*} 17 \to 25 \to37 \to 55 \to 41 \to61 \to 91 \to 17 \end{eqnarray*}$

Das zeigt klar, dass deine Überlegung kein Beweis ist, dass alle Folgen zur $\begin{eqnarray*} 1 \end{eqnarray*}$ gehen, denn sie gilt ja umso mehr für die modifizierte Folge.

16.09.2022, 14:53

dalek

Auf diesen Beitrag antworten »

RE: Collatz-Vermutung
Vielen Dank für Deine Antwort.

Ich hab mir den Vortrag von Terence Tao gerade angeschaut. Meine Schlussfolgerung ist wirklich kein Beweis für die Collatz-Vermutung und sagt insbesondere nichts darüber aus, ob irgendeine Collatz-Folge in einer Schleife enden kann oder nicht. Es wäre ja auch zu schön gewesen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »