Carmichael Zahlen (Visualisierung und lückenlose Erzeugung)
-
volkard schrieb:
Erhard Henkes schrieb:
Wir rechnen hier (19 ^ 1000000) % 19. Da wäre uint64_t schnell out_of_range.
Quatsch. Das ist doch der Trick an PowMod
Ja, Du hast recht, aber das powm von GMP ist echt schnell. Kannst es ja mal mit deinem vergleichen.
-
Erhard Henkes schrieb:
volkard schrieb:
Erhard Henkes schrieb:
Wir rechnen hier (19 ^ 1000000) % 19. Da wäre uint64_t schnell out_of_range.
Quatsch. Das ist doch der Trick an PowMod
Ja, Du hast recht, aber das powm von GMP ist echt schnell. Kannst es ja mal mit deinem vergleichen.
Oder besser...
997633 passt ja auch gut tausendmal in einen uint32_t.
Falls Du noch kein schnelles mulmod64 hast, ein schnelles mulmod32 wäre return uint64(a)*b;. Könnte mir vorstellen, daß es 100-mal so schnell davon wird.
-
Mit a^1000000 mod b = a^(1000000 mod b) mod b und b<=19 passen alle Zwischenresultate in einen 64-Bit-Integer und du musst nur einmal am Schluss modulo rechnen.
-
Erhard Henkes schrieb:
Zuerst mal vielen Dank an alle, die hier bei diesem staubtrockenen Thema konstruktiv mitmischen! Keine Ahnung, warum mich diese Sachen als Nicht-Mathematiker faszinieren.
Quatsch Zahlentheorie ist gleich nach der Algebra das schönste was es gibt
-
Ich habe es mit diesem Programm (auf Wunsch mit <chrono>
) bis 10^7 probiert: http://codepad.org/oK7tLmv6... und schon wieder zwei neue "Lügner": 5968873 und 9699690
a = 2 ... 19 reicht da also schon wieder nicht. Für diesen Zahlenbereich muss man den range von a erweitern. Bei a = 2 ... 29 verschwindet 9699690, aber die 5968873 bleibt. Ich denke, die hat man auf https://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Carmichael-Zahlen schlicht vergessen (43*127*1093 = 5968873). https://de.numberworld.info/5968873
Hier steht sie dabei: http://oeis.org/A097061/internal
Nobody is perfect. Ich ergänze die dort mal in diesem wikibook.
Endlich mal ein nützliches Resultat.9699690 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 <== finde ich auch bewundernswert. hat aber keinen Namen, soweit ich das weiß.
EDIT: "The p-primorial is the product of all primes less than or equal to p. It is sometimes denoted by p#. ... First ten: 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230" ( http://www.numbergossip.com/list )
-
@Bengo: Habe ich das so richtig verstanden bei Dir?
a=2 ... p ?
for (mpz_class a = 2; a <= p; ++a)Da dauert der Programmlauf ewig. Völlig indiskutabel.
Carmichael Numbers: 561 time: 122 ms 1105 time: 474 ms 1729 time: 1162 ms 2465 time: 2359 ms 2821 time: 3100 ms 6601 time: 16911 ms 8911 time: 30719 ms 10585 time: 43505 ms 15841 time: 97253 ms
-
Die Primzahlen von 2 bis zur Carmichael-Zahl reichen, wie bereits gesagt (und wenn nicht 1 rauskommt, dann prüfen ob die Zahl Teiler von Carmichael-Zahl ist, die Sache mit dem ggT kann man sich dann auch komplett sparen). Wenn du es nicht machst, kannst du Lügner aber nie ausschließen
-
Irgendetwas machst du grundsätzlich falsch...
https://ideone.com/eZX8Kr
-
@selfistheman: Danke für den Nachweis.
-
int gcd(int a, int b) { return !b ? a : gcd(b, a%b); }Sowas versaut einem doch den ganzen Tag.
-
Du brauchst nicht mal die gdc-Funktion (Ich hab es schon 2 bis 3 mal hier geschrieben, du musst nicht vorher auf teilerfremd prüfen, es reicht wenn nachher nicht 1 rauskommt, zu prüfen ob die Zahl teilerfremd ist. Wenn du nur Primzahlen testest, ist das äquivalent dazu, dass die Primzahl ein Teiler ist), und wenn du ihn doch brauchen wilst, solltest du den euklidischen Algo auch richtig implementieren.
Ich geb dir mal ein Zahlenbeispiel:
117 113:
117 = 1 * 113 + 4
113 = 28 * 4 + 1
4 = 4 * 1 + 0
Er endet wenn 0 rauskommt, und der Rest der vorletzen Zeile ist der ggT. Du bruachst also nicht nur den Rest, sondern auch den ganzahligen Anteil der Zahl.