Forum
 
Fragen
 
Suchen
 
Über Uns
 
 

Collatz Schleife
Neue Frage »

09.04.2016, 16:24 Auf diesen Beitrag antworten »
blindmessenger Collatz Schleife

Meine Frage:
Hallo,
im Internet habe ich einen Code aufgeschnappt womit man Collatz reihen generieren kann. Ich interessiere mich mathematisch für das Collatz Problem und würde den Code gerne modifizieren. Leider habe ich von Informatik keine Ahnung. Brauche den Code also nur als Mittel zum Zweck... Vielleicht kann mir jemand helfen...

Der Code generiert mit VBA Excel für die Zahlen 1-100 (die in der ersten Zeile einer Excel Tabelle aufgereiht sind) die Bildungsvorschrift bei geraden Zahlen durch 2 und bei ungeraden Zahlen 3n+1 bis man bei 1 angelangt ist. Wenn ich den Code mit 5n+1 durchrechnen lasse taucht interessanterweise mehr als eine Schleife auf.

Ich brauche den Code also so dass er nicht bei 1 abbricht sondern genau dann wenn eine Zahl doppelt auftaucht. So dass man sofort sieht wenn eine Schleife auftacht. Beispiel für 5n+1

1,6,3,16,8,4,2,1
2,1,6,3,16,8,4,2,1
3,16,8,4,2,1,6,3,16,8,4,2,1
4,2,1,6,3,16,8,4,2,1
5,26,13,66,33,166,83,416,208,104,52,26


Hier gibt es also für die Zahlen 1-4 die Schleife mit der Zahl 1. Bei der 5. Zahl kommt nun eine neue Schleife mit der Zahl 26. Da mein Code ja nun immer bis 1 rechnen muss kommt es dann in diser 5. Spalte zu einer Dauerschleife... Er soll aber genau dann abbrechen wenn die Zahl in der Spalte das zweite Mal auftaucht.

Weiß jemand was ich da schreiben muss?




Meine Ideen:
Sub eintragen()
Dim maxSpalten As Integer, Zeile As Integer
Dim fertig As Boolean
maxSpalten = 100
Rows("1:65536").ClearContents
For Spalte = 1 To maxSpalten 'erste Zeile eintragen
fertig = False
Zeile = 1
Cells(1, Spalte).Value = Spalte
Do Until fertig = True
Cells(Zeile + 1, Spalte).Value = Collatz(Cells(Zeile, Spalte).Value)
If Collatz(Cells(Zeile, Spalte).Value) = 1 And Zeile >= 2 Then
fertig = True
End If
Zeile = Zeile + 1
Loop
Next
End Sub

Function Collatz(zahl As Integer) As Integer
If zahl Mod 2 = 0 Then 'zahl ist gerade
Collatz = zahl / 2
Else 'zahl ist ungerade
Collatz = 5 * zahl + 1
End If
End Function
 
 
09.04.2016, 16:50 Auf diesen Beitrag antworten »
eulerscheZahl

Excel ist die falsche Wahl: die Zahlen werden ziemlich schnell ziemlich groß - dafür hat Excel nicht die nötige Genauigkeit in der Zahlendarstellung.

Auch Computer stoßen da an die Grenzen.

Hier die Ergebnisse für die ersten 50 Zahlen. Wenn nach 10000 Schritten noch keine Schleife gefunden wurde, gebe ich einfach die größte bisher aufgetretene Zahl aus (damit du siehst, wie groß das wird).
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:
49:

