Mathematik zum Wochenende – Lösung der Zusatzaufgabe

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Zusatzaufgabe: Welche Ziffer steht als nächstes vor den Nullen?

Ich hab ewig nach einer klugen Lösung gesucht – mir ist nur keine eingefallen. Also mit brutaler Kraft die Exponenten aller Primfaktoren von 2019! ermittelt – genauso wie für die 5en:

$$\sum_{k=1}^\infty \lfloor \tfrac{2019}{5^k}\rfloor$$

Wegen 5⁵ = 3125 > 2019 kann man bei k = 4 aufhören:

$$\sum_{k=1}^4 \lfloor \tfrac{2019}{5^k} \rfloor = \lfloor \tfrac{2019}{5} \rfloor + \lfloor \tfrac{2019}{25} \rfloor + \lfloor \tfrac{2019}{125} \rfloor + \lfloor \tfrac{2019}{625} \rfloor$$

$$\sum_{k=1}^\infty \lfloor \tfrac{2019}{2^k}\rfloor = \sum_{k=1}^{10} \lfloor \tfrac{2019}{2^k}\rfloor = \lfloor \tfrac{2019}{2} \rfloor + \lfloor \tfrac{2019}{4} \rfloor + \lfloor \tfrac{2019}{8} \rfloor + \cdots + \lfloor \tfrac{2019}{1024} \rfloor$$

$$\sum_{k=1}^\infty \lfloor \tfrac{2019}{3^k}\rfloor = \sum_{k=1}^6 \lfloor \tfrac{2019}{3^k}\rfloor = \lfloor \tfrac{2019}{3} \rfloor + \lfloor \tfrac{2019}{9} \rfloor + \lfloor \tfrac{2019}{27} \rfloor + \cdots + \lfloor \tfrac{2019}{729} \rfloor$$

Die Exponenten auszurechnen kann ein Script besser (Codepen):

const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 2017];

const exponents = primes.map(prime => {
	let sum = 0;
	
	for (let denominator = prime; denominator <= 2019; denominator *= prime)
	{
		sum += Math.floor(2019/denominator);
	}
	
	return sum;
});

console.log(exponents); // [2011, 1005, 502, 334, 200, 166, 124, 111, 90, 71, ...]

Die Primfaktoren von 2019! sind also:

$$2019! = 2^{2011} \cdot 3^{1005} \cdot 5^{502} \cdot 7^{334} \cdot 11^{200} \cdot 13^{166} \cdot 17^{124} \cdot 19^{111} \cdot 23^{90} \cdot 29^{71} \cdot \dotsc \cdot 2017$$

Sei s die Zahl, die übrig bleibt, wenn man bei 2019! rechts die 502 Nullen abtrennt. Wir suchen nun die letzte Stelle von s.

$$\begin{align} s = \frac{2019!}{10^{502}} = 2^{2011-502} &\cdot 3^{1005} \cdot 7^{334} \cdot 11^{200} \cdot 13^{166} \cdot 17^{124} \cdot 19^{111} \cdot 23^{90} \cdot 29^{71} \cdot \dotsc \cdot 2017
\equiv 2^{1509} &\cdot 3^{1005} \cdot 7^{334} \cdot \ \ 1^{200} \cdot \ \ 3^{166} \cdot \ \ 7^{124} \cdot \ \ 9^{111} \cdot \ \ 3^{90} \cdot \ \ 9^{71} \cdot \dotsc \cdot \ \ \ \ \ \ 7 \mod 10
\equiv 2^{1509} &\cdot 3^{1005 + 166 + 90 + \dotsc} \cdot 7^{334 + 124 + \dotsc} \cdot 9^{111 + 71 + \dotsc} \mod 10 \end{align}$$

Die auf 1 endenden Primfaktoren haben keinen Einfluss auf die letzte Stelle von s. Das Zusammenzählen der Exponenten der auf 3, 7 bzw. 9 endenden Primfaktoren kann das Script wieder besser:

let exp3 = 0, exp7 = 0, exp9 = 0;

primes.forEach((prime, index) => {
	const primeString = prime.toString();
	if      (primeString.endsWith('3')) exp3 += exponents[index];
	else if (primeString.endsWith('7')) exp7 += exponents[index];
	else if (primeString.endsWith('9')) exp9 += exponents[index];
});

console.log(exp3, exp7, exp9); // 1618 835 467

$$\begin{align} s &\equiv 2^{1509} \cdot 3^{1618} \cdot 7^{835} \cdot 9^{467}\mod 10
\end{align}$$

Die 2er-Potenzen enden auf 2, 4, 8, 6, 2, … – ein Zyklus der Länge 4.
Die 3er-Potenzen enden auf 3, 9, 7, 1, 3, … – ein Zyklus der Länge 4.
Die 7er-Potenzen enden auf 7, 9, 3, 1, 7, … – ein Zyklus der Länge 4.
Die 9er-Potenzen enden auf 9, 1, 9, 1, 9, … – ein Zyklus der Länge 2.

$$\begin{align} s &\equiv 2^{1509} \cdot 3^{1618} \cdot 7^{835} \cdot 9^{467}\mod 10
&\equiv 2^{1\ \ \ \ \ \ } \cdot 3^{2\ \ \ \ \ \ } \cdot 7^{3\ \ \ \ } \cdot 9^{1\ \ \ \ }\mod 10
&\equiv 2 \ \ \ \ \ \ \cdot 9 \ \ \ \ \ \ \cdot 3 \ \ \ \ \ \cdot 9 \ \ \ \ \mod 10
&\equiv 6 \mod 10 \end{align}$$

Die letzte Stelle von 2019! vor den Nullen ist also die 6.

Und jetzt bin ich auf Rolfs Lösung gespannt, die sicher eleganter ist und mit viel weniger Rechnerei auskommt.

LLAP 🖖