Rosetta Code

Iterated digits squaring: Difference between revisions

Page Discussion

Iterated digits squaring (view source)

Revision as of 12:13, 14 March 2020

17 bytes added ,  4 years ago
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(X86 Assembly implementation)
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
Line 130:
Number of values whose squared digit sum is 89: 85744333
</pre>
 
=={{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.
Line 410 ⟶ 411:
choose_sum_and_count_89(chosen, 0, 8, 0, 10, &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;
}
Line 777 ⟶ 734:
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.
 
=={{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}}==
Line 909 ⟶ 910:
both tested on i7 CPU 920@2.67GHZ)
</pre>
 
=={{header|Common Lisp}}==
<lang lisp>
Line 1,218 ⟶ 1,220:
Running time: 55.76544594 seconds
</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 &mdash;i.e. XML, JSON&mdash; 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}}==
Line 1,320 ⟶ 1,314:
85744333
</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 &mdash;i.e. XML, JSON&mdash; 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}}==
Line 1,417 ⟶ 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.
 
=={{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}}==
Line 1,577 ⟶ 1,524:
# user 0m3.942s
# 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}}==
Line 1,713 ⟶ 1,715:
 
{{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}}==
Line 1,764 ⟶ 1,813:
856,929
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>
 
Line 2,033 ⟶ 2,035:
 
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}}==
Line 2,792 ⟶ 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.
 
=={{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}}==
Line 2,981 ⟶ 2,984:
24.337392 sec
</pre>
 
 
=={{header|Rust}}==
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/249980"