Stern-Brocot sequence: Difference between revisions
Add Miranda
(add RPL) |
Not a robot (talk | contribs) (Add Miranda) |
||
Line 4,096:
1179
True</pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay
["First 15: " ++ show first15,
"Indices of first 1..10: " ++ show idx10,
"Index of first 100: " ++ show idx100,
"The GCDs of the first 1000 pairs are all 1: " ++ show allgcd])]
first15 :: [num]
first15 = take 15 stern
idx10 :: [num]
idx10 = [find num stern | num<-[1..10]]
idx100 :: num
idx100 = find 100 stern
allgcd :: bool
allgcd = and [gcd a b = 1 | (a, b) <- take 1000 (zip2 stern (tl stern))]
|| Stern-Brocot sequence
stern :: [num]
stern = 1 : 1 : concat (map consider (zip2 stern (tl stern)))
where consider (prev,item) = [prev + item, item]
|| Supporting functions
gcd :: num->num->num
gcd a 0 = a
gcd a b = gcd b (a mod b)
find :: *->[*]->num
find item = find' 1
where find' idx [] = 0
find' idx (a:as) = idx, if a = item
= find' (idx + 1) as, otherwise</syntaxhighlight>
{{out}}
<pre>First 15: [1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]
Indices of first 1..10: [1,3,5,9,11,33,19,21,35,39]
Index of first 100: 1179
The GCDs of the first 1000 pairs are all 1: True</pre>
=={{header|Modula-2}}==
| |||