Hält dieses Programm?



  • 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



  • 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?



  • 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."


  • 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.



  • 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.



  • 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

    2n*2n-1

    (2n+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.



  • 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.



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



  • 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.



  • 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.



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


Anmelden zum Antworten