Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Chin. Restsatz - einfache Faustregeln
Autor
Schule J Chin. Restsatz - einfache Faustregeln
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 2892
  Themenstart: 2022-08-15

Hallo, wenn man statt dreier Zahlen, drei gleich grosse Restmengen hat, z. B. Menge 1 0mod3, 3mod5, 0mod7, 7mod11, 5mod13, 1mod17, 18mod19 Menge 2 0mod3, 3mod5, 0mod7, 7mod11, 5mod13, 14mod17, 1mod19 Menge 3 0mod3, 3mod5, 0mod7, 7mod11, 5mod13, 1mod17, 12mod19 Dann kann man natürlich die Zahlen ausrechen. Die Frage aber ist, ob es irgendwelche Faustregeln gibt, so etwa wie die Teilerregeln bei der Teilbarkeit, die es erlauben, alleine vom Anblick der Restmengen her zu entscheiden, welche der drei Zahlen die grösste, welche die mittlere und welche die kleinste Zahl ist. Beachte die gegebene Sonderbedingung: Die Modi sind überall gleich.


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2310
Wohnort: Thüringen
  Beitrag No.1, eingetragen 2022-08-15

Das bezweifel ich stark ! Es ist so schon aufwendig, immer eine weitere Bedingung hinzuzuziehen. Ich habe zwar ein Verfahren entwickelt, was es schnell erledigen kann, aber am Ende sieht man erst durch einen Vergleich, was man haben will. Für solch kleine Primteiler, reicht aber ein einfaches Schleifendurchlaufen. ...wird ja am Ende ein Xn + 4849845*k sein...aber das Xn vorab zu schätzen, denke nicht.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3182
  Beitrag No.2, eingetragen 2022-08-16

