|
Autor |
Letzte Stellen sehr großer Zahlen auf Richtigkeit überprüfen |
|
hyperG
Senior  Dabei seit: 03.02.2017 Mitteilungen: 1681
 | Themenstart: 2022-01-28
|
In einem anderen Beitrag hatte ich ja gezeigt, wie man die letzte Stelle sehr großer Bell-Zahlen überprüfen kann.
Sobald ich aber mehr als die eine letzte überprüfen will, wird es kompliziert.
Bei GroßeZahl Mod (10^n)
sieht man sofort, dass man damit die letzten n Stellen bekommt.
Wie sieht es aber mit n=Primzahl
\sourceon nameDerSprache
GroßeZahl Mod (Primzahl) = Konstante
kurz: G mod p = K
\sourceoff
aus?
Zunächst dachte ich an " eine neben 10^n" also z.B. p=101,
aber wenn K =5, dann bekommt man lauter unterschiedliche "mögliche letzte Stellen":
101106,101207,101308,101409,101510,...
die Mod 101 eine 5 ergeben.
Frage: gibt es besonders günstige Kombinationen aus Primzahl und Konst.,
um sofort Aussagen zu den letzten n Dezimalstellen tätigen zu können?
Ziel ist möglich großes n (viele richtige Stellen zu finden).
Natürlich könnte man mehrere Kombinationen aus {p,K} sammeln, um dann Rückschlüsse auf die letzten Ziffern zu ziehen -> kann beliebig kompliziert werden...
Ich suche aber eine sehr einfache...
Und dabei muss G beliebig sein! Also keine Sonderfälle aus G,p,K
sondern nur Sonderfälle aus {p,K}.
Grüße
|
Profil
|
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 3545
 | Beitrag No.1, eingetragen 2022-01-28
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Hallo,
wenn $p$ eine zu $10$ teilerfremde Primzahl ist, dann gibt es nach dem chinesischen Restsatz für alle $K,L,m,n\in \IN$ eine Zahl $G\in \IZ$ mit $G\equiv K \pmod {p^m}$ und $G\equiv L \pmod {10^n}$.
Man kann also aus dem Rest von $G$ modulo $p^m$ keine Rückschlüsse auf die letzten $n$ Dezimalstellen von $G$ ziehen.\(\endgroup\)
|
Profil
|
DavidM
Senior  Dabei seit: 11.06.2012 Mitteilungen: 396
 | Beitrag No.2, eingetragen 2022-01-28
|
Hallo hyperG,
wenn ich dich richtig verstehe, dann funktioniert das, was du willst, nicht. Wenn $p$ eine beliebige Primzahl außer 2 und 5 ist und $K$ irgendeine natürliche Zahl kleiner als $p$, dann gibt es zu jeder beliebigen Folge von $n$ letzten Ziffern immer eine Zahl $G$, sodass der Rest von $G$ modulo $p$ gerade $K$ ist und $G$ diese Folge von letzten Ziffern hat. Das gilt für alle $n$, $K$ und $p$ (außer, wie gesagt, $p=2$ und $p=5$). Letztlich ist das einfach eine Folgerung aus dem chinesischen Restsatz.
Gruß,
David
[Die Antwort wurde vor Beitrag No.1 begonnen.]
|
Profil
|
pzktupel
Aktiv  Dabei seit: 02.09.2017 Mitteilungen: 2180
Wohnort: Thüringen
 | Beitrag No.3, eingetragen 2022-01-28
|
Äh, da fällt mir vielleicht was dazu ein.
Man könnte den ganzen String zum Bsp. in 7er Blöcke von rechts nach links splitten und die addieren.
Die Summe macht man dann MOD 239 oder MOD 4649, die Primfaktoren von 9999999 oder eben 1111111.
Also 98174891741 MOD 239 = 146
9817+4891741=4901558
4901558 MOD 239 = 146
Selbige mit 4649 -> 1512
Einen anderen Check sehe ich jetzt mit Primzahlen nicht.
Merke, das passt nicht zum Problem...🤔
Als spielerei vielleicht noch...
98174891741 , schneide 2 Stellen ab:
98+1748917 = MOD 239 = 13
13*100-146 von oben =1154
1154 MOD 239=198
239-198=41 waren beide letzten Stellen.
|
Profil
|
hyperG
Senior  Dabei seit: 03.02.2017 Mitteilungen: 1681
 | Beitrag No.4, vom Themenstarter, eingetragen 2022-01-28
