Welche Zahlen fehlen noch? (Chinesischer Restsatz?)

16.02.2023, 18:59

Malcang

Auf diesen Beitrag antworten »

Welche Zahlen fehlen noch? (Chinesischer Restsatz?)

Hallo mal wieder,

ich tue mir immer noch sehr schwer, mehrere Kongruenzen in Kombination zu sehen.
Für ein bestimmtes Problem hat mir nun ein python-Skript zumindest schonmal einie Lösungen präsentieren können. Dies sind die diejenigen Zahlen $\begin{eqnarray*} k \end{eqnarray*}$ für die gilt:
$\begin{eqnarray*} k\equiv 1 \pmod 9 \end{eqnarray*}$ oder $\begin{eqnarray*} k \equiv 8 \mod 9 \end{eqnarray*}$ oder $\begin{eqnarray*} k\equiv 4 \pmod 20 \end{eqnarray*}$ oder $\begin{eqnarray*} k \equiv 0 \pmod 5 \end{eqnarray*}$ oder...oder...oder. Insgesamt habe ich 15 Kongruenzen raus.
Nun möchte ich gerne wissen, ob das "alle" Zahlen sind.

Leider macht mir das immer noch Probleme.
Wie gehe ich diese Fragestellung nun an?

16.02.2023, 20:09

HAL 9000

Auf diesen Beitrag antworten »

Wirklich oder ??? Der chinesische Restsatz befasst sich mit und, also gleichzeitig geltenden Kongruenzen!

----------------------------------------------------------

Falls es wirklich um oder geht, dann kannst du das ganze natürlich durch "Streichen" lösen, wie beim Sieb des Eratosthenes:

Bilde den kgV aller Module der 15 Kongruenzen, das sei $\begin{eqnarray*} m \end{eqnarray*}$ und schreibe die Restklassen $\begin{eqnarray*} 0,1,\ldots,m-1 \end{eqnarray*}$ dieses Moduls auf. Jetzt streiche alle Zahlen

1) $\begin{eqnarray*} k=9n+1 \end{eqnarray*}$
2) $\begin{eqnarray*} k=9n+8 \end{eqnarray*}$
3) $\begin{eqnarray*} k=20n+4 \end{eqnarray*}$
4) $\begin{eqnarray*} k=5n \end{eqnarray*}$
...

jeweils für $\begin{eqnarray*} n=0,1,\ldots \end{eqnarray*}$ (soweit wie eben nötig). Wenn am Ende noch ungestrichene Restklassen übrig bleiben, tja, dann waren es eben nicht alle.

16.02.2023, 20:27

Malcang

Auf diesen Beitrag antworten »

N'Abend HAL 9000,

