010
13.10.2002, 23:47 Uhr
NemoEimi
|
Zitat: |
Eine X-Y-Z Folge sei definiert wie folgt: 1. W(1) ist eine beliebige natürliche Zahl X (Startwert) != 0 2. W(n) ist die zahl bestehenden aus dem letzten Y Ziffern des Z-Fachen von W(n-1).
|
Ok, also W(1):= x, W(n+1) := z*W(n) mod 10^y, oder, als Haskell-Programm ausgedrückt (damit ich auch noch was programmiere hierzu):
Code: |
xyzFolge(x,y,z) = x:xyzFolge(z*x `mod` 10^y,y,z)
erste_n_Folgenglieder(n,x,y,z) = take n (xyzFolge(x,y,z))
|
Zitat: |
Nun die Aufgaben: 1. Suche das X, dessen X-2-2 Folge die minimale Periode hat. 2. Suche das X, dessen X-2-2 Folge die maximale Periode hat
|
Klar gilt W(n)=x*z^(n-1) mod 10^y, d.h. aus z^n=z^m folgt W(n+1)=W(m+1), und mit mod 10^y invertierbarem, d.h. nicht durch 2 oder durch fünf teilbarem x funktioniert auch der Umkehrschluss, woraus folgt, daß die maximale Periode für diese x erreicht wird. (Bemerkung: mit invertierbarem z funktioniert der Umkehrschluss hier natürlich nicht , Gegenbeispiel ist etwa 5*3 = 5 mod 10, 3 != 1 mod 10) Minimale Wiederholperiode wird beispielsweise mit x=50 erreicht, da dann schon W(1)=0 ist.
Zitat: |
3. Für welche X kommt in der X-3-2 Folge die Zahl 123 vor?
|
Nur für x=123, da 123 invertierbar mod 1000 ist und alles, was einmal mit 2 multipliziert wurde, nicht mehr diese Eigenschaft hat.
Zitat: |
4. Sind Folgen mit grossem Z tendenziell länger, kürzer, oder gleich periodisch wie die mit kleinem Z?[/i]
|
Gleich periodisch, weil 10^y-z = -z mod 10^y offensichtlich die gleichen Perioden erzeugt wie z.
Grüße, NemoEimi Dieser Post wurde am 13.10.2002 um 23:53 Uhr von NemoEimi editiert. |