1 6 3 16 8 4 2 1
2 1 6 3 16 8 4 2
3 16 8 4 2 1 6 3
4 2 1 6 3 16 8 4
5 26 13 66 33 166 83 416 208 104 52 26
6 3 16 8 4 2 1 6
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
8 4 2 1 6 3 16 8
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
10 5 26 13 66 33 166 83 416 208 104 52 26
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
12 6 3 16 8 4 2 1 6
13 66 33 166 83 416 208 104 52 26 13
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
15 76 38 19 96 48 24 12 6 3 16 8 4 2 1 6
16 8 4 2 1 6 3 16
17 86 43 216 108 54 27 136 68 34 17
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
19 96 48 24 12 6 3 16 8 4 2 1 6
20 10 5 26 13 66 33 166 83 416 208 104 52 26
3427256734262498071965123901364836139796960802471824625388054851888079140463270940004955424335501242360573822675361146221646090697268224953971370744830563600628973596722754057083899830266552920702255625422627800628697664368363792866361439171956743555501066513528308596994671533587975513077381224492382362243493416
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
24 12 6 3 16 8 4 2 1 6
75247545803496213320752115050464759867960318117839537765423170607389129480512180305752013218372437939901608622854672520479081193001888667283123046851816360852523862097925866059805173356076052989755078943476574223770613240897818077495767893572214976243334125100344685347237937033518680381828557965653428792928059896
26 13 66 33 166 83 416 208 104 52 26
27 136 68 34 17 86 43 216 108 54 27
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
29431440604095411132960617552112392938631121192836586724686820074558647917135466174850113026992898457362898331063631711909777673759653155404751065858604243933363050375839810281615576720614246362297675644671359170896195058121861558085614235585512682177804036153113683105856279706587587751236001388637641267765853244268116
30 15 76 38 19 96 48 24 12 6 3 16 8 4 2 1 6
75247545803496213320752115050464759867960318117839537765423170607389129480512180305752013218372437939901608622854672520479081193001888667283123046851816360852523862097925866059805173356076052989755078943476574223770613240897818077495767893572214976243334125100344685347237937033518680381828557965653428792928059896
32 16 8 4 2 1 6 3 16
33 166 83 416 208 104 52 26 13 66 33
34 17 86 43 216 108 54 27 136 68 34
7715275565719987456038828127580951134504516633974954190356301761625102199589559644939908029348026373206939620098344671486876758510050516770423063408437950921667523477724151226463833743848700998398161884196728778495412157316297276282795258173328636556818261253321833344101588587403696603460010348023025832497211832865416
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
18733429300543278489300706190849803658083436229099221308553546565271875089050431880399113291413263858504163409521252527619467538065053254006651798430389640229639327646216910341902972620482604251189569264021485148686731880902667078236015768448428956110564849573308706254531049904501329676785939310719031520779181887348366052656091595884128151626936616
38 19 96 48 24 12 6 3 16 8 4 2 1 6
75247545803496213320752115050464759867960318117839537765423170607389129480512180305752013218372437939901608622854672520479081193001888667283123046851816360852523862097925866059805173356076052989755078943476574223770613240897818077495767893572214976243334125100344685347237937033518680381828557965653428792928059896
40 20 10 5 26 13 66 33 166 83 416 208 104 52 26
6659394537276667148290763487751388780715430606445646197270156133839317883258590266091862925479591436088735725205813808797271549713596068551968001047239044433788906864660233769165569632740257484316373626073728886708444671171024485839326996228002064668740007781278238460928025931424134680807740550177411976632627943003896
3427256734262498071965123901364836139796960802471824625388054851888079140463270940004955424335501242360573822675361146221646090697268224953971370744830563600628973596722754057083899830266552920702255625422627800628697664368363792866361439171956743555501066513528308596994671533587975513077381224492382362243493416
43 216 108 54 27 136 68 34 17 86 43
7715275565719987456038828127580951134504516633974954190356301761625102199589559644939908029348026373206939620098344671486876758510050516770423063408437950921667523477724151226463833743848700998398161884196728778495412157316297276282795258173328636556818261253321833344101588587403696603460010348023025832497211832865416
1457874773577161457720074332958418114848377744579106658419708067645541698662055985164245442342688605997299097252555715305020502408391671127551546538207547531950017248334967098808262416648171353954679457593621910653203672119321858501621730261858489312474583518815861797185301855281661204637325834214420836618251899416
12055118071437480400060668949345236147663307240585865922431721502539222186858686945218606295856291208135843156403663549198244935171953932453786036575684298315105505433943986291349740224763595309997127944057388716399081495806714494191867590895825994620028533208315364600158732167818275942906266168785977863276893488852216
3836606320751263434608784627886039789175487739719520523991766336567680018237528449105738402081436438221652666269952517656466951795722906420562288318543798319030134301945223238021728792674837350643623785271600158451042689208866217622736029378238250211443681192613623040927959020441872317805760370835257655455576450528945367583967558837069445453196616
48 24 12 6 3 16 8 4 2 1 6
75247545803496213320752115050464759867960318117839537765423170607389129480512180305752013218372437939901608622854672520479081193001888667283123046851816360852523862097925866059805173356076052989755078943476574223770613240897818077495767893572214976243334125100344685347237937033518680381828557965653428792928059896