ja, in der Tat "oder". Deshalb auch das Fragezeichen hinter dem Chinesischen Restsatz. Ich dachte mir schon, dass das sicherlich falsch ist, aber ich wusste es auch nicht besser.
Zum Hintergrund:
Ich befasse mich ja mit den Proth-Zahlen. Sei $\begin{eqnarray*} h \end{eqnarray*}$ ungerade. Gesucht ist nun eine Menge $\begin{eqnarray*} \mathfrak{D} \end{eqnarray*}$ , sodass für alle $\begin{eqnarray*} k\in\mathbb N \end{eqnarray*}$ eine Primzahl $\begin{eqnarray*} p\in\mathfrak{D} \end{eqnarray*}$ existiert, sodass
$\begin{eqnarray*} \left( \frac{h\cdot 2^k + 1}{p} \right) = -1 \end{eqnarray*}$ erfllt ist, wobei dies das Jacobisymbol ist.
Die Frage ist, ob diese Menge endlich ist für vorgegebenes $\begin{eqnarray*} h \end{eqnarray*}$ .
Nun weiß ich ja folgendes:
$\begin{eqnarray*} \left( \frac{h\cdot 2^k+1}{p} \right) = \left( \frac{h\cdot 2^{k'}+1}{p} \right) \end{eqnarray*}$ mit $\begin{eqnarray*} k' \equiv k \pmod{ord_2(p)} \end{eqnarray*}$ .
Mit dem Skript hatte ich nun beispielsweise für $\begin{eqnarray*} h = 105 \end{eqnarray*}$ heraus:
$\begin{eqnarray*} \left( \frac{h\cdot 2^1+1}{11} \right) = -1 \end{eqnarray*}$ . Wegen $\begin{eqnarray*} ord_{11}(2) = 10 \end{eqnarray*}$ weiß ich $\begin{eqnarray*} \left( \frac{h\cdot 2^{21}+1}{11} \right) = \left( \frac{h\cdot 2^{11}+1}{11} \right) = -1 \end{eqnarray*}$ und so weiter.
Nun hatte ich bis $\begin{eqnarray*} k = 10.000 \end{eqnarray*}$ insgesamt 15 Werte / Kongruenzen rausbekommen und hatte gehofft, damit alle Zahlen abdecken zu können und insbesondere das Muster zu erkennen.

Edit: Jetzt sehe ich deinen Edit. Das sind ja dann doch so einige. Hm, ich hatte -wie immer- auf weniger Brute-Force gehofft Big Laugh

Big Laugh

16.02.2023, 20:29

HAL 9000

Auf diesen Beitrag antworten »

Wenn die Module so bunt durcheinander verschieden sind, dann wäre es ein unerhörter Glücksfall, alle Zahlen zu erwischen - kann ich mir kaum vorstellen, dass das gelingt. unglücklich

unglücklich

16.02.2023, 20:32

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Wenn die Module so bunt durcheinander verschieden sind, dann wäre es ein unerhörter Glücksfall, alle Zahlen zu erwischen - kann ich mir kaum vorstellen, dass das gelingt. unglücklich

unglücklich

In dem Paper das ich lese (was allerdings von 1993 ist) steht auch drin, dass es noch nicht bewiesen ist. Statistiken sprechen allerdings dafür, dass für alle $\begin{eqnarray*} h \end{eqnarray*}$ die durch drei teilbar und nicht von der Form $\begin{eqnarray*} 4^m-1 \end{eqnarray*}$ sind (hätte ich eben wohl schon erwähnen sollen) immer eine endliche Menge existiert. Ich wollte mir dafür jetzt mal einen Überblick verschaffen.

Aus diesem Grund war auch meine Frage gestern bezüglich der Ordnung von 2. Es wäre ja schön wenn ich von vornherein bestimmen könnte, welches $\begin{eqnarray*} p \end{eqnarray*}$ für das Jacobisymbol in Frage kommt (oder auch nicht)

17.02.2023, 08:48

HAL 9000

Auf diesen Beitrag antworten »

Ich will ja nicht sagen, dass es grundsätzlich nicht geht: Hat man beispielsweise oder-verknüpft

$\begin{eqnarray*} k\equiv 0\bmod 2 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 3\bmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 5\bmod 6 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 1\bmod 12 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 9\bmod 12 \end{eqnarray*}$

dann sind am Ende schon alle Zahlen von mindestens einer der 5 Kongruenzen erfasst. Aber irgendwie sieht es bei deinem Fall nicht so aus, als würde man einen derart perfekten Abschluss hinkriegen.

Ein bisschen erinnert mich das an das Collatz-Problem: Da kann man beliebig viele Kongruenzbedingungen für einen Anfangswert $\begin{eqnarray*} n \end{eqnarray*}$ bestimmen, so dass die zugehörige Collatz-Folge irgendwann diesen Anfangswert unterschreitet. Was ja bei einer vollständigen Abdeckung aller Fälle dann einen Beweis per Vollständiger Induktion ermöglichen würde, dass die Collatz-Folge immer in den 4-2-1-Zyklus einmündet. Diese Kongruenzbedingungen "dünnen" zwar das Feld aller natürlichen Zahlen immer mehr aus, aber nie komplett - ein auf dieser "Idee" basierender Beweis ist hoffnungslos.

Anzeige

17.02.2023, 14:25

Malcang

Auf diesen Beitrag antworten »

Hallo HAL,

vielen Dank für deine Auskunft. Ich habe auch deinen Beitrag im anderen Thread zur Ordnung gesehen. Ich werde das gleich einmal umsetzen, sitze gerade noch an einem für mich schwierigen python-Problem. Melde mich aber gleich wieder zurück, habe auch noch eine Frage zu dem Topic Big Laugh

Big Laugh

17.02.2023, 15:33

Malcang

Auf diesen Beitrag antworten »

Da bin ich wieder.

Zitat:

Original von HAL 9000
Diese Kongruenzbedingungen "dünnen" zwar das Feld aller natürlichen Zahlen immer mehr aus, aber nie komplett - ein auf dieser "Idee" basierender Beweis ist hoffnungslos.

Ich nehme an du meinst damit sowohl die der Collatz-Vermutung, als auch meine Art des "Ausdünnens"?

Ich fürchte auch dass das nicht reicht. Aber ich würde trotzdem gerne mal wissen, ob es einfach an meinem viel zu unerfahrenen Blick liegt, um das entscheiden zu können. Ich würde daher hier mal die Kongruenzen aufschreiben, die ich für $\begin{eqnarray*} h=3 \end{eqnarray*}$ sogerade berechnet habe. Das sind alle Werte bis einschließlich $\begin{eqnarray*} k = 6000 \end{eqnarray*}$ .

Ich stelle gerade fest, dass man hier im Board nicht spoilern kann. Ich hoffe es ist ok, dass ich nun diese lange Liste hier anfüge. Falls es eine lesbarere Methode gibt, sagt sie mir gerne smile

smile

$\begin{eqnarray*} k\equiv 1 \pmod 3 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 3 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 3 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 1 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 5 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 1 \pmod 7 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 5 \pmod 7 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 6 \pmod 7 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 6 \pmod 9 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 6 \pmod {10} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 8 \pmod {10} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 7 \pmod {11} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 1 \pmod {11} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod {11} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 5 \pmod {11} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 6 \pmod {11} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 8 \pmod {11} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 9 \pmod {11} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 10 \pmod {14} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 9 \pmod {15} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 12 \pmod {18} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 18 \pmod {21} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 12 \pmod {23} \end{eqnarray*}$

17.02.2023, 15:59

HAL 9000

Auf diesen Beitrag antworten »

Ein kleines Skript wirft mir für den kgV-Modul 318780 folgendes aus:

[0, 6120, 7380, 7560, 9900, 10080, 11340, 13860, 17460, 19980, 21240, 21420, 23760, 23940, 25200, 27720, 31320, 33840, 35100, 35280, 37620, 37800, 39060, 41580, 45180, 47700, 48960, 51480, 51660, 52920, 55440, 59040, 62820, 63000, 65340, 65520, 66780, 69300, 72900, 75420, 76680, 76860, 79200, 79380, 80640, 83160, 86760, 89280, 90720, 93060, 93240, 94500, 97020, 100620, 103140, 104400, 104580, 106920, 108360, 110880, 114480, 117000, 118260, 118440, 120780, 120960, 122220, 124740, 128340, 130860, 132120, 132300, 134640, 134820, 138600, 142200, 144720, 145980, 146160, 148680, 149940, 152460, 156060, 158580, 159840, 160020, 162360, 162540, 163800, 166320, 169920, 172440, 173700, 173880, 176220, 176400, 177660, 180180, 183780, 186300, 187560, 187740, 190080, 190260, 191520, 197640, 200160, 201420, 201600, 203940, 204120, 205380, 207900, 211500, 214020, 215280, 215460, 217800, 217980, 219240, 221760, 225360, 227880, 229140, 229320, 231660, 231840, 233100, 235620, 239220, 241740, 243000, 243180, 245520, 245700, 246960, 249480, 253080, 255600, 256860, 257040, 259380, 259560, 260820, 263340, 266940, 269460, 270720, 270900, 273240, 273420, 274680, 277200, 280800, 283320, 284580, 284760, 287100, 287280, 288540, 291060, 294660, 297180, 298440, 298620, 300960, 301140, 302400, 304920, 308520, 311040, 312300, 312480, 314820, 315000, 316260]

Das sind die Restklassen, die durch das Raster deines Kongruenzsystems fallen.

17.02.2023, 16:06

Malcang

Auf diesen Beitrag antworten »

Danke dir für die Mühen.
Ich glaube, das ist leider wirklich nicht zielführend. Wirklich schade unglücklich

unglücklich

Ich möchte aber noch fragen:
Mir ist die Kongruenz $\begin{eqnarray*} k\equiv 1\pmod 4 \end{eqnarray*}$ und $\begin{eqnarray*} k\equiv 3\pmod 4 \end{eqnarray*}$ aufgefallen. Kann ich die nicht beide ersetzen durch $\begin{eqnarray*} k\equiv 1\pmod 4 \end{eqnarray*}$ ?

17.02.2023, 16:11

HAL 9000

Auf diesen Beitrag antworten »

Nein, aber durch $\begin{eqnarray*} k\equiv 1\bmod 2 \end{eqnarray*}$ .

Tatsächlich bewirken

$\begin{eqnarray*} k\equiv 1 \pmod 3 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 3 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 3 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 1 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 5 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 6 \pmod {10} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 8 \pmod {10} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 9 \pmod {15} \end{eqnarray*}$

allein, dass alle Zahlen bis auf die durch 60 teilbaren erfasst sind.

17.02.2023, 16:20

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Nein, aber durch $\begin{eqnarray*} k\equiv 1\bmod 2 \end{eqnarray*}$ .

War auch mein Gedanke, aber falsch geschrieben. DAnke für den Hinweis!

Zitat:

Original von HAL 9000
Tatsächlich bewirken

$\begin{eqnarray*} k\equiv 1 \pmod 3 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 3 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 3 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 1 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 4 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 2 \pmod 5 \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 6 \pmod {10} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 8 \pmod {10} \end{eqnarray*}$
$\begin{eqnarray*} k\equiv 9 \pmod {15} \end{eqnarray*}$

allein, dass alle Zahlen bis auf die durch 60 teilbaren erfasst sind.

Sowas ist ja toll zu sehen geschockt

geschockt

An dem Blick muss ich arbeiten, ich experimentiere hier noch rum.
HAL, vielen Dank für all diese Hilfestellungen! Freude

Freude

Ich habe nun noch ein paar Fragen, die aber das Programmieren/optimieren angehen. Ich würde das in einen neuen Thread packen. Falls das falsch ist, liebe Mods, bitte mich darüber informieren.

21.02.2023, 12:02

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Ein kleines Skript wirft mir für den kgV-Modul 318780 folgendes aus:
[...]

HAL, kannst du mir hier vielleicht zur Hand gehen?
Ich wollte das gerne automatisieren. Sprich, ich gebe eine Grenze, das Skript ermittelt mir, welche Kongruenzen dabei anfallen und die übrigbleibenden gebe ich dann aus. Das ganze mache ich ja mit dem Bosma-Test. Nur zur kurzen Erläuterung: Ich gebe eine Liste primes mit Primzahlen vor und einen Koeffizienten h. Nun ermittele ich für itererierendes k die Funktion

code:
1:	bosma(h, k, primes)

Diese ermittelt also, ob $\begin{eqnarray*} h\cdot2^k+1 \end{eqnarray*}$ prim ist und gibt mir beispielweise aus

code:
1:	bosma(21, 5, primes) = [True, 5].

Das bedeutet: $\begin{eqnarray*} 21\cdot 2^5 + 1 \end{eqnarray*}$ ist prim. Ermittelt wurde das mit dem Jacobisymbol $\begin{eqnarray*} \left( \frac{h\cdot2^5+1}{5}\right) = -1 \end{eqnarray*}$ .
Nun weiß ich: $\begin{eqnarray*} ord_5(2) = 4 \end{eqnarray*}$ , also wird die Primzahl $\begin{eqnarray*} 5 \end{eqnarray*}$ funktionieren für alle $\begin{eqnarray*} k\equiv 5 \equiv 1 \pmod{4} \end{eqnarray*}$ .

Das ist der Ansatz.
Nun lasse ich also k laufen und schaue, welche Primzahl und vor allem welche Ordnung dort benutzt wird.

Hier mein Code:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

h = 21
primes = np.load("primes_3_to_10e9")
ords = []
kgv = 1


lim = 5
for k in range(1,lim+1):
    B = bosma(h, k, primes)[1]
    o = ord(2, B)
    entry = [k % o, o, B]
    if entry not in ords:
        ords.append(entry)

Die Liste entry beinhaltet also Restklassen, Modul und zugehörige Primzahl. Letztere ist mir gerade nicht wichtig.
Dann ermittele ich das kgv und baue die entsprechende Liste auf:

code:
1: 2: 3:	for el in ords: kgv = math.lcm(kgv, el[1]) numbers = list(range(1, kgv+1))

Jetzt kommt das für mich schwerste: Ich laufe nun die Elemente in ords durch und pro Element jeweils die komplette Liste numbers, deren Restklassen ich dann streiche:

code:
1: 2: 3: 4: 5: 6:	for el in ords: rest = el[0] mod = el[1] for n in numbers: if (n % mod == rest): numbers.remove(n)

Das funktioniert zwar, aber es ist auch sehr langsam. Natürlich, ich baue die Liste jedesmal wieder neu auf. Ich bin aber nicht gut in solchen DIngen. Wie kann ich das optimieren?

21.02.2023, 13:09

HAL 9000

Auf diesen Beitrag antworten »

Naja, du könntest ja stattdessen ein Feld (auch eine Liste) nehmen, mit Werten 0 und 1. Alles mit 0 initialisieren, und die dann gestrichenen mit 1 markieren (so bearbeitest du jedesmal nur ein Feldelement, was schnell gehen sollte). Zum Abschluss dann natürlich nochmal die Liste scannen, wo noch Nullen stehen.

Das wäre für mich die naheliegendste Variante, so hatte ich es oben ja auch implementiert:

code:

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

import sympy

def ausduennen(k):
    n = 1
    for i in k:
        n = sympy.lcm(n,i[1])
    z = [0 for j in range(0,n)]
    for i in k:
        j = i[0]
        while (j < n):
            z[j] += 1
            j += i[1]
    y = [j for j in range(0,n) if (z[j]==0)]
    print("{}: {}".format(n,y))
    
if __name__ == '__main__':
    ausduennen([(1,3),(2,3),(3,4),(1,4),(2,4),(2,5),(6,10),(8,10),(9,15),(1,7),(5,7),(6,7),(6,9),(7,11),(1,11),(2,11),(5,11),(6,11),(8,11),(9,11),(10,14),(12,18),(18,21),(12,23)])

21.02.2023, 14:21

Malcang

Auf diesen Beitrag antworten »

Danke HAL. Jetzt versuche ich noch, das ganze in die erste Schleife einzubauen, sodass immer möglichst wenig Elemente da sind, die überhaupt geprüft werden müssten. Das mache ich heute abend nochmal.

22.02.2023, 12:11

Malcang

Auf diesen Beitrag antworten »

Hallo nochmal,

das Skript konnte ich gut benutzen, vielen Dank dafür!

Nun habe ich mich gefragt, ob ich der Sache nicht auch analystischer auf die Spur kommen kann.
Es geht mir im Endeffekt "nur" darum zu wissen, ob noch Restklassen übrig bleiben. Welche das im einzelnen sind, ist erstmal nicht relevant.
Nun weiß ich ja, dass mit $\begin{eqnarray*} k \equiv \{1,2,3\}\pmod 4 \end{eqnarray*}$ bereits $\begin{eqnarray*} \frac{3}{4} \end{eqnarray*}$ aller Zahlen erfasst sind.
Wenn ich nun noch $\begin{eqnarray*} k\equiv\{1,2\}\pmod 3 \end{eqnarray*}$ dazunehme, sind alle Zahlen erfasst bis auf diejenigen, die $\begin{eqnarray*} \equiv 0 \pmod{12} \end{eqnarray*}$ sind.

Kann ich diesen Anteil nicht auch berechnen? Mir geistert dazu die Siebformel im Kopf rum aber ich sehe es noch nicht recht verwirrt

verwirrt

22.02.2023, 12:59

HAL 9000

Auf diesen Beitrag antworten »

Die Sonderfälle, die du nennst, sind natürlich algorithmisch in der Allgemeinheit schwer fassbar. Gehen wir von $\begin{eqnarray*} s \end{eqnarray*}$ solchen ODER-verknüpften Kongruenzen

$\begin{eqnarray*} k \equiv r_i\bmod m_i \end{eqnarray*}$ für $\begin{eqnarray*} i=1,\ldots,s \end{eqnarray*}$

aus. Weiterhin sei wie gehabt $\begin{eqnarray*} m=\operatorname{kgV}\left(m_1,\ldots,m_r\right) \end{eqnarray*}$ und wir betrachten die Mengen

$\begin{eqnarray*} \Omega = \left\{0,1,\ldots,m-1\right\} \end{eqnarray*}$

$\begin{eqnarray*} A_i = \left\{ k\in\Omega \mid k \equiv r_i\bmod m_i \right\} \end{eqnarray*}$

Du interessierst dich nun nur dafür, ob die Anzahl $\begin{eqnarray*} n = \left| \Omega\setminus \left( \bigcup\limits_{i=1}^s A_i\right)\right| \end{eqnarray*}$ der nichterfassten $\begin{eqnarray*} k \end{eqnarray*}$ nun Null ist oder nicht.

Dieses n lässt sich tatsächlich per Siebformel berechnen, und zwar gemäß

$\begin{eqnarray*} n = \sum_{J\subseteq \{1,\ldots,s\}} (-1)^{|J|}\cdot \left| \bigcap_{i\in J} A_i\right| \end{eqnarray*}$

D.h., die Summation läuft über $\begin{eqnarray*} 2^s \end{eqnarray*}$ Teilmengen $\begin{eqnarray*} J \end{eqnarray*}$ . Wie groß sind nun die Durchschnitte? Nun, das ist $\begin{eqnarray*} \left| \bigcap_{i\in J} A_i\right| = \frac{m}{\operatorname{kgV}\left(\{ m_i \mid i\in J\}\right)} \end{eqnarray*}$ sofern die Kongruenzen in $\begin{eqnarray*} J \end{eqnarray*}$ miteinander vereinbar sind - sonst Null.

Wenn du natürlich sowas hast wie $\begin{eqnarray*} k\equiv 1\bmod 4 \end{eqnarray*}$ und $\begin{eqnarray*} k\equiv 3\bmod 4 \end{eqnarray*}$ , und beide sind in einem $\begin{eqnarray*} J \end{eqnarray*}$ , dann haben wir natürlich den Nullfall, wir müssen diese $\begin{eqnarray*} J \end{eqnarray*}$ bei der Summenberechnung gar nicht beachten. Damit kann man den vollen Baum von $\begin{eqnarray*} 2^s \end{eqnarray*}$ Teilmengen schon mal hier und da deutlich beschneiden - dennoch sollte $\begin{eqnarray*} s \end{eqnarray*}$ natürlich nicht zu groß sein.

Fazit: Es ist möglich, mit Siebformel zu einem Ergebnis zu kommen, und im Fall $\begin{eqnarray*} 2^s \ll m \end{eqnarray*}$ (was i.a. der Fall sein sollte) ist es sicher auch eine Zeitersparnis gegenüber dem naiven Zugang von mir oben. Ist aber noch einiges an Programmierarbeit zu leisten zur

a) Feststellung, ob die ausgewählten Kongruenzen miteinander vereinbar sind, und

b) darauf basierend den Baum der einzubeziehenden $\begin{eqnarray*} J \end{eqnarray*}$ "intelligent" zu beschneiden.

22.02.2023, 13:06

Malcang

Auf diesen Beitrag antworten »

Ich danke die für die Antwort, HAL. Ich muss das gleich in Ruhe durcharbeiten.
Eine Anmerkung ist mir allerdings direkt aufgefallen:
Ich habe bei den ersten 30 Kongruenzen ein kgV von $\begin{eqnarray*} 120180060 \end{eqnarray*}$ heraus. Damit ist ja $\begin{eqnarray*} 2^s << m \end{eqnarray*}$ nicht gegeben verwirrt

verwirrt

22.02.2023, 13:14

HAL 9000

Auf diesen Beitrag antworten »

Tja, dann kommt es drauf an, wieviel du im Baum wegschneiden kannst. Ich hab nicht gesagt, dass schon alle Probleme geklärt sind.

22.02.2023, 13:50

Malcang

Auf diesen Beitrag antworten »

Das muss ich noch etwas verdauen.
Insbesondere bekomme ich den Eindruck, dass meine dahinterliegende Vermutung falsch ist. Ich gehe dazu mal ein paar Ideen durch, glaube aber, dass mir deine Wegschneidetechnik dabei hilft Augenzwinkern

Augenzwinkern

Ich werde mich dazu auf jeden Fall wieder melden, vielleicht dann aber in einem anderen Thread.

Vielen Dank für die Unterstützung smile

smile

01.03.2023, 11:21

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Dieses n lässt sich tatsächlich per Siebformel berechnen, und zwar gemäß

$\begin{eqnarray*} n = \sum_{J\subseteq \{1,\ldots,s\}} (-1)^{|J|}\cdot \left| \bigcap_{i\in J} A_i\right| \end{eqnarray*}$

HAL, wo vertue ich mich in der folgenden Rechnung?

Sei $\begin{eqnarray*} k\equiv 0 \pmod 3 \end{eqnarray*}$ oder $\begin{eqnarray*} k\equiv 1 \pmod 3 \end{eqnarray*}$ oder $\begin{eqnarray*} k\equiv 1 \pmod 2. \end{eqnarray*}$
Dann sind $\begin{eqnarray*} s = 3, m = 6, \Omega = \{0,1,2,3,4,5\}, A_1 = \{0,3\}, A_2 = \{1,4\}, A_3 = \{1,3,5\} \end{eqnarray*}$ .

Jetzt betrachte ich doch für die Siebformel die Teilmengen $\begin{eqnarray*} J \in \{ \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \} \end{eqnarray*}$ . Die Siebformel bringt mir jetzt:
$\begin{eqnarray*} n = -2-2-3+0+1+1- = -5 \end{eqnarray*}$
verwirrt

verwirrt

Ich hätte $\begin{eqnarray*} n=1 \end{eqnarray*}$ erwartet.

01.03.2023, 11:37

IfindU

Auf diesen Beitrag antworten »

Da hat HAL wohl einen Vorzeichenfehler. Es sollte eigentlich $\begin{eqnarray*} n=5 \end{eqnarray*}$ rauskommen, d.h. die Mengen $\begin{eqnarray*} A_1, A_2, A_3 \end{eqnarray*}$ zusammen decken 5 Zahlen ab. Du musst dann sagen wie viele Zahlen du erwartet hättest und dann kannst du die Differenz ausrechnen.

01.03.2023, 11:41

Malcang

Auf diesen Beitrag antworten »

Hallo IFindU,

danke für den Einwand. Ich wollte gerade meine Antwort editieren. Sollte nicht eher $\begin{eqnarray*} n=1 \end{eqnarray*}$ rauskommen? Wir suchen ja die übrigen Elemente. Womöglich fehlt in der Formel $\begin{eqnarray*} +|\Omega| \end{eqnarray*}$ (eventuell codiert durch $\begin{eqnarray*} A_0? \end{eqnarray*}$ Dann würde es ins Muster passen).

Trotzdem noch eine andere Frage. Ich habe HALs Post verstanden bis auf

Zitat:

D.h., die Summation läuft über $\begin{eqnarray*} 2^s \end{eqnarray*}$ Teilmengen $\begin{eqnarray*} J \end{eqnarray*}$ . Wie groß sind nun die Durchschnitte? Nun, das ist $\begin{eqnarray*} \left| \bigcap_{i\in J} A_i\right| = \frac{m}{\operatorname{kgV}\left(\{ m_i \mid i\in J\}\right)} \end{eqnarray*}$ sofern die Kongruenzen in $\begin{eqnarray*} J \end{eqnarray*}$ miteinander vereinbar sind - sonst Null.

Was genau ist mit "vereinbar" gemeint?

01.03.2023, 12:49

IfindU

Auf diesen Beitrag antworten »

Ich habe es mir oben noch einmal angeschaut. Offenbar meinte HAL
$\begin{eqnarray*} n = m+ \sum_{J\subseteq \{1,\ldots,s\}} (-1)^{|J|}\cdot \left| \bigcap_{i\in J} A_i\right| \end{eqnarray*}$ .

Vereinbar erklärt HAL auch in einem Beispiel danach. Es gibt Kongruenzen, die einfach keine gemeinsame Lösung zulassen.

01.03.2023, 12:57

Malcang

Auf diesen Beitrag antworten »

DAnke für deine Zeit.

Zitat:

Original von IfindU
Vereinbar erklärt HAL auch in einem Beispiel danach. Es gibt Kongruenzen, die einfach keine gemeinsame Lösung zulassen.

Ich habe mich auch falsch ausgedrückt. Ich frage mich eigentlich, ob ich diese Vereinbarkeit "analytisch" hinbekomme?
Im Beispiel von $\begin{eqnarray*} k\equiv 1 \pmod 4 \end{eqnarray*}$ und $\begin{eqnarray*} k\equiv 3\pmod 4 \end{eqnarray*}$ würde ich das ja erstmal dann erkennen, wenn ich die Zahlen von 1 bis 4 aufschreibe, dann die 1 streiche und dann die 3 streiche. Dann "merke" ich, es war nicht vereinbar.
ich hoffe ich konnte das einigermaßen verständlich formulieren.

01.03.2023, 13:07

IfindU

Auf diesen Beitrag antworten »

Dein Beispiel ist der leichte Fall. Wenn beides bzgl. dem gleichen Modulo genommen wird, muss das gleiche rauskommen oder die sind unvereinbar.

D.h. interessant ist, wenn wir verschiedene Modulo-Werte haben. Wir können Modulos "erweitern".

Beispiel: $\begin{eqnarray*} k \equiv 0 \mod 2 \iff k \equiv 0 \vee k \equiv 2 \mod 4 \end{eqnarray*}$ .

D.h. wir können also Kongruenzgleichung auf mehrere Kongruenzgleichung bzgl. einer größeren Restklasse umformen. Allgemeiner
$\begin{eqnarray*} k \equiv k_0 \mod m_1 \iff \vee_{l \in \{0, \ldots, m_2-1\}} (k \equiv k_0 + l m_1 \mod (m_1m_2)) \end{eqnarray*}$ .

(Ich hoffe ich habe mich jetzt nicht vertan bei den ganzen Indizes)

01.03.2023, 13:19

HAL 9000

Auf diesen Beitrag antworten »

Mal zwei einfache Beispiele mit jeweils den zwei nicht teilerfremden Modulen 4 und 6:

1) $\begin{eqnarray*} k\equiv 1\bmod 4 \end{eqnarray*}$ und $\begin{eqnarray*} k\equiv 3\bmod 6 \end{eqnarray*}$

