Collatz Schleife |
|
Allein durch Rechenleistung kannst du nur zeigen, dass es eine Schleife gibt. Um es zu widerlegen, bräuchtest du unendlich viele Zahlen, was nicht möglich ist.
Ich habe den Code trotzdem mal erweitert:
es werden Textdateien angelegt, die für jede 1000 Zahl der Reihe den aktuellen Wert enthalten (bzw. den Logarithmus davon, um die Werte klein zu halten). Die Ausgabe befindet sich im selben Ordner, wie die .exe, vermutlich also in .../bin/Debug. Das kannst du dann einfach ein Excel kopieren.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
|
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.IO;
namespace Infoboard
{
class MainClass
{
static List<BigInteger> Collatz(int start, int factor, string filename) {
//zum nachgucken, ob schon gefunden - HashSet ist da schneller
HashSet<BigInteger> found = new HashSet<BigInteger> ();
//exakte Reihenfolge des Auftretens
List<BigInteger> sequence = new List<BigInteger> ();
BigInteger next = new BigInteger (start);
using (StreamWriter sw = new StreamWriter(filename)) {
while (!found.Contains(next)) {
found.Add (next);
sequence.Add (next);
if (next.IsEven)
next /= 2;
else
next = factor * next + 1;
if (sequence.Count % 1000 == 0) //alle 1000 Werte einen ausgeben
sw.WriteLine (sequence.Count + " " + BigInteger.Log10 (sequence.Last ()));
if (sequence.Count > 500000) {
Console.WriteLine (sequence.Max ().ToString ().Length);
return new List<BigInteger> { sequence.Max() };
}
}
sequence.Add (next);
}
return sequence;
}
static void Main(string[] args) {
for (int i = 1; i < 8; i++) {
Console.WriteLine (string.Join (" ", Collatz (i, 5, "output" + i + ".txt")));
}
}
}
} |
|
eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
__________________ Syntax Highlighting fürs Board (Link)
|
|
10.04.2016 21:06 |
|
|
|
Immerhin sieht man einen linearen Zusammenhang. Das ist ja schonmal etwas...
__________________ Gruß blindmessenger
|
|
10.04.2016 22:05 |
|
|
|
Hallo,
für die Startzahl 7 bei dem Code 5n+1 entstehen schnell große Zahlen... Das Interessante ist das die Anzahl der Stellen in Abhängigkeit der Rechenschritte eine ungefähre Umkehrfunktion der 3n+1 Entwicklung ist. Beispiel:
3n+1:
Anzahl Stellen (der Startzahl): 10; Anzahl Rechenschritte (Stellen): 3
Anzahl Stellen (der Startzahl): 100; Anzahl Rechenschritte (Stellen): 4
Anzahl Stellen (der Startzahl): 1000; Anzahl Rechenschritte (Stellen): 5
5n+1 (Startzahl 7):
Anzahl Rechenschritte (Stellen): 3; Anzahl Stellen (grösste Zahl): 10
Anzahl Rechenschritte (Stellen): 4; Anzahl Stellen (grösste Zahl): 100
Anzahl Rechenschritte (Stellen): 5; Anzahl Stellen (grösste Zahl): 1000
Ich will damit nur sagen, dass hier ein ähnliches lineares Wachstum vorliegt.
__________________ Gruß blindmessenger
|
|
21.04.2016 11:01 |
|
|
|
Zitat: |
Original von eulerscheZahl
Na, meinetwegen.
Hier alle Kreise, deren Maximalwert nicht über 1 Million liegt für Faktoren < 1000.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
|
3: 1, 4, 2
5: 1, 6, 3, 16, 8, 4, 2 : 17, 86, 43, 216, 108, 54, 27, 136, 68, 34
7: 1, 8, 4, 2
15: 1, 16, 8, 4, 2
31: 1, 32, 16, 8, 4, 2
63: 1, 64, 32, 16, 8, 4, 2
127: 1, 128, 64, 32, 16, 8, 4, 2
181: 27, 4888, 2444, 1222, 611, 110592, 55296, 27648, 13824, 6912, 3456, 1728, 864, 432, 216, 108, 54 : 35, 6336, 3168, 1584, 792, 396, 198, 99, 17920, 8960, 4480, 2240, 1120, 560, 280, 140, 70
255: 1, 256, 128, 64, 32, 16, 8, 4, 2
511: 1, 512, 256, 128, 64, 32, 16, 8, 4, 2
|
|
Die Kreise zur 1 hin für 2^n-1 überaschen nicht.
Für 5 und 181 gibt es 2 Kreise.
Bei 181 habe ich keinen Kreis mit Startwert 1 gefunden. Den kann es natürlich trotzdem geben, er hat dann aber definitiv eine Länge > 100000.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
|
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
namespace Infoboard
{
class MainClass
{
static void Main(string[] args) {
int max = (int)1e6;
int[] collatz = new int[max + 1];
for (int f = 3; f < 1000; f+=2) {
for (int i = 1; i <= max; i++) {
if (i % 2 == 0)
collatz [i] = i / 2;
else
collatz [i] = f * i + 1;
}
List<List<int>> loops = new List<List<int>> ();
for (int start = 1; start <= max; start++) {
if (collatz [start] == 0)
continue;
List<int> seq = new List<int> ();
int current = start;
while (current <= max && collatz[current] != 0) {
seq.Add (current);
int tmp = collatz [current];
collatz [current] = 0;
current = tmp;
}
if (current == start)
loops.Add (seq);
}
if (loops.Count > 0)
Console.WriteLine (f + ": " + string.Join (" : ", loops.Select (loop => string.Join (", ", loop))));
}
}
}
} |
|
|
Hallo eulersche Zahl,
den Code den Du hier geschrieben hast bricht leider nach 2047 ab mit der Fehlermeldung: Der Index war außerhalb des Arraybereichs. Kann man den Code so gestalten das er über 2047 noch weiter Zyklen findet?
MfG
__________________ Gruß blindmessenger
|
|
06.11.2016 19:52 |
|
|
|
Da gab es einen Überlauf bei collatz[i] = f*i+1.
Ich habe die Datentypen auf long geändert:
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
|
using System;
using System.Collections.Generic;
using System.Linq;
namespace Infoboard
{
class MainClass
{
static void Main(string[] args) {
int max = (int)1e6;
long[] collatz = new long[max + 1];
for (int f = 3; f < 10000; f += 2) {
for (long i = 1; i <= max; i++) {
if (i % 2 == 0)
collatz [i] = i / 2;
else
collatz [i] = f * i + 1;
}
List<List<long>> loops = new List<List<long>> ();
for (int start = 1; start <= max; start++) {
if (collatz [start] == 0)
continue;
List<long> seq = new List<long> ();
long current = start;
while (current <= max && collatz[current] != 0) {
seq.Add (current);
long tmp = collatz [current];
collatz [current] = 0;
current = tmp;
}
if (current == start)
loops.Add (seq);
}
if (loops.Count > 0)
Console.WriteLine (f + ": " + string.Join (" : ", loops.Select (loop => string.Join (", ", loop))));
}
}
}
} |
|
Es wird den Überlauf weiterhin geben, aber erst bei etwa 10^12. Wenn das nicht reicht, musst du BigInteger verwenden, wird dann aber deutlich langsamer.
__________________ Syntax Highlighting fürs Board (Link)
|
|
07.11.2016 07:51 |
|
|
|
Danke Dir...
__________________ Gruß blindmessenger
|
|
07.11.2016 17:39 |
|
|
|
Hallo Euler,
kannst Du mir noch erklären bis zu welcher Startzahl jeder Algorithmus überprüft wird und wo ich das einstellen kann?
Ich nehme an folgendes sind die Anzahl der Iterationen die er für jede Startzahl durchrechnet:
int max = (int)1e6
Und folgendes ist die Anzahl der Algorithmen die überprüft wird:
for (int f = 3; f < 10000; f += 2)
MfG
blindmessenger
__________________ Gruß blindmessenger
|
|
09.11.2016 19:24 |
|
|
|
for (int f = 3; f < 10000; f += 2)
Das f ist Teil der Abbildungsvorschrift: wenn i ungerade, dann nimm f * i + 1 als Funktionswert.
max = (int)1e6;
Wenn eine Zahl größer als max (hier 1 Million ist), wird die Suche abgebrochen. Das Programm findet also keine Kreise, bei denen die größte Zahl max übersteigt. Mache die Zahl größer, dann bekommst du bessere Ergebnisse (findest vielleicht mehr Kreise), musst aber auch länger warten.
__________________ Syntax Highlighting fürs Board (Link)
|
|
09.11.2016 19:29 |
|
|
|
Ich wollte die Code schneller machen indem ich sage dass er jeden Algorithmus kn+1 nur z.b. bis zur Startzahl 500 überprüft. Meine Frage ist also bis zu welcher Startzahl er die Algorithmen überprüft?
__________________ Gruß blindmessenger
|
|
09.11.2016 19:38 |
|
|
|
Will sagen: Es müsste doch eigentlich drei Parameter geben:
Anzahl der zu überprüfenden Algorithmen: 3n+1, 5n+1, 7n+1,...
Anzahl der Iterationsschritte
Startzahl bis wohin jeder Algorithmus durchleuchtet wird...
__________________ Gruß blindmessenger
|
|
09.11.2016 19:43 |
|
|
|
Es werden alle Zahlen bis max überprüft:
Zunächst wird für jede Zahl bis max der collatz Wert berechnet. Dann wird die erste Zahl gesucht, bei der der Wert nicht 0 ist. Der Wert wird dann auf 0 gesetzt, um zu speichern, dann man dort schon war. An der Stelle des soeben überschriebenen Werts wird der nächste Funktionswert nachgeschlagen.
Wenn du weniger Startwerte verwenden willst, siehe meinen Beitrag vom 10.04.2016 21:06.
Hier wird der Funktion Collatz ein Startwert mit übergeben.
sequence.Count > 500000 gibt die maximale Zykluslänge an.
__________________ Syntax Highlighting fürs Board (Link)
|
|
09.11.2016 19:46 |
|
|
|
Alle Mersenne Algorithmen (1n+1, 3n+1, 7n+1, 15n+1, ...) haben (wahrscheinlich) die Eigenschaft genau ein Zyklus aufzuweisen. Neben den Mersennealgorithmen gibt es dann noch die 5n+1 und die 181n+1...
Die Frage ist doch ob es noch mehr Nicht-Mersenne-Algorithmen gibt ausser der 5n+1 und der 181n+1...
Ich habe bis 2^19n+1 überprüft und nur 5n+1 und 181n+1 gefunden... Das hat allerdings 12 Stunden gedauert...
Meine Vermutung: Wenn Zyklen auftreten dann schon bei relativ kleinen Startzahlen...
Kann man den letzten von Dir geposteten Code vielleicht so stricken, dass man Iterationsschritte und Startzahlen unabhängig voneinander stellen kann?
Beispiel:
Überprüfung 1n+1 - 1000n+1 (Parameter1)
Überprüfung von Startzahl 1-1000 (Parameter2)
Iterationsschritte 10000 (Parameter3)
Wenn man den Code von Beitrag vom 10.04.2016 21:06 nimmt, kann leider nur immer genau ein Algorithmus z.B. 3n+1 überprüft werden.
__________________ Gruß blindmessenger
|
|
09.11.2016 20:36 |
|
|
|
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
|
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.IO;
namespace Infoboard
{
class MainClass
{
static List<BigInteger> Collatz(int start, int factor, int maxLoop, string filename) {
//zum nachgucken, ob schon gefunden - HashSet ist da schneller
HashSet<BigInteger> found = new HashSet<BigInteger> ();
//exakte Reihenfolge des Auftretens
List<BigInteger> sequence = new List<BigInteger> ();
BigInteger next = new BigInteger (start);
while (!found.Contains (next) && found.Count < maxLoop) {
found.Add (next);
sequence.Add (next);
if (next.IsEven)
next /= 2;
else
next = factor * next + 1;
if (next < sequence [0])
break;
}
sequence.Add (next);
if (sequence[0] == next) {
Console.WriteLine ("f = " + factor + ": " + string.Join (", ", sequence));
if (filename != null) {
using (StreamWriter sw = new StreamWriter (filename, true))
sw.WriteLine ("f = " + factor + ": " + string.Join (", ", sequence));
}
}
return sequence;
}
static void Main(string[] args) {
int maxLoop = 10000; //maximale Länge eines Zyklus
string outputFile = null; //hier Dateinamen für Ausgabe eintragen, z.B. "/home/eulerschezahl/Dokumente/output.txt" (Linux) oder @"C:\Users\eulerschezahl\output.txt" (Windows)
for (int factor = 3; factor < 1000; factor += 2) { //Collatz Abbildungsvorschrift
for (int start = 1; start <= 500; start++) { //nur an diesen Stellen mit Suche beginnen
Collatz (start, factor, maxLoop, outputFile);
}
}
}
}
} |
|
__________________ Syntax Highlighting fürs Board (Link)
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von eulerscheZahl: 09.11.2016 20:53.
|
|
09.11.2016 20:49 |
|
|
|
Deine Werte für 12 und 15 sind falsch (oder mein Programm, das ich eben zusammengetippt habe).
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
|
using System;
using System.Linq;
using System.Collections.Generic;
class Collatz
{
static int Steps(long n) {
int result = 0;
while (n > 1) {
if (n % 2 == 0)
n /= 2;
else {
n = 3 * n + 1;
result++;
}
}
return result;
}
static void Main() {
List<int> zerfall = new List<int> ();
for (int i = 3; i < 1024; i += 2) {
int tmp = Steps (i);
while (zerfall.Count <= tmp)
zerfall.Add (0);
zerfall [tmp]++;
}
for (int i = 1; i < zerfall.Count; i++) {
Console.WriteLine (i + ": " + zerfall [i]);
}
}
} |
|
__________________ Syntax Highlighting fürs Board (Link)
|
|
20.11.2016 17:51 |
|
|
|