Startzahl Z für 3n + 1 bestimmen |
| 26.10.2022, 10:58 | Cardbox | Auf diesen Beitrag antworten » | ||||||
| Startzahl Z für 3n + 1 bestimmen Gegeben sei eine Startzahl Z. Es gelten folgende Regeln: 1. Ist die Startzahl oder sind die nachfolgenden Zahlen gerade, so werden sie halbiert. 2. Ist die Startzahl oder sind die nachfolgenden Zahlen ungerade, so wird diese verdreifacht und eins addiert. In dieser Form rechnet man so lange, bis man zur 1 gelangt. Die Abfolge von Z bis zur 1 nennen wir einen Durchgang. AUFGABE: Vor dir liegt eine Liste mit den Zahlen von 1 bis 1000. Wann immer in einem Durchgang eine Zahl auftaucht, so wird diese auf der Liste durchgestrichen. Die Startzahl bleibt dabei jeweils unberücksichtigt. Frage: Wie hoch muss Z maximal sein, um im letzten Durchgang alle Zahlen von 1 bis 1000 durchgestrichen zu haben? Meine Ideen: Ich würde jetzt von 2000 ausgehen. Denn man kann ja jede Zahl vom doppelten der Zahl erreichen. Also braucht man z. B. die 1998, um die 999 zu erreichen. Allerdings kann man die 999 ja auch von einer niedrigeren Startzahl aus erreichen, so simpel ist es also eventuell doch nicht. Aber 2000 ist auf jeden Fall die obere Schranke. Wie würdet ihr an diese Aufgabe herangehen? |
||||||||
| 26.10.2022, 11:30 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Du redest von der Collatz-Folge. Allein zum Stichwort "Collatz" findet man hier im Board 34 Threads...
Kann man nicht: 999 ist nicht in der Form 3n+1 darstellbar. Es geht als tatsächlich nur durch Halbierung von 1998. Tatsächlich ist es bei Collatz-Folgen so: Sobald auch nur einmal die Operation 3n+1 durchgeführt wird, sind ALLE (!) weiteren Glieder der Folge nicht durch 3 teilbar. 1000 wiederum ist gleich 3*333+1. |
||||||||
| 26.10.2022, 11:42 | Phenix | Auf diesen Beitrag antworten » | ||||||
| RE: 3n + 1 Ist die Startzahl gerade, wird sie halbiert, wenn ungerade wird sie verdreifacht + 1. Mit der Startzahl 333 wird die 1000 gestrichen, weil 333*3+1 = 1000. Mit der Startzahl 1998 wird die 999 gestrichen weil 1998/2 = 999 … usw. Um deine Aufgabe zu erfüllen braucht man Z < 1000. |
||||||||
| 26.10.2022, 12:59 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||
RE: 3n + 1
Die 1000 kommt schon in der Folge der Startzahl 327 vor.
Die 999 wird mit Startzahl 999 gestrichen.
Korrekt. Aber kann man das ohne Brute Force beweisen? Viele Grüße Steffen |
||||||||
| 26.10.2022, 13:01 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
| RE: 3n + 1 @Phenix Hast du die Frage richtig gelesen?
Wir hatten schon festgestellt, dass wir mindestens Z=1998 brauchen allein um die 999 zu streichen (Startwert Z soll ja laut Cardbox jeweils NICHT gestrichen werden). Das reicht dann allerdings auch, denn die 1000 wird ja bereits bei Z=333 gestrichen. -----------------------------------------------------------------------------------------------------
Nein, auch du hast die Bedingungen von Cardbox nicht richtig gelesen:
|
||||||||
| 26.10.2022, 13:06 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||
RE: 3n + 1
Stimmt, Mist. Immer dieses Kleingedruckte. |
||||||||
| Anzeige | ||||||||
|
|
||||||||
| 26.10.2022, 17:56 | Phenix | Auf diesen Beitrag antworten » | ||||||
| RE: 3n + 1 @Cardbox Rechne das Ganze mal durch, dann weißt du wieviele Durchgänge du brauchst. Ich Tippe auf Z < 1000. |
||||||||
| 26.10.2022, 17:59 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||
RE: 3n + 1
Mein Programm sagt, dass bei Z=1000 erst 810 der 1000 Zahlen auf der Liste durchgestrichen sind. |
||||||||
| 26.10.2022, 18:10 | Phenix | Auf diesen Beitrag antworten » | ||||||
| RE: 3n + 1 Was für ein Programm? |
||||||||
| 26.10.2022, 20:34 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||
| RE: 3n + 1 Ich sprach ja schon von Brute Force. Ein Programm, das für alle Zahlen von 1 bis 2000 die Collatzfolgen berechnet und alle auftretenden Zahlen abhakt, ist schnell geschrieben. |
||||||||
| 26.10.2022, 22:25 | Phenix | Auf diesen Beitrag antworten » | ||||||
| RE: 3n + 1 … toll 
Mit Python? Na, dann wird es dir ein Leichtes sein Z zu bestimmen und uns hier mitzuteilen, oder willst du das Ergebnis lieber für dich behalten? |
||||||||
| 26.10.2022, 22:41 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Das Ergebnis ist doch längst klar - und steht auch schon lange oben geschrieben: Z=1998 |
||||||||
| 26.10.2022, 22:55 | Phenix | Auf diesen Beitrag antworten » | ||||||
Kommt denn der @Steffen Bühler mit seinem „Brute Force Programm“ auf das selbe Ergebnis? |
||||||||
| 27.10.2022, 08:56 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||
Ja, natürlich. |
||||||||
| 27.10.2022, 12:25 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Zur Begründung, weil die oben womöglich nicht deutlich genug war:
Denn NACH einer Operation 3n+1 hat man logischerweise keine durch 3 teilbare Zahl vorliegen. Und die Halbierung einer geraden nicht durch 3 teilbaren Zahl ergibt ebenfalls wieder eine nicht durch 3 teilbare Zahl. D.h., die einzige Möglichkeit in der Collatz-Folge eine durch 3 teilbare Zahl zu streichen ist, wenn diese durch eine ununterbrochene Anzahl von Halbierungsschritten aus einer geraden durch drei teilbaren Startzahl entstanden ist. Im Fall von 999 ist die kleinste Chance dafür Z=1998. |
||||||||
| 27.10.2022, 16:50 | Phenix | Auf diesen Beitrag antworten » | ||||||
@Cardbox Alternative Überlegung: Z1: (2 * 1)/2 = 1 Z2: (2 * 2)/2 = 2 Z3: (2 * 3)/2 = 3 … … Z998: (2 * 998)/2 = 998 Z999: (2 * 999)/2 = 999 Z1000: (2 * 1000)/2 = 1000 Ergebnis: Man braucht maximal 1000 Durchgänge (Z) um im letzten (im 1000.) Durchgang alle Zahlen von 1 - 1000 durchgestrichen zu haben. Gruß Phenix |
||||||||
| 27.10.2022, 17:17 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Du interpretierst die Problemstellung nun so, dass es nicht um die maximale Startzahl geht, die man untersuchen muss, sondern mit wieviel Startzahlen man auskommt, um alle Zahlen 1..1000 wegstreichen zu können? 
So habe ich die obige Formulierung von Cardbox nicht aufgefasst, aber das wäre natürlich die wesentlich interessantere Fragestellung. --------------------------------------------------------------------------------------------------------------------- Anfangen könnte man beispielsweise mit den durch 3 teilbaren Zahlen, von denen wir ja schon viel wissen: Da wird man sicher nicht als Startzahl wählen, sondern besser , dann kann man in einem Ritt 768, 384, 192, 96, 48, 24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1 wegstreichen. Genauso verfährt man mit den anderen durch 3 teilbaren Zahlen, soweit sie nicht schon gestrichen wurden, also als nächstes 576, 288, 144, 72, 36, 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10 und den Rest haben wir schon. Hier "verschenkt" man nichts, denn die durch 3 teilbaren Zahlen müssen alle weggestrichen werden, und sie kommen pro Durchgang nur in solchen ununterbrochenen Halbierungsfolgen am Anfang des Durchgangs vor - sonst nirgendwo. Das sind dann von 1*3,3*3,5*3 bis hin zu 333*3 genau 167 Durchgänge und zugehörige Startzahlen. Mit denen hat man nun alle durch 3 teilbaren Zahlen erfasst und darüber hinaus auch schon viele weitere. Der weitere Weg hin zur optimal niedrigen Durchgangszahl wird - fürchte ich - nicht mehr so einfach sein. |
||||||||
| 27.10.2022, 17:26 | Phenix | Auf diesen Beitrag antworten » | ||||||
@HAL9000 @Cardbox fragt (s.o.) wieviele Durchgänge man braucht bis alle Zahlen von 1 - 1000 durchgestrichen sind … … man braucht dazu maximal 1000 Durchgänge und die höchste Startzahl ist 2000. Gruß Phenix |
||||||||
| 27.10.2022, 17:28 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Nein, klar nachlesbar wird oben gefragt:
Und Z wurde klar benannt als Startwert, nicht als Anzahl der Durchgänge. Womöglich hat Cardbox das von dir geschriebene gemeint, aber geschrieben hat er was anderes.
Das ist nun wirklich ignorant von dir: Wir haben nun schon zigmal festgestellt, dass wir nur bis 1998 gehen müssen, weil 1000 = 3*333+1 schon anderweitig erfasst wird. 1000 ist wirklich nur eine grobe obere Schranke für die Anzahl der nötigen Durchgänge, denn wie von mir oben skizziert, erwischt man alle durch 3 teilbaren Zahlen bis 1000 (das sind 333 Stück) bereits in 167 Durchgängen. |
||||||||
| 27.10.2022, 17:37 | Phenix | Auf diesen Beitrag antworten » | ||||||
@HAL9000 Meine letzte Zusammenfassung zeigt aber, dass man 1000 Durchgänge braucht und die maximale Startzahl bei 2000 liegt, um alle Zahlen von 1 - 1000 streichen zu können. Gruß Phenix PS: Doppelstreichungen brauchen ja nicht vorgenommen zu werden, sind aber auch nicht verboten! |
||||||||
| 27.10.2022, 17:52 | Phenix | Auf diesen Beitrag antworten » | ||||||
@HAL9000 Sobald man zwei unterschiedliche Startzahlen verwendet, wird im Collatz-Verlauf mindestens eine doppelte Zahl generiert. 2 > 1 4 > 2 > 1 Die 1 ist doppelt! |
||||||||
| 27.10.2022, 17:55 | IfindU | Auf diesen Beitrag antworten » | ||||||
@Phenix Jeder Startwert zwischen 1 und 1000 endet irgendwann in der unendlichen(!) Kette 4-2-1. Magst du erklären was deine Interpretation der Aufgabe ist?
|
||||||||
| 27.10.2022, 18:05 | Phenix | Auf diesen Beitrag antworten » | ||||||
@Ifindu Die Aufgabe hat @Cardbox bereits interpretiert (s.g.o.) … Ich habe die Aufgabe nur gelöst, zwei Zahlen: 1000 Durchgänge und Startzahl maximal 2000. |
||||||||
| 27.10.2022, 18:06 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Nein: Der Durchgang für deinen Startwert enthält u.a. auch bereits die 1000: 666, 333, 1000, 500, 250, 125, 376, 188, 94, ... Und die (von dir nun geänderte) Problemstellung war doch, mit möglichst wenig Durchgängen auszukommen, oder? Warum dann also in die Liste aufnehmen, wo doch SÄMTLICHE gestrichenen Zahlen dieses Durchgangs bereits von erfasst werden? Das ist schlicht unnötig im Optimalitätssinn. |
||||||||
| 27.10.2022, 18:12 | Phenix | Auf diesen Beitrag antworten » | ||||||
@HAL9000 Bei mir gilt: Z666: (2 * 666)/2 = 666 … das heißt, um die Zahl 666 streichen zu können, muss man 1332 als Startzahl eingeben/wählen. Um die Zahl 1000 streichen zu können, muss man 2000 als Startzahl eingeben. Wenn man mehrfach auftretende Zahlen berücksichtigt (sie nicht erlaubt sind), braucht man weniger als 1000 Durchgänge. Sind mehrfach auftretende Zahlen erlaubt, braucht man maximal 1000 Durchgänge. |
||||||||
| 27.10.2022, 18:18 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Das habe ich doch eben gesagt: Mit Startwert streicht man als erstes die 666. Dein Widerspruchsgeist an völlig falschen Stellen ist irgendwie sehr seltsam. 
------------------------------------------------------------------------------ Wie auch immer, ich habe mal die oben skizzierten 167 Durchgänge zur Abhakung aller durch 3 teilbaren Zahlen unter 1000 analysiert und festgestellt, dass lediglich die 41 Zahlen 487 , 541 , 613 , 649 , 667 , 685 , 703 , 721 , 731 , 751 , 757 , 763 , 775 , 781 , 799 , 811 , 812 , 817 , 823 , 829 , 835 , 853 , 859 , 865 , 871 , 883 , 889 , 907 , 913 , 919 , 920 , 925 , 937 , 943 , 955 , 961 , 967 , 973 , 974 , 979 , 997 unter 1000 noch nicht von diesen 167 Durchgängen erfasst wurden. Also selbst wenn es ganz blöd läuft und wir für jede dieser Zahlen einen eigenen Durchgang benötigen, so sind es dennoch nur maximal 167+41 = 208 Durchgänge. Bleibt zu untersuchen, ob man nicht doch noch Durchgänge mit zwei oder mehr dieser 41 Zahlen findet (ich sehe sofort schon 2*487 = 974, und da wird es noch mehr geben). |
||||||||
| 27.10.2022, 18:27 | Phenix | Auf diesen Beitrag antworten » | ||||||
HAL900 Wieviele Durchgänge braucht man denn nach deinen Berechnungen mindestens, wenn man mehrfach auftretende Zahlen berücksichtig, bis alle Zahlen von 1 - 1000 gestrichen sind? |
||||||||
| 27.10.2022, 18:36 | Phenix | Auf diesen Beitrag antworten » | ||||||
@HAL9000 Das Problem ist, dass @Cardbox in seiner Aufgabenstellung mehrfach auftretende Zahlen nicht ausgeschlossen hat … … und da das so ist, ist mein Ergebnis richtig, dass man maximal 1000 Durchgänge mit den Startzahlen 1 - 2000 braucht, um alle Zahlen von 1 - 1000 streichen zu können. Gruß Phenix PS: sollen mehrfach auftretende Zahlen berücksichtigt werden, ist mein Ergebnis falsch, weil dann deutlich weniger als 1000 Durchgänge notwendig sind. |
||||||||
| 27.10.2022, 18:51 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
1000 ist natürlich eine obere Schranke, aber man braucht nicht 1000 im Optimalfall, sondern (wie ich gerade nachgerechnet habe) lediglich 167+24 = 191. Zuzügllich zu den oben schon mehrfach erwähnten 167 Durchgängen kommen die 24 Durchgänge mit den Startzahlen 1514 , 1526 , 1550 , 1562 , 1598 , 1622 , 1634 , 1658 , 1670 , 1706 , 1730 , 1742 , 1766 , 1778 , 1814 , 1840 , 1850 , 1874 , 1886 , 1910 , 1922 , 1946 , 1958 , 1994 Wer es nicht glaubt, kann gern nachprüfen, dass in diesen insgesamt 191 Durchgängen dann alle Zahlen von 1 bis 1000 weggestrichen werden.
Da gibt es nichts auszuschließen: Eine Zahl, die schon mal gestrichen wurde und in einem weiteren Durchgang nochmal vorkommt, ist doch nichts schlimmes - das kommt ständig vor. Na und? Das hat doch keinerlei Auswirkung auf das Verfahren. |
||||||||
| 27.10.2022, 19:03 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Ok, hier nochmal alle diese 191 Startwerte Z aufsteigend geordnet aufgelistet: 1002 , 1008 , 1014 , 1020 , 1026 , 1032 , 1038 , 1044 , 1050 , 1056 , 1062 , 1068 , 1074 , 1080 , 1086 , 1092 , 1098 , 1104 , 1110 , 1116 , 1122 , 1128 , 1134 , 1140 , 1146 , 1152 , 1158 , 1164 , 1170 , 1176 , 1182 , 1188 , 1194 , 1200 , 1206 , 1212 , 1218 , 1224 , 1230 , 1236 , 1242 , 1248 , 1254 , 1260 , 1266 , 1272 , 1278 , 1284 , 1290 , 1296 , 1302 , 1308 , 1314 , 1320 , 1326 , 1332 , 1338 , 1344 , 1350 , 1356 , 1362 , 1368 , 1374 , 1380 , 1386 , 1392 , 1398 , 1404 , 1410 , 1416 , 1422 , 1428 , 1434 , 1440 , 1446 , 1452 , 1458 , 1464 , 1470 , 1476 , 1482 , 1488 , 1494 , 1500 , 1506 , 1512 , 1514 , 1518 , 1524 , 1526 , 1530 , 1536 , 1542 , 1548 , 1550 , 1554 , 1560 , 1562 , 1566 , 1572 , 1578 , 1584 , 1590 , 1596 , 1598 , 1602 , 1608 , 1614 , 1620 , 1622 , 1626 , 1632 , 1634 , 1638 , 1644 , 1650 , 1656 , 1658 , 1662 , 1668 , 1670 , 1674 , 1680 , 1686 , 1692 , 1698 , 1704 , 1706 , 1710 , 1716 , 1722 , 1728 , 1730 , 1734 , 1740 , 1742 , 1746 , 1752 , 1758 , 1764 , 1766 , 1770 , 1776 , 1778 , 1782 , 1788 , 1794 , 1800 , 1806 , 1812 , 1814 , 1818 , 1824 , 1830 , 1836 , 1840 , 1842 , 1848 , 1850 , 1854 , 1860 , 1866 , 1872 , 1874 , 1878 , 1884 , 1886 , 1890 , 1896 , 1902 , 1908 , 1910 , 1914 , 1920 , 1922 , 1926 , 1932 , 1938 , 1944 , 1946 , 1950 , 1956 , 1958 , 1962 , 1968 , 1974 , 1980 , 1986 , 1992 , 1994 , 1998 Wenn du nicht glaubst, dass die ausreichend sind, dann nenne mir eine Zahl im Bereich 1...1000, die nicht in einem der zugehörigen 191 Collatz-Durchgänge gestrichen wird. |
||||||||
| 27.10.2022, 19:04 | Phenix | Auf diesen Beitrag antworten » | ||||||
@HAL9000 Okay, endlich geschafft und alles klar: Die obere* Schranke sind 1000 und die untere** Schranke sind 191 Durchgänge. *mit Zahlenwiederholung nach Phenix **ohne Zahlenwiederholung nach @HAL9000 Gruß Phenix PS: ob sich @Cardbox für unsere Ergebnisse interessiert? |
||||||||
| 27.10.2022, 19:26 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Nein: Es gibt keine obere Schranke. Was hindert einen daran, auch noch andere Startwerte zu nehmen? Man kann z.B. alle Startwerte von 1...2000 nehmen (also auch die ungeraden), das sind dann schon 2000. Oder auch alle von 1...1000000, warum nicht?
Habe ich nirgendwo behauptet: Wenn man sich die 191 Durchgänge anschaut, gibt es selbstverständlich Zahlen, die da mehrfach vorkommen. Wichtig ist nur, dass jede Zahl 1...1000 mindestens einmal vorkommt. Allein die schon oft erwähnte 1000 taucht in fünf dieser Durchgänge auf: Startwerte 1308 , 1332 , 1550 , 1662 , 1746 Ganz zu schweigen von "4, 2, 1", die nun wirklich in allen 191 Durchgängen auftauchen. |
||||||||
| 27.10.2022, 20:00 | Phenix | Auf diesen Beitrag antworten » | ||||||
@ HAL9000 Bei mir kommt ja jede Zahl 1 … 1000 mindestens einmal vor. Meine obere Grenze sagt ja nur, dass darüber hinaus keine weiteren Durchgänge notwendig sind, weil bereits alle Zahlen von 1 - 1000 gestrichen wurden. |
||||||||
| 27.10.2022, 20:25 | Phenix | Auf diesen Beitrag antworten » | ||||||
HAL9000 Stimmt, aber in den Collatz-Reihen deiner 191 Zahlen kommen nur so viele Zahlen mehrfach vor, wie zur Streichung aller Zahlen von 1 - 1000 unvermeidlich sind, während bei meiner Version vermeidbar viele Zahlen mehrfach vorkommen, was der Aufgabensteller aber in seiner Fragestellung nicht explizit geregelt hat. |
||||||||
| 27.10.2022, 20:52 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Das gilt ja auch für die 191 Durchgänge. Was also ist an deinen 1000 Durchgängen besonders? Es ist weder Minimum noch Maximum, sondern einfach irgendeine Konfiguration. |
||||||||
| 27.10.2022, 21:22 | Phenix | Auf diesen Beitrag antworten » | ||||||
@HAL9000 Mehr als 1000 Durchgänge sind nicht notwendig um alle Zahlen (1-1000) zu streichen und weniger als 191 Durchgänge sind nicht möglich, wenn man alle Zahlen (1-1000) streichen soll. Das ist der Unterschied zwischen 1000 und 191 Durchgängen. Zwischen 191 und 1000 sind alle Angaben der Durchgänge sinnvoll, weil der Aufgabensteller seine Aufgabenstellung nicht eindeutig spezifiziert hat. |
||||||||
| 27.10.2022, 21:29 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Wir können uns auf diese Weise immer weiter im Kreise drehen, aber ich habe bisher kein einleuchtendes Argument gefunden, was an den 1000 Durchgängen denn nun besonders sein soll.
|
||||||||
| 27.10.2022, 22:16 | Phenix | Auf diesen Beitrag antworten » | ||||||
@HAL9000 … deine 191 Durchgänge sind von einer wesentlich größeren Besonderheit geprägt als meine 1000 Durchgänge, weil auf meine 1000 Durchgänge fast jeder problemlos selbst kommen kann, aber auf deine nicht. Vielen Dank für das zivilisierte Streitgespräch … 
|
||||||||
| 28.10.2022, 10:44 | Luftikus | Auf diesen Beitrag antworten » | ||||||
Mit dem Hinweis von Hal9000, dass Zahlen 3n nicht in einer Collatzfolge auftreten können, ausser als Startzahl, ist doch schon alles gesagt 
Aber für das Collatzproblem ist eigentlich die umgekehrte Fragestellung viel interessanter: Wieviele Lücken ("ungestrichene Zahlen") bleiben für durch 3 teilbare ungerade Startzahlen 3(2k+1)=6k+3 bis zu dieser Startzahl bzw. ab welcher Startzahl 6k'+3 werden dann diese Lücken geschlossen? |
||||||||
| 28.10.2022, 10:50 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||
Ähem, Vorsicht: Du meinst "Startsequenz bestehend ausschließlich aus Halbierungen" statt nur "Startzahl". |
||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
