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/

Java

Works with: Java version 8

<lang java>import java.util.stream.LongStream;

public class IteratedDigitsSquaring {

   public static void main(String[] args) {
       long r = LongStream.range(1, 100_000_000L)
               .parallel()
               .filter(n -> calc(n) == 89)
               .count();
       System.out.println(r);
   }

   private static long calc(long n) {
       while (n != 89 && n != 1) {
           long total = 0;
           while (n > 0) {
               total += Math.pow(n % 10, 2);
               n /= 10;
           }
           n = total;
       }
       return n;
   }

}</lang>

85744333

Perl 6

This example is incomplete. Please ensure that it meets all task requirements and remove this message.

This is a brute force version. There's no way it can go up to the required limit in any decent time so we mark this solution as incomplete for now.

<lang perl6>sub Euler92($n) {

   (state @)[$n] //=
   $n == 1|89 ?? $n !!
   Euler92([+] $n.comb X** 2)

}

say +grep 89, map &Euler92, 1 .. 100_000_000;</lang>

Python

Translation of: D

<lang python>from math import ceil, log10, factorial

def next_step(x):

   result = 0
   while x > 0:
       result += (x % 10) ** 2
       x /= 10
   return result

def check(number):

   candidate = 0
   for n in number:
       candidate = candidate * 10 + n

   while candidate != 89 and candidate != 1:
       candidate = next_step(candidate)

   if candidate == 89:
       digits_count = [0] * 10
       for d in number:
           digits_count[d] += 1

       result = factorial(len(number))
       for c in digits_count:
           result /= factorial(c)
       return result

   return 0

def main():

   limit = 100000000
   cache_size = int(ceil(log10(limit)))
   assert 10 ** cache_size == limit

   number = [0] * cache_size
   result = 0
   i = cache_size - 1

   while True:
       if i == 0 and number[i] == 9:
           break
       if i == cache_size - 1 and number[i] < 9:
           number[i] += 1
           result += check(number)
       elif number[i] == 9:
           i -= 1
       else:
           number[i] += 1
           for j in xrange(i + 1, cache_size):
               number[j] = number[i]
           i = cache_size - 1
           result += check(number)

   print result

main()</lang>

Output:

85744333