---

Hvis jeg har en sekvens af tal som gentages efter 9 værdier, og en anden
sekvens der gentages efteer 5, og de starter samtidigt, hvornår gentager den
samlede sekvens sig så?

Det gør den efter 45 værdier.
9 mod 5 = 4
9/4=2.25
2.25 er ikke heltallig, så den ganges med 4 for at få den gjort til et
heltal, og det er 9
Den korte sekvens skal altså gennemløbe 9 hele perioder af hver 5 værdier,
hvilket er 45.

Er perioderne istedet 150 og 100, så er det 600
150 mod 100 =50
150/50=3, som er et heltal og ikke ganges op
3*100 = 300, som er samlede periodelængde.

Det er ikke så svært, men... hvordan opskriver jeg en formel for dette?
Jeg skal på en måde lave en faktor som er længde1/længde2 ganget op med en
konstant, så det bliver et heltal, men kan ikke finde en pæn måde at skrive
det på.

jeg har rodet ud i retnig af

a= 9/4 = 2.25
b = 9 div 4 = 2
c = a-b = 0.25
k = 1/c = 4, som er min skaleringsfaktor

Dette er dog klodset, jeg ved ikke man man matematisk kan bruge udtryk som
div (for heltalsdivision), og det fejler hvis c er nul.

---

> Hvis jeg har en sekvens af tal som gentages efter 9 værdier, og en anden
> sekvens der gentages efteer 5, og de starter samtidigt, hvornår gentager
> den samlede sekvens sig så?

Hvis det er uklart hvad jeg mener, så se listen her
123456789123456789123456789123456789123456789-123456789123456789123456789123456789
123451234512345123451234512345123451234512345-123451234512345123451234512345123451

Efter 45 værdier starter BÅDE 9'eren og 5'eren forfra. Før de 45 starter de
også forfra, men ikke samtidigt.

---

Niels Torvaldsen skrev:

> Hvis jeg har en sekvens af tal som gentages efter 9 værdier, og en anden
> sekvens der gentages efteer 5, og de starter samtidigt, hvornår gentager den
> samlede sekvens sig så?

Efter mindste fælles multiplum. Det er det matematiske udtryk for
det tal du søger.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

> Efter mindste fælles multiplum. Det er det matematiske udtryk for
> det tal du søger.

"Mindste fælles multiplum er det mindste positive heltal (mindste dividend),
som et eller flere heltal (divisorer) går op i. Tallet er nyttigt, når flere
brøker skal samles på en fælles brøkstreg."

Nej, jeg søger jo netop ikke det tal de går op i.
For 9 og 5 er det ... hov... 45.... som er resultatet. Du har ret. Jeg lader
min benægtigelse stå i svaret, så du kan få lov at godte dig lidt ekstra.
Det er jo jul, og så'n

Jeg kan imidlertid ikke lige finde en metode til at beregne den? Det vil
sige. Jeg har jo selv fundet en metode, men den kan jeg så ikke skrive på en
pæn matematisk måde and end ved at lave to udtryk. Et for division med og et
for division uden rest.

---

> Jeg kan imidlertid ikke lige finde en metode til at beregne den?

My bad. Søgte efter lowest common multiplum og ikke multiple.
Metoderne ser imidlertid ud til at være itterative?

Det vil virker lidt underligt, da man som sagt kan regne det som beskrevet
tidligere. Det har i hvert fald fungeret for alle de test jeg har lavet
undervejs.

---

Niels Torvaldsen skrev:

> My bad. Søgte efter lowest common multiplum og ikke multiple.
> Metoderne ser imidlertid ud til at være itterative?

Man kan opskrive en formel idet mfm er en funktion der returnerer
mindste fælles mangefold (et herligt ord der snart er glemt), og
sff returnerer største fælles faktor:

   mfm(x,y) = x*y / sff(x,y)

Den er ikke i sig selv rekursiv.

Hvis du derimod snakker om beregning på computer, så bruger man
Euklids metode til at beregne sff, og den laves ofte rekursiv
(men kan lige så let laves med et loop).

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

> Hvis du derimod snakker om beregning på computer, så bruger man
> Euklids metode til at beregne sff, og den laves ofte rekursiv
> (men kan lige så let laves med et loop).

Jamen...tilsyneladende kan det jo skrives som følgende, omend det er rodet
uden mellemregninger

