Modulo einer Potenz aus reeller Basis und ganzzahligem Exponenten

01.01.2025, 15:36

Torsten_Straeter

Modulo einer Potenz aus reeller Basis und ganzzahligem Exponenten

Meine Frage:
Gegeben sei eine reelle Zahl a (als Basis), eine ganze Zahl e (als Exponent) sowie eine ganze Zahl m (als Modulus).
Gesucht ist floor(a^e) mod m.

Meine Ideen:
Sofern e kleinere Werte annimmt, sehe ich keine Probleme, die Aufgabe mit bspw. Python oder auch Mathematica zu lösen. Wenn der Exponent e aber in Sphären > 10^7 gelangt, wird es schwierig.
Z. B. floor((3,7253526)^135792468) mod 100000007
Ich hatte überlegt, ob ich die Potenz mit einem Logarithmus bearbeite, kam allerdings nicht wirklich weiter.

01.01.2025, 19:47

HAL 9000

Auf diesen Beitrag antworten »

Mit Logarithmen kann man in etwa abschätzen, welche Genauigkeit man für die Floating-Point-Rechnung benötigt, damit das ganze überhaupt funktionieren kann:

Es ist $\begin{eqnarray*} 3,7253526^{135\,792\,468} = 2^{135\,792\,468\cdot \log_2(3,7253526)}\approx 2^{257\,649\,503} \end{eqnarray*}$ , d.h. man benötigt mindestens $\begin{eqnarray*} 257\,649\,503 \end{eqnarray*}$ Bit Mantisse für die Floatingpointrechnung - hübsch anspruchsvoll. Augenzwinkern

Die ganzen Mechanismen, welche bekanntermaßen bei $\begin{eqnarray*} a^e\bmod m \end{eqnarray*}$ mit ganzzahligen (!) Basen $\begin{eqnarray*} a \end{eqnarray*}$ greifen, kann man hier weitestgehend vergessen. Selbst wenn $\begin{eqnarray*} a \end{eqnarray*}$ rational ist mit $\begin{eqnarray*} a=\frac{p}{q} \end{eqnarray*}$ , so kann man bei der Bestimmung von

$\begin{eqnarray*} \left\lfloor \left(\frac{p}{q}\right)^e \right\rfloor \bmod m \end{eqnarray*}$

das ganze allenfalls auf $\begin{eqnarray*} p^e \bmod \left(m\cdot q^e\right) \end{eqnarray*}$ zurückführen, was einem wohl so gut wie gar nichts nützt.

Erklär doch mal, in welchem Zusammenhang dir diese ziemlich seltsame Problemstellung begegnet ist.

01.01.2025, 20:10

Torsten_Straeter

Auf diesen Beitrag antworten »

Gefragt, gejagt. Mein Bruder hatte die Frage über Weihnachten aufgeworfen. Ich habe jetzt nochmal nachgehakt. Er meinte, es gibt wohl bei Projekt Euler (ja, ich weiß...) die Problemstellung, dass zu einer kubischen Gleichung die Nullstellen gefunden werden sollen. Die Lösung stellt dann die Basis (siehe oben) dar, der Exponent ist ziemlich groß und der ganzzahlige Teil der Potenz soll dann per modulo reduziert werden.
Falls Interesse besteht, kann ich sicher auch den Index des Problems herausfinden.

01.01.2025, 20:14

HAL 9000

Auf diesen Beitrag antworten »

Du meinst aber nicht https://projecteuler.net/problem=251 ? Das war vor langer Zeit mal hier im Forum aufgeschlagen...

EDIT: Vermutlich meinst du https://projecteuler.net/minimal=324. Hast du denn eine Rekursionsgleichung für dieses $\begin{eqnarray*} f(n) \end{eqnarray*}$ dort aufstellen können? Ich denke, hier über Potenzen reeller Zahlen mit gigantischem Exponenten zum Ziel kommen zu wollen, ist ein Irrweg.

02.01.2025, 02:58

Torsten_Straeter

Auf diesen Beitrag antworten »

