Anzahl der Ziffern einer Zahl < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:02 Mo 20.10.2014 | | Autor: | Eleos |
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Aufgabe 2: [Zahldarstellung]
Sei $z$ eine natuerliche Zahl. Beweisen sie, dass sich die Ziffernanzahl $n$ der Zahl $z$
dargestellt in der Basis $b \in \IN$ mit $b > 1$ durch folgende Gleichung bestimmen laesst:
$n=\lfloor \log_b(z)\rfloor + 1$. |
Hallo liebe Community!
Ich habe da was ausgearbeitet, bin mir aber nicht sicher, ob das legitim ist, was ich da anstelle.
Eine Zahl $z$ zur Basis $b$ laesst sich durch $\summe_{i=0}^{n-1}(z_i*b^i)$ darstellen.
Mit dem Satz $\summe_{i=0}^{n-1}(b^i) = \bruch{b^n-1}{b-1}$, und mit der Ungleichung
$\summe_{i=0}^{n-1}(z_i*b^i) \ge \summe_{i=0}^{n-1}(b^i)$ kann man dann folgende Umformung vornehmen.
$\left\lfloor\log_b\left (\summe_{i=0}^{n-1}(b^i)\right )\right\rfloor + 1 = \left\lfloor\log_b\left (\bruch{b^n-1}{b-1}\right )\right\rfloor + 1$
$= \lfloor\log_b(b^n-1) - \log_b(b-1)\rfloor +1$
Mit der regelt $\log(x + y) = \log(x) + \log\left (1+\bruch{y}{x}\right )$ gilt:
$=\left \lfloor\log_b(b^n) + \log_b\left (1-\bruch{1}{b^n} \right ) - \log_b(b) - \log_b\left (1-\bruch{1}{b}\right )\right\rfloor +1$
$=\left \lfloor n-1+ \log_b\left (1-\bruch{1}{b^n} \right ) - \log_b\left (1-\bruch{1}{b}\right )\right\rfloor +1$
Da $0 < \log_b\left (1-\bruch{1}{b^n} \right ) - \log_b\left (1-\bruch{1}{b}\right ) < 1$ gilt:
$=n - 1 + 1=n$.
Durch die Abschaetzungen nach unten ist das ganze angreifbar, oder?
Habt ihr vielleicht eine besser Idee?
Danke im vorraus
MfG
Eleos
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:32 Mo 20.10.2014 | | Autor: | fred97 |
> Aufgabe 2: [Zahldarstellung]
> Sei [mm]z[/mm] eine natuerliche Zahl. Beweisen sie, dass sich die
> Ziffernanzahl [mm]n[/mm] der Zahl [mm]z[/mm]
> dargestellt in der Basis [mm]b \in \IN[/mm] mit [mm]b > 1[/mm] durch
> folgende Gleichung bestimmen laesst:
> [mm]n=\lfloor \log_b(z)\rfloor + 1[/mm].
> Hallo liebe Community!
>
> Ich habe da was ausgearbeitet, bin mir aber nicht sicher,
> ob das legitim ist, was ich da anstelle.
>
> Eine Zahl [mm]z[/mm] zur Basis [mm]b[/mm] laesst sich durch
> [mm]\summe_{i=0}^{n-1}(z_i*b^i)[/mm] darstellen.
> Mit dem Satz [mm]\summe_{i=0}^{n-1}(b^i) = \bruch{b^n-1}{b-1}[/mm],
> und mit der Ungleichung
> [mm]\summe_{i=0}^{n-1}(z_i*b^i) \ge \summe_{i=0}^{n-1}(b^i)[/mm]
Diese Ungleichung wird i.a. falsch sein ! Im Falle b=2 ist [mm] z_i \in \{0,1\}
[/mm]
Also
[mm]\summe_{i=0}^{n-1}(z_i*b^i) \le \summe_{i=0}^{n-1}(b^i)[/mm] .
Ist ein [mm] z_i=0, [/mm] so haben wir
[mm]\summe_{i=0}^{n-1}(z_i*b^i) < \summe_{i=0}^{n-1}(b^i)[/mm]
FRED
> kann man dann folgende Umformung vornehmen.
>
> [mm]\left\lfloor\log_b\left (\summe_{i=0}^{n-1}(b^i)\right )\right\rfloor + 1 = \left\lfloor\log_b\left (\bruch{b^n-1}{b-1}\right )\right\rfloor + 1[/mm]
>
> [mm]= \lfloor\log_b(b^n-1) - \log_b(b-1)\rfloor +1[/mm]
> Mit der
> regelt [mm]\log(x + y) = \log(x) + \log\left (1+\bruch{y}{x}\right )[/mm]
> gilt:
> [mm]=\left \lfloor\log_b(b^n) + \log_b\left (1-\bruch{1}{b^n} \right ) - \log_b(b) - \log_b\left (1-\bruch{1}{b}\right )\right\rfloor +1[/mm]
> [mm]=\left \lfloor n-1+ \log_b\left (1-\bruch{1}{b^n} \right ) - \log_b\left (1-\bruch{1}{b}\right )\right\rfloor +1[/mm]
>
> Da [mm]0 < \log_b\left (1-\bruch{1}{b^n} \right ) - \log_b\left (1-\bruch{1}{b}\right ) < 1[/mm]
> gilt:
> [mm]=n - 1 + 1=n[/mm].
>
> Durch die Abschaetzungen nach unten ist das ganze
> angreifbar, oder?
> Habt ihr vielleicht eine besser Idee?
>
> Danke im vorraus
> MfG
> Eleos
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:18 Mo 20.10.2014 | | Autor: | Eleos |
Danke fuer die Antwort.
Bin nun auf die Loesung gekommen.
Die Loesung liegt in der Ungleichung [mm] $b^n [/mm] > z [mm] \ge b^{n-1}$
[/mm]
Mit dem Logarithmus zur Basis b und der Unteren Gaussklammer klappt das ganze dann.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:24 Mo 20.10.2014 | | Autor: | Marcel |
Hallo,
> Danke fuer die Antwort.
> Bin nun auf die Loesung gekommen.
> Die Loesung liegt in der Ungleichung [mm]b^n > z \ge b^{n-1}[/mm]
>
> Mit dem Logarithmus zur Basis b und der Unteren
> Gaussklammer klappt das ganze dann.
das klingt gut, jedenfalls habe ich es, wenn meine Erinnerung mich nicht
trübt, so auch in
"Einführung in die Kryptographie" von Johannes Buchmann
gesehen (und nachgerechnet).
Gruß,
Marcel
|
|
|
|