lcm(q,w)
a=max(q,w);
b=min(q,w);
if( a/(a%b)-a//(a%b)>0, (1/(a/(a%b)-a//(a%b))*(a/b)*b, a/(a%b) * b)

eller omskrevet

divi = a/b
modu=(a mod b)
frac= (a/modu)-(a//modu)
scale=1/frac

if(frac>0, 1/frac * divi * b, a/modu*b)

Virker denne metode ikke? Samme som jeg skrev i OP. Jeg har ikke set den
fejle endnu, men jeg har trods alt også kun lavet et begrænset antal test.

---

Niels Torvaldsen skrev:

> Jamen...tilsyneladende kan det jo skrives som følgende, omend det er rodet
> uden mellemregninger
> [...]
> eller omskrevet

> divi = a/b
> modu=(a mod b)
> frac= (a/modu)-(a//modu)
> scale=1/frac

> if(frac>0, 1/frac * divi * b, a/modu*b)

> Virker denne metode ikke?

Den virker hvis de to tal er indbyrdes primiske, men så er den
unødigt besværlig fordi resultatet i de tilfælde blot er a * b.

Den fejler ved visse tal der ikke er indbyrdes primiske (de har
en fælles faktor).

Sæt a = 65 og b = 55

divi = 65/55
modu = 65 mod 55 = 10
frac = (65/10) - (65//10) = 6,5 - 6 = 0,5
mfm(65,55) = 0,5 * 65/55 * 55 = 32,5 (fejl)

Det er forkert. Det rigtige tal er 65 * 55 / 5 fordi 5 er største
fælles faktor for de to tal.

Din metopde virker ved (150,100) som har en fælles faktor, men
det skyldes at de to tal begge ligger i faktortabellen
(50-tabellen).

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

> Sæt a = 65 og b = 55
>
> divi = 65/55
> modu = 65 mod 55 = 10
> frac = (65/10) - (65//10) = 6,5 - 6 = 0,5
> mfm(65,55) = 0,5 * 65/55 * 55 = 32,5 (fejl)

Du laver en fejl i linien "> mfm(65,55) = 0,5 * 65/55 * 55 = 32,5
(fejl)", som du jo også skriver
Det er (1/0.5)*65/10*55 = 715, som er korrekt.

Vi kludrede begge i det. Du glemte at tage den reciprokke værdi, og jeg
skrev forkert med divisionen, for det er jo ikke
if(frac>0, 1/frac * divi * b, a/modu*b)
men
if(frac>0, 1/frac * a/modu * b, a/modu*b)

for 9 og 5 er det
if(true, 1/0.25 * 9/4 * 5, ...) = 45, som er korrekt

for 150 og 100 er det
if(false, ..., 150/50*100) = 300, som er korrekt

for 9 og 3 er det exception, da jeg i farten glemte at checke for en
modulusværdi på nul, men det kan man jo skrive med ind som en betingelse. I
så fald er svaret altid den største af de to.
if(modu=0, max(a,b), if( frac>0), 1/frac*a/modu*b, a/modu*b) )

I den form så reduceres det for 9,5 og 65,55 og 100,150 til det gamle udtryk
fra før, og for 9 og 3, som i den grad ikke er indbyrdes primiske, er
modu=0, så det reduceres til
if(true, max(9,3), ... ) => 9, som er korrekt

Jeg synes stadig det ser ud til at "min metode" kan finde mindste fælles
multiplum i een udregning istedet for at itterere...?

---

Niels Torvaldsen skrev:

> Vi kludrede begge i det.

Ja, dine formler passer som vinden blæser, men din metode er
rigtig nok (kan dog ikke bevise det). Her er de rigtige formler:

Det forudsættes at a>b

HVIS b går op i a, så er svaret a og sfd(a,b) = b

ELLERS beregnes:
modu = a mod b
HVIS modu går op i a, så er svaret a * b / modu og sfd(a,b) = modu

ELLERS er svaret a * b og sfd(a,b) = 1

Din metode kan bruges til at beregne sfd og mfm uden løkke og rekursion.


Eksempler:

150,15
15 går op i 150, så svaret er 150 og sfd = 15

150,120
modu = 150 mod 120 = 30
30 går op i 150, så svaret er 150 * 120 / 30 = 600 og sfd = 30

150,100
modu = 15 mod 100 = 50
50 går op i 150, så svaret er 150 * 100 / 50 = 600 og sfd = 50

9,4
modu = 9 mod 5 = 4
4 går ikke op i 9, så svaret er 9 * 4 og sfd = 1

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

> Ja, dine formler passer som vinden blæser

Jah, og du læser dem som vinden blæser, men ja... det blev lidt rodet.

> Din metode kan bruges til at beregne sfd og mfm uden løkke og rekursion.

Jamen...hvorfor kan min metode det, når standarden tilsyneladende er at
itterere sig frem til en løsning? Det virker ikke sansynligt at jeg skulle
have opdaget noget nyt og smart, så hvorfor bruges "min" metode ikke i
stedet for de der blev foreslået her i tråden?

---

Niels Torvaldsen skrev:

>> Din metode kan bruges til at beregne sfd og mfm uden løkke og rekursion.

> Jamen...hvorfor kan min metode det, når standarden tilsyneladende er at
> itterere sig frem til en løsning?

Der er grænser for hvor meget jeg ved om matematik. Måske er din
løsning opdaget for længst (det vil jeg tro - den er jo ikke
kompleks), men vi holder jo de gamle grækeres metoder i hævd
fordi de var ret godt med i betragtning af det grundlag de havde
at gå ud fra.

> Det virker ikke sansynligt at jeg skulle have opdaget noget nyt
> og smart, så hvorfor bruges "min" metode ikke i stedet for de
> der blev foreslået her i tråden?

Euklids metode med rekursion er smart når folk skal lære om
rekursiv programmering.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Bertel Lund Hansen skrev:

> Euklids metode med rekursion er smart når folk skal lære om
> rekursiv programmering.

I sprog med halerekursion giver formuleringen ovenikøbet
en effektiv implementation. Så den er ikke kun smart
for begyndere

En smart ting er, at metoden kan genbruges, når man skal
finde største fælles divisor mellem polynomier med
heltallige koeffecienter.

Brents metode fra 1970 (den er ny!) til at finde største
fælles divisor, benytter følgende regler:

a) Hvis u og v er lige, så er

sfd(u,v) = 2 sfd(u/2,v/2)

b) Hvis u er lige, og v ulige, så er

sfd(u,v) = sfd(u/2,v)

c) Som i Euklids algoritme:

sfd(u,v) = sfd(u-v,v)

d) Hvis u og v er ulige, så er u-v lige, og |u-v|<max(u,v)

I Scheme bliver det:

(define lige? even?)
(define ulige? odd?)

(define (sfd a b)
(cond
[(= a b) a]
[(and (lige? a) (lige? b)) (* 2 (sfd (/ a 2) (/ b 2)))]
[(and (lige? a) (ulige? b)) (sfd (/ a 2) b)]
[(and (ulige? a) (lige? b)) (sfd a (/ b 2))]
[(and (ulige? a) (ulige? b) (< a b)) (sfd a (- b a))]
[else (sfd (- a b) b)]))

For små heltal er den nye metode god, for der er ingen
dyre divisioner - halvering klares med et bit-skifte.

--
Jens Axel Søgaard

---

"Niels Torvaldsen" <spam@hater.me> writes:

> Virker denne metode ikke? Samme som jeg skrev i OP. Jeg har ikke set den
> fejle endnu, men jeg har trods alt også kun lavet et begrænset antal test.

Prøv med 63345213 og 30108462.

Resultatet skulle gerne blive 51.

--
Thorbjørn Ravn Andersen

---

Når nu ingen andre har vist Euklids algoritme, så lad mig:

-- sfd(x,y) finder største fælles divisor af x og y, forudsat x <= y

sfd(0,y) = y
sfd(x,y) = sfd(y `mod` x, x)

-- mff(x,y) finder største fælles fold af x og y, forudsat x <= y

mff(x,y) = x*y `div` sfd(x,y)

Ovenstående er i Haskell, men det kan skrives i C som

unsigned int sfd(unsigned int x, unsigned int y)
{
if (x==0) return y;
else return sfd(y % x, y);
}

unsigned int mff(unsigned int x, unsigned int y)
{
return x*y / sfd(x,y);
}

Hvis man vil undgå rekursionen i C (som normalt ikke optimerer
halerekursion), kan man bruge en løkke:


unsigned int sfd(unsigned int x, unsigned int y)
{
unsigned int t;

while (x>0) {
t = x;
x = y % x;
y = t;
}
return y;
}

Og som flere andre har påpeget, så er den samlede periode mindste
fælles fold af de individuelle perioder. Hvis man kombinerer mere end
to perioder, kan man gøre det i vilkårlig rækkefølge, f.eks.
mff(x,mff(y,z)) eller mff(mff(x,y),z).

   Torben

---

Bertel Lund Hansen <unospamo@lundhansen.dk> writes:

> Niels Torvaldsen skrev:
>
>> Vi kludrede begge i det.
>
> Ja, dine formler passer som vinden blæser, men din metode er
> rigtig nok (kan dog ikke bevise det). Her er de rigtige formler:
>
> Det forudsættes at a>b
>
> HVIS b går op i a, så er svaret a og sfd(a,b) = b
>
> ELLERS beregnes:
> modu = a mod b
> HVIS modu går op i a, så er svaret a * b / modu og sfd(a,b) = modu
>
> ELLERS er svaret a * b og sfd(a,b) = 1
>
> Din metode kan bruges til at beregne sfd og mfm uden løkke og rekursion.

Metoden er "bare" Euklids metde udfoldet et par gange, så den virker
kun i nogle (men mange) tilfælde. Et eksempel, hvor den ikke virker
er:

30, 21:

modu = 30 mod 21 = 9

9 går ikke op i 30, så din metode siger, at sfd er 1 og svaret er
30*21 = 630.

Men sfd er 3, og svaret er 30*21/3 = 210.

   Torben

---

> Metoden er "bare" Euklids metde udfoldet et par gange, så den virker
> kun i nogle (men mange) tilfælde. Et eksempel, hvor den ikke virker
> er:
>
> 30, 21:
>
> modu = 30 mod 21 = 9
>
> 9 går ikke op i 30, så din metode siger, at sfd er 1 og svaret er
> 30*21 = 630.
> Men sfd er 3, og svaret er 30*21/3 = 210.

30 % 21 = 9

30/9=3+1/3

Det skal ganges op til det er et lige tal, altså ganges med (1/fraction) 3
så man får (1/0.33) = 3*(3+1/3)=10

Den korte cykel skal løbe 10 gange før man finder lcm, og det er 21*10=210

Jeg mener da ikke jeg lige lavede min formel om (igen), så det passer vist
stadig? Hvis jeg altså ikke i farten fik lavet den om igen, så den passer.

Princippet er jo helt banalt.
a og b forskydes a%b, hver gang b gennemløbes. Så skal b altså køre en
runde, og give en forskydning, indtil man har fodskudt sig tilbage til 0.
For 9 og 5 forskyder man 4 hver gang, men da 4 ikke går op 9 9, så skal man
køre mere end en runde før man rammer starten.

---

"Niels Torvaldsen" <spam@hater.me> writes:

> Det gør den efter 45 værdier.

Leder du ikke efter mindste fælles multiplum?

Det finder du nemt ved at finde største fælles divisor først. Euklids
algoritme er nem at implementere.

--
Thorbjørn Ravn Andersen

---

Niels Torvaldsen wrote:
> Hvis jeg har en sekvens af tal som gentages efter 9 værdier, og en
> anden sekvens der gentages efteer 5, og de starter samtidigt, hvornår
> gentager den samlede sekvens sig så?
>
> Det gør den efter 45 værdier.
> 9 mod 5 = 4
> 9/4=2.25
> 2.25 er ikke heltallig, så den ganges med 4 for at få den gjort til et
> heltal, og det er 9
> Den korte sekvens skal altså gennemløbe 9 hele perioder af hver 5
> værdier, hvilket er 45.
>
> Er perioderne istedet 150 og 100, så er det 600
> 150 mod 100 =50
> 150/50=3, som er et heltal og ikke ganges op
> 3*100 = 300, som er samlede periodelængde.
>
> Det er ikke så svært, men... hvordan opskriver jeg en formel for
> dette? Jeg skal på en måde lave en faktor som er længde1/længde2 ganget op
> med en konstant, så det bliver et heltal, men kan ikke finde en pæn
> måde at skrive det på.
>
> jeg har rodet ud i retnig af
>
> a= 9/4 = 2.25
> b = 9 div 4 = 2
> c = a-b = 0.25
> k = 1/c = 4, som er min skaleringsfaktor
>
> Dette er dog klodset, jeg ved ikke man man matematisk kan bruge
> udtryk som div (for heltalsdivision), og det fejler hvis c er nul.

Du skriver ikke, hvad dit formål med alt dette er. Jeg er enig i, at det
ikke bliver nemt at opskrive en formel. Det bliver ikke engang helt nemt at
opskrive algoritmisk.