Und der Code (C#)
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:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace Infoboard
{
	class MainClass
	{
		static List<BigInteger> Collatz(int start, int factor) {
			//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.Add (next);
				sequence.Add (next);
				if (next.IsEven)
					next /= 2;
				else
					next = factor * next + 1;
				if (sequence.Count > 10000)
				return new List<BigInteger> { sequence.Max() };
			}
			sequence.Add (next);
			return sequence;
		}

		static void Main(string[] args) {
			for (int i = 1; i < 50; i++) {
				Console.WriteLine (string.Join (" ", Collatz (i, 5)));
			}
		}
	}
}
09.04.2016, 17:21 Auf diesen Beitrag antworten »
eulerscheZahl

Ich habe dir noch für die klassische und die modifizierte Sequenz ein Bildchen gemalt Wink
09.04.2016, 17:40 Auf diesen Beitrag antworten »
blindmessenger

Ja cool... Danke... Das muss ich erst mal sacken lassen... Doofe Frage... Wo kann ich mir den Code denn jetzt ausrechnen lassen? Bin leider absoluter Laie... Ich habe VS drauf aber da sind soviele Anwendungen... Muss ich ein neues Projekt öffnen oder eher nur eine Datei? Wie bekomme ich die Zahlen angezeigt?
 Anzeige
 
09.04.2016, 17:47 Auf diesen Beitrag antworten »
eulerscheZahl

Hast du eine VS Version, die C# unterstützt?
Ich habe die Abfolge nicht genau im Kopf - ich nutze MonoDevelop.
Neues Projekt -> C# Konsolenanwendung -> Speicherort wählen.
Dann kannst du meinen Code reinkopieren (den Namespace lässt du am besten so, wie er bei dir heißt).
Um BigInteger verwenden zu können, musst du dann noch einen Verweis hinzufügen.
Dazu in der Projektmappe (standardmäßig am rechten Rand) einen Rechtsklick auf Verweise und dann System.Numerics auswählen.

Wenn das erledigt ist, kannst du mit F5 ausführen.
Wenn die Ausgabebox sofort wieder verschwindet, füge am besten zwischen Zeile 33 und 34 noch ein Conosle.ReadLine() ein. Dann schließt sich das Fenster erst mit Enter.
09.04.2016, 17:49 Auf diesen Beitrag antworten »
blindmessenger

Wie sieht es denn für 7n+1 aus? Oder 9n+1? Kannst DU mir die vielleicht auch noch kurz ausgeben? Bis ich den Code verwenden kann muss ich erst noch ein paar Bücher lesen... ;-)
09.04.2016, 17:52 Auf diesen Beitrag antworten »
eulerscheZahl

7:
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

1 8 4 2 1
2 1 8 4 2
4 2 1 8 4
5 36 18 9 64 32 16 8 4 2 1 8
8 4 2 1 8
9 64 32 16 8 4 2 1 8
10 5 36 18 9 64 32 16 8 4 2 1 8
16 8 4 2 1 8
18 9 64 32 16 8 4 2 1 8
20 10 5 36 18 9 64 32 16 8 4 2 1 8
32 16 8 4 2 1 8
36 18 9 64 32 16 8 4 2 1 8
40 20 10 5 36 18 9 64 32 16 8 4 2 1 8
41 288 144 72 36 18 9 64 32 16 8 4 2 1 8
64 32 16 8 4 2 1 8
72 36 18 9 64 32 16 8 4 2 1 8
73 512 256 128 64 32 16 8 4 2 1 8
80 40 20 10 5 36 18 9 64 32 16 8 4 2 1 8
82 41 288 144 72 36 18 9 64 32 16 8 4 2 1 8


