48 lines
1.2 KiB
ObjectPascal
48 lines
1.2 KiB
ObjectPascal
function digits(n: integer): sequence of integer;
|
|
begin
|
|
result := new List<integer>;
|
|
repeat
|
|
result := result + n mod 10;
|
|
n := n div 10;
|
|
until n = 0;
|
|
end;
|
|
|
|
function gen(n: integer): integer;
|
|
begin
|
|
result := n;
|
|
while (result <> 1) and (result <> 89) do
|
|
begin
|
|
var s := 0;
|
|
foreach var d in digits(result) do s += d * d;
|
|
result := s;
|
|
end;
|
|
end;
|
|
|
|
function chainsEndingWith89(ndigits: integer): int64;
|
|
begin
|
|
var prevcount := new Dictionary<integer, int64>;
|
|
var currcount := new Dictionary<integer, int64>;
|
|
for var i := 0 to 9 do prevcount[i * i] := 1;
|
|
|
|
loop ndigits - 1 do
|
|
begin
|
|
currcount.Clear;
|
|
foreach var prev in prevcount do
|
|
for var newdigit := 0 to 9 do
|
|
begin
|
|
var nextgen := newdigit * newdigit + prev.key;
|
|
currcount[nextgen] := currcount.get(nextgen) + prev.value;
|
|
end;
|
|
prevcount := new Dictionary<integer, int64>(currcount);
|
|
end;
|
|
|
|
foreach var curr in currcount do
|
|
if (curr.key <> 0) and (gen(curr.key) = 89) then
|
|
result += curr.value;
|
|
end;
|
|
|
|
begin
|
|
println('For 8 digits: ', chainsEndingWith89(8));
|
|
println('For 18 digits: ', chainsEndingWith89(18));
|
|
println(milliseconds, 'ms');
|
|
end.
|