Hält dieses Programm?
-
-
hkjhjk schrieb:
Ja, das Programm wird immer halten.
Wird eine gerade Zahl eingegeben, so muss diese durch die Teilung durch 2 irgendwann 1 erreichen. Damit ist die Schleifenbedingung y != 1 nicht mehr erfüllt und die Schleife endet.
Ist die Zahl hingehen ungerade, so wird diese durch die Multiplikation mit 3 und der anschließenden Addition von 1 gerade sein.
Selbstverständlich gilt das nur für positive Zahlen. Bei einer negativen Zahl wird 1 nie erreicht.
Das ist eben falsch. Das gilt nur, wenn du eine Zweierpotenz erreichst. Aber dass man die immer erreicht, ist überhaupt nicht klar.
-
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.
-
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.
-
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.
Das ist doch gerade die Frage in diesem Thread. Scheinbar geht es nicht, sonst wäre das von "life" verlinkte Problem wohl nicht ungelöst.
-
volkard schrieb:
Das Programm kann man aber schnell testen, es gibt ja nur 2^32 ints.
Das hängt wohl stark vom Rechner ab.
-
earli schrieb:
volkard schrieb:
Das Programm kann man aber schnell testen, es gibt ja nur 2^32 ints.
Das hängt wohl stark vom Rechner ab.
Bis 10000000 terminiert der Algorithmus. Längste Sequenz bis dort ist 686 bei 8400511. Nichts deutet darauf hin, dass es nicht immer so ist. Muß mal ein Mathematiker mit Induktion beweisen. Sind keine Hobbymathematiker hier?
-
Wikipedia lesen bildet!
"Computer haben alle Zahlen bis 3\cdot 2^{61} (Stand 2008) durchprobiert; immer endet die Zahlenfolge mit 1, bestätigt also die Vermutung."
-
life schrieb:
Wikipedia lesen bildet!
"Computer haben alle Zahlen bis 3\cdot 2^{61} (Stand 2008) durchprobiert; immer endet die Zahlenfolge mit 1, bestätigt also die Vermutung."Es bleibt trotzdem eine Vermutung. Du sollst nicht nur Wikipedia lesen, sondern auch verstehen was da steht.
-
IntegerNoob schrieb:
Es bleibt trotzdem eine Vermutung. Du sollst nicht nur Wikipedia lesen, sondern auch verstehen was da steht.
Wo hab ich denn behauptet, dass das Problem gelöst wäre?
-
life schrieb:
IntegerNoob schrieb:
Es bleibt trotzdem eine Vermutung. Du sollst nicht nur Wikipedia lesen, sondern auch verstehen was da steht.
Wo hab ich denn behauptet, dass das Problem gelöst wäre?
Wer ein arrogantes "Wikipedia bildet!" postet, verdient es nicht anders. Aber um Dich Pfeife geht es hier auch garnicht. Mach also nicht so einen Lauten.
-
IntegerNoob schrieb:
earli schrieb:
volkard schrieb:
Das Programm kann man aber schnell testen, es gibt ja nur 2^32 ints.
Das hängt wohl stark vom Rechner ab.
Bis 10000000 terminiert der Algorithmus.
Mein Prog streikt bei 113383 und landet in
-82
-41
-122
-61
-182
-91
-272
-136
-68
-34
-17
-50
-25
-74
-37
-110
-55
-164
-82
Es wurden ja nur ints benutzt, nichmal unsigned ints.Nimmt man unsigned int, ist die 1431655765 kaputt und läuft gegen 0->0->0->...
-
volkard schrieb:
IntegerNoob schrieb:
earli schrieb:
volkard schrieb:
Das Programm kann man aber schnell testen, es gibt ja nur 2^32 ints.
Das hängt wohl stark vom Rechner ab.
Bis 10000000 terminiert der Algorithmus.
Mein Prog streikt bei 113383, kann das sein?
-82
-41
-122
-61
-182
-91
-272
-136
-68
-34
-17
-50
-25
-74
-37
-110
-55
-164
-82Meins sieht so aus:
public class Test { static final BigInteger ZERO = BigInteger.ZERO; static final BigInteger ONE = BigInteger.ONE; static final BigInteger THREE = BigInteger.valueOf(3); static BigInteger collatzCount (BigInteger n) { BigInteger c = ONE; while (n.compareTo(ONE) != 0) { if (n.testBit(0) == false) n = n.shiftRight(1); else n = n.multiply(THREE).add(ONE); c = c.add(ONE); } return c; } public static void main (String[] args) { BigInteger start = ONE; BigInteger end = BigInteger.valueOf(10000000); BigInteger n = ZERO; BigInteger val = ZERO; while (start.compareTo(end) < 0) { BigInteger c = collatzCount (start); if (c.compareTo(n) > 0) { n = c; val = start; System.out.println ("Longest: " + n + " - " + val); } start = start.add(ONE); } } }
-
IntegerNoob schrieb:
Meins sieht so aus:
BigIntegerJa, klar, aber das sagt wenig über das vorgelegte Programm aus und ob es Eingaben gibt, wo es nicht terminiert.
-
volkard schrieb:
Ja, klar, aber das sagt wenig über das vorgelegte Programm aus und ob es Eingaben gibt, wo es nicht terminiert.
Ach ja. Immer mein Hang zum "besser machen".
Dann hast Du ja einen Fall gefunden, bei dem sich das Originalprogramm aufhängt.
-
IntegerNoob schrieb:
volkard schrieb:
Ja, klar, aber das sagt wenig über das vorgelegte Programm aus und ob es Eingaben gibt, wo es nicht terminiert.
Ach ja. Immer mein Hang zum "besser machen".
Dann hast Du ja einen Fall gefunden, bei dem sich das Originalprogramm aufhängt.Ja.
Trotzdem boote ich mal um und lasse Dein Programm laufen (hab unter Win kein Java).
-
Habe ein wenig Speicher dazugemacht.
public class Test { static final BigInteger ZERO = BigInteger.ZERO; static final BigInteger ONE = BigInteger.ONE; static final BigInteger THREE = BigInteger.valueOf(3); static final BigInteger CACHESIZE = BigInteger.valueOf(100000); static BigInteger[] Cache; static BigInteger collatzCount (BigInteger n) { BigInteger c = ONE; while (n.compareTo(ONE) != 0) { if (n.testBit(0) == false) n = n.shiftRight(1); else n = n.multiply(THREE).add(ONE); c = c.add(ONE); } return c; } static BigInteger fastCollatzCount (BigInteger n) { BigInteger c = ONE; while (n.compareTo(CACHESIZE) >= 0) { if (n.testBit(0) == false) n = n.shiftRight(1); else n = n.multiply(THREE).add(ONE); c = c.add(ONE); } return c.add(Cache[n.intValue()]).subtract(ONE); } public static void main (String[] args) { BigInteger start = ONE; BigInteger end = BigInteger.valueOf(10000000); BigInteger n = ZERO; BigInteger val = ZERO; Cache = new BigInteger[CACHESIZE.intValue()]; while (start.compareTo(CACHESIZE) < 0) { BigInteger c = collatzCount (start); Cache[start.intValue()]=new BigInteger(c.toString()); if (c.compareTo(n) > 0) { n = c; val = start; System.out.println ("Longest: " + n + " - " + val); } start = start.add(ONE); } while (start.compareTo(end) < 0) { BigInteger c = fastCollatzCount (start); if (c.compareTo(n) > 0) { n = c; val = start; System.out.println ("Longest: " + n + " - " + val); } start = start.add(ONE); } } }Aber so richtig viel bringt das nicht. Von sechs Minuten auf eine.
Nochmal ein Faktor 6 kommt raus, wenn man sich nicht mehr für die Länge der Ketten interessiert, sondern nur ob die start-Zahl terminiert.
public class Test { static final BigInteger ZERO = BigInteger.ZERO; static final BigInteger ONE = BigInteger.ONE; static final BigInteger THREE = BigInteger.valueOf(3); static final int logfreq=1000000; public static void main (String[] args) { System.out.println("main start"); BigInteger end = BigInteger.valueOf(10000000); BigInteger start = THREE; int logcnt=logfreq-2; while (start.compareTo(end) < 0) { BigInteger y=start; while(y.compareTo(start)>=0) { if (y.testBit(0) == false) y = y.shiftRight(1); else y = y.multiply(THREE).add(ONE); } logcnt--; if (logcnt == 0) { System.out.println("getestet bis "+start); logcnt=logfreq; } start=start.add(ONE); } } }
-
Guten Morgen.
Ich habe mir den Wiki eintrag dazu mal angesehen. Und habe eine Frage. Was passiert wenn man als startwert die NULL nimmt. Dazu muss erst mal geklärt werden gehört die Null zu den natürlichen Zahlen und wenn ja ist sie gerade oder ungerade. da ja auf jede gerade eine ungerade zahl folgt muss die null gerade sein , da ja die 1 bereits ungerade ist. und dann würde das programm nicht halten, bzw in einer endlosschleife verfallen, da bei jeder operation wieder die null heraus kommt.
-
Also zumindest in meinem Programm ist die 0 ausgeschlossen.
Aber man sollte es vielleicht auf unsigned long longs umstellen.
-
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