9: nichts gefunden (Suche bis Startwert 10000, maximale Schleifenlänge 1000).
09.04.2016, 18:13 Auf diesen Beitrag antworten »
blindmessenger

Ja Collatz macht echt Spass... Hier noch ein paar Bildchen. Vielleicht findest Du ja noch mehr Symmetrien
09.04.2016, 18:31 Auf diesen Beitrag antworten »
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))));
			}
		}
	}
}
09.04.2016, 20:19 Auf diesen Beitrag antworten »
blindmessenger

Danke für Deine Mühe... Ich hätte noch eine Frage und zwar bräuchte ich für den 3n+1 Code noch eine kleine Modifikation:

Der normale Collatz geht ja so:

1,4,2,1
2,1
3,10,5,16,8,4,2,1
4,2,1
5,16,8,4,2,1

Ich hätte gerne:

1
2,1
3,5,1
4,1
5,1

Also: Ich bräuchte die Collatz Reihe aber nur mit den ungeraden Zahlen... Hättest Du dafür auch noch einen Code. So könnte man sich eine Matrix bauen und untersuchen...

Das mit VS hat bei mir jetzt auch funktioniert...
09.04.2016, 20:34 Auf diesen Beitrag antworten »
eulerscheZahl

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:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace Infoboard
{
	class MainClass
	{
		static List<long> Collatz(int n) {
			List<long> sequence = new List<long> { n };
			while (n != 1) {
				if (n % 2 == 0)
					n /= 2;
				else
					n = n * 3 + 1;
				if (n % 2 == 1)
					sequence.Add (n);
			}
			return sequence;
		}

		static void Main(string[] args) {
			for (int i = 1; i < 50; i++) {
				Console.WriteLine (string.Join (" ", Collatz (i)));
			}
		}
	}
}


Ausgabe:
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

1
2 1
3 5 1
4 1
5 1
6 3 5 1
7 11 17 13 5 1
8 1
9 7 11 17 13 5 1
10 5 1
11 17 13 5 1
12 3 5 1
13 5 1
14 7 11 17 13 5 1
15 23 35 53 5 1
[...]
09.04.2016, 23:35 Auf diesen Beitrag antworten »
blindmessenger

Ich danke Dir...
10.04.2016, 20:12 Auf diesen Beitrag antworten »
blindmessenger

Hallo,
ich habe mal spasseshalber bei dem 5n+1 Code die Startzahlen auf <8 reduziert und die Anzahl der Sequenze auf 500.000 erhöht. Die grösste Zahl für die Startzahl 7 die er dann ausspuckt hat ca.16.000 Stellen. Ist diese Zahl noch exakt. Oder sind da dann Fehler bei der Berechnung?

Gruß
10.04.2016, 20:36 Auf diesen Beitrag antworten »
eulerscheZahl

Es sind "nur" 16096 Stellen (wie du in deinem Edit ja auch erkannt hast).
Die Zahl ist noch exakt. Das ist auch der Grund, warum ich von Excel abgeraten habe.

Aus der Hilfe:
Zitat:
Der BigInteger-Typ ist ein unveränderlicher Typ, der eine beliebig große ganze Zahl darstellt, deren Wert theoretisch keine obere oder untere Grenze hat.

Die Begrenzung liegt nur im vorhandenen Arbeitsspeicher. Die errechnete Zahl braucht bei guter Speicherverwaltung knapp 7kB, das ist also kein Problem.
10.04.2016, 20:44 Auf diesen Beitrag antworten »
blindmessenger

