Iterated digits squaring: Difference between revisions

From Rosetta Code
m (fix markup)
 
Line 1,685: Line 1,685:
 
But note that while the task description claims "you always end with either 1 or 89", that claim is somewhat arbitrary.
 
But note that while the task description claims "you always end with either 1 or 89", that claim is somewhat arbitrary.
 
:But only somewhat the loop is 89 ? 145 ? 42 ? 20 ? 4 ? 16 ? 37 ? 58 ? 89, so it only ends with 1 or one of the numbers in this loop. 42 is of course far more significant and the one I would choose!!--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:12, 16 September 2014 (UTC)
 
:But only somewhat the loop is 89 ? 145 ? 42 ? 20 ? 4 ? 16 ? 37 ? 58 ? 89, so it only ends with 1 or one of the numbers in this loop. 42 is of course far more significant and the one I would choose!!--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:12, 16 September 2014 (UTC)
  +
:: You should move this comment (and my reply here) to the talk page. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 03:01, 26 September 2022 (UTC)
   
 
<syntaxhighlight lang="j"> sumdigsq^:(i.16) 15
 
<syntaxhighlight lang="j"> sumdigsq^:(i.16) 15
 
15 26 40 16 37 58 89 145 42 20 4 16 37 58 89 145</syntaxhighlight>
 
15 26 40 16 37 58 89 145 42 20 4 16 37 58 89 145</syntaxhighlight>
  +
  +
Here, after the initial three values, the final digit repeats with a period of 8 (so it does not end).
  +
  +
<syntaxhighlight lang=J> 10 8$sumdigsq^:(i.80) 15
  +
15 26 40 16 37 58 89 145
  +
42 20 4 16 37 58 89 145
  +
42 20 4 16 37 58 89 145
  +
42 20 4 16 37 58 89 145
  +
42 20 4 16 37 58 89 145
  +
42 20 4 16 37 58 89 145
  +
42 20 4 16 37 58 89 145
  +
42 20 4 16 37 58 89 145
  +
42 20 4 16 37 58 89 145
  +
42 20 4 16 37 58 89 145</syntaxhighlight>
   
 
You could just as easily claim that you always end with either 1 or 4. So here's a routine which repeats the sum-square process until the sequence converges, or until it reaches the value 4:
 
You could just as easily claim that you always end with either 1 or 4. So here's a routine which repeats the sum-square process until the sequence converges, or until it reaches the value 4:

Latest revision as of 03:02, 26 September 2022

Task
Iterated digits squaring
You are encouraged to solve this task according to the task description, using any language you may know.

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:

>>> 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]


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.

For a quick algorithm for this task see the talk page


Related tasks



11l[edit]

Translation of: Python
F next_step(=x)
   V result = 0
   L x > 0
      result += (x % 10) ^ 2
      x I/= 10
   R result

F check(number)
   V candidate = 0
   L(n) number
      candidate = candidate * 10 + n

   L candidate != 89 & candidate != 1
      candidate = next_step(candidate)

   I candidate == 89
      V digits_count = [0] * 10
      L(d) number
         digits_count[d]++

      V result = factorial(number.len)
      L(c) digits_count
         result I/= factorial(c)
      R result

   R 0

V limit = 100000000
V cache_size = Int(ceil(log10(limit)))
assert(10 ^ cache_size == limit)

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

L
   I i == 0 & number[i] == 9
      L.break
   I i == cache_size - 1 & number[i] < 9
      number[i]++
      result += check(number)
   E I number[i] == 9
      i--
   E
      number[i]++
      L(j) i + 1 .< cache_size
         number[j] = number[i]
      i = cache_size - 1
      result += check(number)

print(result)
Output:
85744333

Ada[edit]

with Ada.Text_IO;

procedure Digits_Squaring is

   function Is_89 (Number : in Positive) return Boolean
   is
      Squares : constant array (0 .. 9)  of Natural :=
        (0, 1, 4, 9, 16, 25, 36, 49, 64, 81);

      Sum : Natural := Number;
      Acc : Natural;
   begin
      loop
         Acc := Sum;
         Sum := 0;
         while Acc > 0 loop
            Sum := Sum + Squares (Acc mod 10);
            Acc := Acc / 10;
         end loop;

         if Sum = 89 then  return True;  end if;
         if Sum =  1 then  return False; end if;
      end loop;
   end Is_89;

   use Ada.Text_IO;
   Count : Natural := 0;
begin
   for A in 1 .. 99_999_999 loop
      if Is_89 (A) then
         Count := Count + 1;
      end if;

      if A = 999_999 then
         Put_Line ("In range 1 ..    999_999: " & Count'Image);
      end if;

   end loop;
   Put_Line ("In range 1 .. 99_999_999: " & Count'Image);
end Digits_Squaring;
Output:
In range 1 ..    999_999:  856929
In range 1 .. 99_999_999:  85744333

ALGOL 68[edit]

Brute-force with some caching.

# count the how many numbers up to 100 000 000 have squared digit sums of 89            #

# compute a table of the sum of the squared digits of the numbers 00 to 99              #
[ 0 : 99 ]INT    digit pair square sum;
FOR d1 FROM 0 TO 9 DO
    FOR d2 FROM 0 TO 9 DO
        digit pair square sum[ ( d1 * 10 ) + d2 ] := ( d1 * d1 ) + ( d2 * d2 )
    OD
OD;
 
# returns the sum of the squared digits of n                                            #
PROC squared digit sum = ( INT n )INT:
     BEGIN
         INT   result := 0;
         INT   rest   := n;
         WHILE rest /= 0 DO
             INT    digit pair = rest MOD 100;
             result PLUSAB digit pair square sum[ digit pair ];
             rest   OVERAB 100
         OD;
         result
     END # squared digit sum # ;

# for values up to 100 000 000, the largest squred digit sum will be that of 99 999 999 #
# i.e. 81 * 8 = 648, we will cache the values of the squared digit sums                 #
INT   cache max = 81 * 8;
[ 1 : cache max ]INT cache;
FOR i TO cache max DO cache[ i ] := 0 OD;

INT count 89 := 0;

# fill in the cache                                                                     #
FOR value FROM 2 TO cache max DO cache[ value ] := squared digit sum( value ) OD;
# we "know" that 89 and 1 are the terminal values                                       #
cache[  1 ] :=  1;
cache[ 89 ] := 89;
FOR value FROM 2 TO cache max DO
    INT sum := cache[ value ];
    WHILE sum /= 1 AND sum /= 89 DO
        sum := cache[ sum ]
    OD;
    cache[ value ] := sum
OD;

FOR value FROM 1 TO 100 000 000 DO
    IF cache[ squared digit sum( value ) ] = 89 THEN count 89 +:= 1 FI
OD;

print( ( "Number of values whose squared digit sum is 89: ", whole( count 89, -10 ), newline ) )
Output:
Number of values whose squared digit sum is 89:   85744333

Arturo[edit]

Translation of: Nim
gen: function [n][
    result: n
    while [not? in? result [1 89]][
        s: new 0
        loop digits result 'd ->
            's + d*d
        result: s
    ]
    return result
]

chainsEndingWith89: function [ndigits][
    [prevCount,currCount]: #[]
    loop 0..9 'i -> prevCount\[i*i]: 1

    res: new 0

    loop 2..ndigits 'x [
        currCount: #[]
        loop prevCount [val,cnt][
            v: to :integer val
            loop 0..9 'newDigit [
                mm: v + newDigit*newDigit
                if not? key? currCount mm -> currCount\[mm]: 0
                currCount\[mm]: currCount\[mm] + cnt
            ]
        ]
        prevCount: currCount
    ]
    loop currCount [val,cnt][
        v: to :integer val
        if and? [v <> 0] [89=gen v] ->
            'res + cnt
    ]
    return res
]

print [
    "Number chains for integers <100000000 that end with an 89 value:" 
    chainsEndingWith89 8
]
Output:
Number chains for integers <100000000 that end with an 89 value: 85744333

AWK[edit]

We use a brute-force approach with buffering for better performance. Numbers are assumed to be double precision floats, which is true for most implementations. It runs in about 320 s on an Intel i5.

# Usage: GAWK -f ITERATED_DIGITS_SQUARING.AWK
BEGIN {
    # Setup buffer for results up to 9*9*8
    for (i = 1; i <= 648; i++) {
        k = i
        do {
            k = squaredigitsum(k)
        } while ((k != 1) && (k != 89))
        if (k == 1) # This will give us 90 entries
            buffer[i] = ""
    }
    # Check sequence for every number
    pow10 = 1
    for (i = 1; i <= 100000000; i++) {
        count += (squaredigitsum(i) in buffer) ? 0 : 1
        if (i == pow10) {
            printf("1->10^%d: %d\n", length(i) - 1, count)
            pow10 *= 10
        }
    }
}
function squaredigitsum(n,    r) {
    while (n) {
        r += (n % 10) ^ 2
        n = int(n / 10)
    }
    return r
}
Output:
1->10^0: 0
1->10^1: 7
1->10^2: 80
1->10^3: 857
1->10^4: 8558
1->10^5: 85623
1->10^6: 856929
1->10^7: 8581146
1->10^8: 85744333

BBC BASIC[edit]

Three versions timed on a 2.50GHz Intel Desktop.

      REM Version 1: Brute force
      REM ---------------------------------------------------------
      T%=TIME
      N%=0
      FOR I%=1 TO 100000000
        J%=I%
        REPEAT
          K%=0:REPEAT K%+=(J%MOD10)^2:J%=J%DIV10:UNTIL J%=0
          J%=K%
        UNTIL J%=89 OR J%=1
        IF J%>1 N%+=1
      NEXT
      PRINT "Version 1: ";N% " in ";(TIME-T%)/100 " seconds."

      REM Version 2: Brute force + building lookup table
      REM ---------------------------------------------------------
      T%=TIME
      DIM B% 9*9*8,H%(9)
      N%=0
      FOR I%=1 TO 100000000
        J%=I%
        H%=0
        REPEAT
          K%=0:REPEAT K%+=(J%MOD10)^2:J%=J%DIV10:UNTIL J%=0
          H%(H%)=K%:H%+=1
          J%=K%
          IF B%?J%=1 EXIT REPEAT
        UNTIL J%=89 OR J%=1
        IF J%>1 N%+=1:WHILE H%>0:H%-=1:B%?H%(H%)=1:ENDWHILE
      NEXT
      PRINT "Version 2: ";N% " in ";(TIME-T%)/100 " seconds."

      REM Version 3: Calc possible combinations (translation of C)
      REM ---------------------------------------------------------
      T%=TIME
      DIM B%(9*9*8):B%(0)=1
      FOR N%=1 TO 8
        FOR I%=9*9*N% TO 1 STEP -1
          FOR J%=1 TO 9
            S%=J%*J%
            IF S%>I% EXIT FOR
            B%(I%)+=B%(I%-S%)
          NEXT
        NEXT
      NEXT

      N%=0
      FOR I%=1 TO 9*9*8
        J%=I%
        REPEAT
          K%=0:REPEAT K%+=(J%MOD10)^2:J%=J%DIV10:UNTIL J%=0
          J%=K%
        UNTIL J%=89 OR J%=1
        IF J%>1 N%+=B%(I%)
      NEXT
      PRINT "Version 3: ";N% " in ";(TIME-T%)/100 " seconds."

      END
Output:
Version 1: 85744333 in 1447.08 seconds.
Version 2: 85744333 in 718.04 seconds.
Version 3: 85744333 in 0.02 seconds.

Befunge[edit]

This is just a brute force solution, so it's not very fast. A decent interpreter will probably take a minute or two for a 1,000,000 iterations. If you want to test with 100,000,000 iterations, change the ::** (100³) near the end of the first line to :*:* (100²²). With that many iterations, though, you'll almost certainly want to be using a compiler, otherwise you'll be waiting a long time for the result.

