Formel für die Anzahl der Nullen am Ende der Binärdarstellung einer Zahl [Zahlentheorie?]

14.03.2016, 16:01

xs2007

Formel für die Anzahl der Nullen am Ende der Binärdarstellung einer Zahl [Zahlentheorie?]

Hallo zusammen,

wie der Titel schon sagt, suche ich nach einer Formel, die $\begin{eqnarray*} n \in \mathbb{N}, n \geq 1 \end{eqnarray*}$ auf die Anzahl der Nullen am Ende ihrer Binärdarstellung abbildet. Diese sollte im Idealfall auf Elemente, mit denen weiteres Umformen deutlich erschwert wird, verzichten. Damit meine ich z.B. so etwas wie Floor, Ceiling, Max, Min, Modulo, usw.

Für die ersten natürlichen Zahlen sieht der Funktionsverlauf - zur Anschauung - wie folgt aus:
$\begin{eqnarray*} f\left(1\right) = 0 f\left(2\right) = 1 f\left(3\right) = 0 f\left(4\right) = 2 f\left(5\right) = 0 f\left(6\right) = 1 ... \end{eqnarray*}$

Der Verlauf für die ersten 2000 natürlichen Zahlen findet sich hier: pastebin.com/GS2b4NT0 (Darf noch keine URL's posten, daher keine Verlinkung)

Meine Ideen

Ich habe eine entprechende Formel gefunden, welche aber leider mittels Floor und Ceiling funktioniert:
$\begin{eqnarray*} f(n) = \sum\limits_{k=1}^{\left\lfloor log_2\left(n\right) \right\rfloor} 1 - \left(\left\lceil\frac{n}{2^k}\right\rceil - \left\lfloor\frac{n}{2^k}\right\rfloor \right) \end{eqnarray*}$

Da ich die gesamte Formel (f(n)) im weiteren Verlauf innerhalb eines Exponenten innerhalb einer Summe verwende, komme ich mit dieser Darstellung nicht sehr viel weiter...

Eine andere Idee war, den Definitionsbereich der Funktion aufs Reelle zu erweitern (Da mich nur Ergebnisse bei ganzzahligen, positiven Eingaben interessieren, kann der Funktionsverlauf bei reellen Eingabewerten jenseits der natürlichen Zahlen beliebig sein) und mit Summen von Sinusfunktionen zu arbeiten. Die Idee dabei wäre es, zunächst eine Sinusfunktion zu konstruieren, welche die Folge 0 1 0 1 0 1 0 ... für die natürlichen Zahlen aufweist und dann im nächsten Summanden eine, die für alle Zahlen mod 4 == 0 noch einmal 1 aufsummiert, dann für alle Zahlen mod 8 == 0 usw.
Meine Hoffnung dabei war, dass ich ggf. im komplexen die Summe dieser Sinusfunktionen auflösen kann, um eine einfache Darstellung zu erhalten.
Problem ist, dass ich nicht sicher bin, ob sich überhaupt Funktionsverläufe wie 0 0 0 1 0 0 0 1 0 0 0 1 ... bzw. 0 0 0 0 0 0 0 1 0 0 ... mit (wenigen) Sinusfunktionen darstellen lassen. (Klar, über Fourier müsste es irgendwie immer gehen, aber ich bin nicht sicher, ob das den Ausdruck einfacher handlebar macht...)

Vielen Dank schon einmal für Antworten und Anregungen smile

Viele Grüße

14.03.2016, 16:10

IfindU

Auf diesen Beitrag antworten »

RE: Formel für die Anzahl der Nullen am Ende der Binärdarstellung einer Zahl [Zahlentheorie?]
Das Problem ist äquivalent zum finden der Darstellung $\begin{eqnarray*} n = 2^k m \end{eqnarray*}$ mit $\begin{eqnarray*} 0 \leq m < 2^k \end{eqnarray*}$ für alle $\begin{eqnarray*} n \end{eqnarray*}$ , und kann als teilweise Primfaktorzerlegung gesehen werden (aka wie oft tritt der Faktor 2 in der Zahl n auf).

Ich kann mir nicht vorstellen, dass es eine schoene Formel dafuer gibt. Implementieren wuerde ich es dadurch $\begin{eqnarray*} n \end{eqnarray*}$ immer weiter durch 2 zu teilen, und zu gucken wann das Ergebnis nicht mehr eine natuerliche Zahl ist. Genau das macht deine Formel auch.

Edit: Wegen Binaer bin ich direkt auf Programmieren gekommen -- sorry, wenn das nicht das Ziel war.

14.03.2016, 16:17

Steffen Bühler

Auf diesen Beitrag antworten »

RE: Formel für die Anzahl der Nullen am Ende der Binärdarstellung einer Zahl [Zahlentheorie?]
In der OEIS findet sich folgende "Bastelanleitung":

Zitat:

To construct the sequence: start with 0,1, concatenate to get 0,1,0,1. Add + 1 to last term gives 0,1,0,2. Concatenate those 4 terms to get 0,1,0,2,0,1,0,2. Add + 1 to last term etc.

Vielleicht hilft's.

Viele Grüße
Steffen

14.03.2016, 16:22

xs2007

Auf diesen Beitrag antworten »

Hey,

Programmierung ist hier nicht primär das Ziel. In Code wäre es auch gut sehr kompakt zu lösen:
(Java:)
while((n & 1) == 0){
++f;
n >>= 1;}

Das mit der Primfaktorzerlegung ist ein guter Punkt, auch, wenn er für mich eher von Nachteil ist...

OEIS ist interessant, die Seite kannte ich gar nicht. Da werde ich mal lesen. Danke dafür!

15.03.2016, 07:19

IfindU

Auf diesen Beitrag antworten »

RE: Formel für die Anzahl der Nullen am Ende der Binärdarstellung einer Zahl [Zahlentheorie?]

Zitat:

Original von IfindU
Das Problem ist äquivalent zum finden der Darstellung $\begin{eqnarray*} n = 2^k m \end{eqnarray*}$ mit $\begin{eqnarray*} 0 \leq m < 2^k \end{eqnarray*}$ für alle $\begin{eqnarray*} n \end{eqnarray*}$

Ich bin schwer enttäuscht vom Board! Ihr müsst mir schon sagen, wenn ich absoluten Stuss rede! Da sind wohl 2 Sachen in meinem Kopf durcheinander geraten. Jede Zahl $\begin{eqnarray*} n \end{eqnarray*}$ hat eine eindeutige Darstellung als $\begin{eqnarray*} n = 2^k + m \end{eqnarray*}$ mit $\begin{eqnarray*} 0 \leq m < 2^k \end{eqnarray*}$ .

Das andere ist $\begin{eqnarray*} n = 2^k m \end{eqnarray*}$ mit $\begin{eqnarray*} m \end{eqnarray*}$ ungerade -- und das ist das nützliche hier. Aus dem oberen kann man hier nichts folgern.

15.03.2016, 09:38

HAL 9000

Auf diesen Beitrag antworten »

Ich kann nur für mich sprechen: Ich hatte deinen Beitrag bis $\begin{align*} n=2^km \end{align*}$ gelesen, innerlich zustimmend genickt (dabei das "m ungerade" implizit dazu gedacht) und dann die $\begin{align*} m \end{align*}$ -Ungleichung als unwichtig überlesen... smile

Wer weiß, wieviel unentdeckte "Gurken" in meinen Beiträgen schlummern. Big Laugh

15.03.2016, 23:19

URL

Auf diesen Beitrag antworten »

Ging mir wie HAL Wink

Neue Frage »

Antworten »

Formel für die Anzahl der Nullen am Ende der Binärdarstellung einer Zahl [Zahlentheorie?]

Verwandte Themen