Wenn man jetzt eine Funktion Anzahl Stellen und Anzahl Rechenschritte hätte könnte man vielleicht sehen, dass die Anzahl der Rechenschritte gegen unendlich geht ohne eine Schleife zu haben...
10.04.2016, 21:06 Auf diesen Beitrag antworten »
eulerscheZahl

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")));
			}
		}
	}
}
10.04.2016, 22:05 Auf diesen Beitrag antworten »
blindmessenger

Immerhin sieht man einen linearen Zusammenhang. Das ist ja schonmal etwas...
21.04.2016, 11:01 Auf diesen Beitrag antworten »
blindmessenger

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.
06.11.2016, 19:52 Auf diesen Beitrag antworten »
blindmessenger

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
07.11.2016, 07:51 Auf diesen Beitrag antworten »
eulerscheZahl

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.
07.11.2016, 17:39 Auf diesen Beitrag antworten »
blindmessenger

Danke Dir...
09.11.2016, 19:24 Auf diesen Beitrag antworten »
blindmessenger

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
09.11.2016, 19:29 Auf diesen Beitrag antworten »
eulerscheZahl

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.
09.11.2016, 19:38 Auf diesen Beitrag antworten »
blindmessenger

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?
09.11.2016, 19:43 Auf diesen Beitrag antworten »
blindmessenger

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...
09.11.2016, 19:46 Auf diesen Beitrag antworten »
eulerscheZahl

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.
09.11.2016, 20:36 Auf diesen Beitrag antworten »
blindmessenger

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.
09.11.2016, 20:49 Auf diesen Beitrag antworten »
eulerscheZahl

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);	
				}
			}
		}
	}
}
20.11.2016, 17:29 Auf diesen Beitrag antworten »
blindmessenger

Hallo Euler,
danke für Deine Mühen... Gott

Ich habe Deinen letzten Code gerechnet und habe bisher keine weiteren Nicht-Mersenne-Algorithmen gefunden ausser der 5n+1 und 181n+1...

Aber ich habe noch eine andere interessante Beobachtung gemacht...

[latex]T_k[/latex] sei eine ungerade Zahl die in [latex] k[/latex] 3n+1-Operationen bei der 1 landet. [latex]M_{T_k}[/latex] sei die Menge der Zahlen einer ZerfallsKlasse [latex]k[/latex]. Es ergibt sich folgendes Bild:

[latex]M_{T_1}=[5,21,85,341,...][/latex]

-----------

[latex]M_{T_{2_1}}=[3,13,53,213,...][/latex]

[latex]M_{T_{2_2}}=[113,453,1813,7253,...][/latex]

[latex]M_{T_{2_3}}=[227,909,3637,14549,...][/latex]

...

[latex]M_{T_{2_n}}[/latex]

-----------

[latex]M_{T_{3_{1_1}}}=[17,69,277,1109,...][/latex] [latex]M_{T_{3_{2_1}}}=[75,301,...][/latex][latex]M_{T_{1_{3_1}}}=[151,...][/latex]



[latex]M_{T_{3_{1_2}}}=[35,141,565,...][/latex] [latex]M_{T_{3_{2_2}}}=[2417,...][/latex][latex]M_{T_{3_{3_2}}}=[4849,...][/latex]



[latex]M_{T_{3_{1_3}}}=[1137,4549,18197,...][/latex] [latex]M_{T_{3_{2_3}}}=[4835,...][/latex] [latex]M_{T_{3_{3_3}}}=[9699,...][/latex]

...

[latex]M_{T_{3_{1_n}}}[/latex] [latex]M_{T_{3_{2_n}}}[/latex] [latex]M_{T_{3_{3_n}}}[/latex]

----------

[latex]M_{T_{k_{n_{n_{..._n}}}}}[/latex]

Folgende Arithmetik ergibt sich:

Aus 2 von 3 ungeraden Zahlen [latex]T_k[/latex] ergibt sich eine TeilMenge [latex]M_{T_{k+1}}[/latex] der nächstgrösseren Klasse. So bilden sich dann auch Gruppen etc....