Dieses System hat die eindeutige Lösung $\begin{eqnarray*} k\equiv 9\bmod 12 \end{eqnarray*}$ .

2) $\begin{eqnarray*} k\equiv 1\bmod 4 \end{eqnarray*}$ und $\begin{eqnarray*} k\equiv 4\bmod 6 \end{eqnarray*}$

Dieses System hat keine Lösung, denn bzgl. des ggT=2 der beiden Module bekommt man die einander widersprechenden Aussagen $\begin{eqnarray*} k\equiv 1\bmod 2 \end{eqnarray*}$ und $\begin{eqnarray*} k\equiv 0\bmod 2 \end{eqnarray*}$ .

01.03.2023, 13:20

Malcang

Auf diesen Beitrag antworten »

Sehr interessant IfindU, vielen Dank dafür. Ich werde mir das gleich nochmal in Ruhe anschauen und aufschreiben.

Eine Frage habe ich aber vorab. Sollte die Äquivalenz im Beispiel vielleicht nur " $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ " sein?
Ich könnte ja $\begin{eqnarray*} \pmod 2 \end{eqnarray*}$ auch auf andere mod erweitern als 4 verwirrt

verwirrt

Edit: HAL, es hat sich gerade mit deiner Antwort überschnitten. Ich lese sie erstmal in Ruhe.