Jede der Bedingungen ist von unendlich vielen Zahlen erfüllt. (allgemein könnte es auch gar keine Lösung geben) Eine "Faustregel", für welche Bedingung es die kleinste natürliche Lösung gibt, wirst du nicht finden. Andererseits kann man die Lösungen so einfach mit dem chinesischen Restsatz ausrechnen, dass es sich auch garnicht lohnt, etwas abzuschätzen, solange man nicht tatsächlich hunderte Reste besitzt. Test eines nichtoptimierten Pythonscripts: \sourceon Python 48101910385405624832776135003558318356692631687302830318110263813380175999389016737260580646458500524476344567042006243868374380965859969407937861764253877891765720077783651214256137600575364962930238751231397287281143169318322650118056530212819464373499921899336508640931259542909191347437325438183174562929094642224257004326131295309959364482881029359197524959131511253055874533265322417408585893299641643506677131329290165168790582161085907717401869906123816993057820957879158221892552074302618645 + k * 228149190778466359139857129449560694398768890311010097463828654491224815518148694118982213266501907813319510339802755210116286128710033577469216383686876489828468343305809248708951955638848225541561183679938518954330081743455665529943822978919620565055708281727728488903436872200715954243071128528640570847681156355685852107481526236406959108765134996706786798249895554286527355555757759316484715637272068433021229401885250566321477959469359370715601925295890694281355883855262254252176942885664808370 solves congruences [(1, 2), (1, 3), (0, 5), (1, 7), (3, 11), (8, 13), (14, 17), (4, 19), (1, 23), (3, 29), (30, 31), (4, 37), (34, 41), (8, 43), (12, 47), (45, 53), (45, 59), (8, 61), (61, 67), (70, 71), (19, 73), (45, 79), (13, 83), (53, 89), (3, 97), (26, 101), (55, 103), (100, 107), (2, 109), (107, 113), (24, 127), (40, 131), (30, 137), (98, 139), (67, 149), (31, 151), (51, 157), (134, 163), (145, 167), (34, 173), (65, 179), (136, 181), (100, 191), (57, 193), (40, 197), (124, 199), (141, 211), (169, 223), (49, 227), (33, 229), (121, 233), (84, 239), (107, 241), (81, 251), (104, 257), (27, 263), (169, 269), (102, 271), (29, 277), (230, 281), (199, 283), (77, 293), (183, 307), (68, 311), (3, 313), (265, 317), (143, 331), (153, 337), (53, 347), (315, 349), (227, 353), (324, 359), (316, 367), (215, 373), (324, 379), (337, 383), (96, 389), (260, 397), (109, 401), (262, 409), (364, 419), (381, 421), (174, 431), (221, 433), (120, 439), (74, 443), (154, 449), (368, 457), (270, 461), (193, 463), (371, 467), (421, 479), (170, 487), (361, 491), (384, 499), (448, 503), (165, 509), (264, 521), (419, 523), (463, 541), (233, 547), (308, 557), (181, 563), (210, 569), (539, 571), (382, 577), (375, 587), (199, 593), (71, 599), (352, 601), (283, 607), (408, 613), (353, 617), (350, 619), (303, 631), (543, 641), (131, 643), (416, 647), (458, 653), (91, 659), (338, 661), (293, 673), (333, 677), (33, 683), (508, 691), (441, 701), (648, 709), (642, 719), (526, 727), (35, 733), (310, 739), (279, 743), (617, 751), (579, 757), (711, 761), (175, 769), (4, 773), (553, 787), (290, 797), (351, 809), (571, 811), (604, 821), (338, 823), (434, 827), (35, 829), (814, 839), (16, 853), (417, 857), (364, 859), (751, 863), (653, 877), (313, 881), (621, 883), (697, 887), (891, 907), (341, 911), (759, 919), (215, 929), (729, 937), (939, 941), (484, 947), (727, 953), (7, 967), (669, 971), (852, 977), (311, 983), (602, 991), (83, 997), (984, 1009), (387, 1013), (417, 1019), (747, 1021), (768, 1031), (422, 1033), (836, 1039), (984, 1049), (266, 1051), (837, 1061), (954, 1063), (241, 1069), (40, 1087), (684, 1091), (1021, 1093), (382, 1097), (90, 1103), (286, 1109), (1010, 1117), (648, 1123), (427, 1129), (784, 1151), (825, 1153), (847, 1163), (383, 1171), (1028, 1181), (593, 1187), (658, 1193)] Calculation time: 1000.7ms \sourceoff Das kann man also problemlos(!) in einer Sekunde lösen.


   Profil
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 2892
  Beitrag No.3, vom Themenstarter, eingetragen 2022-08-22

Ich hab mir nochmal Gedanken gemacht, und dazu ein Beispiel vorgebracht. Es sind 6 Zahlen zu sortieren nach Grösse, von denen wir nur die Reste wissen. Die Restsumme ist jeweils 31. Es geht immer um die Zahl a, unter der stehen die Reste, und in der letzten Zeile, links neben der Zahl die Restsumme: b = a+2, c= a+4 .... Es geht um die Frage, ob man aus einer Menge von Restmengen nicht auf die Grösse der jeweiligen Zahlen schliessen kann? Man kann jetzt die Reste unter a als Restmenge auffassen. https://matheplanet.com/matheplanet/nuke/html/uploads/b/23651_ResteFrei_Radikale1.png Die Restmengen lassen sich bei allen Zahlen teilen in einen festen Teil, das Halbprimorial 3-7, (die Abstände der 6 Zahlen müssen also immer Vielfache von 210 sein!) und einen beweglichen Teil von ebenfalls gleicher Restsumme aber diversen Resten. Dieser bewegliche Teil bestimmt über die Grösse der Zahl. Ich hab dazu die letzte 3 PZ in ihren Stellen als PT mal permutiert. Vergleichen wir 4 und 6, für die 13 und 17 jeweils dieselbe Restsumme. Frage kann man sagen: je kleiner die Restedistanz zwischen Rest17 und Rest13, desto grösser die Zahl? Nein, denn bei 4 und 2. 11 und 13 tauschen die Plätze, Restsumme der beiden Reste jeweils 14. Die Distanz zwischen Rest 11 und Rest 13 = 11-3 = 8 und 9-5=4 Hier hat die grössere Distanz die Nase vorn. Kann man sagen: Hohe Reste bei hohen PZ ziehen nach oben? Der Unterschied zwischen Zahl 1 (kleinste Zahl) und Zahl 4 (grösste Zahl) scheint darauf hinzuweisen....


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3182
  Beitrag No.4, eingetragen 2022-08-23

