Hält dieses Programm?

Fischkopf2009 schrieb:

Dazu muss erst mal geklärt werden gehört die Null zu den natürlichen Zahlen

Das kannst Du dir selbst aussuchen. Für 3n+1 fangen die Zahlen bei 1 an

earli

Z schrieb:

Fischkopf2009 schrieb:

Dazu muss erst mal geklärt werden gehört die Null zu den natürlichen Zahlen

Das kannst Du dir selbst aussuchen. Für 3n+1 fangen die Zahlen bei 1 an

Das wendet man nur auf ungerade Zahlen an. 0 ist gerade.

Die 0 würde man teilen, bis sie ungerade wird.

earli schrieb:

Z schrieb:

Fischkopf2009 schrieb:

Dazu muss erst mal geklärt werden gehört die Null zu den natürlichen Zahlen

Das kannst Du dir selbst aussuchen. Für 3n+1 fangen die Zahlen bei 1 an

Das wendet man nur auf ungerade Zahlen an. 0 ist gerade.
Die 0 würde man teilen, bis sie ungerade wird.

Wie bitte?

life

Steht übrigens auch alles auf der von mir verlinkten Wikipedia Seite:

"Collatz-Problem in den ganzen Zahlen

Für das von den natürlichen Zahlen (positive) auf die ganzen Zahlen (Null und negative) ausgeweitete Collatz-Problem, wurden außer dem 1-4-2-1-Zyklus noch vier weitere Zyklen gefunden:

0, 0
-1, -2, -1
-5, -14, -7, -20, -10, -5 und
-17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34, -17."

earli

Z schrieb:

Wie bitte?

"n := 3n + 1" wird nur berechnet, wenn n ungerade ist. Wenn du mit der 0 anfangen würdest, würdest du nicht bei der 1 auskommen, weil diese Formel nicht angewandt wird.

Michael E.

Fischkopf2009 schrieb:

Dazu muss erst mal geklärt werden gehört die Null zu den natürlichen Zahlen

Das nimmt man immer so, wie es gerade sinnvoll ist. Also ist in diesem Fall die Null keine natürliche Zahl.

volkard

earli schrieb:

Also zumindest in meinem Programm ist die 0 ausgeschlossen.
Aber man sollte es vielleicht auf unsigned long longs umstellen.

Dann rechnet der Computer ein wenig länger. Lang genug, daß es keine Schande ist, selber zu rechnen.

Annahme: unsigned long long, bzw jeder Typ, den wir hier betrachten wollen, ist eine binärzahl bei Überläufen werden die oberen Bits einfach weggeschmissen. Außerdem sind es 8, 16, 32, 64, 128 oder so Bits, eine Zweierpotenz.

Beobachtung: 2^(2n)+1 ist gelegentlich eine Primzahl, aber 2^(2n)-1 ist nie eine.

Begründung: Dritte Binomische Formel.
2^(2n)-1

2^n*2n-1

(2^n+1)*(2n-1)

Induktion: Da die Bitanzahl eine Zweierpotenz p ist, beginnt man mit 2^p-1 und der rechte Faktor wird 2^(p/2)-1, es wird nur p halbiert und das kann man machen bis p=4. Damit ist 3 ein Teiler der größten darstellbaren Zahl.

Beispiel:
2^16-1

(2^8+1) * (2^8-1)

(2^8+1) * (2^4+1) * (2^4-1)

(2^8+1) * (2^4+1) * (2^2+1) * (2^2-1)

257 * 17 * 5 * 3

Schluß:
Da die größte darstellbare Zahl durch 3 teilbar ist, gibt es eine Zahl b mit b*3+1=0. Also gibt es eine gültige Startzahl, die auf den Nullzyklus läuft und die 1 nie erreicht.

Berechnung für 64-bittige unsigned long long.
b=(2^64-1)/3=6148914691236517205

Aber ich erwarte auch viel kleinere Zahlen. Und bestimmt gibt es einen viieel einfacheren direkten Beweis für die Teilbarkeit durch 3.

earli

Das ist eine nette Analyse!

Aber das interessante Problem ist natürlich trotzdem das allgemeine, in dem ohne Überläufe gerechnet wird. Das ist in C natürlich entsprechend anders zu implementieren.

volkard schrieb:

Beobachtung: 2^(2n)+1 ist gelegentlich eine Primzahl, aber 2^(2n)-1 ist nie eine.

2^(2*1)-1 = 3
3 ist eine Primzahl.

volkard schrieb:

IntegerNoob schrieb:

earli schrieb:

Das ist eben falsch. Das gilt nur, wenn du eine Zweierpotenz erreichst. Aber dass man die immer erreicht, ist überhaupt nicht klar.

Wieso sollte y = 3*y+1 nicht irgendwann eine Zweierpotenz erreichen? Ein richtiger Zahlentheoretiker kann bestimmt mathematisch beweisen, dass das irgendwann bei jeder Eingabe passiert.

Soweit ich weiß, haben die es für natürliche Zahlen aber noch nicht geschafft. Der hier gepostetet Link schafft sicher Klarheit.
Das Programm kann man aber schnell testen, es gibt ja nur 2^32 ints.

Und wann sagst du, dass es bei Startwert x nich hält? Einfach 10 min. warten oder wie?

ah damn sorry. sollte erst denken dann posten. die vermutung sagt ja hält immer. und es wurde bis jetzt noch kein gegenbeispiel od. beweis gefunden.

volkard

Für unsigned long long dürfte die kleinste Zahl, die auf die 0 läuft, 2159289658376609607 sein.

Michael E.

trigga: Doch, es wurden schon Gegenbeispiele gefunden, aber eben nur wegen der endlichen Rechnerarithmetik. Man merkt, dass die Funktion nie terminiert, wenn sie in eine Schleife läuft.

earli

Michael E. schrieb:

trigga: Doch, es wurden schon Gegenbeispiele gefunden, aber eben nur wegen der endlichen Rechnerarithmetik. Man merkt, dass die Funktion nie terminiert, wenn sie in eine Schleife läuft.

Es wären aber im Allgemeinen auch Gegenbeispiele denkbar, die keinen Zyklus bilden. Die Zahl könnte ja nach Belieben wachsen.

Michael E.

Das kann sie eben nicht, weil der darstellbare Bereich endlich ist.

earli

Michael E. schrieb:

Das kann sie eben nicht, weil der darstellbare Bereich endlich ist.

Ich schrieb "im Allgemeinen".

JaykopX

Im allgemeinen hat man das aber nicht gelöst. Und es wird auch nicht so einfach werden wenn sich schon die "fiesesten" Mathematiker den Kopf daran zerbrochen haben.

Dieses Problem hängt dicht mit dem Primzahlenproblem(man kann keine analytische Formel für die Reihe der Primzahlen finden) zusammen und mit dem Problem, dass Addition(Substraktion) und Multiplikation(Division) nicht vereinbar sind. Den scheinbar harmlosen Ausdruck a+b = b*c kann man nicht so umformen das die Multiplikation(Division) verschwindet.

earli

JaykopX schrieb:

Den scheinbar harmlosen Ausdruck a+b = b*c kann man nicht so umformen das die Multiplikation(Division) verschwindet.

a+b = bc
a = b(c-1)
a = SUM_0^{c-2} b

Reicht das nicht?

Genmutant

Ich hätte dafür auch noch ln(a+b)-ln(b)=ln(c) anzubieten. Auch keine Multiplikation mehr