Nun habe ich in einem bestimmten Intervall [latex] [1,1024] [/latex] die Anzahl [latex] x [/latex] der ungeraden Zahlen die in gleichviel Schritten zur 1 gelangen gezählt. Und es ergibt sich (wohl unabhängig von n...) folgendes Bild:

[latex]<br /> \tabular{|c|c|}<br /> \multicolumn {2}{|c|}{Anzahl x von ungeraden Zahlen derselben Zerfallsklasse k im Intervall 1-1024 } \\ \hline<br /> Zerfallsklasse k & x\\ \hline<br /> 1& 4\\ \hline<br /> 2& 9\\ \hline<br /> 3& 10 \\ \hline<br /> 4& 15 \\ \hline<br /> 5& 17\\ \hline<br /> 6& 18 \\ \hline<br /> 7& 25\\ \hline<br /> 8& 20\\ \hline<br /> 9& 21\\ \hline<br /> 10& 21\\ \hline<br /> 11& 15\\ \hline<br /> 12& 20\\ \hline<br /> 13& 15\\ \hline<br /> 14& 19 \\ \hline<br /> 15& 18\\ \hline<br /> 16& 10\\ \hline<br /> \endtabular<br /> [/latex]

Ich habe das für verschiedene Intervalle durchgezählt und es ergibt sich, dass immer bei der 7 ein Peak ist. Die Kurve die sich ergibt scheint ein schwach gedämpfter harmonischer Oszillator zu sein.

Um das genauer zu überprüfen, bräuchte man einen Code der diese Tabelle logisch fortführt für größere Intervalle und auch für größere k. Bei kleineren Intervallen ist dieser Oszillator nicht gut zu erkennen, aber je größer das Intervall desto besser sollte sich ein Oszillator herauskristallisieren...
20.11.2016, 17:51 Auf diesen Beitrag antworten »
eulerscheZahl

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]);
		}
	}
}
20.11.2016, 18:11 Auf diesen Beitrag antworten »
blindmessenger

Kann sein das ich mich verzählt habe...

Eine Idee wie man das schön plotten kann ausser mit excel?
20.11.2016, 18:29 Auf diesen Beitrag antworten »
eulerscheZahl

Bei mir klappt das nicht, weil Mono eine NotImplemented Exception wirft. Da du unter Windows arbeitest, könnte es aber klappen.
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:

using System;
using System.Linq;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;
using System.Windows.Forms.DataVisualization.Charting;

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 = 1; i < 1024; i += 2) {
			int tmp = Steps (i);
			while (zerfall.Count <= tmp)
				zerfall.Add (0);
			zerfall [tmp]++;
		}
		Chart chart = new Chart ();
		Series series = new Series ();
		for (int i = 0; i < zerfall.Count; i++) {
			Console.WriteLine (i + ": " + zerfall [i]);
			series.Points.AddXY (i, zerfall [i]);
		}
		chart.Series.Add (series);
		Form form = new Form ();
		chart.Dock = DockStyle.Fill;
		chart.Parent = form;
		form.Width = zerfall.Count;
		form.Height = zerfall.Max ();
		form.ShowDialog ();
	}
}
20.11.2016, 19:29 Auf diesen Beitrag antworten »
blindmessenger

Ich habe mit gnuplot etwas probiert:
23.11.2016, 16:16 Auf diesen Beitrag antworten »
blindmessenger

Hallo,
um die Mengen, Gruppen und Klassen noch ein wenig weiter durchsuchen zu können suche ich ein einfaches Programm folgender Struktur für c-sharp

1. Ich starte mit einer beliebigen positiven ganzen Zahl n.

2. Nun werden nacheinander die 3 Operationen [latex] \frac {2n-1}{3} [/latex] , [latex] \frac {4n-1}{3} [/latex] und [latex] 4n+1 [/latex] durchprobiert bis die erste Operation gefunden ist die auf eine neue ganze Zahl führt.

3. Nun wird mit dieser neuen gefunden Zahl wieder wie in Schritt 2 verfahren.


