Iterated digits squaring: Difference between revisions
(X86 Assembly implementation) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 130: | Line 130: | ||
Number of values whose squared digit sum is 89: 85744333 |
Number of values whose squared digit sum is 89: 85744333 |
||
</pre> |
</pre> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
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. |
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. |
||
Line 410: | Line 411: | ||
choose_sum_and_count_89(chosen, 0, 8, 0, 10, &count); |
choose_sum_and_count_89(chosen, 0, 8, 0, 10, &count); |
||
printf("%d\n",count); |
printf("%d\n",count); |
||
return 0; |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre>85744333</pre> |
|||
=={{header|C++}}== |
|||
Slow (~10 seconds on my machine) brute force C++ implementation: |
|||
<lang cpp> |
|||
#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; |
return 0; |
||
} |
} |
||
Line 777: | Line 734: | ||
1->10^230: 86768211402812128806590576564537513494737520987736487082881857738963221877281843731844788716420658593474347727365894819526796319707828593251356370569187398794672340428112756386987781701631240923503544557476729747177320351749598558 |
1->10^230: 86768211402812128806590576564537513494737520987736487082881857738963221877281843731844788716420658593474347727365894819526796319707828593251356370569187398794672340428112756386987781701631240923503544557476729747177320351749598558 |
||
6.0396929 seconds elapsed.</pre>It doesn't always get to 10^230 in six seconds at Tio.run, sometimes it only gets to 10^201 or so. |
6.0396929 seconds elapsed.</pre>It doesn't always get to 10^230 in six seconds at Tio.run, sometimes it only gets to 10^201 or so. |
||
=={{header|C++}}== |
|||
Slow (~10 seconds on my machine) brute force C++ implementation: |
|||
<lang cpp> |
|||
#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; |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre>85744333</pre> |
|||
=={{header|Ceylon}}== |
=={{header|Ceylon}}== |
||
Line 909: | Line 910: | ||
both tested on i7 CPU 920@2.67GHZ) |
both tested on i7 CPU 920@2.67GHZ) |
||
</pre> |
</pre> |
||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
<lang lisp> |
<lang lisp> |
||
Line 1,218: | Line 1,220: | ||
Running time: 55.76544594 seconds |
Running time: 55.76544594 seconds |
||
</pre> |
</pre> |
||
=={{header|Fōrmulæ}}== |
|||
In [https://wiki.formulae.org/Iterated_digits_squaring this] page you can see the solution of this task. |
|||
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). 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 transportation effects more than visualization and edition. |
|||
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code. |
|||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
Line 1,320: | Line 1,314: | ||
85744333 |
85744333 |
||
</pre> |
</pre> |
||
=={{header|Fōrmulæ}}== |
|||
In [https://wiki.formulae.org/Iterated_digits_squaring this] page you can see the solution of this task. |
|||
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). 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 transportation effects more than visualization and edition. |
|||
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code. |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
Line 1,417: | Line 1,419: | ||
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. |
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. |
||
=={{header|Julia}}== |
|||
{{works with|Julia|0.6}} |
|||
'''Brute force solution''': |
|||
<lang julia>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)</lang> |
|||
'''More clever solution''': |
|||
<lang julia>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</lang> |
|||
'''Benchmarks''' |
|||
<lang julia>@time itercount(100_000_000) |
|||
@time itercountcombos(8) |
|||
@time itercountcombos(17)</lang> |
|||
{{out}} |
|||
<pre> 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)</pre> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
Line 1,577: | Line 1,524: | ||
# user 0m3.942s |
# user 0m3.942s |
||
# sys 0m0.009s</lang> |
# sys 0m0.009s</lang> |
||
=={{header|Julia}}== |
|||
{{works with|Julia|0.6}} |
|||
'''Brute force solution''': |
|||
<lang julia>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)</lang> |
|||
'''More clever solution''': |
|||
<lang julia>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</lang> |
|||
'''Benchmarks''' |
|||
<lang julia>@time itercount(100_000_000) |
|||
@time itercountcombos(8) |
|||
@time itercountcombos(17)</lang> |
|||
{{out}} |
|||
<pre> 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)</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
Line 1,713: | Line 1,715: | ||
{{out}}<pre>85744333</pre> |
{{out}}<pre>85744333</pre> |
||
=={{header|Oberon-2}}== |
|||
{{works with|oo2c Version 2} |
|||
<lang oberon2> |
|||
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. |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
85744333 |
|||
real 0m12.201s |
|||
user 0m12.179s |
|||
sys 0m0.001s |
|||
</pre> |
|||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
Line 1,764: | Line 1,813: | ||
856,929 |
856,929 |
||
85,744,333 |
85,744,333 |
||
</pre> |
|||
=={{header|Oberon-2}}== |
|||
{{works with|oo2c Version 2} |
|||
<lang oberon2> |
|||
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. |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
85744333 |
|||
real 0m12.201s |
|||
user 0m12.179s |
|||
sys 0m0.001s |
|||
</pre> |
</pre> |
||
Line 2,033: | Line 2,035: | ||
85744333 |
85744333 |
||
=={{header|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; |
|||
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;</lang> |
|||
{{out}} |
|||
<pre>856929</pre> |
|||
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> |
|||
{{out}} |
|||
<pre>85744333</pre> |
|||
Which is better, but is still pretty slow. |
|||
The biggest gains are often from choosing the right algorithm. |
|||
<lang perl6>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;</lang> |
|||
{{out}} |
|||
<pre>85744333</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 2,792: | Line 2,698: | ||
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. |
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. |
||
=={{header|Raku}}== |
|||
(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. |
|||
<lang perl6>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;</lang> |
|||
{{out}} |
|||
<pre>856929</pre> |
|||
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> |
|||
{{out}} |
|||
<pre>85744333</pre> |
|||
Which is better, but is still pretty slow. |
|||
The biggest gains are often from choosing the right algorithm. |
|||
<lang perl6>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;</lang> |
|||
{{out}} |
|||
<pre>85744333</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 2,981: | Line 2,984: | ||
24.337392 sec |
24.337392 sec |
||
</pre> |
</pre> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
Revision as of 12:13, 14 March 2020
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:
<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.
For a quick algorithm for this task see the talk page
- Related tasks
Ada
<lang Ada>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;</lang>
- Output:
In range 1 .. 999_999: 856929 In range 1 .. 99_999_999: 85744333
ALGOL 68
Brute-force with some caching. <lang algol68># 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 ) )</lang>
- Output:
Number of values whose squared digit sum is 89: 85744333
AWK
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. <lang AWK># 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
}</lang>
- 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
Three versions timed on a 2.50GHz Intel Desktop. <lang bbcbasic> 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</lang>
- Output:
Version 1: 85744333 in 1447.08 seconds. Version 2: 85744333 in 718.04 seconds. Version 3: 85744333 in 0.02 seconds.
Befunge
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.
<lang befunge>1-1\10v!:/+55\<>::**>>-!| v0:\+<_:55+%:*^^"d":+1$<: >\`!#^ _$:"Y"-#v_$\1+\:^0 >01-\0^ @,+55.<>:1>-!>#^_ >,,,$." >=",,,^ >>".1">#<</lang>
- Output:
1..1000000 => 856929
1..100000000 => 85744333
C
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. <lang c>#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; }</lang>
- 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: <lang c>
- 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;
} </lang>
- Output:
85744333
C#
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.
<lang csharp>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; } }
}</lang>
- Output:
856929 85744333
BigInteger version
Translation of the first C version, with BigIntegers. This can get pretty far in six seconds, even on Tio.run. <lang csharp>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); }
}</lang>
- 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++
Slow (~10 seconds on my machine) brute force C++ implementation: <lang cpp>
- 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;
} </lang>
- Output:
85744333
Ceylon
<lang ceylon>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); }</lang>
Clojure
Direct Method
<lang lisp>(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)))
</lang>
- Output:
85744333 Time: 335 seconds
Using Combinations
<lang> (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)) )
</lang>
{
- 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
<lang lisp> (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)))
</lang>
- 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
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 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/
A purely functional version, from the Haskell code. It includes two functions currently missing in Phobos used in the Haskell code.
<lang d>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;
}</lang> With a small back-porting (to run it with the Phobos of LDC2 2.065) it runs in about 15.5 seconds.
ERRE
<lang ERRE> 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 </lang> This program verifies a number only. With a FOR..END FOR loop it's possible to verify a number range.
Factor
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. <lang>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</lang>
- Output:
85744333 Running time: 55.76544594 seconds
FreeBASIC
<lang freebasic>' 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</lang>
- Output:
There are 85744333 numbers from 1 to 100 million ending with 89 Elapsed milliseconds = 2
Frink
<lang frink> 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] </lang>
- Output:
85744333
Fōrmulæ
In this page you can see the solution of this task.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). 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 transportation effects more than visualization and edition.
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
Go
It's basic. Runs in about 30 seconds on an old laptop.
<lang go>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) }</lang>
- Output:
85744333
Haskell
Basic solution that contains just a little more than the essence of this computation. This runs in less than eight minutes: <lang haskell>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]</lang>
- Output:
85744333
J
Here's an expression to turn a number into digits:
<lang J>digits=: 10&#.inv</lang>
And here's an expression to square them and find their sum: <lang J>sumdigsq=: +/"1@:*:@digits</lang>
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)
<lang J> sumdigsq^:(i.16) 15 15 26 40 16 37 58 89 145 42 20 4 16 37 58 89 145</lang>
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:
<lang J>itdigsq4=:4 = sumdigsq^:(0=e.&4)^:_"0</lang>
But we do not actually need to iterate. The largest value after the first iteration would be:
<lang J> sumdigsq 99999999 648</lang>
So we could write a routine which works for the intended range, and stops after the first iteration: <lang J>itdigsq1=:1 = sumdigsq^:(0=e.&4)^:_"0 digsq1e8=:(I.itdigsq1 i.649) e.~ sumdigsq</lang>
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:
<lang J> +/+/@:-.@digsq1e8"1(1+i.100 1e6) 85744333</lang>
Of course, there are faster ways of obtaining that result. The fastest is probably this: <lang J> 85744333 85744333</lang>
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
<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
jq
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 <lang jq>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 ) ;</lang>
Part 2: The Generic Task
Count how many number chains beginning with n (where 0 < n < 10^D) end with a value 89. <lang jq>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) ;</lang>
Part 3: D=8 <lang jq>task(8)</lang>
- Output:
<lang sh>$ 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</lang>
Julia
Brute force solution: <lang julia>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)</lang>
More clever solution: <lang julia>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</lang>
Benchmarks <lang julia>@time itercount(100_000_000) @time itercountcombos(8) @time itercountcombos(17)</lang>
- 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
<lang scala>// 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")
}</lang>
- Output:
There are 85744333 numbers from 1 to 100 million ending with 89
Lua
<lang lua>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)</lang>
- Output:
85744333
Mathematica / Wolfram Language
<lang Mathematica>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</lang>
- Output:
85744333
Oberon-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 tenth 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>
VBScript
<lang vb> 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 </lang>
- Output:
Elapse time is in seconds. Friends don't let friends do this in VBScript. :-)
Elapse Time: 2559 Count: 85744333
X86 Assembly
<lang asm> 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
</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.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);</lang>
- Output:
85744333
ZX Spectrum Basic
Very, very slow. Use a ZX Spectrum emulator and run with maximum speed option enabled. <lang zxbasic>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</lang>
- Output:
Version 1: 857
- Pages using duplicate arguments in template calls
- Programming Tasks
- Solutions by Programming Task
- Ada
- ALGOL 68
- AWK
- BBC BASIC
- Befunge
- C
- C sharp
- System.Numerics
- C++
- Ceylon
- Clojure
- Common Lisp
- D
- ERRE
- Factor
- FreeBASIC
- Frink
- Fōrmulæ
- Go
- Haskell
- J
- Java
- Jq
- Julia
- Kotlin
- Lua
- Mathematica
- Wolfram Language
- Oberon-2
- VBScript
- X86 Assembly
- Zkl
- ZX Spectrum Basic