---

Hej gruppe,

lad os antage at vi har et antal binære tællere. De starter alle i nul
og tæller med samme hastighed. For hver gang der tælles konkateneres den
binære værdi af tællerne. Dette giver altså et helt nyt tal og der
tælles således i en "tilfældig" rækkefølge.
Tricket med dette er så, at de forskellige tællere er indbyrdes
primiske. Når tællerne er indbyrdes primiske er vi sikret, at den nye
sammensatte tæller aldrig når at ramme det samme tal to gange før vi har
nået værdien nul igen.


Eksempel to binære tællere: 2 bit og 4 bit.. tæller til 3 og 14 (3
primtal, dvs. ingen divisor fælles med 14 og 14 er ikke deleligt med 3)

00,0000
01,0001
10,0010
11,0011
00,0100
01,0101
10,0110
11,0111
00,1000
01,1001
10,1010
11,1011
00,1100
01,1101
10,1110

11,0000
00,0001
01,0010
10,0011
11,0100
00,0101
01,0110
10,0111
11,1000
00,1001
01,1010
10,1011
11,1100
00,1101
01,1110

10,0000
11,0001
00,0010
01,0011
10,0100
11,0101
00,0110
01,0111
10,1000
11,1001
00,1010
01,1011
10,1100
11,1101
00,1110

01,0000
10,0001
11,0010
00,0011
01,0100
10,0101
11,0110
00,0111
01,1000
10,1001
11,1010
00,1011
01,1100
10,1101
11,1110

00,0000


altså har jeg i eksemplet 15*4 unikke tilstande - dvs.
(count1-value+1)*(count2-value+1)



men hvad hedder ovenstående teori egentlig og findes der noget bevis på
at det faktisk passer <- ja, det passer jo tydelig vis nok!


Mvh / Preben Holm

---

"Preben Holm" <64bitNOnoSPAMno@mailme.dk> skrev i en meddelelse news:41a4d670$0$84110$14726298@news.sunsite.dk...
>
> Eksempel to binære tællere: 2 bit og 4 bit.. tæller til 3 og 14 (3
> primtal, dvs. ingen divisor fælles med 14 og 14 er ikke deleligt med 3)
>
Du glemmer at du starter fra nul. Dine tal er altså 4 og 15 og da disse
heller ikke har fælles divisorer mødes de først ved 60. Jeg tror ikke
at denne regel har noget specielt navn. Du kan formentlig bevise det
ved at opstille en modstrid.

Mvh
Martin

---

Scripsit Preben Holm <64bitNOnoSPAMno@mailme.dk>

> lad os antage at vi har et antal binære tællere. De starter alle i nul
> og tæller med samme hastighed. For hver gang der tælles konkateneres
> den binære værdi af tællerne. Dette giver altså et helt nyt tal og der
> tælles således i en "tilfældig" rækkefølge.

Jeg kan ikke helt se hvori det "tilfældige" skulle bestå.

> Tricket med dette er så, at de forskellige tællere er indbyrdes
> primiske. Når tællerne er indbyrdes primiske er vi sikret, at den nye
> sammensatte tæller aldrig når at ramme det samme tal to gange før vi
> har nået værdien nul igen.
....
> men hvad hedder ovenstående teori egentlig og findes der noget bevis
> på at det faktisk passer <- ja, det passer jo tydelig vis nok!

Din observation kaldes for "den kinesiske restklassesætning" -- på
engelsk "the Chinese remainder theorem". Det er et velkendt
talteoretisk resultat, som ikke er svært at bevise. [1] (Og det er i
øvrigt helt uafhængigt at om du nedskriver tællerværdierne i binær
notation eller med et andet talsystem).

Helt præcist siger den kinesiske restklassesætning at hvis du kender
værdien af hver af tællerne, er der én og kun én mulighed for hvor
længe der er gået siden sidste gang de alle var 0. Men det er jo ikke
så forskelligt fra din formulering at det gør noget.


[1] For to tællere: Lad tællernes perioder være p og q. Det er klart
at i skridt nummer t vil den første tæller være 0 netop hvis t er
et multiplum af p, og den anden tæller vil være 0 netop hvis t er
et multiplum af q.

Ved skrift t=pq vil begge tællere være 0, så vi ved at vi
ihvertfald før eller senere når tilbage til (0,0). Lad k
være nummeret på det skrift hvor vi *første gang* rammer (0,0).

Det er klart at samme tællerkombination (a,b) ikke kan forekomme
to gange før vi er nået tilbage til (0,0), for ellers ville den
(0,0)-fri sekvens mellem de to forekomster af (a,b) jo gentage sig
i det uendelige, og vi ville *aldrig* nå til (0,0), men dét ved vi
sker ihvertfald i skridt t=pq.

Vi vil nu vise at k=pq. Fordi anden tæller er 0 i skridt 0, kan k
skrives som xq, hvor x er et passende (men indtil videre ukendt)
heltal. Vi ved også at k=xq kan deles med p, men da p og q er
indbyrdes primiske, betyder det at x kan deles med p. Derfor
findes et heltal y så x=yp. Vi har altså k=ypq.

Men k kan ikke være *større* end pq, for ved t=pq er begge tællere
0, og vi havde jo defineret k som den *første* gang dette sker.
Derfor må y=1 og k=pq.

Idet det tager pq skridt at nå frem til (0,0) og der kun er pq
forskellige mulige kombinationer af tællerværdier, kan vi
konkludere (skuffeprincippet!) at enhver kombination forekommer.

--
Henning Makholm "Panic. Alarm. Incredulity.
*Thing* has not enough legs. Topple walk.
Fall over not. Why why why? What *is* it?"

---

Scripsit Henning Makholm <henning@makholm.net>

> Vi vil nu vise at k=pq. Fordi anden tæller er 0 i skridt 0, kan k
> skrives som xq, hvor x er et passende (men indtil videre ukendt)

"skridt 0" skulle naturligvis have været "skrift k".

--
Henning Makholm "Y'know, I don't want to seem like one of those
hackneyed Jews that you see in heartwarming movies.
But at times like this, all I can say is 'Oy, gevalt!'"

---

"Henning Makholm" <henning@makholm.net> skrev i en meddelelse news:878y8rez5q.fsf@kreon.lan.henning.makholm.net...
>
> Din observation kaldes for "den kinesiske restklassesætning" -- på
> engelsk "the Chinese remainder theorem".

Er det ikke at skyde spurve med lynkinesere? Jeg kommer
mere til at tænke på et teorem som lcm(a,b)*gcd(a,b)=a*b

Mvh
Martin

---

Scripsit "Martin Larsen" <mlarsen@post7.tele.dk>
> "Henning Makholm" <henning@makholm.net> skrev

> > Din observation kaldes for "den kinesiske restklassesætning" -- på
> > engelsk "the Chinese remainder theorem".

> Er det ikke at skyde spurve med lynkinesere?

Tja, jeg mener netop det er den egenskab Preben har genopdaget.

Hvad mener du han mangler?

--
Henning Makholm "Hører I. Kald dem sammen. Så mange som overhovedet
muligt. Jeg siger jer det her er ikke bare stort. Det er
Stortstortstort. Det er allerhelvedes stort. Det er historiEN."

---

>>>Din observation kaldes for "den kinesiske restklassesætning" -- på
>>>engelsk "the Chinese remainder theorem".
>
>
>>Er det ikke at skyde spurve med lynkinesere?
>
>
> Tja, jeg mener netop det er den egenskab Preben har genopdaget.

Genopdaget er så meget sagt - man skal jo alle lære, og det er ikke
noget man lærer som studerende i dag - i hvert fald ikke hvis man læser
datateknologi!

Men ellers mange tak for beviset og navnet på sætningen!