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>

Task

Count how many number chains for integers 1 <= n < 100_000_000 end with a value 89.

Or, for much less credit - (showing that your algorithm and/or language is slow):

Count how many number chains for integers 1 <= n < 1_000_000 end with a value 89.

This problem derives from the Project Euler problem 92.

Cf

• Digital root
• Digital root/Multiplicative digital root

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).count.writeln;

}</lang>

Output:

85744333

The run-time is about 10.9 seconds compiled with ldc2.

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. The run-time is less than 3 seconds compiled with ldc2.

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. The run-time is about 0.04 seconds or less. 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.IntStream;

public class IteratedDigitsSquaring {

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

   private static int calc(int n) {
       while (n != 89 && n != 1) {
           int 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

Python: Combinatorics

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

The run-time is less than half a second.

Python: Simple caching

<lang python>>>> from functools import lru_cache >>> @lru_cache(maxsize=1024) def ids(n): if n in {1, 89}: return n else: return ids(sum(int(d) ** 2 for d in str(n)))

>>> ids(15) 89 >>> [ids(x) for x in range(1, 21)] [1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1, 89] >>> sum(ids(x) == 89 for x in range(1, 100000000)) 85744333 >>> </lang>

This took a much longer time, in the order of hours.

Python: Enhanced caching

Notes that the order of digits in a number does not affect the final result so caches the digits of the number in sorted order for more hits. <lang python>>>> from functools import lru_cache >>> @lru_cache(maxsize=1024) def _ids(nt): if nt in {('1',), ('8', '9')}: return nt else: return _ids(tuple(sorted(str(sum(int(d) ** 2 for d in nt)))))

>>> def ids(n): return int(.join(_ids(tuple(sorted(str(n))))))

>>> ids(1), ids(15) (1, 89) >>> [ids(x) for x in range(1, 21)] [1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1, 89] >>> sum(ids(x) == 89 for x in range(1, 100000000)) 85744333 >>> _ids.cache_info() CacheInfo(hits=99991418, misses=5867462, maxsize=1024, currsize=1024) >>> </lang>

This took tens of minutes to run.