1-1\10v!:/+55\<>::**>>-!|
v0:\+<_:55+%:*^^"d":+1$<:
>\`!#^ _$:"Y"-#v_$\1+\:^0
>01-\0^ @,+55.<>:1>-!>#^_
>,,,$." >=",,,^ >>".1">#<
Output:
1..1000000 => 856929
1..100000000 => 85744333

BQN[edit]

A simple solution is to compute all square-digit sums in the desired range as an addition table, then repeatedly select from this list using itself as an index so that all values that end at 1 converge (those that reach 89 will find some point in the cycle, but not always the same one).

   +´1?1? ?˜?(?2???) ?+?´6?<ט?10
856929

It will take a lot of memory and many seconds to compute the count under 1e8 this way. The following program computes the count for numbers below 10??? by using dynamic programming to determine how many numbers have each possible digit sum. Then it finds the fate of each number in this greatly reduced set. This gives an exact result for inputs up to 16, taking a fraction of a millisecond for each.

DigSq ? {
  d ? ט ?10                  # Digit values
  m ? 1+81×2???                # One plus maximum digit sum
  c ? (+´ d ??0?»¨ <)??? m??1  # Count of numbers having each sum
  s ? m ? ? d +??(?10??m) 0   # Sum for each sum
  e ? 1??˜?(?2???)s           # Which sums end at 89
  ¯1 +´ c×e                   # Total up; subtract 1 to exclude 0
}
   >??DigSq¨ 1+?16
+-                     
?  1                7  
   2               80  
   3              857  
   4             8558  
   5            85623  
   6           856929  
   7          8581146  
   8         85744333  
   9        854325192  
  10       8507390852  
  11      84908800643  
  12     850878696414  
  13    8556721999130  
  14   86229146720315  
  15  869339034137667  
  16 8754780882739336  
                      +

C[edit]

C99, tested with "gcc -std=c99". Record how many digit square sum combinations there are. This reduces numbers to , and the complexity is about . The 64 bit integer counter is good for up to , which takes practically no time to run.

#include <stdio.h>

typedef unsigned long long ull;

int is89(int x)
{
	while (1) {
		int s = 0;
		do s += (x%10)*(x%10); while ((x /= 10));

		if (s == 89) return 1;
		if (s == 1) return 0;
		x = s;
	}
}


int main(void)
{
	// array bounds is sort of random here, it's big enough for 64bit unsigned.
	ull sums[32*81 + 1] = {1, 0};

	for (int n = 1; ; n++) {
		for (int i = n*81; i; i--) {
			for (int j = 1; j < 10; j++) {
				int s = j*j;
				if (s > i) break;
				sums[i] += sums[i-s];
			}
		}

		ull count89 = 0;
		for (int i = 1; i < n*81 + 1; i++) {
			if (!is89(i)) continue;

			if (sums[i] > ~0ULL - count89) {
				printf("counter overflow for 10^%d\n", n);
				return 0;
			}
			count89 += sums[i];
		}

		printf("1->10^%d: %llu\n", n, count89);
	}

	return 0;
}
Output:
1->10^1: 7
1->10^2: 80
1->10^3: 857
1->10^4: 8558
1->10^5: 85623
1->10^6: 856929
1->10^7: 8581146
1->10^8: 85744333
1->10^9: 854325192
1->10^10: 8507390852
1->10^11: 84908800643
1->10^12: 850878696414
1->10^13: 8556721999130
1->10^14: 86229146720315
1->10^15: 869339034137667
1->10^16: 8754780882739336
1->10^17: 87975303595231975
1->10^18: 881773944919974509
1->10^19: 8816770037940618762
counter overflow for 10^20

Fast C implementation (<1 second my machine), which performs iterated digits squaring only once for each unique 8 digit combination. The cases 0 and 100,000,000 are ignored since they don't sum to 89:

#include <stdio.h>

const int digits[] = { 0,1,2,3,4,5,6,7,8,9 };

// calculates factorial of a number
int factorial(int n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

// returns sum of squares of digits of n
unsigned int sum_square_digits(unsigned int n) {
        int i,num=n,sum=0;
        // process digits one at a time until there are none left
        while (num > 0) {
                // peal off the last digit from the number
                int digit=num % 10;
                num=(num - digit)/10;
                // add it's square to the sum
                sum=sum+digit*digit;
        }
        return sum;
}

// builds all combinations digits 0-9 of length len
// for each of these it will perform iterated digit squaring
// and for those which result in 89 add to a counter which is
// passed by pointer.
long choose_sum_and_count_89(int * got, int n_chosen, int len, int at, int max_types, int *count89)
{
        int i;
        long count = 0;
        int digitcounts[10];
        for (i=0; i < 10; i++) {
                digitcounts[i]=0;
        }
        if (n_chosen == len) {
                if (!got) return 1;

                int sum=0;
                for (i = 0; i < len; i++) {
                        int digit=digits[got[i]];
                        digitcounts[digit]++;
                        sum=sum + digit * digit;
                }
                if (sum == 0) {
                        return 1;
                }
                if ((sum != 1) && (sum != 89)) {
                        while ((sum != 1) && (sum != 89)) {
                                sum=sum_square_digits(sum);
                        }
                }
                if (sum == 89) {
                        int count_this_comb=factorial(len);
                        for (i=0; i<10; i++) {
                                count_this_comb/=factorial(digitcounts[i]);
                        }
                        (*count89)+=count_this_comb;
                }

                return 1;
        }

        for (i = at; i < max_types; i++) {
                if (got) got[n_chosen] = i;
                count += choose_sum_and_count_89(got, n_chosen + 1, len, i, max_types, count89);
        }
        return count;
}

int main(void)
{
        int chosen[10];
        int count=0;
        // build all unique 8 digit combinations which represent
        // numbers 0-99,999,999 and count those
        // whose iterated digit squaring sum to 89
        // case 0, 100,000,000 are ignored since they don't sum to 89
        choose_sum_and_count_89(chosen, 0, 8, 0, 10, &count);
        printf("%d\n",count);
        return 0;
}
Output:
85744333

C#[edit]

The largest sum possible for any number is 9*9*9, so the first 730 numbers are calculated and stored in an array.
The rest is then looked up. A limit of 100 million takes about 6 seconds. int.MaxValue takes about 2 and a half minutes.

using System;
public static class IteratedDigitsSquaring
{
    public static void Main() {
        Console.WriteLine(Count89s(1_000_000));
        Console.WriteLine(Count89s(100_000_000));
    }

    public static int Count89s(int limit) {
        if (limit < 1) return 0;
        int[] end = new int[Math.Min(limit, 9 * 9 * 9 + 2)];
        int result = 0;

        for (int i = 1; i < end.Length; i++) {
            for (end[i] = i; end[i] != 1 && end[i] != 89; end[i] = SquareDigitSum(end[i])) { }
            if (end[i] == 89) result++;
        }
        for (int i = end.Length; i < limit; i++) {
            if (end[SquareDigitSum(i)] == 89) result++;
        }
        return result;

        int SquareDigitSum(int n) {
            int sum = 0;
            while (n > 0) {
                int digit = n % 10;
                sum += digit * digit;
                n /= 10;
            }
            return sum;
        }
    }

}
Output:
856929
85744333

BigInteger version[edit]

Translation of: C

Translation of the first C version, with BigIntegers. This can get pretty far in six seconds, even on Tio.run.

using System;
using System.Numerics;

class Program {

  const int MaxPow = 301;
  static int [] sq = {1, 4, 9, 16, 25, 36, 49, 64, 81};
  static BigInteger [] sums;

  static bool is89(int x) {
    while (true) {
      int s = 0, t;
      do if ((t = (x % 10) - 1) >= 0) s += sq[t]; while ((x /= 10) > 0);
      if (s == 89) return true;
      if (s == 1) return false;
      x = s;
    }
  }

  static BigInteger count89(int n) {
      BigInteger result = 0;
      for (int i = n * 81; i > 0; i--) {
        foreach (int s in sq) { if(s > i) break; sums[i] += sums[i - s]; }
        if (is89(i)) result += sums[i];
      }
      return result;
  }

  static void Main(string[] args) {
    BigInteger [] t = new BigInteger[2] {1, 0}; sums = new BigInteger[MaxPow * 81]; Array.Copy(t, sums, t.Length);
    DateTime st = DateTime.Now;
    for (int n = 1; n < MaxPow; n++) {
      Console.Write("1->10^{0,-3}: {1}\n", n, count89(n));
      if ((DateTime.Now - st).TotalSeconds > 6) break;
    }
    Console.WriteLine("{0} seconds elapsed.", (DateTime.Now - st).TotalSeconds);
  }
}
Output:
1->10^1  : 7
1->10^2  : 80
1->10^3  : 857
1->10^4  : 8558
1->10^5  : 85623
1->10^6  : 856929
1->10^7  : 8581146
1->10^8  : 85744333
1->10^9  : 854325192
1->10^10 : 8507390852
1->10^11 : 84908800643
1->10^12 : 850878696414
1->10^13 : 8556721999130
1->10^14 : 86229146720315
1->10^15 : 869339034137667
1->10^16 : 8754780882739336
1->10^17 : 87975303595231975
1->10^18 : 881773944919974509
1->10^19 : 8816770037940618762
1->10^20 : 87994965555707002706
1->10^21 : 877214809753814412449
1->10^22 : 8740475212714948184620
1->10^23 : 87086767569032964273481
1->10^24 : 867912763131207135645491
1->10^25 : 8652685884347431487002838
1->10^26 : 86292591735549905389544085
1->10^27 : 860834491746260610360036431
1->10^28 : 8589383648492973833587962133
1->10^29 : 85719021282987319689186339605
1->10^30 : 855551075003449256539175506135
1->10^31 : 8539846767881104092122936276127
1->10^32 : 85245373514507207808857201531419
1->10^33 : 850921798797738318678358430121498
1->10^34 : 8493602724656082624921256124945709
1->10^35 : 84775765928320499747460839463166887
1->10^36 : 846127234701773214379999133850790428
1->10^37 : 8445101119798901092741398494615146552
1->10^38 : 84297231641833173945386163054551847907
1->10^39 : 841596309978956515337376882969248454407
1->10^40 : 8404688192812158407616126296428757287918
1->10^41 : 83966751636707267524727665346136900559808
1->10^42 : 839249062380369832617111284115323596416189
1->10^43 : 8392404334111393647768734710144578436411820
1->10^44 : 83963458265257975880706035079312646291089162
1->10^45 : 840390620671402119260216748725664301844515595
1->10^46 : 8414380030090502032224993998030998898525187113
1->10^47 : 84268378296544752164579356732419005387066100619
1->10^48 : 844021806190251380758758476585216084473498054164
1->10^49 : 8453427257465803796850958549692384862623307213954
1->10^50 : 84654382110763756920355712358557288888652143589824
1->10^51 : 847537750217936548550698726085731005366031699187697
1->10^52 : 8482595213704622541116090344851904585191448008008698
1->10^53 : 84867114171087369978017651353669784240040553506347863
1->10^54 : 848763596449838290475849513610494144653829069301555744
1->10^55 : 8485560484449848898784875907345401899210439410548661905
1->10^56 : 84809241613331707710051455489300240267084096119421192555
1->10^57 : 847435762855526547824875506635678396375585724580676401281
1->10^58 : 8466611716350744168054316461343227422117005648835357501042
1->10^59 : 84584794275749872157313978459784905712596125963065261887087
1->10^60 : 845072003706634444132974487900963836188835216550117810064042
1->10^61 : 8443993493344896883975002240891650144660444520675597442455846
1->10^62 : 84388114632696697235622301117847815843833846024601175739193818
1->10^63 : 843550873686677877815689986525235580589881417969543147823955468
1->10^64 : 8434235773893302085490040550865199018569738474571414542759091420
1->10^65 : 84349704267294170985441634483996250787548886013951222960902661326
1->10^66 : 843754473866041852258692025296354310048924258957916675280270848383
1->10^67 : 8441681459520956437757926334685945498961397097395903879157454648255
1->10^68 : 84470346186515545447015226246395087364669380975589204241143094714939
1->10^69 : 845322904478358163301387625325558514367250680088175647529431667836984
1->10^70 : 8459894886866423548013102102792807954026974401198186041921374671243280
1->10^71 : 84666946651672233790199404593444235036570835062615369577576893503846807
1->10^72 : 847334186689171226140326334304533885325304121282085041331744831976064350
1->10^73 : 8479611353077227882670645671814119173057689480878540635598355377828682030
1->10^74 : 84853427154299528465645782338465354008595064980299709100384597454288492601
1->10^75 : 849043816798387454378741585441510256257380507579571260789337785619852662347
1->10^76 : 8494856623561856764693867992374031564067482173292744174563186543401165633828
1->10^77 : 84986053947449161776274594245379439290411038180766518290148488651233497246177
1->10^78 : 850173060522433967868762132659331655304647077578564191004961947049948444228365
1->10^79 : 8504307025056582630550030771632855466797975344124296918801658700334809780702180
1->10^80 : 85064277463177819389470781000622284519150163101058649012431344960771964694651571
1->10^81 : 850819394401164074041611461274974545538571046366755739155832724445684685332968364
1->10^82 : 8509704926350516030551921703403722812551632988675827388709515859909259694851647834
1->10^83 : 85110487385572993176128742106677248626395367895834794577983294930763809503319428014
1->10^84 : 851229369385484114012959335791260147114430529630506351180704055826749898923602659534
1->10^85 : 8513481307977862280230328507187688326498927519035854456240791004629338052316252944962
1->10^86 : 85146211618619610403764635439165512633290370187486987569410348341895803492714570487527
1->10^87 : 851568818184158929602427279369759555161328403821517914312791180281061345268793327734747
1->10^88 : 8516622700452095396072535230209391313806399904195398975658231816363535402709890663189362
1->10^89 : 85173334571538953250258781660855404353386662001559167780912035060599928280076465921472154
1->10^90 : 851770344573699439297915741793926110106776082569441364749653121400250416057006702446954384
1->10^91 : 8517598250615252557316601155045090636911412094296867452464613221521534622516854479200111167
1->10^92 : 85168762749001784598676830952569236245621633296172168977732463493080042840432604954811508256
1->10^93 : 851540008029830880300994057100452233115864754809360142651983875738294861965389543527957072529
1->10^94 : 8513047953516561208480829418619110455666666761484728667018453838522192578086491705360981209049
1->10^95 : 85097247949654801901491432145587952810159950536920233184462924578646829963281410434249631392723
1->10^96 : 850537149051806438025447330906036177346231271896967500380026706058200824325895506679143940414076
1->10^97 : 8499972063859782028890346555815409171233558167321697969098574428852568869015102044124776256646518
1->10^98 : 84935580971302195864938049552661540297299353108396246935346418128128262766226035981031392864950607
1->10^99 : 848621012961290009929016807175952691990221212867104144408323613154869710828195585404753698625209870
1->10^100: 8478055976550795533989641628119784566456389856922225836863058100833148222237810283684193376704453622
1->10^101: 84692661332197101015983198300119859021702958967680338663444073316601738058829066776089854542212989340
1->10^102: 846004662712490384489176693903976456406275569081651590341922175721977994554886920688273660628038615530
1->10^103: 8450629841618941841374846246720140022439681757127967533191099545085398501977517119347590327770355321434
1->10^104: 84412639494761330308514535722479416772282357055894579094485879248099506197188362019049795338340624012301
1->10^105: 843220166084720035321606859999967460448483170329902742792363249370695697719160653283805304587721253017361
1->10^106: 8423689005669735317756774969292543189691443702455489905512071638162495163070141112432829369072721001438803
1->10^107: 84159548379569442293630345909810266521615950102980331577692671042526244954280499017296253855362379723006790
1->10^108: 840920167282889832940657933809381773679300456385012266847912623238503960535214111183445921289786823658787691
1->10^109: 8403598353292268590336072525335623277440130064609705442801138149158666937015259427681264313068009086176250877
1->10^110: 83992749011849425594102987318631343125622400751939263715871477971837511761611183001200425931121955124445796563
1->10^111: 839631974560024541066376425245637209524348207271199051409239974688509717594962340253156692813877667108301744106
1->10^112: 8394779353899880586911134833609814206804364692659236923514863543225711320256322212826981126418518735060793772750
1->10^113: 83946601270617664302492383399919020477597958169554254483427394351411967951182614872496928963913457889190568112395
1->10^114: 839593227424935347188648037914393774879073981203516129165175570585940253228070179608775423063767686629889237370343
1->10^115: 8398535261578467944398129353883159481758437570367304189005134894914805401432837029302170166444526790097924367111503
1->10^116: 84023843454035852573265864848894850643884841292094243539904097304702512644040636408661949798936846401719392744529025
1->10^117: 840737765642794051888186278689979033461813727159185802383506635349749710904137817158720048137762867500712046819247594
1->10^118: 8413403299481449636810051588954342805968283459950501545886836317455395792682501121057127293827832135213161768368219253
1->10^119: 84203459731804372791295301224645565239535230919259257974175798305292830946699497417228262643161300276076207336625610134
1->10^120: 842809268870874063928885672713544280450769176965833988262182876494615882586594316787946370157216295565316434490326651405
1->10^121: 8436537269586024582444789405103627999973329698521927747116692346516613959566150658077870051889885971990610726551245907282
1->10^122: 84455834344493608566315467696492314037782180434561295410998128008344540731783028824982047820404300118155481934579800141088
1->10^123: 845514639154622335439026676162812633638571876699098045234551483696103405951596419680669149347110570074557588539445728510018
1->10^124: 8465152995954852314095072658655816590955469635973935795588056505433337123869586772927379963580066217729825686876675663167185
1->10^125: 84755406288317367647502726863830973688269578307186392087532645236745222242400899454278308118658816773299796554538815106946662
1->10^126: 848625504457571338232292398385105460655500154346371677749525133665065153305513976195700074289083571929361989667922170389107535
1->10^127: 8497247491606457974773951687008958065830712221221672428563728962952710482456410072989046167006589524549671922187923421293104261
1->10^128: 85084714431998555684542412118169794176587616263302937222006603793644213669647672530734324336062593730448168482490463581934163209
1->10^129: 851987927694394695842385097569051414740093541977628250087327027568711635166984043208988142923913857460666864202533480163816074202
1->10^130: 8531419217683749662902274331887012779776215625286974893028601621512119501265453211740142140831505959855845555950934192931323135091
1->10^131: 85430328139300947018442720074404606897400678689137949606360116452651125380471435832121200992460847030421534496794199309573886358524
1->10^132: 855465315738173678760862649212737686693137920889352300831379756993911053972720948424411094181836238208234099960617208156267778781898
1->10^133: 8566203985676470440731224844367227028626203877233764214723360280287402102216808298088324826982839611954201836019907306964986020317159
1->10^134: 85775997358049954163025460353028420873131413549826277262221703709641647709337930451236309466814929967802548158100676076963356874077035
1->10^135: 858874654517946257331373751494744684697894687286199674069180793094186295509981754114205911144101048543298035168442378180859108201796265
1->10^136: 8599544133518541190729470603965905587527154359647919952067163387372304281858539652528774948622565592410227289026773964696225096635862537
1->10^137: 86098884446696506849205217476298801856531759087495262915652873693105198539437793396587535380166248596923904768946564631519624154608822690
1->10^138: 861967488519975027278659230468829107364665645483477317437018410008632482976457415861327948074033275571831029811199126478567233637434713802
1->10^139: 8628801966906107103794870359515838367624418995487887432274900379678186901156278250379655878138155038529537336691569617421296295380371760340
1->10^140: 86371751432755850734211313782502597168356853194847423187885795766026223040981206579899447886878504305410691164655066591417733867217657409811
1->10^141: 864471062463358928035890212882855394973552211508640566300839272774044673907427647532988481646812971525433236154760961951830488066552534999023
1->10^142: 8651338962123525381382585497345224517243502289336494055582727855432102914169042172702045582244422419844751183011546403203406688188535065077322
1->10^143: 86570082053814840071676786387711389238199465843648958320947100960909947309631925605038600684044214317481472519092808161209930532770395663770781
1->10^144: 866168646140024454232290939392340553469733795408720476998913174615258133882405119795696045709637935842786961080230573092926927470162827652342923
1->10^145: 8665363711233461583131718626220667710334246969605082108793313417232622503508731655200858605762988314178800129280340217618589701154413543656985768
1->10^146: 86680527755718649759685176307373285371506102115475732941737986612281052787642500311258388070351873908022137905978541886761549544508105211635516228
1->10^147: 866978935858429040804614015372620947011463145811894778944224644840965029116656072947888551840966766335486237021126810837001330600241756682469168167
1->10^148: 8670631140523282973971782080001983833731728340683112114855303301784698980848631949401710274261706144525939388879900371490715240712970153368815534367
1->10^149: 86706559321625893654219061535654670226251515192444823540942376968150754206994835939850628017684192061166333847144398807182953462336351429576667101351
1->10^150: 866995894677201410904770273181085867673520667933560075983432420563205634118449857866990239690356187026767184415381247787966191029231566995411712911007
1->10^151: 8668649286520103298110693613874545220931966501441595187981603679256058680844995640768730126032798906817769842612438159035028750557047429668482063638625
1->10^152: 86668457782766182106365998476602923925113815986769356535308077952464501916435251498791257040294658754611725463671013282549956507413788549087648641846098
1->10^153: 866467232703588323761623292919053615805349473853030836383461617368439378625942338161355425237008265428317731976385096608438676681105037540093273504844483
1->10^154: 8662252981878105789584061011021060141399639813427794770240893198981230593010055187290079715875704519459746894597845545067244523511239294665336648278040637
1->10^155: 86597069279331973627870277117295560971212134258887952139164522646395290648630256852565891654443101159408986732677200310584518068043543948322349006452151755
1->10^156: 865714362687450998043815943867869054665470989918126698474385057239018213934641784542968962053533734187459455324174294359416548556344040132940037126509574890
1->10^157: 8654658327106972791669605830924233521101999366448366696413768175647650132585930189666095910251594686212883617926599504812573308511497426284397573601012279375
1->10^158: 86523281525978906450144206624921581416241237156433481656480265807221677603408225926171146763083505699243678209180779205409664726743837972061944584770689307884
1->10^159: 865020895640273664634221805288900266279823536202089144549284863821848719729621871794854384484450827784422753936554110189466495950347084459481187597192205418793
1->10^160: 8648333092180248361231569929436471172695159651290083551629519955961094099569126130177616360908316038756710670681403062201420194924583089357076176913473551489817
1->10^161: 86467082158234917505257945501916111178867219946014491779173744896435884955641567959785164124416182157534690566327230254824916687748403437579928718500003240088350
1->10^162: 864531718178004477579328299078477740103286866685836705893778259068484361910954920040103346818883066344256341407619054890526196017651798464562371916742275514078096
1->10^163: 8644119047175677532754512732881650797783914476890547159332150786248814701309170973662384365694682365725345684746385423597293333794783119696118927072215437319257440
1->10^164: 86430511442728833953474406348743455606569468731398316056046331180619896926256415048429340648516795318606702261936259185655191185135897215949312081438663747406505352
1->10^165: 864203213098456917179089416334228304803823157191121623901676225339391935646182411440896586741908176885056293738329991372321077500327578045864902843222595891799567806
1->10^166: 8640965882937716485397501931334347152458001316883441819080947648945115844393354807154067487578858173020177220644862075271361572635046969133096397262003200031012088816
1->10^167: 86397460514795855219888182686863463583022651832659752347275952763764870817118284418230695316619420880587709262736889606859182358084380751509419091890525660564555427901
1->10^168: 863826108212994733968753648916344180650270462271158599364947882912609226359091464049878200409969696906956615971127829923562306335697890300823826175463538490380690739451
1->10^169: 8636399468812722554622656891339014659756492411987212588808905238038013917598506567892281064118123161436622230807092368588797239398601813995192754544282167394183895076163
1->10^170: 86340550115810963737132600434455522470569445567277315861058710137153565317691542777881722463942842675087823559441027338766864911001309033038846460880092552344039469739333
1->10^171: 863113184960208420682902249205892077992533001572322252023394244226663293763935715908577243441852383675532094794872800029273307246757568352279588128123766425105968866901616
1->10^172: 8627549056314884656085758650988354705410677397535432663170381749859818305061157900374193823460026020453498398255516128456675018659144733546914336443286666016242464534892623
1->10^173: 86232446087184919482081527092941285304657064140735231468756283252665952399658175811031283829089578449010792434421243969476874537741281407520376270606159166994743509790579870
1->10^174: 861817857595365546195764878782545616412299953305644834253961921594884506100246389780862738254371890536265325177953967353668527189935970175680262525003852416511702685102182441
1->10^175: 8612335411616785098274560702996374588709528639692603595138354547577954344338556793950612531193867992899537665396961790126485441261162978457728277055887715863633046672606059241
1->10^176: 86057252772491914510352333999906105981829362686305939974861378757443054109080895856413489539176272606128074757709987886142026849718775210459324179053970375798833643674653299146
1->10^177: 859838436879206181835365262115744403026095659693962971028229600944239019463572625102155108901336581755998940232822992950041279925927692909953068033242268448253671491806888602951
1->10^178: 8590374261184353667886274109282646777037742508789286305748696410656346178086122686714500258721415114247208450827752012664251102329405203342553434732973912035701717886506338020826
1->10^179: 85817803266299770850481644986303982631777128860751635552122752691142344851161667201711396408118161670019162565320967870657007411787078526807901817918683806698015174468543495149290
1->10^180: 857270931762460513913686774682703804324648224726040993071441204202938055376046440338560584347422946756765924309947940529727632781070244946475500609399411949683310388884381375784900
1->10^181: 8563286235265958004060828215056362716815395263188715179579008718784822735717230155520124874918608746486038288964871349973344482831835476012896645188257511452828884518822322381868751
1->10^182: 85536506257695171155764934949044365934306619258958532693184485997594236754853608694928818673632500990117929221007432007050799573098773278108453310625432989672233773221665984566985995
1->10^183: 854395246301416621734481057207967339862582992135509483575290027545350116527551368346220282638515725751863036555147858491593940486596084736024013227696715945480172650891444104216038874
1->10^184: 8534347782308749360706135913155759188845911594327933372849111132502671161496334420163904587424902551554260396210079867764136411801104476918881616206260973044707888081268917988811150838
1->10^185: 85249942307314506171903880472476276738180469673363011061550119400987556101451609644450156397637792635015315854436060260243452215710896132576011311208019157400087495036186110550299101573
1->10^186: 851604669298520104411896383155212891608415861472826352206829071810468404388469834164266030803667279410619332283818403448641099135191033340387858650321494900510343924107016585921016978274
1->10^187: 8507653139600643336183748904571443328144024262070249799701460854985028722322233794461184321883481989831191858421401529058385608717609471948486505331480282427844359667187865490014911613477
1->10^188: 84999508275236126020381830508721543111473067554541966121589517605650398866751293320363799608712233989549184897359325724581354866372415617540113985299280733097725364579425684134507256488872
1->10^189: 849306296274651882683597422387001923066889384195634499192702671890502375676555190136845726720160747215701213796501622133175006452307225424987441822517508280951544748121555031660346304639001
1->10^190: 8487095911796817623434988696115120825517986522671534265823536015609746863774499420587993803271710140150813684221232159026871093033542365679393034583857094925097687013070985086109793273080806
1->10^191: 84821370246558618609839073367520567864334999557370002647757230099277664105830851234474210899445947000757007737070796386462591548949557365070963572571938326301912601377555644042593381481793406
1->10^192: 847825310704237766880070980506466839658817888477084199818418242818651205859175872441362805453796299246427513786781377975949558744142534256078247658163358081519312966146099874702063865152192028
1->10^193: 8475489555842905339842177447569741889165387333475856347815246130384309138300825424276838743453380208632107646061552066006714782109537135813874993527510102283805650143962763452053420700390547699
1->10^194: 84738701485690450024204013592451605689013445522452704386773936803484296887639018283654199502249150235096649421520132242000546408214958227307607245837895669350870541210854287264223165212086998226
1->10^195: 847339745670078204744803652316933944651393806640268021489971965448240790293322017482045797037713314415845471889231439866706574167693441163081038944023000406430511708854956075209156416422852179500
1->10^196: 8474053834141387286935964031508774220009550200077496813045300456052204100457807211493137607068260269409818097530282626325036633749271383972601174815602843212760330743419406501022962731951260401758
1->10^197: 84758029161467432826119523898351898166282436501022577393790061641703167401164409394596608786688863136133007710604265705419119450632223820509239634351960138619310640443557197024847616720893834274556
1->10^198: 847859155127420710222264067465116270942345054705199086260046652911576677856574523726808872321246548759971208827865770218551918373067777291678034921219960068578854130134085087015093149046394684100436
1->10^199: 8482352079297050413772331207215755280136129216773296221264447386959877587192996245987959911290858363977880814068455839545348484912691954109930202230242025230487816060905500273627824722575046074286281
1->10^200: 84870048617336420197389727058863637424671320482647512598431088512958837365267475929180277480415786149971408009142371369019940386605860817912162814180167542797887574063677218639448400450114606809880493
1->10^201: 849246096864711958382140828789832341037541146449645765069443078515013899970754673189319764864878892878621617974941584582320988065756019066241199502894793046393859712076059928423517853448438863067863226
1->10^202: 8498624925606251826356755549843759984710649122272275679601866626755415511646464540638291701107135708359249734273392831194179172090092563707579355305268689407169443037588913674810901899690254156949367275
1->10^203: 85053974280141213857917842958407824057059580960693420355947997850134934176999635011238282707984566250378973275121221997840304574485093785863913446713844175190847992565857356412233852383266765346485977576
1->10^204: 851267793619122872630161782552104405308466360210406324429007428807568945258070114676614779203675989708980801172282855929544686979305743506670689733623543666749958573824475094895872235404030549992394708150
1->10^205: 8520367073359573551884982418477013557872986932518885258980976615694060910595076784527929984289747991467246665285419316072687197970688845733149905180272321105942958007079330817594754267934705067270350499956
1->10^206: 85283687596660830853502342927042854500321341431910436337225191217936420987092196489885047475301196582960695295636335734026004076930907280217960505685464052960893990657933932574032561361873483568439847208942
1->10^207: 853659202819987541247160120887834521284760886339623274004394773066680299538480440121545335974469636403243323858304782951228852284398676153012813966360440529328380943838264684632008844950545647229432408419763
1->10^208: 8544952483138354272479452096326871415134170280533803383323382424225457971898051136208471099688648406254320867700931409630655569469573762186473633746768288944756293766713800079402839068636993722539464464014343
1->10^209: 85533733751997391022351921893082947709535591919068528290332852883967864327556645461585949789541151338595934256435388217939077881109820952288423214884499900454917289123598440879211618935608105485422232130901905
1->10^210: 856178628495280232427926168171704244059740501955488094383750755874097867668689843542569526012394028099851590049094767507865596216897633456922557606621505076739639542878814850925266187250164585329019683542629923
1->10^211: 8570131419693618760966628804173079377257638567195555240493311797353797176489667120305647330718511690292693777674170531508951053735086796114378779311384689107558641543989958869638931709314824117850451000380143021
1->10^212: 85783575440047109414461631493979767235315177615543985312544659159056610182875530781537114391430809057845669077275617329819355730217516493005290650519511006772034807212815853844586588988998227020982705473135728765
1->10^213: 858642157725030348223249509804854637186812832528125424148240160404301905107061460749243511335395491708297289251008381529398185566019895635547713725083517506594429645460660280089932247894935780442351898303313140945
1->10^214: 8594287902664891352913658993716294858626490086433812797669386361846753520746735854191540089415236757792436360765472598893490276479705293275725004645785633334970346652528315678317371791476569985195862855380417401542
1->10^215: 86019274419595998866603848298462306888943095199436257368964632161654631977139765349618577697513221456293489609436575083556837195728003126429131084775756767513323846022083954060095590650961801996674310643811350499369
1->10^216: 860931655618474553063989578082933761682457487457489431016612890143003640365600635223968806347174143526789184001346670039335478957198921437817108109746919660278785057686592225736631570790200460497279046021138265882633
1->10^217: 8616435837729622438277275972924774728615421337934287445283316837787898004557496433610326251817310796184207726389126647218963569950986844300319174321919640256132751161493356727133356946791128243709978104039611221929848
1->10^218: 86232688597037059510650496264090044650582001854485728865997396326431091394758611347974329812789632648546842598755241789989941130068748668444311151669575147062603211288550024198424668424830168061712646711077510494361276
1->10^219: 862980094753456140909290085044350220214633094993933779019549067941866017572800599010552481547901256759922208947964802924199156525319895138745088257779570795905170294076748630599291864563865074304312620545350757654949167
1->10^220: 8636018033559847409410591107268210323615373240747163973441778682144682091271457867694794590752142037466191114879096481073228275415949941743493243536215269195973060634460249426462226091308923903368436341962027769078827045
1->10^221: 86419056489171874993789903489060892796455772565320723803637734001174467305715397474011039116397479926656101081127323729931224029537185192310507718579127400181923630610893970171709931933408787373551201437680240028108283958
1->10^222: 864744809847891662279169612523698598292488130571716275496525629546147011808378355197408294680827690818106146785428930909260093817332410616456120307490986571108036081906704392578762581319448395342866886631949686317950079685
1->10^223: 8652627854354814142021372274236655285412150520596931780504767483938734335443732380812376622197005225828947530209843225214814025134173901180081812700123059474516130142427254496259962223594226063501914926447312107963923255816
1->10^224: 86574251920745435851516366426371437236500297164193572646840936487152446338309838340335914152667764515000963423743096085244510673418048367379825329583910629778255879869131857325574114859632491805222223301052145753142373402038
1->10^225: 866181808148306233153035741070162251220868553540999914228623747312278276373367606857723265686649243714013350573228296681022846168327651205292941587217634862968933831862883106033509203213506996294508078581405379889390718900884
1->10^226: 8665782332173490493624385682733920863071548417814598549460323221230417435701507196058986103580683262649034387808689514519733914026030490404939317647480340690773539215255948949250489348489232493792231877166169779541100947510992
1->10^227: 86692919814710675783589991859619703285754546114420206472621039807364718363865261702270566986525194821577798634423416768340074070191330534224131123412508988375899005313698308076230449814177068560441644180880325653197748136923185
1->10^228: 867231990206473247052871536000445102504192081962389666619381949130498077603334870783904602961079237586504849633880397962186289424840869477113707180313165669320870472468535571056811158182157681436281093030894644992830298477981244
1->10^229: 8674838596801362677923547970017972903037995901012236697795083419765821418590394410295854079897879829098141309577554554785416139269074776459368918266410283727698808695686584095897235693981445795558726984321580750493111552025864339
1->10^230: 86768211402812128806590576564537513494737520987736487082881857738963221877281843731844788716420658593474347727365894819526796319707828593251356370569187398794672340428112756386987781701631240923503544557476729747177320351749598558
6.0396929 seconds elapsed.
It doesn't always get to 10^230 in six seconds at Tio.run, sometimes it only gets to 10^201 or so.

C++[edit]

Slow (~10 seconds on my machine) brute force C++ implementation:

#include <iostream>

// returns sum of squares of digits of n
unsigned int sum_square_digits(unsigned int n) {
        int i,num=n,sum=0;
        // process digits one at a time until there are none left
        while (num > 0) {
                // peal off the last digit from the number
                int digit=num % 10;
                num=(num - digit)/10;
                // add it's square to the sum
                sum+=digit*digit;
        }
        return sum;
}
int main(void) {
        unsigned int i=0,result=0, count=0;
        for (i=1; i<=100000000; i++) {
                // if not 1 or 89, start the iteration
                if ((i != 1) || (i != 89)) {
                        result = sum_square_digits(i);
                }
                // otherwise we're done already
                else {
                        result = i;
                }
                // while we haven't reached 1 or 89, keep iterating
                while ((result != 1) && (result != 89)) {
                        result = sum_square_digits(result);
                }
                if (result == 89) {
                        count++;
                }
        }
        std::cout << count << std::endl;
        return 0;
}
Output:
85744333

Ceylon[edit]

shared void run() {
	
	function digitsSquaredSum(variable Integer n) {
		variable value total = 0;
		while(n > 0) {
			total += (n % 10) ^ 2;
			n /= 10;
		}
		return total;
	}
	
	function lastSum(variable Integer n) {
		while(true) {
			n = digitsSquaredSum(n);
			if(n == 89 || n == 1) {
				return n;
			}
		}
	}
	
	variable value eightyNines = 0;
	for(i in 1..100M - 1) {
		if(lastSum(i) == 89) {
			eightyNines++;
		}
	}
	print(eightyNines);
}

Clojure[edit]

Direct Method[edit]

(ns async-example.core
  (:require [clojure.math.numeric-tower :as math])
  (:use [criterium.core])
  (:gen-class))
(defn sum-sqr [digits]
  " Square sum of list of digits "
  (let [digits-sqr (fn [n]
                     (apply + (map #(* % %) digits)))]
    (digits-sqr digits)))

(defn get-digits [n]
  " Converts a digit to a list of digits (e.g. 545 -> ((5) (4) (5)) (used for squaring digits) "
  (map #(Integer/valueOf (str %)) (String/valueOf n)))

(defn -isNot89 [x]
  " Returns nil on 89 "
  (cond
    (= x 0) 0
    (= x 89) nil
    (= x 1) 0
    (< x 10) (recur (* x x))
    :else (recur (sum-sqr (get-digits x)))))

;; Cached version of isNot89 (i.e. remembers prevents inputs, and returns result by looking it up when input repeated)
(def isNot89 (memoize -isNot89))

(defn direct-method [ndigits]
  " Simple approach of looping through all the numbers from 0 to 10^ndigits - 1 "
  (->>
    (math/expt 10 ndigits)
    (range 0)									; 0 to 10^ndigits
    (filter #(isNot89 (sum-sqr (get-digits %))))	; filters out 89
    (count)										; count non-89
    (- (math/expt 10 ndigits))))				; count 89 (10^ndigits - (count 89))


(time (println (direct-method 8)))
Output:
85744333
Time: 335 seconds

Using Combinations[edit]

(def DIGITS (range 0 10))

(defn -factorial [n]
  (apply * (take n (iterate inc 1))))
;   Cached version of factorial
(def factorial (memoize -factorial))

(defn -combinations [coll k]
  " From http://rosettacode.org/wiki/Combinations_with_repetitions#Clojure "
  (when-let [[x & xs] coll]
    (if (= k 1)
      (map list coll)
      (concat (map (partial cons x) (-combinations coll (dec k)))
              (-combinations xs k)))))
;   Cached version of combinations
(def combinations (memoize -combinations))

(defn comb [n r]
  " count of n items select r "
  (/ (/ (factorial n) (factorial r)) (factorial (- n r))))

(defn count-digits [digit-list]
  " count nunmber of occurences of digit in list "
  (reduce (fn [m v] (update-in m [v] (fnil inc 0))) {} digit-list))

(defn count-patterns [c]
  " Count of number of patterns with these digits "
  (->>
    c
    (count-digits)
    (reduce (fn [accum [k v]]
              (* accum (factorial v)))
            1)
    (/ (factorial (count c)))))

(defn itertools-comb [ndigits]
  (->>
    ndigits
    (combinations DIGITS)
    (filter #(is89 (sum-sqr %)))                 ; items which are not 89 (i.e. 1 since lower count)
    (reduce (fn [acc c]
              (+ acc (count-patterns c)))
            0)
    (- (math/expt 10 ndigits))))

(println (itertools-comb 8))
;; Time obtained using benchmark library (i.e. (bench (itertools-comb 8))  )
{
Output:
85744333
Time: 78 ms  (i.e. using combinations was over 4,000 times faster
                   both tested on i7 CPU 920@2.67GHZ)

Common Lisp[edit]

(defun square (number)
  (expt number 2))

(defun list-digits (number)
  "Return the `number' as a list of its digits."
  (loop
    :for (rest digit) := (multiple-value-list (truncate number 10))
                      :then (multiple-value-list (truncate rest 10))
    :collect digit
    :until (zerop rest)))