Den "kleinsten" Rest von 1 finden wir, wenn die Reste bzgl. aller Moduln 1 sind. Den "größten" Rest von -1 finden wir, wenn die Reste bzgl. aller Moduln -1 sind. Alles andere wird kaum abzuschätzen sein, da die multiplikativen Inversen in die Berechnung eingehen. Daneben stellt sich die Frage, warum man etwas abschätzen will, das man schnell und effizient exakt ausrechnen kann. PS.: Da du ja auf Folgen von Zahlen mit kleinen Primteilern stehst - hier ein Beispiel der Länge 159 (also 79 ungerade Zahlen im Abstand 2, wenn man es wie bekellüblich unnötig kompliziert machen will.) Length: 159 Position: 18118886481725597855129403410 + k * 40729680599249024150621323470 Divisors: [2, 3, 2, 37, 2, 5, 2, 3, 2, 67, 2, 7, 2, 3, 2, 5, 2, 17, 2, 3, 2, 13, 2, 59, 2, 3, 2, 43, 2, 41, 2, 3, 2, 19, 2, 5, 2, 3, 2, 7, 2, 11, 2, 3, 2, 5, 2, 13, 2, 3, 2, 17, 2, 7, 2, 3, 2, 23, 2, 29, 2, 3, 2, 11, 2, 5, 2, 3, 2, 31, 2, 19, 2, 3, 2, 5, 2, 37, 2, 3, 2, 7, 2, 47, 2, 3, 2, 53, 2, 61, 2, 3, 2, 71, 2, 5, 2, 3, 2, 13, 2, 73, 2, 3, 2, 5, 2, 11, 2, 3, 2, 41, 2, 43, 2, 3, 2, 29, 2, 17, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 31, 2, 3, 2, 5, 2, 7, 2, 3, 2, 59, 2, 67, 2, 3, 2, 19, 2, 23, 2, 3, 2, 17, 2, 5, 2, 3, 2]


   Profil
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 2892
  Beitrag No.5, vom Themenstarter, eingetragen 2022-08-23

