19 lines
555 B
D
19 lines
555 B
D
import std.stdio, std.algorithm, std.range, std.array;
|
|
|
|
uint Q(in int n) nothrow
|
|
in {
|
|
assert(n > 0);
|
|
} body {
|
|
__gshared static Appender!(int[]) s = [0, 1, 1];
|
|
|
|
foreach (immutable i; s.data.length .. n + 1)
|
|
s ~= s.data[i - s.data[i - 1]] + s.data[i - s.data[i - 2]];
|
|
return s.data[n];
|
|
}
|
|
|
|
void main() {
|
|
writeln("Q(n) for n = [1..10] is: ", iota(1, 11).map!Q);
|
|
writeln("Q(1000) = ", Q(1000));
|
|
writefln("Q(i) is less than Q(i-1) for i [2..100_000] %d times.",
|
|
iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));
|
|
}
|