(defun next (number)
  (loop
    :for digit :in (list-digits number)
    :sum (square digit)))

(defun chain-end (number)
  "Return the ending number after summing the squaring of the digits of
`number'.  Either 1 or 89."
  (loop
    :for next := (next number) :then (next next)
    :until (or (eql next 1)
               (eql next 89))
    :finally (return next)))

(time
 (loop
   :with count := 0
   :for candidate :from 1 :upto 100000000
   :do (when (eql 89 (chain-end candidate))
         (incf count))
   :finally (return count)))
Output:
Evaluation took:
  1128.773 seconds of real time
  1126.231095 seconds of total run time (1117.296987 user, 8.934108 system)
  [ Run times consist of 56.419 seconds GC time, and 1069.813 seconds non-GC time. ]
  99.77% CPU
  2,815,545,509,836 processor cycles
  580,663,356,272 bytes consed

*

D[edit]

A simple memoizing partially-imperative brute-force solution:

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;
}
Output:
85744333

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

A fast imperative brute-force solution:

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);
}

The output is the same. The run-time is less than 3 seconds compiled with ldc2.

A more efficient solution:

import core.stdc.stdio, std.algorithm, std.range;

enum factorial = (in uint n) pure nothrow @safe @nogc
    => reduce!q{a * b}(1u, iota(1u, n + 1));

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 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 {
    uint candidate = reduce!((tot, n) => tot * 10 + n)(0, number);

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

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

        return reduce!((r, c) => r / c.factorial)
                      (number.length.factorial, digitsCount);
    }

    return 0;
}

void main() nothrow @nogc {
    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);
}

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/

A purely functional version, from the Haskell code. It includes two functions currently missing in Phobos used in the Haskell code.

Translation of: Haskell
import std.stdio, std.typecons, std.traits, std.typetuple, std.range, std.algorithm;

auto divMod(T)(T x, T y) pure nothrow @safe @nogc {
    return tuple(x / y, x % y);
}

auto expand(alias F, B)(B x) pure nothrow @safe @nogc
if (isCallable!F &&
    is(ParameterTypeTuple!F == TypeTuple!B)
    && __traits(isSame, TemplateOf!(ReturnType!F), Nullable)
    && isTuple!(TemplateArgsOf!(ReturnType!F)[0])
    && is(TemplateArgsOf!(TemplateArgsOf!(ReturnType!F)[0])[1] == B)) {

    alias NAB = ReturnType!F;
    alias AB = TemplateArgsOf!NAB[0];
    alias A = AB.Types[0];

    struct Expand {
        bool first;
        NAB last;

        @property bool empty() pure nothrow @safe @nogc {
            if (first) {
                first = false;
                popFront;
            }
            return last.isNull;
        }

        @property A front() pure nothrow @safe @nogc {
            if (first) {
                first = false;
                popFront;
            }
            return last.get[0];
        }

        void popFront() pure nothrow @safe @nogc { last = F(last.get[1]); }
    }

    return Expand(true, NAB(AB(A.init, x)));
}

//------------------------------------------------

uint step(uint x) pure nothrow @safe @nogc {
    Nullable!(Tuple!(uint, uint)) f(uint n) pure nothrow @safe @nogc {
        return (n == 0) ? typeof(return)() : typeof(return)(divMod(n, 10u).reverse);
    }

    return expand!f(x).map!(x => x ^^ 2).sum;
}

uint iter(uint x) pure nothrow @nogc {
    return x.recurrence!((a, n) => step(a[n - 1])).filter!(y => y.among!(1, 89)).front;
}

void main() {
    iota(1u, 100_000u).filter!(n => n.iter == 89).count.writeln;
}

With a small back-porting (to run it with the Phobos of LDC2 2.065) it runs in about 15.5 seconds.

ERRE[edit]

PROGRAM ITERATION

BEGIN
   PRINT(CHR$(12);) ! CLS
   INPUT(N)
   LOOP
      N$=MID$(STR$(N),2)
      S=0
      FOR I=1 TO LEN(N$) DO
         A=VAL(MID$(N$,I,1))
         S=S+A*A
      END FOR
      IF S=89 OR S=1 THEN PRINT(S;)  EXIT END IF
      PRINT(S;)
      N=S
   END LOOP
   PRINT
END PROGRAM

This program verifies a number only. With a FOR..END FOR loop it's possible to verify a number range.

Factor[edit]

A brute-force approach with some optimizations. It uses the fact that the first digit-square-sum of any number < 100,000,000 is, at most, 648. These few chains are rapidly memoized as the results for all hundred-million numbers are calculated for the first time or looked up.

USING: kernel math math.ranges math.text.utils memoize
prettyprint sequences tools.time ;
IN: rosetta-code.iterated-digits-squaring

: sum-digit-sq ( n -- m ) 1 digit-groups [ sq ] map-sum ;

MEMO: 1or89 ( n -- m )
    [ dup [ 1 = ] [ 89 = ] bi or ] [ sum-digit-sq ] until ;

[
    0 1
    [
        dup sum-digit-sq 1or89 89 = [ [ 1 + ] dip ] when
        1 + dup 100,000,000 <
    ] loop
    drop .
] time
Output:
85744333
Running time: 55.76544594 seconds

Forth[edit]

Tested for VFX Forth and GForth in Linux
\ To explain the algorithm: Each iteration is performed in set-count-sumsq below.
\ sum square of digits for 1 digit numbers are
\   Base   1  2  3  4  5  6  7  8  9
\   Sumsq: 1  4  9 16 25 36 49 54 81
\ Adding 10 to the base adds 1 to the sumsq, 
\ Adding 20 to the base adds 4
\         ||
\ Adding 90 adds 81
\ Similarly for n00, n000 etc..

\ Worked example for base 3 ( to keep the lists short ).  
\ The base 10 version performs 1.1 .. 1.9  with shifts of 1, 4, 9 .. 81 cells
\   
\    Ix      0   1   2   3   4   5   6   7   8
\    0     [ 1 ]
\    1.1       [ 1 ]                               Previous result shifted 1 cell ( 1**2 )
\    1.2                   [ 1 ]                   Previous result shifted 4 cells ( 2** 2 )
\    ------------------------------
\    Sum   [ 1,  1,  0,  0,  1  ]
\    2.1       [ 1,  1,  0,  0,  1  ]              Previous result shifted 1 cell ( 1**2 )
\    2.2                   [ 1,  1,  0,  0,  1 ]   Previous result shifted 4 cells ( 2** 2 )
\    --------------------------------------------
\    Sum   [ 1,  2,  1,  0,  2,  2,  0,  0,  1 ]   Number of integers with ix as first iteration sum of digits sq

CELL 8 * 301 * 1000 /   CONSTANT max-digits   \  301 1000 /  is log10( 2 )
\ 19 for a 64 bit Forth and 9 for a 32 bit one.

\ **********************************
\ ****  Create a counted array  ****
\ **********************************

: counted-array  \ create: #elements -- ;  does> -- a ;
  CREATE
    HERE SWAP 1+ CELLS DUP ALLOT ERASE
  DOES> ;

\ ***********************************
\ **** Array manipulation words. ****
\ ***********************************

: arr-copy  \ a-src a-dest -- ;  \ Copy array array at a-src to array at a-dest
  OVER @ 1+ CELLS CMOVE ;

: arr-count  \ a -- a' ct ;
\ Fetch the count of cells in the array and shift addr to point to element 0.
  DUP CELL+ SWAP @ ;

: th-element  \ a ix -- a' ;  \ Leave address of the ix th element of array at a on the stack
  1+ CELLS + ;

: arr-empty   \ a -- ;  \ Sets all array elements to zero and zero length
  dup @ 1+ CELLS ERASE ;

: arr+   \ a-src a-dest count -- ;
  \ Add each cell from a-src to the cells from a-dest for count elements
  \ Storing the result in a-dest
  CELLS 0 DO                
    OVER I + @ OVER I + +!   \ I is a byte count offset into either array
  CELL +LOOP
  2DROP ;  \ DROP the two base addresses

: arr.   \ a -- ;   \ Print the array. Used to debug.
  ." [ "  arr-count CELLS BOUNDS ?DO   i @ .   CELL +LOOP ." ]"   ;

\ ***********************************
\ ****  Sum digit squared words  ****
\ ***********************************

: sum-digit-sq   \ n -- n' ;
  0 SWAP
  BEGIN   DUP   WHILE
    10 /MOD  >R DUP * + R>
  REPEAT DROP ;

: 89or1<>    \ n -- f ;  \ True if n not equal to 89 or 1.
  DUP 89 <> AND 1 > ;

: iterated-89=   \ n -- f ;   \ True if n iterates to 89, false once it iterates to 1 ( or 0 ).
  BEGIN   DUP 89or1<>   WHILE
    sum-digit-sq
  REPEAT 89 = ;

\ *****************************************************
\ **** Create `count-sumsq` and `sumsq-old` arrays ****
\ *****************************************************

max-digits 81 * 1+    counted-array count-sumsq
max-digits 1- 81 * 1+ counted-array sumsq-old

: init-count-sumsq  \ -- ; \ Initialise the count-sumsq to [ 1 ]
  count-sumsq arr-empty             \ Ensure all zero
  1 count-sumsq !                   \ Set the length of the count-sumsq to 1 cell. 
  1 count-sumsq  0 th-element ! ;   \ Store 1 in the first element.

: set-count-sumsq  \ #digits -- ;    \ The main work.  Only called with valid #digits
  init-count-sumsq
  0 ?DO
    count-sumsq sumsq-old arr-copy   \ copy count-sumsq to sumsq-old 
    81 count-sumsq +!              \ Extend count-sumsq by 81 (9*9) cells
    10 1 DO                   
      sumsq-old arr-count                    ( a-sumsq-old' len )
      count-sumsq I DUP * th-element SWAP arr+
    LOOP
  LOOP ;

: count-89s   \ #digits -- n ;
  DUP max-digits U> IF
    ." Number of digits must be between 0 and " max-digits .
    DROP 0 
  ELSE
    set-count-sumsq
    0 count-sumsq @ 0 DO
      count-sumsq I th-element @      ( cum ith-count )
      I iterated-89=              \ True if the index delivers 89. 
      AND +     \ True is -1 ( all bits set ) AND with the count and add to the cum. 
    LOOP 
  THEN ;

: test    \ #digits :
  CR max-digits min 1+ 1 ?DO
    I 5 .r 2 SPACES I count-89s . CR
  LOOP ;
Output:
19 test 
    1  7 
    2  80 
    3  857 
    4  8558 
    5  85623 
    6  856929 
    7  8581146 
    8  85744333 
    9  854325192 
   10  8507390852 
   11  84908800643 
   12  850878696414 
   13  8556721999130 
   14  86229146720315 
   15  869339034137667 
   16  8754780882739336 
   17  87975303595231975 
   18  881773944919974509 
   19  8816770037940618762 

FreeBASIC[edit]

' FB 1.05.0 Win64

' similar to C Language (first approach)
' timing for i3 @ 2.13 GHz

Function endsWith89(n As Integer) As Boolean
  Dim As Integer digit, sum = 0
  Do
    While n > 0
      digit = n Mod 10
      sum += digit * digit
      n \= 10
    Wend
    If sum = 89 Then Return True
    If sum = 1 Then Return False
    n = sum
    sum  = 0
  Loop  
End Function

Dim As Double start = timer 
Dim sums(0 To 8 * 81) As UInteger 
sums(0) = 1
sums(1) = 0
Dim s As Integer
For n As Integer = 1 To 8 
  For i As Integer = n * 81 To 1 Step -1
    For j As Integer = 1 To 9
      s = j * j        
      If s > i Then Exit For
      sums(i) += sums(i - s)
    Next j
  Next i

  If n = 8 Then
    Dim As UInteger count89 = 0 
    For i As Integer = 1 To n * 81
      If Not endsWith89(i) Then Continue For
      count89 += sums(i)
    Next i 
    Print "There are";count89; " numbers from 1 to 100 million ending with 89"
  End If
Next
Print "Elapsed milliseconds ="; Int((timer - start) * 1000 + 0.5) 
Print
Print "Press any key to quit"
Sleep
Output:
There are 85744333 numbers from 1 to 100 million ending with 89
Elapsed milliseconds = 2

Frink[edit]

total = 0
d = new dict
var sum

for n = 1 to 100 million - 1
{
   sum = n
   do
   {
      if sum < 1000 and d@sum != undef
      {
         sum = d@sum
         break
      }

      c = sum
      
      sum = 0
      for digit = integerDigits[c]
         sum = sum + digit^2
   } while (sum != 89) and (sum != 1) 

   if (n < 1000)
      d@n = sum

   if (sum == 89)
      total = total + 1
}

println[total]
Output:
85744333

Formulæ[edit]

Formulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Formulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.

In this page you can see the program(s) related to this task and their results.

Go[edit]

It's basic. Runs in about 30 seconds on an old laptop.

package main

import (
	"fmt"
)

func main() {
	var d, n, o, u, u89 int64

	for n = 1; n < 100000000; n++ {
		o = n
		for {
			u = 0
			for {
				d = o%10
				o = (o - d) / 10
				u += d*d
				if o == 0 {
					break 
				}
			}
			if u == 89 || u == 1 {
				if u == 89 { u89++ }
				break
			}
			o = u
		}
	}
	fmt.Println(u89)
}
Output:
85744333

Haskell[edit]

Basic solution that contains just a little more than the essence of this computation. This runs in less than eight minutes:

import Data.List (unfoldr)
import Data.Tuple (swap)

step :: Int -> Int
step = sum . map (^ 2) . unfoldr f where
    f 0 = Nothing
    f n = Just . swap $ n `divMod` 10

iter :: Int -> Int
iter = head . filter (`elem` [1, 89]) . iterate step

main = do
    print $ length $ filter ((== 89) . iter) [1 .. 99999999]
Output:
85744333

J[edit]

Here's an expression to turn a number into digits:

digits=: 10&#.inv

And here's an expression to square them and find their sum:

sumdigsq=: +/"1@:*:@digits

But note that while the task description claims "you always end with either 1 or 89", that claim is somewhat arbitrary.

But only somewhat the loop is 89 ? 145 ? 42 ? 20 ? 4 ? 16 ? 37 ? 58 ? 89, so it only ends with 1 or one of the numbers in this loop. 42 is of course far more significant and the one I would choose!!--Nigel Galloway (talk) 10:12, 16 September 2014 (UTC)
You should move this comment (and my reply here) to the talk page. --Rdm (talk) 03:01, 26 September 2022 (UTC)
   sumdigsq^:(i.16) 15
15 26 40 16 37 58 89 145 42 20 4 16 37 58 89 145

Here, after the initial three values, the final digit repeats with a period of 8 (so it does not end).

   10 8$sumdigsq^:(i.80) 15
15 26 40 16 37 58 89 145
42 20  4 16 37 58 89 145
42 20  4 16 37 58 89 145
42 20  4 16 37 58 89 145
42 20  4 16 37 58 89 145
42 20  4 16 37 58 89 145
42 20  4 16 37 58 89 145
42 20  4 16 37 58 89 145
42 20  4 16 37 58 89 145
42 20  4 16 37 58 89 145

You could just as easily claim that you always end with either 1 or 4. So here's a routine which repeats the sum-square process until the sequence converges, or until it reaches the value 4:

itdigsq4=:4 = sumdigsq^:(0=e.&4)^:_"0

But we do not actually need to iterate. The largest value after the first iteration would be:

   sumdigsq 99999999
648

So we could write a routine which works for the intended range, and stops after the first iteration:

itdigsq1=:1 = sumdigsq^:(0=e.&4)^:_"0
digsq1e8=:(I.itdigsq1 i.649) e.~ sumdigsq

In other words, if the result after the first iteration is any of the numbers in the range 0..648 which converges to 1, it's not a result which would converge to the other loop. This is considerably faster than trying to converge 1e8 sequences, and also evades having to pick an arbitrary stopping point for the sequence which loops for the bulk computation.

And this is sufficient to find our result. We don't want to compute the entire batch of values in one pass, however, so let's break this up into 100 batches of one million each:

   +/+/@:-.@digsq1e8"1(1+i.100 1e6)
85744333

Of course, there are faster ways of obtaining that result. The fastest is probably this:

   85744333
85744333

This might be thought of as representing the behavior of a highly optimized compiled program. We could abstract this further by using the previous expression at compile time, so we would not have to hard code it.

Java[edit]

Works with: Java version 8
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;
    }
}
85744333

jq[edit]

Works with: jq version 1.4

The algorithm presented here caches the results for 1 ... D*81 (where D is the relevant number of digits) and uses the combinatorial approach, but to keep things relatively brief, the factorials themselves are not cached.

Part 1: Foundations

def factorial: reduce range(2;.+1) as $i (1; . * $i);

# Pick n items (with replacement) from the input array,
# but only consider distinct combinations:
def pick(n):
  def pick(n; m):  # pick n, from m onwards
    if n == 0 then []
    elif m == length then empty
    elif n == 1 then (.[m:][] | [.])
    else ([.[m]] + pick(n-1; m)), pick(n; m+1)
    end;
  pick(n;0) ;

# Given any array, produce an array of [item, count] pairs for each run.
def runs:
  reduce .[] as $item
    ( [];
      if . == [] then [ [ $item, 1] ] 
      else  .[length-1] as $last
            | if $last[0] == $item then (.[0:length-1] + [ [$item, $last[1] + 1] ] )
              else . + [[$item, 1]]
              end
      end ) ;

Part 2: The Generic Task

Count how many number chains beginning with n (where 0 < n < 10^D) end with a value 89.

def terminus:
  # sum of the squared digits
  def ssdigits: tostring | explode | map(. - 48 | .*.) | add;

  if . == 1 or . == 89 then . 
  else ssdigits | terminus
  end;

# Count the number of integers i in [1... 10^D] with terminus equal to 89.
def task(D):
  # The max sum of squares is D*81 so return an array that will instantly
  # reveal whether n|terminus is 89:
  def cache:
    reduce range(1; D*81+1) as $d ([false]; . + [$d|terminus == 89]);

  # Compute n / (i1! * i2! * ... ) for the given combination,
  # which is assumed to be in order:
  def combinations(n):
    runs | map( .[1] | factorial) | reduce .[] as $i (n; ./$i);

  cache as $cache
  | (D|factorial) as $Dfactorial
  | reduce ([range(0;10)] | pick(D)) as $digits
      (0;
       ($digits | map(.*.) | add) as $ss
       | if $cache[$ss] then . + ($digits|combinations($Dfactorial))
         else . 
         end) ;

Part 3: D=8

task(8)
Output:
$ jq -M -n -f Iterated_digits_squaring_using_pick.jq
85744333

# Using jq>1.4:
# user	0m2.595s
# sys	0m0.010s

# Using jq 1.4: 
# user	0m3.942s
# sys	0m0.009s

Julia[edit]

Works with: Julia version 0.6

Brute force solution:

function iterate(m::Integer)
    while m != 1 && m != 89
        s = 0
        while m > 0 # compute sum of squares of digits
            m, d = divrem(m, 10)
            s += d ^ 2
        end
        m = s
    end
    return m
end
itercount(k::Integer) = count(x -> iterate(x) == 89, 1:k)

More clever solution:

using Combinatorics
function itercountcombos(ndigits::Integer)
    cnt = 0
    f = factorial(ndigits)
    # loop over all combinations of ndigits decimal digits:
    for comb in combinations(1:(10+ndigits-1), ndigits)
        s = 0
        perms = 1
        prevd = -1
        rep = 1
        for k = eachindex(comb) # sum digits ^ 2 and count permutations
            d = comb[k] - k
            s += d ^ 2
            # accumulate number of permutations of repeated digits
            if d == prevd
                rep += 1
                perms *= rep
            else
                prevd = d
                rep = 1
            end
        end
        if s > 0 && iterate(s) == 89
            cnt += f ÷ perms # numbers we can get from digits
        end
    end
    return cnt
end

Benchmarks

@time itercount(100_000_000)
@time itercountcombos(8)
@time itercountcombos(17)
Output:
  8.866063 seconds (4.32 k allocations: 232.908 KiB)
  0.053470 seconds (101.05 k allocations: 8.729 MiB)
  1.588977 seconds (12.50 M allocations: 1.536 GiB, 16.94% gc time)

Kotlin[edit]

Translation of: FreeBASIC
// version 1.0.6

fun endsWith89(n: Int): Boolean {
    var digit: Int
    var sum = 0
    var nn = n
    while (true) {
        while (nn > 0) {
            digit = nn % 10
            sum += digit * digit
            nn /= 10
        }
        if (sum == 89) return true
        if (sum == 1) return false
        nn = sum
        sum  = 0
    }
}

fun main(args: Array<String>) {
    val sums = IntArray(8 * 81 + 1)
    sums[0] = 1
    sums[1] = 0
    var s: Int
    for (n in 1 .. 8)
        for (i in n * 81 downTo 1) 
            for (j in 1 .. 9) {
                s = j * j
                if (s > i) break
                sums[i] += sums[i - s]
            }
    var count89 = 0 
    for (i in 1 .. 8 * 81) 
        if (endsWith89(i)) count89 += sums[i]
    println("There are $count89 numbers from 1 to 100 million ending with 89")
}
Output:
There are 85744333 numbers from 1 to 100 million ending with 89

Lua[edit]

squares = {}

for i = 0, 9 do
    for j = 0, 9 do
        squares[i * 10 + j] = i * i + j * j
    end
end

for i = 1, 99 do
    for j = 0, 99 do
        squares[i * 100 + j] = squares[i] + squares[j]
    end
end

function sum_squares(n)
    if n < 9999.5 then
        return squares[n]
    else
        local m = math.floor(n / 10000)
        return squares[n - 10000 * m] + sum_squares(m)
    end
end

memory = {}

function calc_1_or_89(n)
    local m = {}
    n = memory[n] or n
    while n ~= 1 and n ~= 89 do
        n = memory[n] or sum_squares(n)
        table.insert(m, n)
    end
    for _, i in pairs(m) do
        memory[i] = n
    end
    return n
end

counter = 0

for i = 1, 100000000 do
    if calc_1_or_89(i) == 89 then
        counter = counter + 1
    end
end

print(counter)
Output:
85744333

Mathematica / Wolfram Language[edit]

sumDigitsSquared[n_Integer] := Total[IntegerDigits[n]^2]
stopValues = Join[{1}, NestList[sumDigitsSquared, 89, 7]];
iterate[n_Integer] := 
 NestWhile[sumDigitsSquared, n, Intersection[stopValues, {#}] == {} &]

numberOfDigits = 8;
maxSum = numberOfDigits 9^2;
loopVariables = 
  ToExpression@Table["i" <> ToString[n], {n, numberOfDigits}];
iteratesToOne = Cases[Range@maxSum, _?(iterate[#] == 1 &)];
allIterators = 
  Flatten[{Reverse@#, 9}] & /@ Partition[loopVariables, 2, 1];
maxCombinations = numberOfDigits!;

ssd = 
  SparseArray[Table[n^2 -> numberOfDigits, {n, 9}], {maxSum}];

Do[
  variables = loopVariables[[;; digitCount]];
  iterators = allIterators[[;; digitCount - 1]];
  
  Do[ssd += 
    SparseArray[
     Total[variables^2] -> 
      maxCombinations/
       Times @@ (Tally[PadRight[variables, numberOfDigits]][[All, 
            2]]!), {maxSum}], {i, 9}, Evaluate[Sequence @@ iterators]],
            
  {digitCount, 2, numberOfDigits}];

onesCount = 
 Total[Cases[
    ArrayRules[ssd] /. 
     HoldPattern[{a_} -> b_] :> {a, 
       b}, {_?(MemberQ[iteratesToOne, #] &), _}][[All, 2]]];

(10^numberOfDigits - 1) - onesCount
Output:
85744333

Nim[edit]

An extremely fast version which computes how many numbers gives a sum (starting with one digit and adding digits one by one). If a sum ends with 89, we adds the associated count to the result. As we have no need to deal with the numbers, but only with the sums of square of digits, there is no need to use big numbers.

We provide the result for 8 digits and also for 50 digits. The result is obtained in 7 ms.

import tables

iterator digits(n: int): int =
  ## Yield the digits starting from the unit.
  var n = n
  while true:
    yield n mod 10
    n = n div 10
    if n == 0:
      break


func gen(n: int): int =
  ## Compute the chain.
  result = n
  while result notin [1, 89]:
    var s = 0
    for d in digits(result):
      inc s, d * d
    result = s


func chainsEndingWith89(ndigits: Natural): Natural =
  ## Compute the number of chains ending with 89.

  # Initialize the count table with values for one digit numbers.
  var prevCount, currcount: CountTable[int]
  for i in 0..9: prevcount[i * i] = 1

  # Add next digits.
  for _ in 2..ndigits:
    # Create the next generation count array.
    currcount.clear()
    for val, count in prevcount:
      for newdigit in 0..9:
        # As 0 is included, "currcount" includes "prevcount".
        currcount.inc(newdigit * newdigit + val, count)
    prevcount = currcount

  for val, count in currcount:
    if val != 0 and gen(val) == 89:
      inc result, count

echo "For  8 digits: ", chainsEndingWith89(8)
echo "For 50 digits: ", chainsEndingWith89(15)
Output:
For  8 digits: 85744333
For 50 digits: 869339034137667

Oberon-2[edit]

Works with: oo2c Version 2
MODULE DigitsSquaring;
IMPORT
  Out;

VAR
  i,hits89: LONGINT;
  
  PROCEDURE Squaring(n: LONGINT): LONGINT;
  VAR
    d, sum: LONGINT;
  BEGIN
    LOOP
      sum := 0;
      WHILE n > 0 DO
        d := n MOD 10;
        INC(sum,d * d);
        n := n DIV 10
      END;
      IF (sum = 1) OR (sum = 89) THEN EXIT END;
      n := sum;
    END;
    
    RETURN sum
  END Squaring;
  
BEGIN
  hits89 := 0;
  FOR i := 1 TO 100000000 DO
    IF Squaring(i) = 89 THEN INC(hits89) END
  END;
  Out.LongInt(hits89,0);Out.Ln
END DigitsSquaring.
Output:
85744333

real    0m12.201s
user    0m12.179s
sys     0m0.001s

Objeck[edit]

class Abbreviations {
  function : Main(args : String[]) ~ Nil {
    Count89s(1000000)->PrintLine();
    Count89s(100000000)->PrintLine();
  }

  function : Count89s(limit : Int) ~ Int {
    if(limit < 1) {
      return 0;
    };

    result := 0;
    ends := Int->New[Int->Min(limit, 9 * 9 * 9 + 2)];
    for(i := 1; i < ends->Size(); i++;) {
      ends[i] := i;
      while(ends[i] <> 1 & ends[i] <> 89) {
        ends[i] := SquareDigitSum(ends[i]);
      };
      
      if(ends[i] = 89) {
        result++;
      };
    };

    for(i := ends->Size(); i < limit; i++;) {
      if(ends[SquareDigitSum(i)] = 89) {
        result++;
      };
    };
            
    return result;
  }

  function : SquareDigitSum(n : Int) ~ Int {
    sum := 0;
    while(n > 0) {
      digit := n % 10;
      sum += digit * digit;
      n /= 10;
    };

    return sum;
  }
}

Output:

856,929
85,744,333

Oforth[edit]

Brute force implementation

: sq_digits(n) 
   while (n 1 <> n 89 <> and ) [ 
      0 while(n) [ n 10 /mod ->n dup * + ] 
      ->n 
      ] n ;

: iterDigits  | i | 0 100000000 loop: i [ i sq_digits 89 &= + ] . ;
Output:
85744333

PARI/GP[edit]

ssd(n)=n=digits(n); sum(i=1, #n, n[i]^2);
happy(n)=while(n>6, n=ssd(n)); n==1;
ct(n)=my(f=n!,s=10^n-1,d); forvec(v=vector(9,i,[0,n]), d=vector(9,i, if(i>8,n,v[i+1])-v[i]); if(happy(sum(i=1,9,d[i]*i^2)), s-=f/prod(i=1,9,d[i]!)/v[1]!), 1); s;
ct(8)
Output:
%1 = 85744333

Pascal[edit]

A limited, but fast implementation (up to 10e14). It calculates first all the possible sums up to cM= sqrt(MAX), with the drawback that cM must be 10^n and can only count from 10^n to 10^(2*n). Runtime: n-> 100*n => t(100*n)-> ~10*t(n) O(n) sqrt(n)

1E8 -> runtime 0..4 ms // not really measureable 
1E12-> runtime 0.22 secs
1E14 -> runtime 2,7 secs
1E16 -> runtime 31,0 secs
1E18 -> runtime  354 secs // 2GByte

Tested with freepascal.

program Euler92;
const
  maxdigCnt = 14;
  //2* to use the sum of two square-sums without access violation
  maxPoss = 2* 9*9*maxdigCnt;// every digit is 9
  cM  = 10*1000*1000;// 10^(maxdigCnt div 2)
  IdxSqrSum = cM;//MaxPoss;//max(cM,MaxPoss);
type
  tSqrSum   = array[0..IdxSqrSum] of Word;
  tEndsIn   = array[0..maxPoss]of Byte;
  tresCache = array[0..maxPoss]of Uint64;

var
  aSqrDigSum : tSqrSum;
  aEndsIn: tEndsIn;
  aresCache : tresCache;

procedure CreateSpuareDigitSum;
var
  i,j,k,l : integer;
begin
  For i := 0 to 9 do
    aSqrDigSum[i] := sqr(i);
  k := 10;
  l := k;
  while k < cM do
  begin
    For i := 1 to 9 do
      For j := 0 to k-1 do
      begin
        aSqrDigSum[l]:=aSqrDigSum[i]+aSqrDigSum[j];
        inc(l);
      end;
    k := l;
  end;
  aSqrDigSum[l] := 1;
end;

function InitEndsIn(n:LongWord):longWord;
{fill aEndsIN recursive}
var
  d,s:LongWord;
begin
  IF n in [0..1] then
  begin
    InitEndsIn := n;
    EXIT;
  end;
  s := aSqrDigSum[n];
  {if unknown}
  IF aEndsIN[s] = byte(-1) then
  begin
    d := InitEndsIn(s);
    aEndsIN[s]:= d;
    InitEndsIn := d;
  end
  else
    InitEndsIn := aEndsIN[s];
end;

function CntSmallOnes(s:longWord;
                      n:longWord=cM-1):NativeUint;
var
  i: longword;
begin
  result := 0;
  For i := cM-1 downto 0 do
    result := result+aEndsIN[aSqrDigSum[i]+s];
end;

procedure Init;
var
  i,j,cnt : integer;
begin
  CreateSpuareDigitSum;
  fillchar(aEndsIN,Sizeof(aEndsIN) ,#255);
  aEndsIN[0] := 0;
  aEndsIN[1]:= 1;
  aEndsIN[89]:= 0;// no need to use 89
  For i := 1 to maxPoss do
    aEndsIN[i]:= InitEndsIN(i);

  cnt := 0;
  fillchar(aresCache,SizeOf(aresCache),#0);
  For i := Low(tSqrSum) to high(tSqrSum) do
  begin
    j := aSqrDigSum[i];
    If aresCache[j] = 0 then
    begin
//      write(i,',');
      aresCache[j] := CntSmallOnes(j);
      inc(cnt);
    end;
  end;
//  writeln;  writeln(cnt,' small counts out of ',cM);
end;
{
function EndsIn(n:LongWord):Word;
var
  d,s:LongWord;
begin
  d := n;
  s := 0;
  while d > High(tSqrSum) do
  begin
    s := s+aSqrDigSum[d Mod cM];
    d := d Div cM
  end;
  s :=s+aSqrDigSum[d];
  EndsIn := aEndsIN[s];
end;
}

function CntOnes(s: longWord;n:Int64):Int64;
var
  i : Int64;
begin
writeln;
  result := 0;
  i := n div cM;
  repeat
    result := result+aresCache[s+aSqrDigSum[i]];
    dec(i)
  until i < 0
end;

const
  upperlimit = cM*cM ;
var
  Res : Int64;
begin
  Init;
  Res := CntOnes(0,upperlimit-1)+1;
  writeln('there are ',res,'  1s ');
  writeln('there are ',upperlimit-res,' 89s ');
end.
output i3 3.5 Ghz
10e18
//658 small counts out of 1000000000
there are 118226055080025491  1s 
there are 881773944919974509 89s 

real	5m54.431s
user	5m53.977s

10e14
there are 13770853279685  1s
there are 86229146720315 89s

real  0m2.699s
user  0m2.693s

Perl[edit]

Translation of: Raku
use warnings;
use strict;

my @sq = map { $_ ** 2 } 0 .. 9;
my %cache;
my $cnt = 0;

sub Euler92 {
    my $n = 0 + join( '', sort split( '', shift ) );
    $cache{$n} //= ($n == 1 || $n == 89) ? $n : 
    Euler92( sum( @sq[ split '', $n ] ) )
}

sub sum {
   my $sum;
   $sum += shift while @_;
   $sum;
}

for (1 .. 100_000_000) {
   ++$cnt if Euler92( $_ ) == 89;
}
 
print $cnt;
   85744333

Phix[edit]

Translation of: C
with javascript_semantics
constant MAXINT = power(2,iff(machine_bits()=32?53:64))
 
procedure main(integer limit)
    sequence sums = repeat(0,limit*81+1)
    sums[1] = 1
    for n=1 to limit do
        for i=n*81 to 1 by -1 do
            for j=1 to 9 do
                integer s = j*j, i1= i+1, i1ms = i1-s
                if s>i then exit end if
                sums[i1] += sums[i1ms]
            end for
        end for
        atom count89 = 0
        for i=1 to n*81 do
            integer r, digit, w = i, i1 = i+1
            while w!=1 do
                r = 0
                while w!=0 do
                    digit = mod(w,10)
                    r += digit*digit
                    w = floor(w/10)
                end while
                if r=89 then
                    count89 += sums[i1]
                    if count89>MAXINT then
                        printf(1,"counter overflow for 10^%d\n",n)
                        return
                    end if
                    exit
                end if
                w = r
            end while
        end for
        printf(1,"There are %d numbers from 1 to 10^%d ending with 89\n",{count89,n})
    end for
end procedure
 
atom t0 = time()
main(20)
?time()-t0
Output:

on 32 bit:

There are 7 numbers from 1 to 10^1 ending with 89
There are 80 numbers from 1 to 10^2 ending with 89
There are 857 numbers from 1 to 10^3 ending with 89
There are 8558 numbers from 1 to 10^4 ending with 89
There are 85623 numbers from 1 to 10^5 ending with 89
There are 856929 numbers from 1 to 10^6 ending with 89
There are 8581146 numbers from 1 to 10^7 ending with 89
There are 85744333 numbers from 1 to 10^8 ending with 89
There are 854325192 numbers from 1 to 10^9 ending with 89
There are 8507390852 numbers from 1 to 10^10 ending with 89
There are 84908800643 numbers from 1 to 10^11 ending with 89
There are 850878696414 numbers from 1 to 10^12 ending with 89
There are 8556721999130 numbers from 1 to 10^13 ending with 89
There are 86229146720315 numbers from 1 to 10^14 ending with 89
There are 869339034137667 numbers from 1 to 10^15 ending with 89
There are 8754780882739336 numbers from 1 to 10^16 ending with 89
counter overflow for 10^17
0.031

same on 64-bit, but ending

There are 87975303595231975 numbers from 1 to 10^17 ending with 89
There are 881773944919974509 numbers from 1 to 10^18 ending with 89
There are 8816770037940618762 numbers from 1 to 10^19 ending with 89
counter overflow for 10^20
0.109

Combinatorics version[edit]

Following the steps outlined on the talk page.
I realised I needed to do this in two stages.
Phase 1. Make sure we can count.

with javascript_semantics
function comb(sequence res, set, integer n, at=1, sequence chosen={})
    if length(chosen)=n then
        sequence digits = repeat(0,10)
        for i=1 to length(chosen) do
            integer idx = chosen[i]+1
            digits[idx]+=1
        end for
        atom p = factorial(length(chosen))
        for i=1 to 10 do
            if digits[i] then
                p /= factorial(digits[i])
            end if
        end for
        res = sq_add(res,{p,1})
    else
        for i=at to length(set) do
            res = comb(res,set,n,i,append(deep_copy(chosen),set[i]))
        end for
    end if
    return res
end function
 
constant nums = {0,1,2,3,4,5,6,7,8,9}
for i=1 to 8 do
    printf(1,"%V\n",{comb({0,0},nums,i)})
end for

Starting with the combinations method from http://rosettacode.org/wiki/Combinations_with_repetitions#Phix converted to a function, make sure we are covering all the numbers correctly by checking that we have indeed found power(10,n) of them, and show we are looking at significantly fewer combinations.

Output:
{10,10}
{100,55}
{1000,220}
{10000,715}
{100000,2002}
{1000000,5005}
{10000000,11440}
{100000000,24310}

Phase 2. Add in the rest of the logic, as suggested count 1's in preference to 89's and subtract from 10^n to get the answer.
[PS There is an eerie similarity between this and the 2nd C version, but I swear it is not a copy, and I noticed that later.]

with javascript_semantics
sequence is1
 
function comb(atom res, sequence set, integer n, at=1, sequence chosen={})
    if length(chosen)=n then
        sequence digits = repeat(0,10)
        atom sumsq = 0
        for i=1 to length(chosen) do
            integer ci = chosen[i]
            sumsq += ci*ci
            ci += 1
            digits[ci] += 1
        end for
        if sumsq=0 or is1[sumsq] then
            atom perms = factorial(length(chosen))
            for i=1 to 10 do
                if digits[i] then
                    perms /= factorial(digits[i])
                end if
            end for
            res += perms
        end if
    else
        chosen = deep_copy(chosen)&0
        for i=at to length(set) do
            chosen[$] = set[i]
            res = comb(res,set,n,i,chosen)
        end for
    end if
    return res
end function
 
procedure setis1(integer n)
    is1 = repeat(0,n*81)
    for i=1 to length(is1) do
        integer r, digit, w = i
        while 1 do
            r = 0
            while w!=0 do
                digit = mod(w,10)
                r += digit*digit
                w = floor(w/10)
            end while
            if r=89 then exit end if
            if r=1 then
                is1[i] = 1
                exit
            end if
            w = r
        end while
    end for
end procedure
 
constant nums = {0,1,2,3,4,5,6,7,8,9}
atom t00 = time()
for i=1 to 16 do
    atom t0 = time()
    setis1(i)
    printf(1,"There are %d numbers from 1 to 10^%d ending with 89 (%3.2fs)\n",{power(10,i)-comb(0,nums,i),i,time()-t0})
end for
?elapsed(time()-t00)
Output:

Sadly, while still very much faster than brute force, several times slower than the translated from C version.

There are 7 numbers from 1 to 10^1 ending with 89 (0.00s)
There are 80 numbers from 1 to 10^2 ending with 89 (0.00s)
There are 857 numbers from 1 to 10^3 ending with 89 (0.00s)
There are 8558 numbers from 1 to 10^4 ending with 89 (0.02s)
There are 85623 numbers from 1 to 10^5 ending with 89 (0.00s)
There are 856929 numbers from 1 to 10^6 ending with 89 (0.02s)
There are 8581146 numbers from 1 to 10^7 ending with 89 (0.02s)
There are 85744333 numbers from 1 to 10^8 ending with 89 (0.03s)
There are 854325192 numbers from 1 to 10^9 ending with 89 (0.08s)
There are 8507390852 numbers from 1 to 10^10 ending with 89 (0.16s)
There are 84908800643 numbers from 1 to 10^11 ending with 89 (0.31s)
There are 850878696414 numbers from 1 to 10^12 ending with 89 (0.61s)
There are 8556721999130 numbers from 1 to 10^13 ending with 89 (1.16s)
There are 86229146720315 numbers from 1 to 10^14 ending with 89 (2.16s)
There are 869339034137667 numbers from 1 to 10^15 ending with 89 (3.77s)
There are 8754780882739336 numbers from 1 to 10^16 ending with 89 (6.59s)
"15s"

PicoLisp[edit]

Brute force with caching

(de *Idx1or89 (89 . 89) ((1 . 1)))

(de 1or89 (N)
   (let L (mapcar format (chop N))
      (if (lup *Idx1or89 (setq N (sum * L L)))
         (cdr @)
         (prog1
            (1or89 N)
            (idx '*Idx1or89 (cons N @) T) ) ) ) )

Test:

(let Ones 0
   (for I 100000000
      (and (=1 (1or89 I)) (inc 'Ones)) )
   (println (- 100000000 Ones)) )

Output:

85744333

PL/I[edit]

test: procedure options (main, reorder); /* 6 August 2015 */

   declare (m, n) fixed decimal (10);
   declare (i, j, p, s, tally initial (0) ) fixed binary (31);
   declare d fixed binary (7);
   declare (start_time, finish_time, elapsed_time) float (15);

   start_time = secs();

   do m = 1 to 1000000;
      n = m;
      do until ((n = 1) | (n = 89));
         p = n; s = 0;
         do while (p > 0);
            d = mod(p, 10);
            p = p/10;
            s = s + d*d;
         end;
         n = s;
      end;
      if n = 89 then tally = tally + 1;
   end;

   finish_time = secs();
   put skip edit (Tally, ' numbers iterated to 89') (f(10), A);
   elapsed_time = finish_time - start_time;
   put skip edit ('Elapsed time=', elapsed_time, ' secs') (A, F(10,3));

end test;

Output:

    856929 numbers iterated to 89
Elapsed time=    39.280 secs

PureBasic[edit]

Translation of: C
OpenConsole()
Procedure is89(x)
  Repeat
    s=0
    While x : s+ x%10*x%10 : x/10 : Wend
    If s=89 : ProcedureReturn 1 : EndIf
    If s=1  : ProcedureReturn 0 : EndIf
    x=s
  ForEver
EndProcedure

Procedure main()
  Dim sums(32*81+1) : sums(0)=1 : sums(1)=0
  
  For n=1 To n+1
    For i=n*81 To 1 Step -1
      For j=1 To 9
        s=j*j : If s>i : Break : EndIf
        sums(i)+sums(i-s)
      Next
    Next
    count89=0
    For i=1 To n*81+1
      If Not is89(i) : Continue : EndIf
      If sums(i)>9223372036854775807-count89
        PrintN("counter overflow for 10^"+Str(n))
        ProcedureReturn 0
      EndIf
      count89+sums(i)
    Next
    PrintN("1->10^"+LSet(Str(n),2,Chr(32))+": "+Str(count89))
  Next  
EndProcedure

start=ElapsedMilliseconds()
main()
Print("elapsed milliseconds= "+Str(ElapsedMilliseconds()-start))
Input()
Output:
1->10^1 : 7
1->10^2 : 80
1->10^3 : 857
1->10^4 : 8558
1->10^5 : 85623
1->10^6 : 856929
1->10^7 : 8581146
1->10^8 : 85744333
1->10^9 : 854325192
1->10^10: 8507390852
1->10^11: 84908800643
1->10^12: 850878696414
1->10^13: 8556721999130
1->10^14: 86229146720315
1->10^15: 869339034137667
1->10^16: 8754780882739336
1->10^17: 87975303595231975
1->10^18: 881773944919974509
1->10^19: 8816770037940618762
counter overflow for 10^20
elapsed milliseconds= 9
Translation of: C++
OpenConsole()
Procedure sum_square_digits(n)
  num=n : sum=0
  While num>0
    digit=num%10
    num=(num-digit)/10
    sum+ digit*digit
  Wend
  ProcedureReturn sum
EndProcedure

Procedure main()
  i=0 : result=0 : count=0
  For i=1 To 1e8
    If Not i=1 Or Not i=89
      result=sum_square_digits(i)
    Else
      result=i
    EndIf
    While Not result=1 And Not result=89
      result=sum_square_digits(result)
    Wend
    If result=89 : count+1 : EndIf
  Next
  PrintN(Str(count))
EndProcedure

start=ElapsedMilliseconds()
main()
Print("elapsed milliseconds: "+Str(ElapsedMilliseconds()-start))
Input()
Output:
85744333
elapsed milliseconds: 65553

Python[edit]

Combinatorics[edit]

Translation of D[edit]

Translation of: D
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()
Output:
85744333

The run-time is less than half a second.

Translation of Ruby[edit]

Translation of: Ruby
from itertools import combinations_with_replacement
from array import array
from time import clock
D = 8
F = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000]
def b(n):
    yield 1
    for g in range(1,n+1):
        gn = g
        res = 0
        while gn > 0:
            gn,rem = divmod(gn,10)
            res += rem**2
        if res==89:
            yield 0
        else:
            yield res
N = array('I',b(81*D))
for n in range(2,len(N)):
    q = N[n]
    while q>1:
        q = N[q]
    N[n] = q

es = clock()
z = 0
for n in combinations_with_replacement(range(10),D):
    t = 0
    for g in n:
        t += g*g
    if N[t] == 0:
        continue
    t = [0,0,0,0,0,0,0,0,0,0]
    for g in n:
        t[g] += 1
    t1 = F[D]
    for g in t:
        t1 /= F[g]
    z += t1
ee = clock() - es
print "\nD==" + str(D) + "\n  " + str(z) + " numbers produce 1 and " + str(10**D-z) + " numbers produce 89"
print "Time ~= " + str(ee) + " secs"
Output:
D==8
 14255667 numbers produce 1 and 85744333 numbers produce 89
Time ~= 0.14 secs

D==11
15091199357 numbers produce 1 and 84908800643 numbers produce 89
Time ~= 1.12 secs

D==14
13770853279685 numbers produce 1 and 86229146720315 numbers produce 89
Time ~= 7.46 secs

D==17
12024696404768025 numbers produce 1 and 87975303595231975 numbers produce 89
Time ~= 34.16 secs

Python: Simple caching[edit]

>>> 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
>>>

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

Python: Enhanced caching[edit]

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.

>>> 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)
>>>

This took tens of minutes to run.

Count digit sums[edit]

If we always count up to powers of 10, it's faster to just record how many different numbers have the same digit square sum. The check89() function is pretty simple-minded, because it doesn't need to be fancy here.

from __future__ import print_function
from itertools import count

def check89(n):
    while True:
        n, t = 0, n
        while t: n, t = n + (t%10)**2, t//10
        if n <= 1: return False
        if n ==89: return True

a, sq, is89 = [1], [x**2 for x in range(1, 10)], [False]
for n in range(1, 500):
    b, a = a, a + [0]*81
    is89 += map(check89, range(len(b), len(a)))

    for i,v in enumerate(b):
        for s in sq: a[i + s] += v

    x = sum(a[i] for i in range(len(a)) if is89[i])
    print("10^%d" % n, x)

QBasic[edit]

Works with: QBasic
Works with: QuickBasic
Translation of: BBC BASIC
REM Version 1: Brute force

T = TIMER
n1 = 0
FOR i = 1 TO 10000000
    j = i
    DO
        k = 0
        DO
            k = INT(k + (j MOD 10) ^ 2)
            j = INT(j / 10)
        LOOP WHILE j <> 0
        j = k
    LOOP UNTIL j = 89 OR j = 1
    IF j > 1 THEN n1 = n1 + 1
NEXT i
PRINT USING "Version 1: ####### in ##.### seconds."; n1; (TIMER - T)
END


Quackery[edit]

[ abs 0 swap 
  [ base share /mod 
    dup *
    rot + swap 
    dup 0 = until ] 
  drop ]            is digitsquaresum ( n --> n )

[ dup 1 != while
  dup 89 != while
  digitsquaresum 
  again ]           is chainends      ( n --> n ) 
  
0 1000000 times 
  [ i^ 1+ chainends
    89 = + ]
echo
Output:
856929

Racket[edit]

This contains two versions (in one go). The naive version which can (and should, probably) be used for investigating a single number. The second version can count the IDSes leading to 89 for powers of 10.

#lang racket
;; Tim-brown 2014-09-11

;; The basic definition.
;; It is possible to memoise this or use fixnum (native) arithmetic, but frankly iterating over a
;; hundred million, billion, trillion numbers will be slow. No matter how you do it.
(define (digit^2-sum n)
  (let loop ((n n) (s 0))
    (if (= 0 n) s (let-values ([(q r) (quotient/remainder n 10)]) (loop q (+ s (sqr r)))))))

(define (iterated-digit^2-sum n)
  (match (digit^2-sum n) [0 0] [1 1] [89 89] [(app iterated-digit^2-sum rv) rv]))

;; Note that: ids(345) = ids(354) = ids(435) = ids(453) = ids(534) = ids(543) = 50 --> 89
;; One calculation does for 6 candidates.
;; The plan:
;;  - get all the ordered combinations of digits including 0's which can be used both as digits and
;;    "padding" digits in the most significant digits. (n.b. all-zeros is not in the range to be
;;    tested and should be dropped)
;;  - find the digit sets that have an IDS of 89
;;  - find out how many combinations there are of these digits

;; output: a list of n-digits long lists containing all of the digit combinations.
;;         a smart bunny would figure out the sums of the digits as they're generated but I'll plod
;;         along step-by-step. a truly smart bunny would also count the combinations. that said, I
;;         don't think I do much unnecessary computation here.
(define (all-digit-lists n-digits)
  (define (inner remain acc least-digit)
    (cond
      [(zero? remain) (list (list))]
      [(= least-digit 10) null]
      [else
       (for*/list
           ((ld+ (in-range least-digit 10))
            (rgt (in-list (inner (sub1 remain) empty ld+))))           
         (append acc (cons ld+ rgt)))]))
  (inner n-digits '() 0))

;; We calculate IDS differently since we're presented with a list of digits rather than a number
(define (digit-list-IDS c)
  (define (digit-combo-IDS c)
    (apply + (map sqr c)))  
  (iterated-digit^2-sum (digit-combo-IDS c)))

;; ! (factiorial) -- everyone's favourite combinatorial function! (that's just an exclamation mark)
;; there's one in (require math/number-theory) for any heavy lifting, but we're not or I could import
;; it from math/number-theory -- but this is about all I need. A lookup table is going to be faster
;; than a more general function.
(define (! n)
  (case n [(0 1) 1] [(2) 2] [(3) 6] [(4) 24] [(5) 120] [(6) 720] [(7) 5040] [(8) 40320] [(9) 362880]
    [else (* n (! (sub1 n)))] ; I expect this clause'll never be called
    ))

;; We need to count the permutations -- digits are in order so we can use the tail (cdr) function for
;; determining my various k's. See: https://en.wikipedia.org/wiki/Combination
(define (count-digit-list-permutations c #:length (l (length c)) #:length! (l! (! l)))
  (let loop ((c c) (i 0) (prev -1 #;"never a digit") (p l!))
    (match c
      [(list) (/ p (! i))]
      [(cons (== prev) d) (loop d (+ i 1) prev p)]
      [(cons a d) (loop d 1 a (/ p (! i)))])))

;; Wrap it all up in a neat function
(define (count-89s-in-100... n)
  (define n-digits (order-of-magnitude n))
  (define combos (drop (all-digit-lists n-digits) 1)) ; don't want first one which is "all-zeros"
  (for/sum ((c (in-list combos)) #:when (= 89 (digit-list-IDS c)))
    (count-digit-list-permutations c #:length n-digits)))

(displayln "Testing permutations:")
(time (printf "1000000:\t~a~%"        (count-89s-in-100...       1000000)))
(time (printf "100000000:\t~a~%"      (count-89s-in-100...     100000000)))
(time (printf "1000000000:\t~a~%"     (count-89s-in-100...    1000000000)))
(time (printf "1000000000000:\t~a~%"  (count-89s-in-100... 1000000000000)))
(newline)
;; Do these last, since the 10^8 takes longer than my ADHD can cope with
(displayln "Testing one number at a time (somewhat slower):")
(time (printf "1000000:\t~a~%"   (for/sum ((n (in-range 1   1000000))
                                           #:when (= 89 (iterated-digit^2-sum n))) 1)))
(time (printf "100000000:\t~a~%" (for/sum ((n (in-range 1 100000000))
                                           #:when (= 89 (iterated-digit^2-sum n))) 1)))

{module+ test
  (require tests/eli-tester)
  [test
   (iterated-digit^2-sum 15) => 89
   (iterated-digit^2-sum 7) => 1
   (digit-combo-perms '()) => 1
   (digit-combo-perms '(1 2 3)) => 6
   (digit-combo-perms '(1 1 3)) => 3
   (for/sum ((n (in-range 1 1000000)) #:when (= 89 (iterated-digit^2-sum n))) 1) => 856929
   (all-digit-lists 1) => '((0) (1) (2) (3) (4) (5) (6) (7) (8) (9))
   (length (all-digit-lists 2)) => 55
   (length (all-digit-lists 3)) => 220
   (count-89s-in-100... 1000000) => 856929]
  }
Output:
Testing permutations:
1000000:	856929
cpu time: 8 real time: 8 gc time: 0
100000000:	85744333
cpu time: 44 real time: 43 gc time: 0
1000000000:	854325192
cpu time: 112 real time: 110 gc time: 20
1000000000000:	850878696414
cpu time: 1108 real time: 1110 gc time: 472

Testing one number at a time (somewhat slower):
1000000:	856929
cpu time: 1168 real time: 1171 gc time: 0
100000000:	85744333
cpu time: 130720 real time: 130951 gc time: 0

Ok, so maybe 131 seconds is not so flattering -- but I have not memoised or anything fancy like that, because even doing that isn't going to come anywhere near competing with 44ms.

Raku[edit]

(formerly Perl 6) This fairly abstract version does caching and filtering to reduce the number of values it needs to check and moves calculations out of the hot loop, but is still interminably slow... even for just up to 1,000,000.

constant @sq = ^10 X** 2;
my $cnt = 0;

sub Euler92($n) {
    $n == any(1,89) ?? $n !!
    (state %){$n} //= Euler92( [+] @sq[$n.comb] )
}

for 1 .. 1_000_000 -> $n {
   my $i = +$n.comb.sort.join;
   ++$cnt if Euler92($i) == 89;
}
 
say $cnt;
Output:
856929

All is not lost, however. Through the use of gradual typing, Raku scales down as well as up, so this jit-friendly version is performant enough to brute force the larger calculation:

my @cache;
@cache[1] = 1;
@cache[89] = 89;

sub Euler92(int $n) {
    $n < 649  # 99,999,999 sums to 648, so no point remembering more
        ?? (@cache.AT-POS($n) //= ids($n))
        !! ids($n)
}

sub ids(int $num --> int) {
    my int $n = $num;
    my int $ten = 10;
    my int $sum = 0;
    my int $t;
    my int $c;
    repeat until $n == 89 or $n == 1 {
        $sum = 0;
        repeat {
            $t = $n div $ten;
            $c = $n - $t * $ten;
            $sum = $sum + $c * $c;
        } while $n = $t;
        $n = @cache.AT-POS($sum) // $sum;
    }
    $n;
}

my int $cnt = 0;
for 1 .. 100_000_000 -> int $n {
   $cnt = $cnt + 1 if Euler92($n) == 89;
}
say $cnt;
Output:
85744333

Which is better, but is still pretty slow.

The biggest gains are often from choosing the right algorithm.

sub endsWithOne($n --> Bool) {
    my $digit;
    my $sum = 0;
    my $nn = $n;
    loop {
        while $nn > 0 {
            $digit = $nn % 10;
            $sum += $digit²;
            $nn = $nn div 10;
        }
        return True  if $sum == 1;
        return False if $sum == 89;
        $nn = $sum;
        $sum = 0;
    }
}

my $k = 8; # 10**8
my @sums is default(0) = 1,0;
my $s;
for 1 .. $k -> $n {
    for $n*811 -> $i {
        for 1 .. 9 -> $j {
            $s = $j²;
            last if $s > $i;
            @sums[$i] += @sums[$i - $s];
        }
    }
}

my $ends-with-one = sum flat @sums[(1 .. $k*81).grep: { endsWithOne($_) }], +endsWithOne(10**$k);

say 10**$k - $ends-with-one;
Output:
85744333

REXX[edit]

{Both REXX versions don't depend on a specific end-number.}

with memoization[edit]

/*REXX program performs the squaring of iterated digits  (until the sum equals 1 or 89).*/
parse arg n .                                    /*obtain optional arguments from the CL*/
if n=='' | n==","  then n=10 * 1000000           /*Not specified?  Then use the default.*/
!.=0;   do m=1  for 9;  !.m=m**2;  end  /*m*/    /*build a short-cut for the squares.   */
a.=.;                                #.=!.       /*intermediate counts of some numbers. */
     do j=1  for n;                  x=j         /* [?] process the numbers in the range*/
       do q=1  until s==89 | s==1;   s=0         /*add sum of the squared decimal digits*/
             do  until x==''                     /*process each of the dec. digits in X.*/
             parse var x _ +1 x;     s=s + !._   /*get a digit;  sum the fast square,   */
             end   /*until x ··· */              /* [?]  S=is sum of the squared digits.*/
       z.q=s                                     /*assign sum to a temporary auxiliary. */
       if a.s\==.  then do;  s=a.s;  leave;  end /*Found a previous sum?  Then use that.*/
       x=s                                       /*substitute the sum for the "new"  X. */
       end   /*q*/                               /* [?]  keep looping 'til   S= 1 or 89.*/
                   do f=1  for q;  _=a.f;  a._=s /*use the auxiliary arrays (for lookup)*/
                   end   /*f*/
     #.s=#.s + 1                                 /*bump the counter for the 1's or 89's.*/
     end   /*j*/

  do k=1  by 88  for 2;   @k=right('"'k'"', 5)   /*display two results; define a literal*/
  say 'count of'   @k   " chains for all natural numbers up to "     n     ' is:'      #.k
  end   /*k*/                                    /*stick a fork in it,  we're all done. */
output   when using the default input:


(ten million)

count of   "1"  chains for all natural numbers up to  10000000  is: 1418854
count of  "89"  chains for all natural numbers up to  10000000  is: 8581146

process in chunks[edit]

This version is about     times faster than the previous REXX version.

/*REXX program performs the squaring of iterated digits  (until the sum equals 1 or 89).*/
parse arg n .                                    /*obtain optional arguments from the CL*/
if n=='' | n==","  then n=10 * 1000000           /*Not specified?  Then use the default.*/
!.=0;      do m=1  for 9;  !.m=m**2;  end /*m*/  /*build a short-cut for the squares.   */
$.=.; $.0=0;  $.00=0;  $.000=0;  $.0000=0; @.=$. /*short-cuts for sub-group summations. */
#.=0                                             /*count of  1  and  89  results so far.*/
     do j=1  for n;       s=sumDs(j)             /* [?]  process each number in a range.*/
     #.s=#.s + 1                                 /*bump the counter for  1's  or  89's. */
     end   /*j*/

  do k=1  by 88  for 2;   @=right('"'k'"', 5)    /*display two results; define a literal*/
  say 'count of'   @    " chains for all natural numbers up to "     n     ' is:'      #.k
  end   /*k*/                                    /*stick a fork in it,  we're all done. */
exit                                             /*stick a fork in it,  we're all done. */
/*--------------------------------------------------------------------------------------*/
sumDs: parse arg z;  chunk=3                     /*obtain the number (for adding digits)*/
       p=0                                       /*set partial sum of the decimal digits*/
          do m=1  by chunk  to length(z)         /*process the number, in chunks of four*/
          y=substr(z, m, chunk)                  /*extract a 4-byte chunk of the number.*/
          if @.y==.  then do;   oy=y;      a=0   /*Not done before?  Then sum the number*/
                            do  until y==''      /*process each of the dec. digits in Y.*/
                            parse var y  _ +1 y  /*obtain a decimal digit; add it to  A.*/
                            a=a + !._            /*obtain a decimal digit; add it to  A.*/
                            end  /*until y ···*/ /* [?]   A = is the sum of squared digs*/
                          @.oy=a                 /*mark original  Y  as being summed.   */
                          end
                     else a=@.y                  /*use the  pre-summed  digits of  Y.   */
          p=p + a                                /*add all the parts of number together.*/
          end   /*m*/

       if $.p\==.  then return $.p               /*Computed before?  Then use the value.*/
       y=p                                       /*use a new copy of  P.                */
              do  until s==1 | s==89;  s=0       /*add the squared decimal digits of  P.*/
                 do  until y==''                 /*process each  decimal digits in    X.*/
                 parse var y  _ +1 y;  s=s + !._ /*get a dec. digit; sum the fast square*/
                 end   /*until y ···*/           /* [?]  S = is sum of the squared digs.*/
              y=s                                /*substitute the sum for a  "new"  X.  */
              end      /*until s ···*/           /* [?]  keep looping 'til  S=1  or  89.*/
       $.p=s                                     /*use this for memoization for the sum.*/
       return s
output   when using the input of:   100000000


(one hundred million)

count of   "1"  chains for all natural numbers up to  100000000  is  14255667
count of  "89"  chains for all natural numbers up to  100000000  is  85744333

Ring[edit]

nr = 1000
num = 0
for n = 1 to nr 
   sum = 0
   for m = 1 to len(string(n))
       sum += pow(number(substr(string(n),m,1)),2)
       if sum = 89 num += 1 see "" + n + " " + sum + nl ok
   next
next   
see "Total under 1000 is : " + num + nl

Output:

58 89
85 89
229 89
267 89
276 89
292 89
348 89
384 89
438 89
483 89
508 89
580 89
581 89
582 89
583 89
584 89
585 89
586 89
587 89
588 89
589 89
627 89
672 89
726 89
762 89
805 89
834 89
843 89
850 89
851 89
852 89
853 89
854 89
855 89
856 89
857 89
858 89
859 89
922 89
Total under 1000 is : 41

Ruby[edit]

# Count how many number chains for Natural Numbers < 10**d end with a value of 1.
def iterated_square_digit(d)
  f = Array.new(d+1){|n| (1..n).inject(1, :*)}      #Some small factorials
  g = -> (n) { res = n.digits.sum{|d| d*d} 
               res==89 ? 0 : res }
  
  #An array: table[n]==0 means that n translates to 89 and 1 means that n translates to 1
  table = Array.new(d*81+1){|n| n.zero? ? 1 : (i=g.call(n))==89 ? 0 : i}
  table.collect!{|n| n = table[n] while n>1; n}
  z = 0                                             #Running count of numbers translating to 1
  [*0..9].repeated_combination(d) do |rc|           #Iterate over unique digit combinations
    next if table[rc.inject(0){|g,n| g+n*n}].zero?  #Count only ones
    nn = [0] * 10                                   #Determine how many numbers this digit combination corresponds to
    rc.each{|n| nn[n] += 1}
    z += nn.inject(f[d]){|gn,n| gn / f[n]}          #Add to the count of numbers terminating in 1
  end
  puts "\nd=(#{d}) in the range 1 to #{10**d-1}",
       "#{z} numbers produce 1 and #{10**d-1-z} numbers produce 89"
end

[8, 11, 14, 17].each do |d|
  t0 = Time.now
  iterated_square_digit(d)
  puts "  #{Time.now - t0} sec"
end
Output:
d=(8) in the range 1 to 99999999
14255667 numbers produce 1 and 85744332 numbers produce 89
  0.116007 sec

d=(11) in the range 1 to 99999999999
15091199357 numbers produce 1 and 84908800642 numbers produce 89
  0.921052 sec

d=(14) in the range 1 to 99999999999999
13770853279685 numbers produce 1 and 86229146720314 numbers produce 89
  5.503315 sec

d=(17) in the range 1 to 99999999999999999
12024696404768025 numbers produce 1 and 87975303595231974 numbers produce 89
  24.337392 sec

Rust[edit]

These are two naive solutions, one with lots of redundant calculations (memoizationless recursion) and one with a few precomputed values. All digit square sums are no greater than 648 for numbers < 100_000_000.

Both are slow algorithms, however, Rust is among faster languages, so this doesn't take minutes or hours.

Naive Recursion

fn digit_square_sum(mut num: usize) -> usize {
    let mut sum = 0;
    while num != 0 {
        sum += (num % 10).pow(2);
        num /= 10;
    }
    sum
}

fn last_in_chain(num: usize) -> usize {
    match num {
        1 | 89 => num,
        _ => last_in_chain(digit_square_sum(num)),
    }
}

fn main() {
    let count = (1..100_000_000).filter(|&n| last_in_chain(n) == 89).count();
    println!("{}", count);
}
Output:
85744333

Runtime: 6s on a 2500k @ 4Ghz

With precomputation

fn dig_sq_sum(mut num : usize ) -> usize {
    let mut sum = 0;
    while num != 0 {
        sum += (num % 10).pow(2);
        num /= 10;
    }
    sum
}

fn last_in_chain(num: usize) -> usize {
    match num {
        0 => 0,
        1 | 89 => num,
        _ => last_in_chain(dig_sq_sum(num)),
    }
}

fn main() {
    let prec: Vec<_> = (0..649).map(|n| last_in_chain(n)).collect();
    let count = (1..100_000_000).filter(|&n| prec[dig_sq_sum(n)] == 89).count();
    println!("{}", count);
}

Runtime: 1.7s on a 2500k @ 4Ghz

Output:
85744333

Scala[edit]

Naïve Version, conventional iteration and (tail) recursive in one[edit]

Output:
Best seen running in your browser either by ScalaFiddle (ES aka JavaScript, non JVM) or Scastie (remote JVM) to compare the run times.
import scala.annotation.tailrec

object Euler92 extends App {
  override val executionStart = compat.Platform.currentTime

  @tailrec
  private def calcRec(i: Int): Int = {

    @tailrec
    def iter0(n: Int, total: Int): Int =
      if (n > 0) {
        val rest = n % 10
        iter0(n / 10, total + rest * rest)
      }
      else total


    if (i == 89 || i == 1) i else calcRec(iter0(i, 0))
  }


  private def calcConv(i: Int) = {
    var n: Int = i
    while (n != 89 && n != 1) {
      var total = 0
      while (n > 0) {
        val x = n % 10
        total += (x * x)
        n /= 10
      }
      n = total
    }
    n
  }

  println((1 until 100000000).par.count(calcConv(_) == 89))
  println(s"Runtime conventional loop.[total ${compat.Platform.currentTime - executionStart} ms]")

  val executionStart0 = compat.Platform.currentTime
  println((1 until 100000000).par.count(calcRec(_) == 89))
  println(s"Runtime recursive loop.   [total ${compat.Platform.currentTime - executionStart0} ms]")

}

Sidef[edit]

func digit_square_sum_iter(n) is cached {

    if ((n == 1) || (n == 89)) {
        return n
    }

    __FUNC__(n.digits.sum { .sqr })
}

say (1..1e6 -> count_by { digit_square_sum_iter(_) == 89 })
Output:
856929

Swift[edit]

Translation of: C

With nth power support.

import BigInt

func is89(_ n: Int) -> Bool {
  var n = n

  while true {
    var s = 0

    repeat {
      s += (n%10) * (n%10)
      n /= 10
    } while n > 0

    if s == 89 {
      return true
    } else if s == 1 {
      return false
    }

    n = s
  }
}

func iterSquare(upToPower pow: Int) {
  var sums = [BigInt](repeating: 0, count: pow * 81 + 1)
  sums[0] = 1

  for n in 1...pow {
    var i = n * 81

    while i > 0 {
      for j in 1..<10 {
        let s = j * j
        guard s <= i else { break }
        sums[i] += sums[i-s]
      }

      i -= 1
    }

    var count89 = BigInt(0)

    for x in 1..<n*81 + 1 {
      guard is89(x) else { continue }

      count89 += sums[x]
    }

    print("1->10^\(n): \(count89)")
  }
}

iterSquare(upToPower: 8)
Output:
1->10^1: 7
1->10^2: 80
1->10^3: 857
1->10^4: 8558
1->10^5: 85623
1->10^6: 856929
1->10^7: 8581146
1->10^8: 85744333

Tcl[edit]

All three versions below produce identical output (85744333), but the third is fastest and the first is the slowest, both by substantial margins.

Very Naïve Version[edit]

proc ids n {
    while {$n != 1 && $n != 89} {
	set n [tcl::mathop::+ {*}[lmap x [split $n ""] {expr {$x**2}}]]
    }
    return $n
}
for {set i 1} {$i <= 100000000} {incr i} {
    incr count [expr {[ids $i] == 89}]
}
puts $count

Intelligent Version[edit]

Conversion back and forth between numbers and strings is slow. Using math operations directly is much faster (around 4 times in informal testing).

proc ids n {
    while {$n != 1 && $n != 89} {
	for {set m 0} {$n} {set n [expr {$n / 10}]} {
	    incr m [expr {($n%10)**2}]
	}
	set n $m
    }
    return $n
}
for {set i 1} {$i <= 100000000} {incr i} {
    incr count [expr {[ids $i] == 89}]
}
puts $count

Substantially More Intelligent Version[edit]

Using the observation that the maximum value after 1 step is obtained for 999999999, which is . Thus, running one step of the reduction and then using a lookup table (which we can construct quickly at the start of the run, and which has excellent performance) is much faster overall, approximately 3–4 times than the second version above (and over 12 times faster than the first version).

Donald, you have 1 too many 9's the value after step 1 is 81*8 = 648. Not that that is the problem here, you can not afford to go around this loop 100 million times. Notice that IDS[21] == IDS[12], IDS[123] == IDS[132] == IDS[213} ... etc, etc. The Ruby version takes about a tenth of a second.--Nigel Galloway (talk) 12:47, 31 August 2014 (UTC)
# Basic implementation
proc ids n {
    while {$n != 1 && $n != 89} {
	for {set m 0} {$n} {set n [expr {$n / 10}]} {
	    incr m [expr {($n%10)**2}]
	}
	set n $m
    }
    return $n
}

# Build the optimised version
set body {
    # Microoptimisation to avoid an unnecessary alloc in the loop
    for {set m 0} {$n} {set n [expr {"$n[unset n]" / 10}]} {
	incr m [expr {($n%10)**2}]
    }
}
set map 0
for {set i 1} {$i <= 729} {incr i} {
    lappend map [ids $i]
}
proc ids2 n [append body "return \[lindex [list $map] \$m\]"]

# Put this in a lambda context for a little extra speed.
apply {{} {
    set count 0
    for {set i 1} {$i <= 100000000} {incr i} {
	incr count [expr {[ids2 $i] == 89}]
    }
    puts $count
}}

VBScript[edit]

start_time = Now
cnt = 0
For i = 1 To 100000000
	n = i
	sum = 0
	Do Until n = 1 Or n = 89
		For j = 1 To Len(n)
			sum = sum + (CLng(Mid(n,j,1))^2)
		Next
		n = sum
		sum = 0
	Loop
	If n = 89 Then
		cnt = cnt + 1
	End If
Next
end_time = Now

WScript.Echo "Elapse Time: " & DateDiff("s",start_time,end_time) &_
			vbCrLf & "Count: " & cnt
Output:

Elapse time is in seconds. Friends don't let friends do this in VBScript. :-)

Elapse Time: 2559
Count: 85744333

Wren[edit]

Translation of: FreeBASIC
var endsWith89 = Fn.new { |n|
    var digit = 0
    var sum = 0
    while (true) {
        while (n > 0) {
            digit = n % 10
            sum = sum + digit*digit
            n = (n/10).floor
        }
        if (sum == 89) return true
        if (sum == 1) return false
        n = sum
        sum = 0
    }
}

var start = System.clock
var sums = List.filled(8*81 + 1, 0)
sums[0] = 1
sums[1] = 0
var s = 0
for (n in 1..8) {
    for (i in n*81..1) {
        for (j in 1..9) {
            s = j * j
            if (s > i) break
            sums[i] = sums[i] + sums[i-s]
        }
    }
    if (n == 8) {
        var count89 = 0
        for (i in 1..n*81) {
            if (endsWith89.call(i)) count89 = count89 + sums[i]
        }
        System.print("There are %(count89) numbers from 1 to 100 million ending with 89.")
    }
}
System.print("Took %(((System.clock - start)*1000).round) milliseconds.")
Output:

Timing for Intel Core i7-8565U machine running Ubuntu 18.04.

There are 85744333 numbers from 1 to 100 million ending with 89.
Took 4 milliseconds.

X86 Assembly[edit]

Works with: nasm
section .data
    count dd 0
    
section .text
global _main
_main:
    mov ecx, 1
    looping:
        mov eax, ecx ;pass parameter in eax
        push ecx
        call doMath
        pop ecx
        add [count], eax ;doMath returns 0 or 1 in eax
        inc ecx
        cmp ecx, 100000001
        jl looping
    mov eax, count ;returns memory address of count
    ret
    
addSquaredDigits:
    push ebx
    mov ebx, 0
    mov esi, 10
    looping2:
        xor edx, edx ;clear edx for division
        div esi ;div by 10 to get last digit in edx
        mov ecx, eax ;save parameter
        mov eax, edx ; get last digit
        mul eax ;square last digit
        add ebx, eax ;add the square to the result
        jecxz aSDend ;if the parameter is 0 we have all digits
        mov eax, ecx ;restore parameter before looping
        jmp looping2
    aSDend:
        mov eax, ebx ;move result to return register
        pop ebx
        ret
        
doMath:
    looping3:
        call addSquaredDigits ;do until eax is 89 or 1
        cmp eax, 89
        je ret1
        cmp eax, 1
        je ret0
        jmp looping3
    ret1: ;if eax == 89 we return 1 -> inc count
        mov eax, 1
        ret
    ret0: ;if eax == 1 we return 0 -> don't inc count
        mov eax, 0
        ret

zkl[edit]

Using brute force is a never ending process so need to be clever, which takes under a second.

Translation of: Python
Translation of: D
fcn check(number){  // a list of digits: 13 is L(0,0,0,0,0,0,1,3)
   candidate:=number.reduce(fcn(sum,n){ sum*10 + n },0);  // digits to int

   while(candidate != 89 and candidate != 1)  // repeatedly sum squares of digits
      { candidate = candidate.split().reduce(fcn(sum,c){ sum + c*c },0); }
 
   if(candidate == 89){ // count permutations of these digits, they all sum to 89
      digitsCount:=List(0,0,0,0,0,0,0,0,0,0);
      foreach d in (number){ digitsCount[d] += 1; }
      return(digitsCount.reduce(fcn(r,c){ r/factorial(c) },cacheBang)); // cacheBang==number.len()!
   }
   0 // this number doesn't sum to 89 (ie sums to 1)
}
fcn factorial(n) { (1).reduce(n,fcn(N,n){ N*n },1) }
 
limit:=0d100_000_000;  cacheSize:=limit.toFloat().log10().ceil().toInt();
number:=(0).pump(cacheSize,List().write,0); // list of zeros
result:=0; i:=cacheSize - 1;
var cacheBang=factorial(cacheSize);  //== number.len()!
 
while(True){  // create numbers s.t. no set of digits is repeated
   if(i == 0 and number[i] == 9) break;
   if(i == cacheSize - 1 and number[i] < 9){ number[i] += 1; result += check(number); }
   else if(number[i] == 9) i -= 1;
   else{
      number[i] += 1;
      foreach j in ([i + 1 .. cacheSize - 1]){ number[j] = number[i]; }
      i = cacheSize - 1;
      result += check(number);
   }
}
println(result);
Output:
85744333

ZX Spectrum Basic[edit]

Translation of: BBC_BASIC

Very, very slow. Use a ZX Spectrum emulator and run with maximum speed option enabled.

10 LET n=0
20 FOR i=1 TO 1000
30 LET j=i
40 LET k=0
50 LET k=INT (k+FN m(j,10)^2)
60 LET j=INT (j/10)
70 IF j<>0 THEN GO TO 50
80 LET j=k
90 IF j=89 OR j=1 THEN GO TO 100
95 GO TO 40
100 IF j>1 THEN LET n=n+1
110 NEXT i
120 PRINT "Version 1: ";n
200 DEF FN m(a,b)=a-INT (a/b)*b: REM modulo
Output:
Version 1: 857