In der Konsole sollen dann diese ganzen Zahlen aufgelistet werden.
Parameter des Algorithmus sind dann die Startzahl n und wie oft Schritt 2 wiederholt wird...
23.11.2016, 22:16 Auf diesen Beitrag antworten »
eulerscheZahl

Wäre es nicht einfacher, selbst die Grundlagen des Programmierens zu lernen?

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:

using System;
using System.Linq;
using System.Collections.Generic;

class Player
{
	static void Main(string[] args)
	{
		Console.Write ("Startwert: ");
		long n = long.Parse (Console.ReadLine ());
		Console.Write ("maximale Schritte: ");
		int steps = int.Parse (Console.ReadLine ());

		HashSet<long> numbers = new HashSet<long>();
		for (int i = 0; i < steps && !numbers.Contains(n); i++) {
			numbers.Add (n);
			if ((2 * n - 1) % 3 == 0)
				n = (2 * n - 1) / 3;
			else if ((4 * n - 1) % 3 == 0)
				n = (4 * n - 1) / 3;
			else
				n = 4 * n + 1;
			Console.Write (n + " ");
		}
		Console.WriteLine ();
	}
}
23.11.2016, 23:07 Auf diesen Beitrag antworten »
blindmessenger

Ich gebe Dir recht... Ich muss mich da mal ein bisschen reinarbeiten...
02.12.2016, 13:26 Auf diesen Beitrag antworten »
blindmessenger

Ich habe mir ein Streichalgorithmus überlegt, den ich aber nicht beweisen kann der aber bisher für kleinere Zahlen bis 1024"empirisch" funktioniert.

Es geht darum Collatzreihen auf andere Collatzreihen zurückzuführen, genauer gesagt gemeinsame Elemente zu finden. Sobald also zwei Reihen ein gemeinsames Element besitzen, dann haben sie auch dasselbe Ende, und man bracht nicht mehr beide Reihen zu testen sondern nur noch eine von beiden.

Als aller erstes streichen wir mal alle geraden Zahlen, weil wir ja wissen, dass diese immer nach endlichen Schritten bei einer ungeraden Zahl landen.

Nun teilen wir die verbleibenden ungeraden Zahlen in zwei Restklassen ein. Einmal in die Restklasse 4k+1 und einmal in die Restklasse 4k+3.

Mit dem Bild 4k+3 möchte ich zeigen, dass die Reihen der StartZahlen der Form 4k+3 immer auch in Reihen der Startzahlen der Form 4k+1 landen. Folgende Schritte werden hier angewendet:

1. Zahlen der Form 4k+3 werden einer Spalte aufgelistet und nach rechts gemäß des Collatzalgorithmus (nur mit ungeraden Zahlen) aufgereiht, bis ein Zahl entsteht die kleiner ist als ihre VorgängerZahl.

2. Es entstehen somit Verschieden lange Reihen. Jede zweite Reihe hat genau 3 Elemente. Nun ist die Idee, dass man die Folgen die mehr als drei Elemente besitzen streichen kann, weil sie immer auch in Folgen mit genau drei Elementen landen.

3. Nachdem wir diese längeren Folgen gestrichen haben, bleiben also nur Folgen mit genau drei Elementen. Nun wird die komplette erste Spalte gestrichen. Also immer das erste Element jeder Folge.

Nun ist zu sehen, dass die ersten Elemente dieser verbleibenden Folgen alle von der Form 8k+1 sind. Da [latex]8k+1 \subset 4k+1[/latex] lassen sich somit alle Zahlen der Form 4k+3 auf die Zahlen der Form 4k+1 zurückführen.



Also können wir 4k+3 auch abhacken und uns auf 4k+1 konzentrieren. Mit Bild 4k+1 will ich nun zeigen, dass durch mehrmaliges Wiederholen eines Streichzykluses Folgen auf immer größere Restklassen zurückgeführt werden.

Vorbereitung:

