Carmichael Zahlen (Visualisierung und lückenlose Erzeugung)
-
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.