Danke Einfältiger! 1. Hab die 2-en mal gelöscht. Nun sieht deine Folge so aus: 79 [3, 37, 5, 3, 67, 7, 3, 5, 17, 3, 13, 59, 3, 43, 41, 3, 19, 5, 3, 7, 11, 3, 5, 13, 3, 17, 7, 3, 23, 29, 3, 11, 5, 3, 31, 19, 3, 5, 37, 3, 7, 47, 3, 53, 61, 3, 71, 5, 3, 13, 73, 3, 5, 11, 3, 41, 43, 3, 29, 17, 3, 7, 5, 3, 11, 31, 3, 5, 7, 3, 59, 67, 3, 19, 23, 3, 17, 5, 3] 2. Du notierst übrigens immer die kleinste PT. Ich habe mir angewöhnt immer die grössten unterwurzligen PT zu notieren, da kann man Primoriale besser erkennen. Das sähe dann so aus: 79 [3, 37, 5, 31, 67, 23, 3, 5, 17, 11, 13, 59, 7, 43, 41, 3, 19, 5, 3, 7, 11, 3, 5, 13, 3, 17, 7, 5, 23, 29, 3, 11, 5, 7, 31, 19, 13, 5, 37, 3, 7, 47, 17, 53, 61, 3, 71, 7, 3, 13, 73, 23, 5, 11, 19, 41, 43, 5, 29, 17, 3, 13, 5, 3, 11, 31, 3, 5, 7, 3, 59, 67, 5, 19, 23, 13, 17, 11, 3] Wenn man mit Code arbeitet, werden die Listen kürzer. Code: [1, 3, 6, 10, 11, 9, 17, 6, 1, 4, 2, 15, 14, 42, 44, 12, 45, 5, 47, 51] 4. Was Du übermittelst, ist ein ganze Serie von 79 Folgen innerhalb des Halbprimorials 79, da die 79 als PT <= Länge nicht eingezeichnet ist in Deinen Daten. Man kann sie daher setzen, wo man will. Da die Folge 79 Glieder hat, handelt es sich um eine Serie von 79 Folgen! - deren Sitz man über den CRT eruieren kann. 5. Zugleich scheint es eine Folge neuen Typs zu sein, weil a: im Grundkonstellat kein geschlossenes PartialPrimorial zu finden ist. (Damit zerstörst Du eine weitere kleine Illusion von mir. Gott sei Dank!) Und b: es die erste mir bekannte Bekell-Folge, die mit einer PZ weniger auskommt. 6. Kannst Du mal verraten, warum Du die geraden Zahlen mitbearbeitest? Das scheint doch unnötiger Rechenaufwand, auch für die Maschine. 7. Ich habe gestern übrigens das erste Intervall im Primorialkörper 47 berechnet, also nicht herausgesiebt bzw. nur ein ganz kleines Stück gesiebt. 8. Hier der Teilerspiegel Deiner Bekell-Folge79: https://matheplanet.com/matheplanet/nuke/html/uploads/b/23651_Einfa_ltigenFolge79Bild2.png 9. Hiermit kann ich die Anzahl dieser aus Deiner Folge herauszufilternden Folgen korrigieren. Es sind 5 PZ im Trichter (Rosa unten) Die kann man 5! verstehen, sind 120 Örter. Zu diesen 120 Örtern kommt noch 79 mal der Primteiler 79. Da hast also, - wenn ich richtig denke - :120 mal 79 = 9480 Folgen gefunden! Gratulation! Trotzdem, das ist auf 79 Primorial gerechnet, immer noch sehr, sehr selten. Noch viel seltener als die 96 Folgen von Länge 43! 10. Jedoch ist immer noch nicht bekannt, wie man intelligant die Startzahl der kleinsten 79-er-Bekell-Folge ermittelt. Konkret, wie müssen die PT auf den 5 durch die rosa Felder gekennzeichneten Columnen im Trichter verteilt sein (120 Möglichkeiten), dass die Reste die Startzahl der kleinsten Bekell-Folge79 verraten? Mein bisheriger Weg ist, alle Startzahlen berechnen und dann vergleichen. Der scheint mir aber altertümlich zu sein. Es muss was Bessres geben! 11. Da hier der Fall vorliegt, dass eine ganze PZ übrig bleibt, steht zu vermuten, dass andere Grundkonstellationen mit mehr als 15 Löchern, auch Bekell-Folgen produzieren können. Das müsste auch abgeklärt werden. 12. Was den bzw. einen unteren Grenzwert betrifft, also den Wert, der kleiner als die Startzahlen aller gefundenen Bekell-Folgen der Serie ist, so könnte man doch aus der Restmenge der diversen Startzahlen einfach die grossen Reste der PZ > 43 (in diesem Beispiel) entfernen und die Zahl eruieren, die mit den verbleibenden kleineren PZ sich per crt ergibt. Das wäre in Deinem Fall: 4063194755801031 (Reste 3 bis inkl. 43) Kann man dann sagen: Die Startzahlen aller Bekell-Folgen dieser Serie sind grösser? Dann hätte man einen Wert, über den man sagen könnte: Er ist immer grösser als 79^2!


   Profil
Bekell hat die Antworten auf ihre/seine Frage gesehen.
Bekell hat selbst das Ok-Häkchen gesetzt.
Bekell wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]