|
\quoteon(2022-01-28 17:28 - Nuramon in Beitrag No. 1)
... keine Rückschlüsse auf die letzten $n$ Dezimalstellen von $G$ ziehen.
\quoteoff
Ja, das mit 1 Primzahl nur die letzte Stelle, jedoch nicht mehr, das hatte ich ja schon geschrieben.
Mir geht es aber um Kombinationen {p,K}
also p1=10^17-3
p2=10^17+3
Wenn man dann das Modulo-Ergebnis nochmals Modulo 10^4 nimmt, bekommt man doch mehr Informationen:
https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Modulo_vorletzteStellen.png
Also etwa in der Art:
Wenn das Modulo-Ergebnis nochmals Modulo 10^4 bei 10^17-3 genau 6 und bei p2=10^17+3 dann 0 ist, müssten die letzten 3 Stellen von G "003" lauten...
Nachsatz: also "führende Nullen" + "Mittelwert der beiden Modulo 10^4 Ergebnisse", wobei die "10^nochmaligeMod" kleiner als das aktuelle p sein muss... und das erste Ergebnis (vorletzte Spalte) größer als letzte Spalte sein muss.
[Die Antwort wurde nach Beitrag No.1 begonnen.]
|
Profil
|
Nuramon
Senior  Dabei seit: 23.01.2008 Mitteilungen: 3545
 | Beitrag No.5, eingetragen 2022-01-28
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}
\newcommand\ceil[1]{\left\lceil #1 \right\rceil}
\newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)
Wenn man von einer Zahl $G$ nur die Reste $r_i := mod(G, p_i)$ für $i=1,...,m$ und Primzahlen $p_1,\ldots, p_m \notin\{2,5\}$ kennt, dann kann man keine Aussage über die Dezimalziffern von $G$ treffen (wegen des chinesischen Restsatzes).
Wenn man von $G$ sogar nur die Reste $r_i':= mod(r_i, 10^4)$ kennt, dann weiß man ja sogar noch weniger über $G$, also kann man mit diesen iterierten Resten erst recht keine Aussage treffen.\(\endgroup\)
|
Profil
|
hyperG
Senior  Dabei seit: 03.02.2017 Mitteilungen: 1681
 | Beitrag No.6, vom Themenstarter, eingetragen 2022-01-28
|
Es sah zunächst bis 31stellig so gut aus:
https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Modulo_vorletzteStellen2.png
Aber später kommen die befürchteten "unbestimmten Fälle"...
Würde ein weiterer p3 helfen, um Sonderfälle zu finden?
Oder welche Randbedingungen muss man noch herausfiltern (was ich mit "?" ausgeben würde)?
|
Profil
|
hyperG
Senior  Dabei seit: 03.02.2017 Mitteilungen: 1681
 | Beitrag No.7, vom Themenstarter, eingetragen 2022-01-28
|
Dass mit p={2 oder 5} bei nur 1 letzten Stelle sehe ich nun ein.
Wenn G nun in Hexadezimalform vorliegt,
müsste man doch mehr herausbekommen, denn
mod 13 entspricht mod 0D
die letzte Hex-Stelle von G kann dann nur zw. 0...0C liegen...
zwar keine "vollen 2 Dezimalstellen", aber doch etwas mehr Info beim Vergleich zweier großen G1 & G2.
|
Profil
|
pzktupel
Aktiv  Dabei seit: 02.09.2017 Mitteilungen: 2180
Wohnort: Thüringen
 | Beitrag No.8, eingetragen 2022-01-28
|
Sowas brauchbar ?
N=123456789
M=(N MOD 99999)-1234 = 56789 ?
oder
N=279837124191341 MOD 9999999999 - 27983 = 7124191341
|
Profil
|
hyperG
Senior  Dabei seit: 03.02.2017 Mitteilungen: 1681
 | Beitrag No.9, vom Themenstarter, eingetragen 2022-01-28
|
\quoteon(2022-01-28 19:39 - pzktupel in Beitrag No. 8)
Sowas brauchbar ?
...
M=(N MOD 99999)...
... MOD 9999999999
...
\quoteoff
Nein, da weder 99999 noch 9999999999 Primzahlen sind.
Leider scheint die Idee mit anderer Basis natürlich nichts zu bringen, da die Modulo-Funktion unabhängig von der Basis funktioniert. Bei String-Funktionen ist das was anderes.
Ich dachte nur, weil die BBP-Algorithmen für Pi ja auch nur mit Basis 2^n funktionieren...wo man dann einzelne Stellen "dieser anderen Basis" herauspicken kann.
|
Profil
|
hyperG hat die Antworten auf ihre/seine Frage gesehen. |
|
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]
|