Iterated digits squaring

Iterated digits squaring is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

If you add the square of the digits of a Natural number (an integer bigger than zero), you always end with either 1 or 89:

15 -> 26 -> 40 -> 16 -> 37 -> 58 -> 89
7 -> 49 -> 97 -> 130 -> 10 -> 1

An example in Python:

<lang python>>>> step = lambda x: sum(int(d) ** 2 for d in str(x)) >>> iterate = lambda x: x if x in [1, 89] else iterate(step(x)) >>> [iterate(x) for x in xrange(1, 20)] [1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1]</lang>

Your task is to count how many number chains in [1, 100_000_000) end with a value 89.

This problem derives from the Project Euler problem 92.

D

A simple memoizing partially-imperative brute-force solution: <lang d>import std.stdio, std.algorithm, std.range, std.functional;

uint step(uint x) pure nothrow @safe @nogc {

   uint total = 0;
   while (x) {
       total += (x % 10) ^^ 2;
       x /= 10;
   }
   return total;

}

uint iterate(in uint x) nothrow @safe {

   return (x == 89 || x == 1) ? x : x.step.memoize!iterate;

}

void main() {

   iota(1, 100_000_000).filter!(x => x.iterate == 89).walkLength.writeln;

}</lang>

Output:

85744333

A fast imperative brute-force solution: <lang d>void main() nothrow @nogc {

   import core.stdc.stdio: printf;

   enum uint magic = 89;
   enum uint limit = 100_000_000;
   uint[(9 ^^ 2) * 8 + 1] lookup = void;

   uint[10] squares;
   foreach (immutable i, ref x; squares)
       x = i ^^ 2;

   foreach (immutable uint i; 1 .. lookup.length) {
       uint x = i;

       while (x != magic && x != 1) {
           uint total = 0;
           while (x) {
               total += squares[(x % 10)];
               x /= 10;
           }
           x = total;
       }

       lookup[i] = x == magic;
   }

   uint magicCount = 0;
   foreach (immutable uint i; 1 .. limit) {
       uint x = i;
       uint total = 0;

       while (x) {
           total += squares[(x % 10)];
           x /= 10;
       }

       magicCount += lookup[total];
   }

   printf("%u\n", magicCount);

}</lang> The output is the same.

A more efficient solution: <lang d>uint iLog10(in uint x) pure nothrow @safe @nogc in {

   assert(x > 0);

} body {

   return (x >= 1_000_000_000) ? 9 :
          (x >=   100_000_000) ? 8 :
          (x >=    10_000_000) ? 7 :
          (x >=     1_000_000) ? 6 :
          (x >=       100_000) ? 5 :
          (x >=        10_000) ? 4 :
          (x >=         1_000) ? 3 :
          (x >=           100) ? 2 :
          (x >=            10) ? 1 : 0;

}

uint factorial(in uint n) pure nothrow @safe @nogc {

   import std.algorithm, std.range;
   return reduce!q{a * b}(1u, iota(1u, n + 1));

}

uint nextStep(uint x) pure nothrow @safe @nogc {

   typeof(return) result = 0;

   while (x > 0) {
       result += (x % 10) ^^ 2;
       x /= 10;
   }
   return result;

}

uint check(in uint[] number) pure nothrow @safe @nogc {

   enum uint magic = 89;

   uint candidate = 0;
   foreach (immutable n; number)
       candidate = candidate * 10 + n;

   while (candidate != magic && candidate != 1)
       candidate = candidate.nextStep;

   if (candidate == magic) {
       uint[10] digitsCount;
       foreach (immutable d; number)
           digitsCount[d]++;

       uint result = number.length.factorial;
       foreach (immutable c; digitsCount)
           result /= c.factorial;
       return result;
   }

   return 0;

}

void main() nothrow @nogc {

   import core.stdc.stdio: printf;

   enum uint limit = 100_000_000;
   immutable uint cacheSize = limit.iLog10;

   uint[cacheSize] number;
   uint result = 0;
   uint i = cacheSize - 1;

   while (true) {
       if (i == 0 && number[i] == 9)
           break;
       if (i == cacheSize - 1 && number[i] < 9) {
           number[i]++;
           result += number.check;
       } else if (number[i] == 9) {
           i--;
       } else {
           number[i]++;

           number[i + 1 .. $] = number[i];
           i = cacheSize - 1;
           result += number.check;
       }
   }

   printf("%u\n", result);

}</lang> The output is the same. This third version was ported to D and improved from: mathblog.dk/project-euler-92-square-digits-number-chain/