82 lines
2.1 KiB
Zig
82 lines
2.1 KiB
Zig
const std = @import("std");
|
|
|
|
fn gcd(a: u64, b: u64) u64 {
|
|
if (b == 0) return a;
|
|
return gcd(b, a % b);
|
|
}
|
|
|
|
fn sternBrocot(allocator: std.mem.Allocator, up_to: u64) !std.ArrayList(u64) {
|
|
var seq = std.ArrayList(u64).init(allocator);
|
|
try seq.append(1);
|
|
try seq.append(1);
|
|
|
|
var last: u64 = 1;
|
|
var idx: usize = 1;
|
|
|
|
while (last < up_to) {
|
|
last = seq.items[idx];
|
|
try seq.append(last + seq.items[idx - 1]);
|
|
try seq.append(last);
|
|
idx += 1;
|
|
}
|
|
|
|
return seq;
|
|
}
|
|
|
|
fn testSternBrocot() !void {
|
|
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
|
|
defer arena.deinit();
|
|
const allocator = arena.allocator();
|
|
|
|
var seq = try sternBrocot(allocator, 100);
|
|
|
|
// Print first 15 in sequence
|
|
std.debug.print("First 15 in sequence: ", .{});
|
|
std.debug.print("[", .{});
|
|
for (seq.items[0..15], 0..) |val, i| {
|
|
if (i > 0) std.debug.print(", ", .{});
|
|
std.debug.print("{d}", .{val});
|
|
}
|
|
std.debug.print("]\n", .{});
|
|
|
|
// Print first positions of integers 1 through 10
|
|
std.debug.print("First positions of integers 1 through 10:\n", .{});
|
|
for (1..11) |i| {
|
|
const i_u64 = @as(u64, i);
|
|
var found = false;
|
|
for (seq.items, 0..) |val, pos| {
|
|
if (val == i_u64) {
|
|
std.debug.print(" {d:>2} at position {d}\n", .{i, pos + 1});
|
|
found = true;
|
|
break;
|
|
}
|
|
}
|
|
if (!found) {
|
|
std.debug.print("Error finding position of {d}\n", .{i});
|
|
}
|
|
}
|
|
|
|
// Find position of 100
|
|
for (seq.items, 0..) |val, pos| {
|
|
if (val == 100) {
|
|
std.debug.print(" 100 at position {d}\n", .{pos + 1});
|
|
break;
|
|
}
|
|
}
|
|
|
|
// Check if first 999 consecutive pairs have gcd of 1
|
|
var all_gcd_one = true;
|
|
for (1..1000) |i| {
|
|
if (i >= seq.items.len) break;
|
|
if (gcd(seq.items[i - 1], seq.items[i]) != 1) {
|
|
all_gcd_one = false;
|
|
break;
|
|
}
|
|
}
|
|
std.debug.print("The first 999 consecutive pairs have gcd of 1: {any}.\n", .{all_gcd_one});
|
|
}
|
|
|
|
pub fn main() !void {
|
|
try testSternBrocot();
|
|
}
|