Edit2: Alles klar, danke sehr! Das läuft dann also in diesen Berechnungen auf den chinesischen Restsatz hinaus?

Puh... Ich bin zwar nach wie vor an der puren Anzahl interessiert, aber wirklich leichter als die Brute-Force-Methode mit Wegstreichen kommt es mir jetzt nicht vor. Ich lasse mich dahingehend aber gerne eines besseren belehren.
Ich habe nun übrigens das Wegstreichen mit einem Bitvektor gelöst, das hat das Skript bereits deutlich verschnellert.

01.03.2023, 13:30

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Ich bin zwar nach wie vor an der puren Anzahl interessiert, aber wirklich leichter als die Brute-Force-Methode mit Wegstreichen kommt es mir jetzt nicht vor.

Jetzt weißt du, warum ich mit diesem Weg gezögert habe: Der ist sicher der bessere Weg, wenn alle Module teilerfremd sind oder es zumindest wenige "Überschneidungen" in der Hinsicht gibt.

Bei deiner Anwendung schätze ich die Situation aber so ein, dass es seht viele Überschneidungen gibt, und da verliert dieser Zugang zunehmend an Attraktivität.

01.03.2023, 13:45

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Malcang
Ich bin zwar nach wie vor an der puren Anzahl interessiert, aber wirklich leichter als die Brute-Force-Methode mit Wegstreichen kommt es mir jetzt nicht vor.

Jetzt weißt du, warum ich mit diesem Weg gezögert habe: Der ist sicher der bessere Weg, wenn alle Module teilerfremd sind oder es zumindest wenige "Überschneidungen" in der Hinsicht gibt.

Bei deiner Anwendung schätze ich die Situation aber so ein, dass es seht viele Überschneidungen gibt, und da verliert dieser Zugang zunehmend an Attraktivität.

Deine Einschätzung ist vollkommen korrekt. Die Module werden sogar größtenteils nicht teilerfremd sein, da sie jeweils die Ordnung von 2 modulo Primzahl sind.

HAL und IfinfU, ich danke euch vielmals für diese sehr lehrreichen Antworten! Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »