user
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

* Combinations with repetitions
* Digital root
* Digital root/Multiplicative digital root
* Happy numbers
assistant
(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*81 … 1 -> $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
```