Potenzquotienten

07.11.2019, 18:55

michaeljj

Potenzquotienten

Meine Frage:
Hallo,
ich bin darauf gestossen, dass wahrscheinlich gilt:

floor(3^c/2^c) = floor((3^c-1)/(2^c-1))
Habe ich gerechnet bis c= 130000
Ich kann das aber nicht beweisen.
Kennt jemand einen Beweis?

U.U. gilt sogar floor(a^c/b^c) = floor((a^c-1)/(b^c-1))
für a>b ab einem Wert c>k

Michael

Meine Ideen:
...meine Ansätze laienhaft und nicht interessant

07.11.2019, 20:04

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von michaeljj
floor(3^c/2^c) = floor((3^c-1)/(2^c-1))

Für c=1 gilt es nicht. Augenzwinkern

-------------------------------------------------------------------------------------------------------

Spaß beiseite, ich hab ebenfalls mal alle $\begin{eqnarray*} 2\leq c\leq 10^7 \end{eqnarray*}$ überprüft - kein Treffer für ein Gegenbeispiel. Beweisen kann ich die Behauptung ebenfalls nicht, finde keinen Zugang. Nur ein paar Gedanken zum Thema:

Sei $\begin{eqnarray*} q_c = \left\lfloor\frac{3^c}{2^c}\right\rfloor \end{eqnarray*}$ sowie $\begin{eqnarray*} r_c = \frac{3^c}{2^c}-q_c \end{eqnarray*}$ und $\begin{eqnarray*} r_c' = \frac{3^c-1}{2^c-1}-q_c \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} d_c = r_c'-r_c = \frac{3^c-2^c}{2^c\left(2^c-1\right)} \end{eqnarray*}$ .

Unter der Annahme, dass sich $\begin{eqnarray*} r_c \end{eqnarray*}$ für große $\begin{eqnarray*} c \end{eqnarray*}$ ungefähr wie eine stetige [0,1]-verteilte Zufallsgröße verhält, dann gilt für die Wahrscheinlichkeit $\begin{eqnarray*} p_k \end{eqnarray*}$ , einen Index $\begin{eqnarray*} c\geq k \end{eqnarray*}$ mit $\begin{eqnarray*} r_c'\geq 1 \end{eqnarray*}$ zu finden (das entspräche dann einem $\begin{eqnarray*} c \end{eqnarray*}$ mit $\begin{eqnarray*} \left\lfloor\frac{3^c}{2^c}\right\rfloor < \left\lfloor\frac{3^c-1}{2^c-1}\right\rfloor \end{eqnarray*}$ ) die Abschätzung

$\begin{eqnarray*} p_k \leq \sum_{c=k}^{\infty} d_c = \sum_{c=k}^{\infty} \left(\frac{3}{4}\right)^c \frac{1-\left(\frac{2}{3}\right)^c}{1-\left(\frac{1}{2}\right)^c} < \sum_{c=k}^{\infty} \left(\frac{3}{4}\right)^c = 4\cdot \left(\frac{3}{4}\right)^k \end{eqnarray*}$

Für $\begin{eqnarray*} k=10^7 \end{eqnarray*}$ (die kleineren $\begin{eqnarray*} c \end{eqnarray*}$ habe ich ja überprüft, s.o.) ergibt das $\begin{eqnarray*} p_k < 10^{-1\,249\,386} \end{eqnarray*}$ , also ziemlich unwahrscheinlich, irgendwo noch was zu finden... Selbstverständlich ist das kein Beweis, das mit der "stetigen Gleichverteilung" ist hoch spekulative Heuristik. Augenzwinkern

09.11.2019, 16:51

michaeljj

Auf diesen Beitrag antworten »

Hallo HAL
ich dachte auch, dass die Nachkommawerte zufällig sind, sind sie aber nicht.
Es ist wohl immer FRAC((3^c-1)/(2^c-1)) < FRAC((3^c/2^c)) und das ist schon
seltsam, weil es ja zu einem "Überlauf" kommen könnte, wenn der Quotient des
ersten Bruches xx,9999 ist.

Es lässt sich sogar noch weiter verallgemeinern:
Forall (a>b); exists m sodass forall n>m : FLOOR(na-1)/(nb-1) = FLOOR(na-1)/(nb-1);

Habe aller Kerne meines Rechners tagelang mit ARIBAS arbeiten lassen. Irgendwann gibt es zu jedem m ein n, (mit zufälligen a>b) sodass die Bedingung erfüllt wird.

Mit welchem Langzahlprogramm arbeiten Sie, ARIBAS rechnet "nur" bis 10^64k

Viele Grüsse michaeljj

09.11.2019, 18:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von michaeljj
ich dachte auch, dass die Nachkommawerte zufällig sind, sind sie aber nicht.

Na klar sind sie das nicht, es geht nur um gewisse Aspekte dieser Gleichverteilung. Und ich habe ja auch betont, dass das oben keinerlei Beweiskraft hat.

Zitat:

Original von michaeljj
Es ist wohl immer FRAC((3^c-1)/(2^c-1)) < FRAC((3^c/2^c))

Das ist sicher falsch. Für ALLE $\begin{eqnarray*} c\geq 1 \end{eqnarray*}$ gilt $\begin{eqnarray*} \frac{3^c-1}{2^c-1} > \frac{3^c}{2^c} \end{eqnarray*}$ (siehe die obige Differenz $\begin{eqnarray*} d_c \end{eqnarray*}$ der beiden), und daraus folgt ja $\begin{eqnarray*} \left\lfloor \frac{3^c-1}{2^c-1}\right\rfloor \geq \left\lfloor\frac{3^c}{2^c}\right\rfloor \end{eqnarray*}$ . Es geht dann also um die Frage, ob es ein $\begin{eqnarray*} c\geq 2 \end{eqnarray*}$ gibt, wo hier tatsächlich > statt = gilt, und das passiert eben höchstens, wenn $\begin{eqnarray*} \frac{3^c}{2^c} \end{eqnarray*}$ ganz, ganz knapp unterhalb einer ganzen Zahl liegt, eben maximal um den Wert $\begin{eqnarray*} d_c \end{eqnarray*}$ .

Zitat:

Original von michaeljj
Mit welchem Langzahlprogramm arbeiten Sie, ARIBAS rechnet "nur" bis 10^64k

Eigenes C++ Programm unter Nutzung der GMP, und ich hab auch einigen Grips in den iterativen Algorithmus gesteckt, der sämtliche Langzahl-Multiplikationen und -divisionen im Zusammenhang mit diesem Problem vermeidet.

09.11.2019, 20:19

michaeljj

Auf diesen Beitrag antworten »

... habe das falsche Relationssymbol verwendet und dann noch die falsche Seite auf xx,999 bezogen.
Muss etwas sorgfältiger sein!
Danke für Ihre Hinweise.

Haben Sie einenTip wo im Internet man suchen könnte? Habe das natürlich schon versucht, aber halt erfolglos, deshalb der Versuch hier.

Neue Frage »

Antworten »

Potenzquotienten

Verwandte Themen