Guten Morgen, es soll sich um Nr. 356 handeln. Wie es sich liest, ist eine Funktion gegeben, zu der die größte Nullstelle gesucht wird. Die bildet dann den reellen Wert der Basis und soll potenziert und die Potenz danach reduziert werden.

02.01.2025, 14:14

Torsten_Straeter

Auf diesen Beitrag antworten »

Als Zusatz.... Ich hatte überlegt, ob man die Lösung über das Newton Raphson Verfahren annähern könnte, zum Beispiel in Python als Bruch, und dann bestmöglich zu berechnen. Die Zahlen dürften aber auch hier einiges groß werden. Auch finde ich fraglich, ob die Genauigkeit ausreicht.

15.05.2025, 20:31

HAL 9000

Auf diesen Beitrag antworten »

Auch wenn nun schon über vier Monate ins Land gegangen sind, und der Fragesteller sich wohl nicht wieder blicken lassen wird:

Ich hab mir dieses Problem 356 jetzt mal richtig angesehen, und es ist wie bei vielen anderen dieser Eulerprojekt-Probleme: Man muss erstmal einiges an Überlegung investieren, um mit diesen Vorabeiten am Ende dann doch auch noch einiges rechnen (ohne Computerunterstützung hoffnungslos).

Im vorliegenden Fall resultiert das am Ende in reinen Integerrechnungen, was meine obige Einschätzung

Zitat:

Original von HAL 9000
Ich denke, hier über Potenzen reeller Zahlen mit gigantischem Exponenten zum Ziel kommen zu wollen, ist ein Irrweg.

bestätigt.

Zitat:

Eulerprojekt Problem 356

Sei $\begin{eqnarray*} a_n \end{eqnarray*}$ die größte reelle Nullstelle der kubischen Polynomfunktion $\begin{eqnarray*} g(x)=x^3-2^n\cdot x^2+n \end{eqnarray*}$ .

Man bestimme die letzten 8 Dezimalstellen von $\begin{eqnarray*} \sum_{n=1}^{30} \left\lfloor a_n^{987\,654\,321} \right\rfloor \end{eqnarray*}$ .

Abschnitt 1) Sei $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ zunächst fest gewählt.

Abschnitt 1.1) Wir diskutieren als erstes die Nullstellen von $\begin{eqnarray*} g \end{eqnarray*}$ :

Im Fall $\begin{eqnarray*} n=1 \end{eqnarray*}$ haben wir $\begin{eqnarray*} g(x)=x^3-2x^2+1 = (x-1)\left(x^2-x-1\right) \end{eqnarray*}$ mit den drei reellen Nullstellen $\begin{eqnarray*} \frac{1-\sqrt{5}}{2},1,\frac{1+\sqrt{5}}{2} \end{eqnarray*}$ . Für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ gilt

$\begin{eqnarray*} g(-1) = -1 - 2^n + n < 0 \end{eqnarray*}$
$\begin{eqnarray*} g(0) = n > 0 \end{eqnarray*}$
$\begin{eqnarray*} g(1) = 1 - 2^n + n < 0 \end{eqnarray*}$
$\begin{eqnarray*} g\left(2^n-1\right) = -\left(2^n-1\right)^2 + n < 0 \end{eqnarray*}$
$\begin{eqnarray*} g\left(2^n\right) = n > 0 \end{eqnarray*}$

Unter Anwendung des Zwischenwertsatzes für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ sowie Einbeziehung des Spezialfalls $\begin{eqnarray*} n=1 \end{eqnarray*}$ gilt demnach für alle $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ folgendes:

$\begin{eqnarray*} g \end{eqnarray*}$ besitzt genau drei reelle Nullstellen, und zwar $\begin{eqnarray*} x_1\in (-1,0) \end{eqnarray*}$ , $\begin{eqnarray*} x_2\in (0,1] \end{eqnarray*}$ sowie $\begin{eqnarray*} x_3\in\left(2^n-1,2^n\right) \end{eqnarray*}$ .

