Stern-Brocot sequence: Difference between revisions
Add Cowgol
Not a robot (talk | contribs) (Add MAD) |
Not a robot (talk | contribs) (Add Cowgol) |
||
Line 1,585:
First 100 at 1179
Correct. The GCDs of all the two consecutive numbers are 1.</pre>
=={{header|Cowgol}}==
<lang cowgol>include "cowgol.coh";
# Redefining these is enough to change the type and length everywhere,
# but arrays are 0-based so you need one extra element.
typedef Stern is uint8; # 8-bit math is enough for the numbers we need
var stern: Stern[1201]; # Array containing Stern-Brocot sequence
# Fill up the Stern-Brocot array
sub GenStern() is
stern[1] := 1;
stern[2] := 1;
var i: @indexof stern := 1;
var last: @indexof stern := @sizeof stern / 2;
while i <= last loop
stern[i*2-1] := stern[i] + stern[i-1];
stern[i*2] := stern[i];
i := i + 1;
end loop;
end sub;
# Find the first location of a given number
sub FindFirst(n: Stern): (i: @indexof stern) is
i := 1;
while i < @sizeof stern and stern[i] != n loop
i := i + 1;
end loop;
end sub;
GenStern(); # Generate sequence
# Print the first 15 numbers
var i: @indexof stern := 1;
while i <= 15 loop
print_i32(stern[i] as uint32);
print_char(' ');
i := i + 1;
end loop;
print_nl();
# Print the first occurrence of 1..10
var j: Stern := 1;
while j <= 10 loop
print_i32(FindFirst(j) as uint32);
print_char(' ');
j := j + 1;
end loop;
print_nl();
# Print the first occurrence of 100
print_i32(FindFirst(100) as uint32);
print_nl();
# Check that all GCDs of consecutive pairs are 1
sub gcd(a: Stern, b: Stern): (r: Stern) is
while a != b loop
if a > b then
a := a - b;
else
b := b - a;
end if;
end loop;
r := a;
end sub;
i := 1;
while i < @sizeof stern / 2 loop
if gcd(stern[i], stern[i+1]) != 1 then
print("GCD not 1 at: ");
print_i32(i as uint32);
print_nl();
ExitWithError();
end if;
i := i + 1;
end loop;
print("All GCDs are 1.\n");</lang>
{{out}}
<pre>1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
1 3 5 9 11 33 19 21 35 39
1179
All GCDs are 1.</pre>
=={{header|D}}==
| |||