Kombinationen ohne Periodizitaet

04.04.2006, 22:00

Crock

Kombinationen ohne Periodizitaet

Hi,
ich hab hier gerade wieder einen super-realistischen "Hacker"-Film gesehen, bei denen wieder viele 1en und 0en ueber den Bildschirm huschten ;-)

Da kam mir die Frage in den Kopf, wie viele Kombinationen von z.B 1 und 0 es gitb, die keine Periodizitaet aufweisen.

Mal angenommen wir haben 32 mal eine 1 oder 0 zu vergen,
ergo gaebe es $\begin{eqnarray*} 2^{32} \end{eqnarray*}$ kombinationen allgemein.

Um noch mal kurz die "Peridozitaet" zu klaeren: Ich will solche Folgen wie "1010101010101010" oder "1001100110011001100110011001" vermeiden.

Ich hab nur den Anstanz eines Ansatzes (*tadamm*)

Also wenn man n Elemente hat und immer eines dieser Elemente auf m Plaetze legen kann, dann waere die laegen die Periodenlaengen zwischen 2 und $\begin{eqnarray*} \sqrt{n} \end{eqnarray*}$ .
SOmit muesste man doch alle periodischen-Kombinationen mit $\begin{eqnarray*} \sum^{\sqrt{n}}_{i=2}{i\cdot{}\lfloor \frac{n}{i}}\rfloor \end{eqnarray*}$

Oder?

Bitte um Antwort smile

MfG Alexander Surma

05.04.2006, 02:11

JochenX

Auf diesen Beitrag antworten »

bei endlichen Ketten von Periodizität zu sprechen, finde ich komisch
warum sollte nicht jede beliebige 32-er Kette eine 32-er Periode ausmachen?

Rest verstehe ich nicht, aber Ganzzahlsummen, die bis zu einer Wurzel laufen, kommen mir auch komisch vor.

05.04.2006, 02:31

sqrt(2)

Auf diesen Beitrag antworten »

RE: Kombinationen ohne Periodizitaet

Zitat:

Original von Crock
Um noch mal kurz die "Peridozitaet" zu klaeren: Ich will solche Folgen wie "1010101010101010" oder "1001100110011001100110011001" vermeiden.

So wie du das darstellst, könnten auch zwei aufeinanderfolgende gleiche Ketten von je 16 bits eine solche "periodische Kette" darstellen. Das wären $\begin{eqnarray*} 2^{16} \end{eqnarray*}$ Möglichkeiten, alle anderen mit kürzeren wiederholten Ketten sind dabei schon mitgezählt. Wenn eine "Periode" maximal $\begin{eqnarray*} n \end{eqnarray*}$ Zeichen lang sein soll (mit $\begin{eqnarray*} n=2^k,~k\in\mathbb{N},2\leq k\leq5 \end{eqnarray*}$ ), dann gibt es also allgemein $\begin{eqnarray*} 2^n \end{eqnarray*}$ solcher "periodischer Ketten".

edit: Flüchtigkeitsfehler beseitigt...

05.04.2006, 16:22

Crock

Auf diesen Beitrag antworten »

Ja, jetzt wo ich es am naechsten Tag nochmal lese, hab ich mich echt bekloppt ausgdedrueckt.

Ich meinte: Wie viele Kombinationen gibt es bei einer Kette von binaeren ZIffern der Laenge 32, die keine WIederholungen aufweisen (Beispiel sie alten Post).

Aber sqrt(2) hat meine Frage bereits beantwortet, danke smile

Neue Frage »

Antworten »

Kombinationen ohne Periodizitaet

Verwandte Themen