Darüber hinaus lässt sich noch feststellen, dass wegen Vieta $\begin{eqnarray*} x_1+x_2+x_3=2^n \end{eqnarray*}$ die Ungleichung $\begin{eqnarray*} 0 < 2^n-x_3 = x_1+x_2 \end{eqnarray*}$ gefolgert werden kann, und damit $\begin{eqnarray*} \left|x_1\right| = -x_1 < x_2\leq 1 \end{eqnarray*}$ .

Abschnitt 1.2) Befassen wir uns nun mit den Potenzen einer solchen Nullstelle $\begin{eqnarray*} x\in \left\{x_1,x_2,x_3\right\} \end{eqnarray*}$ :

Durch sukzessives Anwenden von $\begin{eqnarray*} x^3 = 2^nx^2-n \end{eqnarray*}$ kann man jede Potenz $\begin{eqnarray*} x^k \end{eqnarray*}$ darstellen als Linearkombination (mit ganzzahligen Faktoren) von $\begin{eqnarray*} 1,x,x^2 \end{eqnarray*}$ .

Das kann man formalisieren als Skalarprodukt $\begin{eqnarray*} x^k = \left(1,x,x^2\right)\cdot v_k \end{eqnarray*}$ mit $\begin{eqnarray*} v_k\in\mathbb{Z}^3 \end{eqnarray*}$ . Start ist offenbar $\begin{eqnarray*} v_0 = \begin{pmatrix}1\\ 0\\ 0\end{pmatrix} \end{eqnarray*}$ , und für die Iteration betrachtet man $\begin{eqnarray*} x^{k+1} = \left(x,x^2,x^3\right)\cdot v_k = \left(x,x^2,2^nx^2-n\right)\cdot v_k \stackrel{!}{=} \left(1,x,x^2\right)\cdot T_n\cdot v_k \end{eqnarray*}$ bei Wahl von Matrix $\begin{eqnarray*} T_n = \begin{pmatrix} 0 & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 2^n\end{pmatrix} \end{eqnarray*}$ .

Damit haben wir $\begin{eqnarray*} v_{k+1} = T_n\cdot v_k \end{eqnarray*}$ bzw. explizit $\begin{eqnarray*} v_k = T_n^k\cdot v_0 \end{eqnarray*}$ .

Abschnitt 1.3) Es gilt also einzeln $\begin{eqnarray*} x_j^k = \left(1,x_j,x_j^2\right)\cdot T_n^k\cdot v_0 \end{eqnarray*}$ für $\begin{eqnarray*} j=1,2,3 \end{eqnarray*}$ , was in der Summe $\begin{eqnarray*} x_1^k + x_2^k + x_3^k = \left(3,x_1+x_2+x_3,x_1^2+x_2^2+x_3^2\right)\cdot T_n^k\cdot v_0 \end{eqnarray*}$ bedeutet.

Nun wissen wir aber laut Vieta $\begin{eqnarray*} x_1+x_2+x_3 = 2^n \end{eqnarray*}$ sowie auch $\begin{eqnarray*} x_1x_2+x_1x_3+x_2x_3=0 \end{eqnarray*}$ , beides zusammen bewirkt

$\begin{eqnarray*} x_1^2+x_2^2+x_3^2 = \left(x_1+x_2+x_3\right)^2 - 2\left(x_1x_2+x_1x_3+x_2x_3\right) = 2^{2n} \end{eqnarray*}$ .

Damit haben wir als Potenzsumme $\begin{eqnarray*} x_1^k + x_2^k + x_3^k = \left(3,2^n,2^{2n}\right)\cdot T_n^k\cdot v_0 \end{eqnarray*}$ eine ganze (!) Zahl. Nun erinnern wir uns dran, dass die größte Nullstelle $\begin{eqnarray*} x_3 \end{eqnarray*}$ das $\begin{eqnarray*} a_n \end{eqnarray*}$ aus der Problemstellung ist, außerdem gilt für ungerade Exponenten $\begin{eqnarray*} k \end{eqnarray*}$ die Ungleichung $\begin{eqnarray*} 0 < -x_1^k = \left| x_1\right|^k < x_2^k \leq 1 \end{eqnarray*}$ , das bedeutet $\begin{eqnarray*} 0 < x_1^k + x_2^k < 1 \end{eqnarray*}$ . Für $\begin{eqnarray*} a_n^k = \left(3,2^n,2^{2n}\right)\cdot T_n^k\cdot v_0 - \left(x_1^k + x_2^k\right) \end{eqnarray*}$ bedeutet letzteres bei Anwendung der Gaußklammer schlussendlich