Dit grundlæggende problem er at finde mindste fælles multiplum, dvs. for to
tal a og b finde det mindste tal som de begge går op i. Hvad *jeg* ville
gøre, var at kigge på primtalsopløsning af a og b. Har du først den, giver
resten sig selv. Men da jeg ikke ved, hvad du skal bruge det til, kan jeg
ikke sige, om det er den rigtige vej frem. (Hvis du fx har meget store tal,
er primtalsopløsning noget rigtig snavs at kaste sig ud i.)

--
Regards,
Kristian Damm Jensen
"This isn't Jeopardy. Answer below the question."

---

Kristian Damm Jensen wrote:
> Niels Torvaldsen wrote:
>> Hvis jeg har en sekvens af tal som gentages efter 9 værdier, og en
>> anden sekvens der gentages efteer 5, og de starter samtidigt, hvornår
>> gentager den samlede sekvens sig så?
>>
>> Det gør den efter 45 værdier.
>> 9 mod 5 = 4
>> 9/4=2.25
>> 2.25 er ikke heltallig, så den ganges med 4 for at få den gjort til
>> et heltal, og det er 9
>> Den korte sekvens skal altså gennemløbe 9 hele perioder af hver 5
>> værdier, hvilket er 45.
>>
>> Er perioderne istedet 150 og 100, så er det 600
>> 150 mod 100 =50
>> 150/50=3, som er et heltal og ikke ganges op
>> 3*100 = 300, som er samlede periodelængde.
>>
>> Det er ikke så svært, men... hvordan opskriver jeg en formel for
>> dette? Jeg skal på en måde lave en faktor som er længde1/længde2
>> ganget op med en konstant, så det bliver et heltal, men kan ikke
>> finde en pæn måde at skrive det på.
>>
>> jeg har rodet ud i retnig af
>>
>> a= 9/4 = 2.25
>> b = 9 div 4 = 2
>> c = a-b = 0.25
>> k = 1/c = 4, som er min skaleringsfaktor
>>
>> Dette er dog klodset, jeg ved ikke man man matematisk kan bruge
>> udtryk som div (for heltalsdivision), og det fejler hvis c er nul.
>
> Du skriver ikke, hvad dit formål med alt dette er. Jeg er enig i, at
> det ikke bliver nemt at opskrive en formel. Det bliver ikke engang
> helt nemt at opskrive algoritmisk.
>
> Dit grundlæggende problem er at finde mindste fælles multiplum, dvs.
> for to tal a og b finde det mindste tal som de begge går op i. Hvad
> *jeg* ville gøre, var at kigge på primtalsopløsning af a og b. Har du
> først den, giver resten sig selv. Men da jeg ikke ved, hvad du skal
> bruge det til, kan jeg ikke sige, om det er den rigtige vej frem.
> (Hvis du fx har meget store tal, er primtalsopløsning noget rigtig
> snavs at kaste sig ud i.)

Arh. Glem det. Euklids algoritme er vejen frem. (Og jeg har oven i købet
skrevet en lærebog, hvor Euklids algorime blev brugt. Nok er det snart 20 år
siden, men alligevel. Pinligt.)

--
Regards,
Kristian Damm Jensen
"This isn't Jeopardy. Answer below the question."

---

Torben Ægidius Mogensen skrev:
> Når nu ingen andre har vist Euklids algoritme, så lad mig:
>
> -- sfd(x,y) finder største fælles divisor af x og y, forudsat x <= y
>
Den betingelser er ikke nødvendig. Men det ville nok være klogt at
returnere error, hvis x eller y starter som 0.

Mvh
Martin

---

Martin skrev:
> Torben Ægidius Mogensen skrev:
> > Når nu ingen andre har vist Euklids algoritme, så lad mig:
> >
> > -- sfd(x,y) finder største fælles divisor af x og y, forudsat x <= y
> >
> Den betingelser er ikke nødvendig. Men det ville nok være klogt at
> returnere error, hvis x eller y starter som 0.
>
Error er det ikke i matematisk forstand, men det vil nok være lidt
overrraskende, selv for landmænd med EU-tilskud, at 0 kan indeholde et
hvilket som helst mål. For matematikere er det vist naturligt/bekvemt.

"Største fælles mål" hed det vist hos ældre danske matematikere.
Det andet hedder "_mindste_ fælles fold" (eg: 30 er mindste fælles
fold af 6 og 10).

Mvh
Martin