Zahlen der Form 4k+1 werden in einer Spalte aufgelistet und nach rechts gemäß des Collatzalgorithmus (nur mit ungeraden Zahlen) aufgereiht, bis ein Zahl entsteht die kleiner ist als ihre VorgängerZahl.
In diesem Fall (Und wohl in keinem anderen...) brechen alle Folgen beim zweiten Element ab. Interessanterweise: Wenn man diese zweiten Elemente auflisten würde, ergibt sich die OEIS Folge A067745.
Nun wird in 3 Schritten vorgegangen:

1. Schritt: Folgen neu aufbauen

Wir streichen das erste Element (somit die komplette erste Spalte) dieser 2er Folgen und lassen wieder nach dem Collatzalgorithmus neu entwickeln bis eine Zahl erreicht ist die kleiner als ihr Vorgänger ist.


2. Schritt: Gleiche Folgen streichen

Im zweiten Schritt werden aus den gerade neu aufgebauten Folgen, Folgen heraus gestrichen die mehrfach vorkommen. In diesem Fall ergibt sich, dass jede 4. Folge gestrichen werden kann.


3. Schritt: Folgen mit mehr als 2 Elementen streichen

Der dritte Schritt besteht darin, Folgen zu streichen die mehr als 2 Elemente beinhalten. Die Idee dahinter: Man kann empirisch für ein endliches Intervall nachweisen, dass alle Folgen mit mehr als 2 Elementen in Folgen mit genau 2 Elementen übergehen.


Nun ist ein Zyklus abgeschlossen. Nach mehrmaligen Wiederholen dieses Zykluses lassen sich so für beliebig große Restklassen zeigen, dass sie gemeinsame Elemente haben.

Mit diesem Siebalgorithmus ist natürlich noch keine Aussage darüber zu treffen ob alle Zahlen immer bei der 1 landen, aber es ist schon interessant, dass man im Grenzwert beliebig viel Folgen auf immer größere (im Grenzwert unendlich große) Restklassen zurückführen kann.

Das Problem an der ganzen Sache ist, dass ich mir nicht sicher bin, ob es zulässig ist immer Folgen zu streichen die mehr als zwei Elemente haben. Ich habe das nur empirisch für wenige Zahlen mit Excel überprüft.

Hat jemand eine Idee wie man den Streichalgorithmus programmieren kann, der dann aber auch gleichzeitig überprüft, ob und wie man Folgen mit mehr als zwei Elementen auch immer streichen kann?

Die Challenge wäre also ein Beweis, dass das Sieb auch immer zulässig ist...
03.12.2016, 11:39 Auf diesen Beitrag antworten »
blindmessenger

Zitat:
Original von eulerscheZahl
Excel ist die falsche Wahl: die Zahlen werden ziemlich schnell ziemlich groß - dafür hat Excel nicht die nötige Genauigkeit in der Zahlendarstellung.


Und der Code (C#)
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:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace Infoboard
{
	class MainClass
	{
		static List<BigInteger> Collatz(int start, int factor) {
			//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.Add (next);
				sequence.Add (next);
				if (next.IsEven)
					next /= 2;
				else
					next = factor * next + 1;
				if (sequence.Count > 10000)
				return new List<BigInteger> { sequence.Max() };
			}
			sequence.Add (next);
			return sequence;
		}

		static void Main(string[] args) {
			for (int i = 1; i < 50; i++) {
				Console.WriteLine (string.Join (" ", Collatz (i, 5)));
			}
		}
	}
}


Im Prinzip bräuchten wir diesen Code mit folgender Veränderung:

1. Es sollen nur die ungeraden Zahlen ausgegeben werden.

2. Als Startzahlen nur die Zahlen der Form 4k+1

3. Jede Folge stoppt, wenn das "zweite mal" ein Element kleiner ist als sein Vorgänger.

Es sollte sich ein schönes regelmäßiges Treppenmuster ergeben, wo man erkennen kann, dass man Folgen mit mehr als 2 Elementen streichen kann.

Im Bild nochmal zu sehen wie Folgen mit mehr als 2 Elementen gestrichen werden sollen.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


Informatiker Board » Themengebiete » Praktische Informatik » Collatz Schleife

 
© 2005-2019 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen