Discussion:
n*(2^(n-1)-(n-1)*n/2) ist eine Primzahl
Add Reply
m***@gmail.com
2020-08-01 11:17:51 UTC
Antworten
Permalink
Da werden einige Krypto-Firmen Pleite gehen wenn das stimmt.
Alfred Flaßhaar
2020-08-01 11:51:32 UTC
Antworten
Permalink
Post by m***@gmail.com
Da werden einige Krypto-Firmen Pleite gehen wenn das stimmt.
Für welche n soll das stimmen ;-) ?
m***@gmail.com
2020-08-01 12:07:49 UTC
Antworten
Permalink
Post by Alfred Flaßhaar
Für welche n soll das stimmen ;-) ?
Für keines. Ich habe aber noch einen 2. Versuch gemacht, und der soll für alle ungeraden n stimmen.
Alfred Flaßhaar
2020-08-01 13:19:18 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by Alfred Flaßhaar
Für welche n soll das stimmen ;-) ?
Für keines. Ich habe aber noch einen 2. Versuch gemacht, und der soll für alle ungeraden n stimmen.
Es gibt Gründe, Dir zu raten:"Laß´ es!"
m***@gmail.com
2020-08-01 22:27:53 UTC
Antworten
Permalink
Post by Alfred Flaßhaar
Es gibt Gründe, Dir zu raten:"Laß´ es!"
Wir reden später.
m***@gmail.com
2020-08-02 08:44:49 UTC
Antworten
Permalink
Post by m***@gmail.com
Wir reden später.
Ich habe (2^n)-1 jetzt nochmal nach der Anzahl a(n,k) der n Mengen abgezählt, die sich jeweils mit k Mengen schneiden. Womit ich auch ganz sicher wieder nicht der erste bin. Und außerdem müsste man da auch wieder weitersuchen, um zu finden, warum (2^n)-1 für manche n keine Primzahl ist (was nach Wikipedia bis wenigstens 2018 keiner wusste)(Programmierer nehmen übrigens immer 0 basierte Indizes):

a(n,0)=n
a(n,n-1)=1
a(n,k)=a(n-1,k-1)+a(n-1,k) für 0<k<n-1

Summer über k von 0..n-1 : a(n,k) ergibt (2^n)-1

1 2 3 4 5 6 7 8 9
1 3 6 10 15 21 28 36
1 4 10 20 35 56 86
1 5 15 35 79 126
1 6 21 56 126
1 7 28 86
1 8 36
1 9
1

Wahrscheinlich lasse ich das wirklich. Was ich aber schon öfter gesagt habe in letzter Zeit.
Jens Kallup
2020-08-02 09:19:09 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by m***@gmail.com
Wir reden später.
das war auch vor 2018 so der Fall.
Ein BIOS setzt den Computer erst in einen Urzustand.
Davor kennt der Computer nur eine Aufwärmphase, die bei 0 anfängt.
Post by m***@gmail.com
a(n,0)=n
a(n,n-1)=1
a(n,k)=a(n-1,k-1)+a(n-1,k) für 0<k<n-1
Summer über k von 0..n-1 : a(n,k) ergibt (2^n)-1
0 und 1 sind keine Primzahlen!
Primzahlen müssen >= 2 sein!!!

Also 2 < n < n - 1

2 < 3 < (3 - 1) ! peäng

(2^n) - 1 = 2^2 = 4 - 1 = 3 => ok
= 2^3 = 27 - 1 = 26 => peäng
Post by m***@gmail.com
Wahrscheinlich lasse ich das wirklich. Was ich aber schon öfter gesagt habe in letzter Zeit.
Du musst Verstehen können, das in der Kryptografie Primzahlen nicht das
Allheilmittel sind.
Würdest Du nur mit Primzahlen arbeiten, benötigst Du mindestenz 2 Keys:
Kannst ja mal informatib den Anderen Post lesen.

Also:
1x öffentlicher Schlüssel
1x privater Schlüssel

und der 3. Zustand ist leider wegen SAM ein BackDoor!!!

Also Schluß damit.

Jens

P.S.: Jetzt können alle Interpol anrufen!!!
JA, ICH HABS GESCHRIEBEN, BITTE KEINE PANIK !!!
AM BESTEN GLEICH KABEL AUS DER NETZDOS STÖPSEL,
KAUGUMMI IN DOSE UND MINDESTENZ 10 MINUTEN BEI
100 Grad mit Föhn zukleben.
m***@gmail.com
2020-08-02 14:41:00 UTC
Antworten
Permalink
Post by Jens Kallup
1x öffentlicher Schlüssel
1x privater Schlüssel
Weil man mit dem öffentlichen Schlüssel die Primzahl nicht schnell genug wieder herstellen kann.
Post by Jens Kallup
und der 3. Zustand ist leider wegen SAM ein BackDoor!!!
Sagen wir es gibt 1.000.000 Primzahlen zwischen p<q. Wenn ich eine Message in 25ms mit Schlüssel entschlüsseln kann, kann ich sie in 25.000 Sekunden ohne Schlüssel entschlüsseln, also in wenigen Stunden. Ich muss nur 1.000.000 Primzahlen zwischen p<q kennen.
Post by Jens Kallup
Also Schluß damit.
Ok.
Jens Kallup
2020-08-02 14:59:15 UTC
Antworten
Permalink
Post by m***@gmail.com
Sagen wir es gibt 1.000.000 Primzahlen zwischen p<q. Wenn ich eine Message in 25ms mit Schlüssel entschlüsseln kann, kann ich sie in 25.000 Sekunden ohne Schlüssel entschlüsseln, also in wenigen Stunden. Ich muss nur 1.000.000 Primzahlen zwischen p<q kennen.
Post by Jens Kallup
Also Schluß damit.
mit Schluß meinte ich, das hier keine Hacker ausgebildet werden
sollen und die Schläfer hier um Möglichkeiten...

Kryptographie ist zwar mit Mathe eng verbunden, aber ich sehe
schon eine enge Computeraffinität an Dir hier.

Um die Frage aber trotzdem zu beantworten:
Diese sind bereits alle bekannt.

Jens
m***@gmail.com
2020-08-02 15:46:56 UTC
Antworten
Permalink
Post by Jens Kallup
Post by m***@gmail.com
Sagen wir es gibt 1.000.000 Primzahlen zwischen p<q. Wenn ich eine Message in 25ms mit Schlüssel entschlüsseln kann, kann ich sie in 25.000 Sekunden ohne Schlüssel entschlüsseln, also in wenigen Stunden. Ich muss nur 1.000.000 Primzahlen zwischen p<q kennen.
Diese sind bereits alle bekannt.
Hmm...

Wie gesagt, wenn ich 1.000.000.000 aufeinanderfolgende Primzahlen kenne und einen Prozessor mit 64 CPUs habe (kann sich heute jeder Kriminelle beschaffen), kann ich ein kleine Testmessage sagen wir mal in 500µs brute forcen. Den öffentlichen Schlüssel habe ich ja. Dann brauche ich nur 500.000/64 Sekunden, noch nicht mal 2 Stunden um den Schlüssel zu knacken. Ohne jetzt nachzuschauen wieviel bit verwenden werden beim SSL z.B. und zu wissen wie viele Primzahlen in der Range verwendet werden, könnte ich mir vorstellen dass es ziemlich eng für RSA werden könnte?
Jens Kallup
2020-08-02 17:01:15 UTC
Antworten
Permalink
Post by m***@gmail.com
Wie gesagt, wenn ich 1.000.000.000 aufeinanderfolgende Primzahlen kenne und einen Prozessor mit 64 CPUs habe (kann sich heute jeder Kriminelle beschaffen), kann ich ein kleine Testmessage sagen wir mal in 500µs brute forcen. Den öffentlichen Schlüssel habe ich ja. Dann brauche ich nur 500.000/64 Sekunden, noch nicht mal 2 Stunden um den Schlüssel zu knacken. Ohne jetzt nachzuschauen wieviel bit verwenden werden beim SSL z.B. und zu wissen wie viele Primzahlen in der Range verwendet werden, könnte ich mir vorstellen dass es ziemlich eng für RSA werden könnte?
mach Dir keine Sorgen, alles schon gelöst, oder sollte ich sagen,
dass SSL unsicher ist?

Alles verschwendete Geld- und Zeitinvestments.
m***@gmail.com
2020-08-02 19:52:03 UTC
Antworten
Permalink
Post by Jens Kallup
mach Dir keine Sorgen, alles schon gelöst, oder sollte ich sagen,
dass SSL unsicher ist?
Alles verschwendete Geld- und Zeitinvestments.
Lol. Da fällt mir ein, dass man den Key-Generator ja schon längst als Open Source Software hinterhergeworfen bekommt. D.h. ich kann einfach von dort den Primzahl-Generator nehmen und dann Bruteforcen. Lol.
m***@gmail.com
2020-08-04 15:15:58 UTC
Antworten
Permalink
Post by Jens Kallup
mach Dir keine Sorgen, alles schon gelöst, oder sollte ich sagen,
dass SSL unsicher ist?
Alles verschwendete Geld- und Zeitinvestments.
Und das glaube ich Dir immer noch nicht! Schau mal auf Wikipedia. Alle Rekordprimzahlen haben die Form 2^n-1. Aber mit 2^n-1 fängst Du zu wenige ein. Außerdem sieht man ganz klar, dass die Rekordprimzahlen mit Workstations berechnet wurden. Niemand hat z.B. 82.589.933 viele Bits für ein Integer übrig. Für steht fest, dass alles, was zwischen dem 2^n-1 Sieb durchsickert, weitestgehend unbekannt ist.

Ich möchte da noch hinzufügen, dass es sowieso wenig Sinn macht, wenn ich in 2 Stunden jedes SSL Zertifikat knacken könnte. Was sollte ich dann machen? Die Banken arbeiten doch alle mit Salz und Pfeffer, auch als 2F bekannt. Und wenn ich es wirklich schaffen sollte, dann wird der nächste Schlüssel eben in jeder Message direkt erneuert.
m***@gmail.com
2020-08-04 15:25:51 UTC
Antworten
Permalink
Post by m***@gmail.com
Ich möchte da noch hinzufügen, dass es sowieso wenig Sinn macht, wenn ich in 2 Stunden jedes SSL Zertifikat knacken könnte. Was sollte ich dann machen? Die Banken arbeiten doch alle mit Salz und Pfeffer, auch als 2F bekannt. Und wenn ich es wirklich schaffen sollte, dann wird der nächste Schlüssel eben in jeder Message direkt erneuert.
Und wenn ich dennoch schaffen würde, 2/3 der Weltwertschöpfung einzukassieren, dann würde man sowieso jegliche Grundrechte vergessen, um mich zu zerquetschen.
m***@gmail.com
2020-08-04 15:57:45 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by Jens Kallup
mach Dir keine Sorgen, alles schon gelöst, oder sollte ich sagen,
dass SSL unsicher ist?
Alles verschwendete Geld- und Zeitinvestments.
Und das glaube ich Dir immer noch nicht! Schau mal auf Wikipedia. Alle Rekordprimzahlen haben die Form 2^n-1. Aber mit 2^n-1 fängst Du zu wenige ein. Außerdem sieht man ganz klar, dass die Rekordprimzahlen mit Workstations berechnet wurden. Niemand hat z.B. 82.589.933 viele Bits für ein Integer übrig. Für steht fest, dass alles, was zwischen dem 2^n-1 Sieb durchsickert, weitestgehend unbekannt ist.
Ich möchte da noch hinzufügen, dass es sowieso wenig Sinn macht, wenn ich in 2 Stunden jedes SSL Zertifikat knacken könnte. Was sollte ich dann machen? Die Banken arbeiten doch alle mit Salz und Pfeffer, auch als 2F bekannt. Und wenn ich es wirklich schaffen sollte, dann wird der nächste Schlüssel eben in jeder Message direkt erneuert.
Selbst mit meiner winzigsten Erkenntnis, dass mit 2^4-1+17=4*2^3 noch die ein oder andere Primzahl extra zu erhaschen ist, braucht ein Thread für 2^58-n ein paar Millisekunden, für alle Primzahlen in dieser Range rechnet er aber bereits seit Minuten.
m***@gmail.com
2020-08-04 23:43:37 UTC
Antworten
Permalink
Post by m***@gmail.com
Selbst mit meiner winzigsten Erkenntnis, dass mit 2^4-1+17=4*2^3 noch die ein oder andere Primzahl extra zu erhaschen ist, braucht ein Thread für 2^58-n ein paar Millisekunden, für alle Primzahlen in dieser Range rechnet er aber bereits seit Minuten.
n=2 3+1=n*2^(n-1) prime:3
n=3 7+5=n*2^(n-1) prime:7
n=3 7+5=n*2^(n-1) prime:5
n=4 15+17=n*2^(n-1) prime:17
n=5 31+49=n*2^(n-1) prime:31
n=7 127+321=n*2^(n-1) prime:127
n=8 255+769=n*2^(n-1) prime:769
n=13 8191+45057=n*2^(n-1) prime:8191
n=17 131071+983041=n*2^(n-1) prime:131071
n=19 524287+4456449=n*2^(n-1) prime:524287
n=28 268435455+3489660929=n*2^(n-1) prime:3489660929
n=31 2147483647+31138512897=n*2^(n-1) prime:2147483647
n=52 4503599627370495+112589990684262401=n*2^(n-1) prime:112589990684262401
n=56 72057594037927935+1945555039024054273=n*2^(n-1) prime:1945555039024054273

... und zwar bei geraden n. Und für die daraus gewonnenen prims, ist sogar bis n=58 auch 2^(2^n-1)-1 wieder prim.
m***@gmail.com
2020-08-05 07:20:33 UTC
Antworten
Permalink
Am Mittwoch, 5. August 2020 01:43:39 UTC+2 schrieb ***@gmail.com:

Nach Primzahlen geordnet: In Klammern steht "n über k". Mehr gibt es nicht-trivialerweise nicht, z.B. keine 13.

p=7 (3,1)
p=11 (4,2)
p=17 (4,2)
p=23 (5,3)
p=29 (7,5)
p=31 (5,1)
p=37 (8,6)
p=47 (8,6)
p=67 (11,9)
p=79 (12,10)
p=107 (13,11)
p=127 (7,1)
p=137 (16,14)
p=163 (8,4)
p=173 (17,15)
p=191 (19,17)
p=211 (20,18)
p=233 (20,18)
p=277 (23,21)
p=353 (25,23)
p=379 (27,25)
p=443 (9,5)
p=467 (29,27)
p=563 (32,30)
p=631 (35,33)
p=743 (37,35)
p=769 (8,2)
p=821 (40,38)
p=863 (40,38)
p=1013 (10,2)
p=1093 (13,9)
p=1291 (9,3)
p=1471 (14,10)
p=2063 (14,10)
p=3797 (12,4)
p=7547 (21,17)
p=8191 (13,1)
p=9109 (22,18)
p=9949 (15,9)
p=10903 (23,19)
p=12911 (14,6)
p=16369 (14,2)
p=25147 (16,10)
p=32647 (15,3)
p=35401 (17,11)
p=36457 (31,27)
p=47501 (32,28)
p=65519 (16,2)
p=102913 (39,35)
p=125219 (41,37)
p=131071 (17,1)
p=180241 (15,3)
p=190051 (24,18)
p=341303 (17,7)
p=524287 (19,1)
p=1149017 (32,26)
p=1807781 (25,17)
p=3505699 (27,19)
p=3924527 (26,18)
p=11460949 (31,23)
p=16628809 (27,17)
p=20987389 (32,24)
p=24821333 (28,18)
p=61450327 (26,10)
p=67108837 (26,2)
p=75973189 (31,21)
p=222139943 (28,12)
p=301766029 (31,19)
p=390179771 (30,18)
p=483269639 (27,11)
p=773201629 (31,17)
p=1050777737 (30,10)
p=1543503901 (27,3)
p=2136022699 (31,9)
p=2147483647 (31,1)
p=2448023843 (32,16)
p=2537663419 (30,14)
p=2952790453 (28,4)
p=3489660929 (28,2)
p=20401343003 (31,7)
p=81606108293 (33,8)
m***@gmail.com
2020-08-05 07:40:41 UTC
Antworten
Permalink
Am Mittwoch, 5. August 2020 09:20:34 UTC+2 schrieb ***@gmail.com:

n=2
n=3 (k=1) 7 (sum)
n=4 (k=2) 11 (sum) (k=2) 17 (rest)
n=5 (k=1) 31 (sum) (k=3) 23 (rest)
n=6
n=7 (k=1) 127 (sum) (k=5) 29 (sum)
n=8 (k=2) 769 (rest) (k=4) 163 (sum) (k=6) 37 (sum) (k=6) 47 (rest)
n=9 (k=3) 1291 (rest) (k=5) 443 (rest)
n=10 (k=2) 1013 (sum)
n=11 (k=9) 67 (sum)
n=12 (k=4) 3797 (sum) (k=10) 79 (sum)
n=13 (k=1) 8191 (sum) (k=9) 1093 (sum) (k=11) 107 (rest)
n=14 (k=2) 16369 (sum) (k=6) 12911 (sum) (k=10) 1471 (sum) (k=10) 2063 (rest)
n=15 (k=3) 32647 (sum) (k=3) 180241 (rest) (k=9) 9949 (sum)
n=16 (k=2) 65519 (sum) (k=10) 25147 (rest) (k=14) 137 (sum)
n=17 (k=1) 131071 (sum) (k=7) 341303 (rest) (k=11) 35401 (rest) (k=15) 173 (rest)
n=18
n=19 (k=1) 524287 (sum) (k=17) 191 (sum)
n=20 (k=18) 211 (sum) (k=18) 233 (rest)
n=21 (k=17) 7547 (sum)
n=22 (k=18) 9109 (sum)
n=23 (k=19) 10903 (sum) (k=21) 277 (sum)
n=24 (k=18) 190051 (sum)
n=25 (k=17) 1807781 (sum) (k=23) 353 (rest)
n=26 (k=2) 67108837 (sum) (k=10) 61450327 (sum) (k=18) 3924527 (rest)
n=27 (k=3) 1543503901 (rest) (k=11) 483269639 (rest) (k=17) 16628809 (sum) (k=19) 3505699 (sum) (k=25) 379 (sum)
n=28 (k=2) 3489660929 (rest) (k=4) 2952790453 (rest) (k=12) 222139943 (sum) (k=18) 24821333 (sum)
n=29 (k=27) 467 (rest)
n=30 (k=10) 1050777737 (sum) (k=14) 2537663419 (rest) (k=18) 390179771 (rest)
n=31 (k=1) 2147483647 (sum) (k=7) 20401343003 (rest) (k=9) 2136022699 (sum) (k=17) 773201629 (sum) (k=19) 301766029 (sum) (k=21) 75973189 (sum) (k=23) 11460949 (sum) (k=27) 36457 (sum)
n=32 (k=16) 2448023843 (sum) (k=24) 20987389 (rest) (k=26) 1149017 (sum) (k=28) 47501 (rest) (k=30) 563 (rest)
n=33 (k=8) 81606108293 (rest)
n=34
n=35 (k=33) 631 (sum)
n=36
n=37 (k=35) 743 (rest)
n=38
n=39 (k=35) 102913 (rest)
n=40 (k=38) 821 (sum) (k=38) 863 (rest)
n=41 (k=37) 125219 (rest)

m***@gmail.com
2020-08-02 16:01:59 UTC
Antworten
Permalink
Post by Jens Kallup
Diese sind bereits alle bekannt.
Glaube ich nicht. <Genauso wenig wie die Welt eine weitere dumme Krypto-Konversation braucht>. Aber wahrscheinlich sind die dümmsten Verfahren mit 5 verschiedenen Zufallssequenzen deren Kongruenzen vielleicht noch gegenseitig abhängig sind und dann noch Salz und Pfeffer angewendet wird die besten.
Alfred Flaßhaar
2020-08-02 13:03:05 UTC
Antworten
Permalink
(...)

Zum Term im Betreff hatte ich erst den Verdacht, daß ein Spaß sich
entwickelt. Du meinst es aber ernst? Offensichtlich ist das keine
Primzahl, wenn n keine ist. Auch für 2^n-1 finden sich leicht
Gegenbeispiele, daß nicht für alle n das prim wird. Berühmter Klassiker
auf der Suche nach einer Primzahlformel war der (Fehl-)Versuch von L.
Euler n^2+n+41. Anders sieht es aktuell aus mit der Suche nach
Primzahlen der Form 2^n-1 (Mersenne) und 2^2^n+1 (Fermat). Das sind
harte ungelöste Brocken.

Gruß, Alfred Flaßhaar
Alfred Flaßhaar
2020-08-02 13:58:08 UTC
Antworten
Permalink
Post by Alfred Flaßhaar
(...)
Zum Term im Betreff hatte ich erst den Verdacht, daß ein Spaß sich
entwickelt. Du meinst es aber ernst? Offensichtlich ist das keine
Primzahl, wenn n keine ist. Auch für 2^n-1 finden sich leicht
Gegenbeispiele, daß nicht für alle n das prim wird. Berühmter Klassiker
auf der Suche nach einer Primzahlformel war der (Fehl-)Versuch von L.
Euler n^2+n+41. Anders sieht es aktuell aus mit der Suche nach
Primzahlen der Form 2^n-1 (Mersenne) und 2^2^n+1 (Fermat). Das sind
harte ungelöste Brocken.
p.s.

Interessant ist auch die Frage, für welche n der Term 991*n^2+1 prim ist
oder Quadratzahl.
m***@gmail.com
2020-08-02 19:43:27 UTC
Antworten
Permalink
Post by Alfred Flaßhaar
Zum Term im Betreff hatte ich erst den Verdacht, daß ein Spaß sich
entwickelt. Du meinst es aber ernst? Offensichtlich ist das keine
Primzahl, wenn n keine ist. Auch für 2^n-1 finden sich leicht
Gegenbeispiele, daß nicht für alle n das prim wird. Berühmter Klassiker
auf der Suche nach einer Primzahlformel war der (Fehl-)Versuch von L.
Euler n^2+n+41. Anders sieht es aktuell aus mit der Suche nach
Primzahlen der Form 2^n-1 (Mersenne) und 2^2^n+1 (Fermat). Das sind
harte ungelöste Brocken.
Ich habe jetzt nochmal abgezählt, wie viele Schnittmengen ich für den Beweis meiner Mengen-Operationen über 2^n-1 benutze. Und außerdem habe ich erkannt, dass mein a(n,k) auch als "n über k" bekannt und nicht-rekursiv berechnet werden kann.

D.h.

Ich kürze jetzt mal "Summe über k von 1 bis n: (k-1)*(n über k)" als Sum((k-1)*(n,k)) ab.

Dann habe ich: 2^n-1=n*2^(n-1)-Sum((k-1)*(n,k)). D.h. immer wenn "n über k" geteilt durch n eine ganze Zahl ist, gilt 2^n-1=n*(2^(n-1)-(Sum((k-1)(n,k))/n) und ist durch n teilbar.
Jens Kallup
2020-08-02 20:18:07 UTC
Antworten
Permalink
Post by m***@gmail.com
Ich habe jetzt nochmal abgezählt, wie viele Schnittmengen ich für den Beweis meiner Mengen-Operationen über 2^n-1 benutze. Und außerdem habe ich erkannt, dass mein a(n,k) auch als "n über k" bekannt und nicht-rekursiv berechnet werden kann.
D.h.
Ich kürze jetzt mal "Summe über k von 1 bis n: (k-1)*(n über k)" als Sum((k-1)*(n,k)) ab.
Dann habe ich: 2^n-1=n*2^(n-1)-Sum((k-1)*(n,k)). D.h. immer wenn "n über k" geteilt durch n eine ganze Zahl ist, gilt 2^n-1=n*(2^(n-1)-(Sum((k-1)(n,k))/n) und ist durch n teilbar.
n := 2
k := 5

2^2 - 1 = 4 - 1 = 3
= 2 * (2^(2 - 1) - (sum_1(5 - 1) * (2, 5)) / 2
= 2 * (2^1 ) - (sum_1(5 + 5 - 1) / 2
= 2 * 1 - sum_1(9 * 9) / 2
= 1 - 81 / 2
= 40
----------------------
=> no prime !
m***@gmail.com
2020-08-02 20:09:36 UTC
Antworten
Permalink
Post by Alfred Flaßhaar
Zum Term im Betreff hatte ich erst den Verdacht, daß ein Spaß sich
entwickelt. Du meinst es aber ernst? Offensichtlich ist das keine
Primzahl, wenn n keine ist. Auch für 2^n-1 finden sich leicht
Gegenbeispiele, daß nicht für alle n das prim wird. Berühmter Klassiker
auf der Suche nach einer Primzahlformel war der (Fehl-)Versuch von L.
Euler n^2+n+41. Anders sieht es aktuell aus mit der Suche nach
Primzahlen der Form 2^n-1 (Mersenne) und 2^2^n+1 (Fermat). Das sind
harte ungelöste Brocken.
Den Term im Betreff habe ich böse versemmelt, der Ansatz zeigt aber schon mal was:

Sei "Sum((k-1)*(n,k)" die Summe von (k-1)*"n über k" von k=1..n.

Dann ist 2^n-1=n*2^(n-1)-Sum((k-1)*(n,k)).

Also immer wenn n*2 und Sum((k-1)*(n,k)) nicht Teilerfremd sind, ist 2^n-1 keine Primzahl. Schonmal.
m***@gmail.com
2020-08-02 20:17:43 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by Alfred Flaßhaar
Zum Term im Betreff hatte ich erst den Verdacht, daß ein Spaß sich
entwickelt. Du meinst es aber ernst? Offensichtlich ist das keine
Primzahl, wenn n keine ist. Auch für 2^n-1 finden sich leicht
Gegenbeispiele, daß nicht für alle n das prim wird. Berühmter Klassiker
auf der Suche nach einer Primzahlformel war der (Fehl-)Versuch von L.
Euler n^2+n+41. Anders sieht es aktuell aus mit der Suche nach
Primzahlen der Form 2^n-1 (Mersenne) und 2^2^n+1 (Fermat). Das sind
harte ungelöste Brocken.
Sei "Sum((k-1)*(n,k)" die Summe von (k-1)*"n über k" von k=1..n.
Dann ist 2^n-1=n*2^(n-1)-Sum((k-1)*(n,k)).
Also immer wenn n*2 und Sum((k-1)*(n,k)) nicht Teilerfremd sind, ist 2^n-1 keine Primzahl. Schonmal.
1 2 3 4 5 6 7 8 9 *0
1 3 6 10 15 21 28 36 *1
1 4 10 20 35 56 86 *2
1 5 15 35 79 126 *3
1 6 21 56 126 *4
1 7 28 86 *5
1 8 36 *6
1 9 *7
1 *8
Spalte nicht Teilerfremd -> 2^n-1 keine Primzahl
m***@gmail.com
2020-08-02 20:19:06 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by m***@gmail.com
Post by Alfred Flaßhaar
Zum Term im Betreff hatte ich erst den Verdacht, daß ein Spaß sich
entwickelt. Du meinst es aber ernst? Offensichtlich ist das keine
Primzahl, wenn n keine ist. Auch für 2^n-1 finden sich leicht
Gegenbeispiele, daß nicht für alle n das prim wird. Berühmter Klassiker
auf der Suche nach einer Primzahlformel war der (Fehl-)Versuch von L.
Euler n^2+n+41. Anders sieht es aktuell aus mit der Suche nach
Primzahlen der Form 2^n-1 (Mersenne) und 2^2^n+1 (Fermat). Das sind
harte ungelöste Brocken.
Sei "Sum((k-1)*(n,k)" die Summe von (k-1)*"n über k" von k=1..n.
Dann ist 2^n-1=n*2^(n-1)-Sum((k-1)*(n,k)).
Also immer wenn n*2 und Sum((k-1)*(n,k)) nicht Teilerfremd sind, ist 2^n-1 keine Primzahl. Schonmal.
1 2 3 4 5 6 7 8 9 *0
1 3 6 10 15 21 28 36 *1
1 4 10 20 35 56 86 *2
1 5 15 35 79 126 *3
1 6 21 56 126 *4
1 7 28 86 *5
1 8 36 *6
1 9 *7
1 *8
Spalte nicht Teilerfremd -> 2^n-1 keine Primzahl
Falsch!

Ganze Spalte nicht Teilerfremd mit 2 oder n -> 2^n-1 keine Primzahl.
Jens Kallup
2020-08-02 20:21:23 UTC
Antworten
Permalink
Post by m***@gmail.com
Spalte nicht Teilerfremd -> 2^n-1 keine Primzahl
1 kannste streichen - siehe wischung, heute w+rde man
sagen ausrtzelfummeln pder wegradieren.

jojo
m***@gmail.com
2020-08-02 20:30:36 UTC
Antworten
Permalink
Post by Jens Kallup
1 kannste streichen - siehe wischung, heute w+rde man
sagen ausrtzelfummeln pder wegradieren.
jojo
Bringt gar nichts. Ich hatte spekuliert, dass ich n ausklammern kann. Leider falsch.
Jens Kallup
2020-08-02 20:33:13 UTC
Antworten
Permalink
Post by m***@gmail.com
Bringt gar nichts. Ich hatte spekuliert, dass ich n ausklammern kann. Leider falsch.
ich meinte, 1 ist kein prime, und kann auch nicht invertiert werden.
m***@gmail.com
2020-08-02 20:35:59 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by Jens Kallup
1 kannste streichen - siehe wischung, heute w+rde man
sagen ausrtzelfummeln pder wegradieren.
jojo
Bringt gar nichts. Ich hatte spekuliert, dass ich n ausklammern kann. Leider falsch.
Interessant ist aber für n=4, also das erste n für das 2^n-1 nicht prim ist:

n*2^(n-1) - Sum((k-1)(n,)) = 32 - 17 = 15. Hier ist Sum((k-1)(n,k)) prim.
Jens Kallup
2020-08-02 20:37:46 UTC
Antworten
Permalink
Post by m***@gmail.com
n*2^(n-1) - Sum((k-1)(n,)) = 32 - 17 = 15. Hier ist Sum((k-1)(n,k)) prim.
rechne nochmal
m***@gmail.com
2020-08-02 20:41:36 UTC
Antworten
Permalink
Post by Jens Kallup
Post by m***@gmail.com
n*2^(n-1) - Sum((k-1)(n,)) = 32 - 17 = 15. Hier ist Sum((k-1)(n,k)) prim.
rechne nochmal
n=4

4*2^3-(6+8+3)=2^5-17=32-17=15
m***@gmail.com
2020-08-02 20:48:23 UTC
Antworten
Permalink
Post by m***@gmail.com
4*2^3-(6+8+3)=2^5-17=32-17=15
Und außerdem interessant: 15 ist teilbar durch n-1
Jens Kallup
2020-08-02 20:49:35 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by Jens Kallup
Post by m***@gmail.com
n*2^(n-1) - Sum((k-1)(n,)) = 32 - 17 = 15. Hier ist Sum((k-1)(n,k)) prim.
rechne nochmal
n=4
4*2^3-(6+8+3)=2^5-17=32-17=15
2^3 = 27 * 4 = 108

6 + 8 + 3 = 15

108 - 15 = 93


2^5 = 2 * 2 * 2 * 2 * 2 = 32

93 - 32 = 61

=> is prime
Jens Kallup
2020-08-02 20:57:55 UTC
Antworten
Permalink
Am 02.08.2020 um 22:49 schrieb Jens Kallup:

2^3 = 27 * 4 = 108

6 + 8 + 3     = 17

108 - 17      = 91

2^5 = 2 * 2 * 2 * 2 * 2 = 32

91 - 32 = 59
=> is prime
Jens Kallup
2020-08-02 21:00:19 UTC
Antworten
Permalink
Post by Jens Kallup
2^3 = 27 * 4 = 108
6 + 8 + 3     = 17
108 - 17      = 91
2^5 = 2 * 2 * 2 * 2 * 2 = 32
91 - 32 = 59
=> is prime
trotzdem wie kommst drauf?
wieso unterschiedliche Ergebnissummen?
m***@gmail.com
2020-08-02 21:13:02 UTC
Antworten
Permalink
Post by Jens Kallup
trotzdem wie kommst drauf?
wieso unterschiedliche Ergebnissummen?
Ich hatte die Assoziativität und Kommutativität von A+B+C bewiesen, indem ich A+B+C auf D_1+...+D_n vereinfacht hatte mit D_1,...,D_n paarweise disjunkt oder gleich. Mit n=3*2^(3-1). Und am Ende habe ich abgezählt, wie viele Teilmengen ich 2x, 3x, nx habe. Dabei bin ich zuerst darüber gestolpert, dass 2^n-1 Primzahlen enthält. Da bin erstmal total ausgeflippt, wofür ich mich heute noch schäme. Größenwahn eben. Und dann habe ich eben spekuliert, dass ich durch das Abzählen herausfinden kann, wann 2^n-1 prim ist. Ich würde mir den Arsch abbeißen wenn hält: entweder 2^n-1 oder Sum((k-1)(n,k)) ist prim. Probieren wir mal n=6:

6*2^5=3*2^6=3*64=192
15+40+45+24+5=129
192-129=92-29=72-9=63
m***@gmail.com
2020-08-02 21:14:38 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by Jens Kallup
trotzdem wie kommst drauf?
wieso unterschiedliche Ergebnissummen?
6*2^5=3*2^6=3*64=192
15+40+45+24+5=129
192-129=92-29=72-9=63
https://www.matheretter.de/rechner/primzahltest/

Weder 129 noch 63 sind prim
m***@gmail.com
2020-08-02 21:19:17 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by m***@gmail.com
6*2^5=3*2^6=3*64=192
15+40+45+24+5=129
192-129=92-29=72-9=63
https://www.matheretter.de/rechner/primzahltest/
Weder 129 noch 63 sind prim
n=5

5*16=80
10+20+15+4=49
80-49=31
Jens Kallup
2020-08-02 21:23:09 UTC
Antworten
Permalink
Post by m***@gmail.com
6*2^5=3*2^6=3*64=192
15+40+45+24+5=129
192-129=92-29=72-9=63
6 * 2 * 2 * 2 * 2 * 2 = 32 * 6 = 192
3 * 2 * 2 * 2 * 2 * 2 * 2 = 64 * 3 = 192

und nun?
geht es Dir im dieses 6 und 3 am Anfang?
Das sind 2 paar Schuhe, die vielleicht die
gleiche Größe haben, aber doch sehr abweichen.

Du hast einfach nur geraten, indem Du vom
1. Term das doppelte genommen hast und die 6
halbiert hast.
Das ist einfach nur ein Kreuzprodukt.

wie kommst an die anderen Zahlen?
m***@gmail.com
2020-08-02 21:37:12 UTC
Antworten
Permalink
Post by Jens Kallup
Du hast einfach nur geraten, indem Du vom
1. Term das doppelte genommen hast und die 6
halbiert hast.
Das ist einfach nur ein Kreuzprodukt.
Also nochmal von vorne. Wenn ich n Mengen habe, dann schneidet die 2. Menge die erste in 2 Mengen, die 3. schneidet diese beiden wieder jeweils in 2 Mengen, ..., d.h. die erste Menge wird in 2^(n-1) Teilmengen zerlegt. Und da das für alle n Mengen gilt und ich für meinen Beweis auch alle Menge verwende, habe ich n*2^(n-1) Terme.
Post by Jens Kallup
wie kommst an die anderen Zahlen?
Nun habe ich aber einige Mengen 2x gezählt, andere 3x, ..., nx.

Erstmal, wenn ich die erste, in 2^(n-1) Teilmengen zerlegte Menge aus dem Problem entferne, habe ich das gleiche Problem mit n-1 Mengen. Also ergibt sich die Zahl der "echten" Teilmengen zu Summe von 2^(k-1) für k=1..n, was bekanntlich 2^n-1 ist.

D.h. ich suche die Differenz von n*2^(n-1) und 2^n-1. Und das ist Abzählung. Da must Du ein bisschen fummeln und dann kommst Du auf Sum((k-1)*(n,k)).
m***@gmail.com
2020-08-02 21:46:49 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by Jens Kallup
Du hast einfach nur geraten, indem Du vom
1. Term das doppelte genommen hast und die 6
halbiert hast.
Das ist einfach nur ein Kreuzprodukt.
Also nochmal von vorne. Wenn ich n Mengen habe, dann schneidet die 2. Menge die erste in 2 Mengen, die 3. schneidet diese beiden wieder jeweils in 2 Mengen, ..., d.h. die erste Menge wird in 2^(n-1) Teilmengen zerlegt. Und da das für alle n Mengen gilt und ich für meinen Beweis auch alle Menge verwende, habe ich n*2^(n-1) Terme.
Post by Jens Kallup
wie kommst an die anderen Zahlen?
Nun habe ich aber einige Mengen 2x gezählt, andere 3x, ..., nx.
Erstmal, wenn ich die erste, in 2^(n-1) Teilmengen zerlegte Menge aus dem Problem entferne, habe ich das gleiche Problem mit n-1 Mengen. Also ergibt sich die Zahl der "echten" Teilmengen zu Summe von 2^(k-1) für k=1..n, was bekanntlich 2^n-1 ist.
D.h. ich suche die Differenz von n*2^(n-1) und 2^n-1. Und das ist Abzählung. Da must Du ein bisschen fummeln und dann kommst Du auf Sum((k-1)*(n,k)).
Bringt aber wie gesagt leider gar nichts. Da müsste man mit Sum((k-1)*(n,k)) weiterfummeln und versuchen irgendwas mit 2 oder n auszuklammern.
m***@gmail.com
2020-08-02 21:52:08 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by m***@gmail.com
Post by Jens Kallup
Du hast einfach nur geraten, indem Du vom
1. Term das doppelte genommen hast und die 6
halbiert hast.
Das ist einfach nur ein Kreuzprodukt.
Also nochmal von vorne. Wenn ich n Mengen habe, dann schneidet die 2. Menge die erste in 2 Mengen, die 3. schneidet diese beiden wieder jeweils in 2 Mengen, ..., d.h. die erste Menge wird in 2^(n-1) Teilmengen zerlegt. Und da das für alle n Mengen gilt und ich für meinen Beweis auch alle Menge verwende, habe ich n*2^(n-1) Terme.
Post by Jens Kallup
wie kommst an die anderen Zahlen?
Nun habe ich aber einige Mengen 2x gezählt, andere 3x, ..., nx.
Erstmal, wenn ich die erste, in 2^(n-1) Teilmengen zerlegte Menge aus dem Problem entferne, habe ich das gleiche Problem mit n-1 Mengen. Also ergibt sich die Zahl der "echten" Teilmengen zu Summe von 2^(k-1) für k=1..n, was bekanntlich 2^n-1 ist.
D.h. ich suche die Differenz von n*2^(n-1) und 2^n-1. Und das ist Abzählung. Da must Du ein bisschen fummeln und dann kommst Du auf Sum((k-1)*(n,k)).
Bringt aber wie gesagt leider gar nichts. Da müsste man mit Sum((k-1)*(n,k)) weiterfummeln und versuchen irgendwas mit 2 oder n auszuklammern.
...was wiederum bei n=4 ja nicht funktioniert, weil Sum((k-1),(n,))=17. Also nix ausklammern und trotzdem kein prim, aber dafür selbst prim. Vielleicht geht da noch was.
m***@gmail.com
2020-08-02 22:03:21 UTC
Antworten
Permalink
Post by m***@gmail.com
...was wiederum bei n=4 ja nicht funktioniert, weil Sum((k-1),(n,))=17. Also nix ausklammern und trotzdem kein prim, aber dafür selbst prim. Vielleicht geht da noch was.
Jetzt wieder bei n=6:

Sum((k-1)*(n,k))=129=3*43

3*2=6. Hier also doch ausklammern. Aber wie?
m***@gmail.com
2020-08-03 14:37:37 UTC
Antworten
Permalink
Post by Alfred Flaßhaar
harte ungelöste Brocken.
An dieser Stelle will jetzt nochmal Werbung für einen in 8 Jahre gelösten harten Brocken mit einem dynamischen Programm 3. Ordnung, negativen und positiven endlich kodierten überabzählbar großen Mengen und einem Prozessor mit 24 CPUs und 64 GB Arbeitsspeicher machen. Wen SIE tatsächlich 10 Minuten und 24 Sekunden Zeit haben, würde ich allerdings empfehlen, den Lautsprecher stumm zu schalten.


Alfred Flaßhaar
2020-08-03 15:17:11 UTC
Antworten
Permalink
Post by m***@gmail.com
Post by Alfred Flaßhaar
harte ungelöste Brocken.
An dieser Stelle will jetzt nochmal Werbung für einen in 8 Jahre gelösten harten Brocken mit einem dynamischen Programm 3. Ordnung, negativen und positiven endlich kodierten überabzählbar großen Mengen und einem Prozessor mit 24 CPUs und 64 GB Arbeitsspeicher machen. Wen SIE tatsächlich 10 Minuten und 24 Sekunden Zeit haben, würde ich allerdings empfehlen, den Lautsprecher stumm zu schalten.
http://youtu.be/87emAiYEIig
Wäre gut, wenn Du zu "input" und "output" (Ziel der Aufgabe) etwas
gesagt hättest. Welche praktischen Anwendungen sind beabsichtigt?
Ansonsten ist die Generierung und Manipulation verzweigter Polygone
nicht neu (Netzgeneratoren der FEM, auch räumliche Netze). Musik geht,
bin aus der Verwandtschaft härtere Sachen gewöhnt.

Gruß, Alfred Flaßhaar
m***@gmail.com
2020-08-04 12:51:21 UTC
Antworten
Permalink
Post by Alfred Flaßhaar
Wäre gut, wenn Du zu "input" und "output" (Ziel der Aufgabe) etwas
gesagt hättest. Welche praktischen Anwendungen sind beabsichtigt?
Ansonsten ist die Generierung und Manipulation verzweigter Polygone
nicht neu (Netzgeneratoren der FEM, auch räumliche Netze). Musik geht,
bin aus der Verwandtschaft härtere Sachen gewöhnt.
Das ist Polygonmatching und kann zur Symmetrieerkennung in GIS Polygonlayern, speziell Gebäudeumrissen, eingesetzt werden.

Einen effizienten Primzahltest habe ich mittlerweile gefunden:

Summe über x(n,k) von k=k_0...n schreibe ich als Sum(k_0)(x)
"n über k" schreibe ich als (n,k)

p ist Primzahl, wenn
(i) Sum(p-2)(p-1,p-2)=p oder alternativ auch
(ii) Sum(p-3)((k-p-1)*(p-2,p-3))=p

Es sind jeweils nur zweimal "n über k" zu addieren. Wahrscheinlich steht das aber alles schon auf Wikipedia. Wenn ich mir die Rechner der Leute ansehe, die die Rekordprimzahlen gefunden habe, wundert mich gar nichts mehr.
Loading...