Iterated digits squaring: Difference between revisions
(Added zkl) |
|||
Line 327: | Line 327: | ||
This took tens of minutes to run. |
This took tens of minutes to run. |
||
=={{header|zkl}}== |
|||
Using brute force is a never ending process so need to be clever, which takes under a second. |
|||
{{trans|Python}} |
|||
{{trans|D}} |
|||
{{trans|http://www.mathblog.dk/project-euler-92-square-digits-number-chain/}} |
|||
<lang zkl>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.toString().reduce(fcn(sum,c){ sum + 1*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);</lang> |
|||
{{out}} |
|||
<pre>85744333</pre> |
Revision as of 02:26, 25 August 2014
If you add the square of the digits of a Natural number (an integer bigger than zero), you always end with either 1 or 89:
15 -> 26 -> 40 -> 16 -> 37 -> 58 -> 89 7 -> 49 -> 97 -> 130 -> 10 -> 1
An example in Python:
<lang python>>>> step = lambda x: sum(int(d) ** 2 for d in str(x)) >>> iterate = lambda x: x if x in [1, 89] else iterate(step(x)) >>> [iterate(x) for x in xrange(1, 20)] [1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1]</lang>
- Task
- Count how many number chains for integers 1 <= n < 100_000_000 end with a value 89.
Or, for much less credit - (showing that your algorithm and/or language is slow):
- Count how many number chains for integers 1 <= n < 1_000_000 end with a value 89.
This problem derives from the Project Euler problem 92.
- Cf
D
A simple memoizing partially-imperative brute-force solution: <lang d>import std.stdio, std.algorithm, std.range, std.functional;
uint step(uint x) pure nothrow @safe @nogc {
uint total = 0; while (x) { total += (x % 10) ^^ 2; x /= 10; } return total;
}
uint iterate(in uint x) nothrow @safe {
return (x == 89 || x == 1) ? x : x.step.memoize!iterate;
}
void main() {
iota(1, 100_000_000).filter!(x => x.iterate == 89).count.writeln;
}</lang>
- Output:
85744333
The run-time is about 10.9 seconds compiled with ldc2.
A fast imperative brute-force solution: <lang d>void main() nothrow @nogc {
import core.stdc.stdio: printf;
enum uint magic = 89; enum uint limit = 100_000_000; uint[(9 ^^ 2) * 8 + 1] lookup = void;
uint[10] squares; foreach (immutable i, ref x; squares) x = i ^^ 2;
foreach (immutable uint i; 1 .. lookup.length) { uint x = i;
while (x != magic && x != 1) { uint total = 0; while (x) { total += squares[(x % 10)]; x /= 10; } x = total; }
lookup[i] = x == magic; }
uint magicCount = 0; foreach (immutable uint i; 1 .. limit) { uint x = i; uint total = 0;
while (x) { total += squares[(x % 10)]; x /= 10; }
magicCount += lookup[total]; }
printf("%u\n", magicCount);
}</lang> The output is the same. The run-time is less than 3 seconds compiled with ldc2.
A more efficient solution: <lang d>uint iLog10(in uint x) pure nothrow @safe @nogc in {
assert(x > 0);
} body {
return (x >= 1_000_000_000) ? 9 : (x >= 100_000_000) ? 8 : (x >= 10_000_000) ? 7 : (x >= 1_000_000) ? 6 : (x >= 100_000) ? 5 : (x >= 10_000) ? 4 : (x >= 1_000) ? 3 : (x >= 100) ? 2 : (x >= 10) ? 1 : 0;
}
uint factorial(in uint n) pure nothrow @safe @nogc {
import std.algorithm, std.range; return reduce!q{a * b}(1u, iota(1u, n + 1));
}
uint nextStep(uint x) pure nothrow @safe @nogc {
typeof(return) result = 0;
while (x > 0) { result += (x % 10) ^^ 2; x /= 10; } return result;
}
uint check(in uint[] number) pure nothrow @safe @nogc {
enum uint magic = 89;
uint candidate = 0; foreach (immutable n; number) candidate = candidate * 10 + n;
while (candidate != magic && candidate != 1) candidate = candidate.nextStep;
if (candidate == magic) { uint[10] digitsCount; foreach (immutable d; number) digitsCount[d]++;
uint result = number.length.factorial; foreach (immutable c; digitsCount) result /= c.factorial; return result; }
return 0;
}
void main() nothrow @nogc {
import core.stdc.stdio: printf;
enum uint limit = 100_000_000; immutable uint cacheSize = limit.iLog10;
uint[cacheSize] number; uint result = 0; uint i = cacheSize - 1;
while (true) { if (i == 0 && number[i] == 9) break; if (i == cacheSize - 1 && number[i] < 9) { number[i]++; result += number.check; } else if (number[i] == 9) { i--; } else { number[i]++;
number[i + 1 .. $] = number[i]; i = cacheSize - 1; result += number.check; } }
printf("%u\n", result);
}</lang> The output is the same. The run-time is about 0.04 seconds or less. This third version was ported to D and improved from: mathblog.dk/project-euler-92-square-digits-number-chain/
Java
<lang java>import java.util.stream.IntStream;
public class IteratedDigitsSquaring {
public static void main(String[] args) { long r = IntStream.range(1, 100_000_000) .parallel() .filter(n -> calc(n) == 89) .count(); System.out.println(r); }
private static int calc(int n) { while (n != 89 && n != 1) { int total = 0; while (n > 0) { total += Math.pow(n % 10, 2); n /= 10; } n = total; } return n; }
}</lang>
85744333
Perl 6
This is a brute force version. There's no way it can go up to the required limit in any decent time so we mark this solution as incomplete for now.
<lang perl6>sub Euler92($n) {
(state @)[$n] //= $n == 1|89 ?? $n !! Euler92([+] $n.comb X** 2)
}
say +grep 89, map &Euler92, 1 .. 100_000_000;</lang>
Python
Python: Combinatorics
<lang python>from math import ceil, log10, factorial
def next_step(x):
result = 0 while x > 0: result += (x % 10) ** 2 x /= 10 return result
def check(number):
candidate = 0 for n in number: candidate = candidate * 10 + n
while candidate != 89 and candidate != 1: candidate = next_step(candidate)
if candidate == 89: digits_count = [0] * 10 for d in number: digits_count[d] += 1
result = factorial(len(number)) for c in digits_count: result /= factorial(c) return result
return 0
def main():
limit = 100000000 cache_size = int(ceil(log10(limit))) assert 10 ** cache_size == limit
number = [0] * cache_size result = 0 i = cache_size - 1
while True: if i == 0 and number[i] == 9: break if i == cache_size - 1 and number[i] < 9: number[i] += 1 result += check(number) elif number[i] == 9: i -= 1 else: number[i] += 1 for j in xrange(i + 1, cache_size): number[j] = number[i] i = cache_size - 1 result += check(number)
print result
main()</lang>
- Output:
85744333
The run-time is less than half a second.
Python: Simple caching
<lang python>>>> from functools import lru_cache >>> @lru_cache(maxsize=1024) def ids(n): if n in {1, 89}: return n else: return ids(sum(int(d) ** 2 for d in str(n)))
>>> ids(15)
89
>>> [ids(x) for x in range(1, 21)]
[1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1, 89]
>>> sum(ids(x) == 89 for x in range(1, 100000000))
85744333
>>> </lang>
This took a much longer time, in the order of hours.
Python: Enhanced caching
Notes that the order of digits in a number does not affect the final result so caches the digits of the number in sorted order for more hits. <lang python>>>> from functools import lru_cache >>> @lru_cache(maxsize=1024) def _ids(nt): if nt in {('1',), ('8', '9')}: return nt else: return _ids(tuple(sorted(str(sum(int(d) ** 2 for d in nt)))))
>>> def ids(n):
return int(.join(_ids(tuple(sorted(str(n))))))
>>> ids(1), ids(15) (1, 89) >>> [ids(x) for x in range(1, 21)] [1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1, 89] >>> sum(ids(x) == 89 for x in range(1, 100000000)) 85744333 >>> _ids.cache_info() CacheInfo(hits=99991418, misses=5867462, maxsize=1024, currsize=1024) >>> </lang>
This took tens of minutes to run.
zkl
Using brute force is a never ending process so need to be clever, which takes under a second.
<lang zkl>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.toString().reduce(fcn(sum,c){ sum + 1*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);</lang>
- Output:
85744333