Iterated digits squaring
If you add the square of the digits of a Natural number (an integer bigger than zero), you always end with either 1 or 89:
15 -> 26 -> 40 -> 16 -> 37 -> 58 -> 89 7 -> 49 -> 97 -> 130 -> 10 -> 1
An example in Python:
<lang python>>>> step = lambda x: sum(int(d) ** 2 for d in str(x)) >>> iterate = lambda x: x if x in [1, 89] else iterate(step(x)) >>> [iterate(x) for x in xrange(1, 20)] [1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1]</lang>
Your task is to count how many number chains in [1, 100_000_000) end with a value 89.
This problem derives from the Project Euler problem 92.
D
A simple memoizing partially-imperative brute-force solution: <lang d>import std.stdio, std.algorithm, std.range, std.functional;
uint step(uint x) pure nothrow @safe @nogc {
uint total = 0; while (x) { total += (x % 10) ^^ 2; x /= 10; } return total;
}
uint iterate(in uint x) nothrow @safe {
return (x == 89 || x == 1) ? x : x.step.memoize!iterate;
}
void main() {
iota(1, 100_000_000).filter!(x => x.iterate == 89).walkLength.writeln;
}</lang>
- Output:
85744333
A fast imperative brute-force solution: <lang d>void main() nothrow @nogc {
import core.stdc.stdio: printf;
enum uint magic = 89; enum uint limit = 100_000_000; uint[(9 ^^ 2) * 8 + 1] lookup = void;
uint[10] squares; foreach (immutable i, ref x; squares) x = i ^^ 2;
foreach (immutable uint i; 1 .. lookup.length) { uint x = i;
while (x != magic && x != 1) { uint total = 0; while (x) { total += squares[(x % 10)]; x /= 10; } x = total; }
lookup[i] = x == magic; }
uint magicCount = 0; foreach (immutable uint i; 1 .. limit) { uint x = i; uint total = 0;
while (x) { total += squares[(x % 10)]; x /= 10; }
magicCount += lookup[total]; }
printf("%u\n", magicCount);
}</lang> The output is the same.
A more efficient solution: <lang d>uint iLog10(in uint x) pure nothrow @safe @nogc in {
assert(x > 0);
} body {
return (x >= 1_000_000_000) ? 9 : (x >= 100_000_000) ? 8 : (x >= 10_000_000) ? 7 : (x >= 1_000_000) ? 6 : (x >= 100_000) ? 5 : (x >= 10_000) ? 4 : (x >= 1_000) ? 3 : (x >= 100) ? 2 : (x >= 10) ? 1 : 0;
}
uint factorial(in uint n) pure nothrow @safe @nogc {
import std.algorithm, std.range; return reduce!q{a * b}(1u, iota(1u, n + 1));
}
uint nextStep(uint x) pure nothrow @safe @nogc {
typeof(return) result = 0;
while (x > 0) { result += (x % 10) ^^ 2; x /= 10; } return result;
}
uint check(in uint[] number) pure nothrow @safe @nogc {
enum uint magic = 89;
uint candidate = 0; foreach (immutable n; number) candidate = candidate * 10 + n;
while (candidate != magic && candidate != 1) candidate = candidate.nextStep;
if (candidate == magic) { uint[10] digitsCount; foreach (immutable d; number) digitsCount[d]++;
uint result = number.length.factorial; foreach (immutable c; digitsCount) result /= c.factorial; return result; }
return 0;
}
void main() nothrow @nogc {
import core.stdc.stdio: printf;
enum uint limit = 100_000_000; immutable uint cacheSize = limit.iLog10;
uint[cacheSize] number; uint result = 0; uint i = cacheSize - 1;
while (true) { if (i == 0 && number[i] == 9) break; if (i == cacheSize - 1 && number[i] < 9) { number[i]++; result += number.check; } else if (number[i] == 9) { i--; } else { number[i]++;
number[i + 1 .. $] = number[i]; i = cacheSize - 1; result += number.check; } }
printf("%u\n", result);
}</lang> The output is the same. This third version was ported to D and improved from: mathblog.dk/project-euler-92-square-digits-number-chain/
Java
<lang java>import java.util.stream.LongStream;
public class IteratedDigitsSquaring {
public static void main(String[] args) { long r = LongStream.range(1, 100_000_000L) .parallel() .filter(n -> calc(n) == 89) .count(); System.out.println(r); }
private static long calc(long n) { while (n != 89 && n != 1) { long total = 0; while (n > 0) { total += Math.pow(n % 10, 2); n /= 10; } n = total; } return n; }
}</lang>
85744333
Perl 6
This is a brute force version. There's no way it can go up to the required limit in any decent time so we mark this solution as incomplete for now.
<lang perl6>sub Euler92($n) {
(state @)[$n] //= $n == 1|89 ?? $n !! Euler92([+] $n.comb X** 2)
}
say +grep 89, map &Euler92, 1 .. 100_000_000;</lang>
Python
<lang python>from math import ceil, log10, factorial
def next_step(x):
result = 0 while x > 0: result += (x % 10) ** 2 x /= 10 return result
def check(number):
candidate = 0 for n in number: candidate = candidate * 10 + n
while candidate != 89 and candidate != 1: candidate = next_step(candidate)
if candidate == 89: digits_count = [0] * 10 for d in number: digits_count[d] += 1
result = factorial(len(number)) for c in digits_count: result /= factorial(c) return result
return 0
def main():
limit = 100000000 cache_size = int(ceil(log10(limit))) assert 10 ** cache_size == limit
number = [0] * cache_size result = 0 i = cache_size - 1
while True: if i == 0 and number[i] == 9: break if i == cache_size - 1 and number[i] < 9: number[i] += 1 result += check(number) elif number[i] == 9: i -= 1 else: number[i] += 1 for j in xrange(i + 1, cache_size): number[j] = number[i] i = cache_size - 1 result += check(number)
print result
main()</lang>
- Output:
85744333