$\begin{eqnarray*} \left\lfloor a_n^k \right\rfloor = \left(3,2^n,2^{2n}\right)\cdot T_n^k\cdot v_0 - 1 \end{eqnarray*}$ ,

und ja, rechts steht ein Term, der durch reine Integerarithmetik ermittelt werden kann.

Abschnitt 2) Wir wollen nun für $\begin{eqnarray*} k=987\,654\,321 \end{eqnarray*}$ die letzten 8 Dezimalstellen der nunmehr so schreibbaren Summe

$\begin{eqnarray*} \sum_{n=1}^{30} \left\lfloor a_n^k \right\rfloor = \sum_{n=1}^{30} \left[ \left(3,2^n,2^{2n}\right)\cdot T_n^k\cdot \begin{pmatrix}1\\ 0\\ 0\end{pmatrix} - 1\right]\qquad (*) \end{eqnarray*}$

bestimmen. Dieses $\begin{eqnarray*} T_n^k \end{eqnarray*}$ enthält exorbitant große ganze Zahlen, aber mit Modul $\begin{eqnarray*} M = 10^8 \end{eqnarray*}$ (für die letzten 8 Dezimalstellen) kann man ja bei der Berechnung nutzen

$\begin{eqnarray*} T_n^{k_1+k_2}\bmod M = \left( \left( T_n^{k_1}\bmod M\right)\cdot \left( T_n^{k_2}\bmod M\right) \right) \bmod M \end{eqnarray*}$

und kann somit effizient in maximal $\begin{eqnarray*} 2\left\lceil \log_2(k)\right\rceil \end{eqnarray*}$ Matrixmultiplikationsschritten der Dimension $\begin{eqnarray*} 3\times 3 \end{eqnarray*}$ und mit ganzzahligen Einträgen in $\begin{eqnarray*} [0,\ldots,M) \end{eqnarray*}$ die Matrix $\begin{eqnarray*} T_n^k\bmod M \end{eqnarray*}$ berechnen - bei unserem $\begin{eqnarray*} k \end{eqnarray*}$ sind übrigens exakt 47 solche Schritte. Damit ist die Berechnung von (*) modulo $\begin{eqnarray*} M \end{eqnarray*}$ auf halbwegs aktuellen PC in Sekundenbruchteilen zu bewältigen, selbst mit einem Python-Programm (Interpreter).

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

import numpy as np

def matrix_power_mod(A, exponent, modul):
    B = np.identity(A.shape[0], dtype = A.dtype)
    while True:
        if exponent & 1:
            B = np.dot(B, A) % modul
        exponent //= 2
        if exponent == 0:
            break
        A = np.dot(A, A) % modul
    return B        

def root_power_floor(n, exponent, modul):
    pow2 = (1 << n) % modul
    A = np.array([[0,0,-n],[1,0,0],[0,1,pow2]], dtype = np.int64)
    Ae = matrix_power_mod(A, exponent, modul)
    pow4 = (pow2 * pow2) % modul
    return (3 * Ae[0][0] + pow2 * Ae[1][0] + pow4 * Ae[2][0] - 1) % modul
            
if __name__ == '__main__':
    modul = 10**8
    digits = sum(root_power_floor(n, 987654321, modul) for n in range(1, 31)) % modul
    print(digits)

Neue Frage »

Antworten »

Modulo einer Potenz aus reeller Basis und ganzzahligem Exponenten

Verwandte Themen