Universal sequences (Q1360981)

Untersucht wird wie lang mindestens eine \((0,1)\)-Test-Folge sein muß, um darin für jedes \(m\) (mit \(k\leq m\leq n\) bei vorgegebenen \(k,n)\) mit \(2^{k}\) Teilfolgen davon alle \((0,1)\)-Folgen der Länge \(k\) zu erhalten, wobei die Teilfolgen spätestens mit dem jeweils \(m\)-ten Folge-Element der Test-Folge vom Teilfolgen-Beginn an endet. Offensichtlich ist die Test-Folgen-Länge bei \(k=n\) mindestens \(2^{k+ (n-1)}\), bei Kreis-Folgen \(2^k\); es gilt sogar Gleichheit wegen Existenz der DeBruijn-Folgen. Für verschiedene Einschränkungen werden Abschätzungen gegeben, insbesondere für \(m=n\). Mit Hilfe von Euler's varphi-Funktion wird auch gezeigt, daß sich Kreis-Testfolgen für \(n\) = Primzahl leicht daraus ableiten lassen.