Iterated digits squaring: Difference between revisions
(Haskell version: added a space after commas, spaces as indents, used swap, used Int instead of Integer for speed.) |
(+ lines too long for Ruby entry) |
||
| Line 531: | Line 531: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{lines too long|ruby}} |
|||
<lang ruby> |
<lang ruby> |
||
# Count how many number chains for Natural Numbers < 100_000_000 end with a value 89. |
# Count how many number chains for Natural Numbers < 100_000_000 end with a value 89. |
||
Revision as of 08:37, 2 September 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>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);
}</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/
Haskell
Basic solution that contains just a little more than the essence of this computation. This takes a long time to run: <lang haskell>import Data.List (unfoldr) import Data.Tuple (swap)
ds :: Int -> Int -> Int ds base = sum . map (^ 2) . unfoldr f where
f 0 = Nothing f n = Just . swap $ n `divMod` base
ids :: Int -> Int -> Int ids base = head . dropWhile (`notElem` [1, 89]) . iterate (ds base)
main = do
print $ length $ filter ((== 89) . ids 10) [1 .. 100000000]</lang>
- Output:
85744333
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
<lang perl>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;</lang>
85744333
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.
<lang perl6>constant @sq = ^10 X** 2; my $cnt = 0; my %cache;
sub Euler92($n) {
%cache{$n} //=
$n == any(1,89) ?? $n !!
Euler92( [+] @sq[$n.comb] )
}
for 1 .. 1_000_000 -> $n {
my $i = +$n.comb.sort.join; ++$cnt if Euler92($i) == 89;
}
say $cnt;</lang>
- Output:
856929
All is not lost, however. Through the use of gradual typing, Perl 6 scales down as well as up, so this jit-friendly version is performant enough to brute force the larger calculation: <lang perl6>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;</lang>
- Output:
85744333
This runs in under ten minutes. We can reduce this to 4 minutes by writing in the NQP (Not Quite Perl6) subset of the language: <lang perl6>my $cache := nqp::list_i(); nqp::bindpos_i($cache, 650, 0); nqp::bindpos_i($cache, 1, 1); nqp::bindpos_i($cache, 89, 89);
sub Euler92(int $n) {
$n < 650
?? nqp::bindpos_i($cache,$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 = nqp::div_i($n, $ten); $c = $n - $t * $ten; $sum = $sum + $c * $c; } while $n = $t; $n = nqp::atpos_i($cache,$sum) || $sum;
} $n;
}
my int $cnt = 0; for 1 .. 100_000_000 -> int $n {
$cnt = $cnt + 1 if Euler92($n) == 89;
} say $cnt;</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.
REXX
version 1
This REXX version is essentially a brute force approach and is slow. <lang rexx>/*REXX program to perform iterated digits squaring ('til sum=1 | sum=89)*/ parse arg n . /*get optional N from the C.L. */ if n== then n=1000000 /*Was N given? No, use default.*/ !.=0; do m=1 to 9; !.m=m**2; end /*build a short-cut for squares. */
- .=0 /*count of 1 & 89 results so far.*/
do j=1 for n /* [↓] process each num in range*/
x=j /*use X for a proxy for the J var*/
do until s==1 | s==89 /*add the squared digits of X.*/
s=0 /*set the sum to zero initially. */
do k=1 for length(x) /*process each of the digits in X*/
_=substr(x,k,1) /*pick off a particular X digit*/
s=s+!._ /*do a fast squaring of it & sum.*/
end /*k*/ /* [↑] S≡is sum of squared digs.*/
x=s /*subsitute the sum for "new" X. */
end /*until*/ /* [↑] keep looping 'til S=1|89.*/
#.s=#.s+1 /*bump the counter for 1's | 89's*/
end /*j*/
do i=1 by 89-1 for 2; c=' 'right('"'i'"',4)' chains '
say 'count of' c 'for all natural numbers up to ' n " is " #.i
end /*i*/
/*stick a fork in it, we're done.*/</lang>
output when using the default input:
count of "1" chains for all natural numbers up to 1000000 is 143071 count of "89" chains for all natural numbers up to 1000000 is 856929
version 2
This Rexx version is optimized (by processing the numbers in four-digit chunks), but it's still on the slow side. <lang rexx>/*REXX program to perform iterated digits squaring ('til sum=1 | sum=89)*/ parse arg n . /*get optional N from the C.L. */ if n== then n=100000000 /*Was N given? No, use default.*/ !.=0; do m=1 to 9; !.m=m**2; end /*build a short-cut for squares. */ $.=.; $.0=0; $.00=0; $.000=0; $.0000=0; @.=. /*short-cuts for some sums*/ @.=. /*placeholder for computed sums. */
- .=0 /*count of 1 & 89 results so far.*/
do j=1 for n /* [↓] process each num in range*/
s=sumds(j) /*get the sum of squared digits. */
#.s=#.s+1 /*bump the counter for 1's | 89's*/
end /*j*/
do i=1 by 89-1 for 2; c=' 'right('"'i'"',4)' chains '
say 'count of' c 'for all natural numbers up to ' n " is " #.i
end /*i*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────SUMDS subroutine────────────────────*/ sumds: parse arg z; p=0
do m=1 by 4 to length(z)
p=p + summer(substr(z,m,4))
end /*m*/
if $.p\==. then return $.p /*if computed before, use the val*/ y=p
do until s==1 | s==89 /*add the squared digits of P.*/
s=0 /*set the sum to zero initially. */
do k=1 for length(y) /*process each of the digits in X*/
_=substr(y,k,1) /*pick off a particular X digit*/
s=s+!._ /*do a fast squaring of it & sum.*/
end /*k*/ /* [↑] S≡is sum of squared digs.*/
y=s /*subsitute the sum for "new" X. */
end /*until*/ /* [↑] keep looping 'til S=1|89.*/
$.p=s return s /*──────────────────────────────────SUMMER subroutine───────────────────*/ summer: parse arg y . 1 oy .; if @.y\==. then return @.y /*use old val*/ a=0
do k=1 for length(y) /*process each of the digits in X*/
_=substr(y,k,1) /*pick off a particular X digit*/
a=a+!._ /*do a fast squaring of it & sum.*/
end /*k*/ /* [↑] S≡is sum of squared digs.*/
@.oy=a return a</lang> output when using the default input:
count of "1" chains for all natural numbers up to 1000000 is 14255667 count of "89" chains for all natural numbers up to 1000000 is 85744333
Ruby
<lang ruby>
- Count how many number chains for Natural Numbers < 100_000_000 end with a value 89.
- Nigel_Galloway
- August 26th., 2014.
require 'benchmark' F = Array.new(9){|n| n==0?1:(1..n).inject(:*)} N = (G=Array.new(649){|n| (i=((n%1000)/100)**2+((n%100)/10)**2+(n%10)**2)==89 ? 0:i}).collect{|n| while n>1 do n = G[n] end; n }
z = [0,0] t = Benchmark.measure do (0..9).each{|n| (n..9).each{|i| (i..9).each{|g| (g..9).each{|e| (e..9).each{|l| (l..9).each{|a| (a..9).each{|o| (o..9).each{|w|
next if w == 0
gn = 40320
nn = [0,0,0,0,0,0,0,0,0,0]
ng = [n,i,g,e,l,a,o,w]
ng.each{|n| nn[n] += 1}
nn.each{|n| gn /= F[n]}
z[N[ng.collect{|n| n*n}.inject(:+)]] += gn
}}}}}}}} end
puts "\n\n#{z[1]} numbers produce 1 and #{z[0]} numbers produce 89"
puts "\n\nTiming\n#{t}" </lang>
- Output:
14255666 numbers produce 1 and 85744333 numbers produce 89 Timing 0.250000 0.000000 0.250000 ( 0.245309)
Tcl
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
<lang tcl>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</lang>
Intelligent Version
Conversion back and forth between numbers and strings is slow. Using math operations directly is much faster (around 4 times in informal testing). <lang tcl>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</lang>
Substantially More Intelligent Version
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 quarter of a second.--Nigel Galloway (talk) 12:47, 31 August 2014 (UTC)
<lang tcl># 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
}}</lang>
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