Combinations with repetitions/Square digit chain: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Perl}}: Fix-up Perl 6 -> Raku references)
m (→‎{{header|Wren}}: Minor tidy)
 
(9 intermediate revisions by 6 users not shown)
Line 13: Line 13:
=={{header|D}}==
=={{header|D}}==
{{improve|D|See talk page}}
{{improve|D|See talk page}}
<syntaxhighlight lang="d">
<lang d>
// Count how many number chains for Natural Numbers < 10**K end with a value of 1.
// Count how many number chains for Natural Numbers < 10**K end with a value of 1.
//
//
Line 117: Line 117:
writefln ("\n(k=%d) In the range 1 to %d\n%d translate to 1 and %d translate to 89\n", K, (cast (ulong) (10))^^K-1,z,(cast (ulong) (10))^^K-1-z);
writefln ("\n(k=%d) In the range 1 to %d\n%d translate to 1 and %d translate to 89\n", K, (cast (ulong) (10))^^K-1,z,(cast (ulong) (10))^^K-1-z);
}
}
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 138: Line 138:
=={{header|Go}}==
=={{header|Go}}==
{{trans|Kotlin}}
{{trans|Kotlin}}
<lang go>package main
<syntaxhighlight lang="go">package main


import (
import (
Line 191: Line 191:
fmt.Println(count1, "numbers produce 1 and", limit-count1, "numbers produce 89\n")
fmt.Println(count1, "numbers produce 1 and", limit-count1, "numbers produce 89\n")
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 209: Line 209:
For k = 17 in the range 1 to 99999999999999999
For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89
</pre>

=={{header|jq}}==
{{trans|Wren}}
'''Works with jq''' (*)

'''Works with gojq, the Go implementation of jq'''

(*) For the given values of k up to and including 14, the C implementation of jq has sufficient
precision, but for k==17, the unbounded precision integer arithmetic
of gojq would be required. The output shown below is taken from a gojq run.

<syntaxhighlight lang="jq"># For gojq:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);

def endsWithOne:
. as $start
| { n: ., sum: 0 }
| until(.stop;
until(.n <= 0;
(.n % 10) as $digit
| .sum += $digit * $digit
| .n = (.n / 10 | floor)
)
| if .sum == 1 then .stop = 1
elif .sum == 89 then .stop = 0
else .n = .sum
| .sum = 0
end )
| .stop == 1 ;
def ks: [7, 8, 11, 14, 17];

ks[] as $k
| {sums: [1,0]}
| reduce range(1; $k+1) as $n (.;
reduce range( $n*81; 0; -1) as $i (.;
.emit = false
| .j = 0
| until(.emit or (.j == 9);
.j+=1
| (.j * .j) as $s
| if ($s > $i) then .emit = true
else .sums[$i] = .sums[$i] + .sums[$i-$s]
end) ))
| .count1 = 0
| reduce range(1; 1 + $k*81) as $i (.; if $i|endsWithOne then .count1 = .count1 + .sums[$i] else . end)
| ((10|power($k)) - 1) as $limit
| "For k = \($k) in the range 1 to \($limit)",
"\(.count1) numbers produce 1 and \($limit - .count1) numbers produce 89.\n"</syntaxhighlight>
{{out}}
<pre>
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89.

For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89.

For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89.

For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89.

For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89.
</pre>
</pre>


=={{header|Julia}}==
=={{header|Julia}}==
<lang julia>using Combinatorics
<syntaxhighlight lang="julia">using Combinatorics


function iterate(m::Integer)
function iterate(m::Integer)
Line 247: Line 313:
testitersquares(i)
testitersquares(i)
end
end
</lang>{{out}}
</syntaxhighlight>{{out}}
<pre>
<pre>
For k = 2, in the range 1 to 99,
For k = 2, in the range 1 to 99,
Line 272: Line 338:


So the following generalizes that code to deal with values of k up to 17 (which requires 64 bit integers) and to count numbers where the squared digits sum sequence eventually ends in 1 rather than 89, albeit the sum of both must of course be 10 ^ k - 1.
So the following generalizes that code to deal with values of k up to 17 (which requires 64 bit integers) and to count numbers where the squared digits sum sequence eventually ends in 1 rather than 89, albeit the sum of both must of course be 10 ^ k - 1.
<lang scala>// version 1.1.51
<syntaxhighlight lang="scala">// version 1.1.51


fun endsWithOne(n: Int): Boolean {
fun endsWithOne(n: Int): Boolean {
Line 313: Line 379:
println("$count1 numbers produce 1 and ${limit - count1} numbers produce 89\n")
println("$count1 numbers produce 1 and ${limit - count1} numbers produce 89\n")
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 332: Line 398:
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89
</pre>
</pre>

=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">import math, strformat

func endsWithOne(n: Natural): bool =
var n = n
while true:
var sum = 0
while n > 0:
let digit = n mod 10
sum += digit * digit
n = n div 10
if sum == 1: return true
if sum == 89: return false
n = sum

const Ks = [7, 8, 11, 14, 17]

for k in Ks:
var sums = newSeq[int64](k * 81 + 1) # Initialized to 0s.
sums[0] = 1
for n in 1..k:
for i in countdown(n * 81, 1):
for j in 1..9:
let s = j * j
if s > i: break
sums[i] += sums[i - s]

var count1 = 0i64
for i in 1..k*81:
if i.endsWithOne(): count1 += sums[i]
let limit = 10^k - 1
echo &"For k = {k} in the range 1 to {limit}"
echo &"{count1} numbers produce 1 and {limit - count1} numbers produce 89\n"</syntaxhighlight>

{{out}}
<pre>For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89

For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89

For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89

For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89

For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89</pre>


=={{header|Perl}}==
=={{header|Perl}}==
{{trans|Raku}}
{{trans|Raku}}
<lang perl>use strict;
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
use feature 'say';
use Math::AnyNum qw(:overload);

#use bigint; # un-comment to support the k = 17 case


sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
Line 360: Line 477:
}
}


my @ks = <7 8 11 14>;
my @ks = <7 8 11 14 17>;


for my $k (@ks) {
for my $k (@ks) {
Line 368: Line 485:
for my $i (reverse 1 .. $n*81) {
for my $i (reverse 1 .. $n*81) {
for my $j (1 .. 9) {
for my $j (1 .. 9) {
no warnings 'uninitialized';
last if ($s = $j**2) > $i;
last if ($s = $j**2) > $i;
$sums[$i] += $sums[$i-$s];
$sums[$i] += $sums[$i-$s];
Line 378: Line 496:
say "For k = $k in the range 1 to " . comma $limit;
say "For k = $k in the range 1 to " . comma $limit;
say comma($count1) . ' numbers produce 1 and ' . comma($limit-$count1) . " numbers produce 89\n";
say comma($count1) . ' numbers produce 1 and ' . comma($limit-$count1) . " numbers produce 89\n";
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>For k = 7 in the range 1 to 9,999,999
<pre>For k = 7 in the range 1 to 9,999,999
Line 390: Line 508:


For k = 14 in the range 1 to 99,999,999,999,999
For k = 14 in the range 1 to 99,999,999,999,999
13,770,853,279,684 numbers produce 1 and 86,229,146,720,315 numbers produce 89</pre>
13,770,853,279,684 numbers produce 1 and 86,229,146,720,315 numbers produce 89

For k = 17 in the range 1 to 99,999,999,999,999,999
12,024,696,404,768,024 numbers produce 1 and 87,975,303,595,231,975 numbers produce 89</pre>


=={{header|Phix}}==
=={{header|Phix}}==
{{trans|Wren}}
There is a solution to this on the [[Iterated_digits_squaring#Combinatorics_version|Iterated_digits_squaring]] page
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">endsWithOne</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">total</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">digit</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">digit</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">==</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">==</span><span style="color: #000000;">89</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">total</span>
<span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">ks</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">count1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">ki</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ks</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ki</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sums</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">k</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">j</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">endsWithOne</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_set_d</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">comma_fill</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">comma_fill</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">,</span><span style="color: #000000;">comma_fill</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"For k = %d in the range 1 to %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s numbers produce 1 and %s numbers produce 89\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
For k = 7 in the range 1 to 9,999,999
1,418,853 numbers produce 1 and 8,581,146 numbers produce 89

For k = 8 in the range 1 to 99,999,999
14,255,666 numbers produce 1 and 85,744,333 numbers produce 89

For k = 11 in the range 1 to 99,999,999,999
15,091,199,356 numbers produce 1 and 84,908,800,643 numbers produce 89

For k = 14 in the range 1 to 99,999,999,999,999
13,770,853,279,684 numbers produce 1 and 86,229,146,720,315 numbers produce 89

For k = 17 in the range 1 to 99,999,999,999,999,999
12,024,696,404,768,024 numbers produce 1 and 87,975,303,595,231,975 numbers produce 89
</pre>
Also, [[Iterated_digits_squaring#Phix]] produces some of the same numbers (just not so high).


=={{header|Raku}}==
=={{header|Raku}}==
(formerly Perl 6)
(formerly Perl 6)
{{trans|Kotlin}}
{{trans|Kotlin}}
<lang perl6>use v6;
<syntaxhighlight lang="raku" line>use v6;


sub endsWithOne($n --> Bool) {
sub endsWithOne($n --> Bool) {
Line 436: Line 629:
say "For k = $k in the range 1 to $limit";
say "For k = $k in the range 1 to $limit";
say "$count1 numbers produce 1 and ",$limit-$count1," numbers produce 89";
say "$count1 numbers produce 1 and ",$limit-$count1," numbers produce 89";
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 451: Line 644:


=={{header|Ruby}}==
=={{header|Ruby}}==
<lang ruby>
<syntaxhighlight lang="ruby">
# Count how many number chains for Natural Numbers < 10**K end with a value of 1.
# Count how many number chains for Natural Numbers < 10**K end with a value of 1.
#
#
Line 474: Line 667:
}
}
puts "\nk=(#{K}) in the range 1 to #{10**K-1}\n#{z} numbers produce 1 and #{10**K-1-z} numbers produce 89"
puts "\nk=(#{K}) in the range 1 to #{10**K-1}\n#{z} numbers produce 1 and #{10**K-1-z} numbers produce 89"
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 491: Line 684:
#(k=17) in the range 1 to 99999999999999999
#(k=17) in the range 1 to 99999999999999999
#12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89
#12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89
</pre>

=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
As Wren doesn't have 64 bit integers, it is necessary to use BigInt here to process k = 17.
<syntaxhighlight lang="wren">import "./big" for BigInt

var endsWithOne = Fn.new { |n|
var sum = 0
while (true) {
while (n > 0) {
var digit = n % 10
sum = sum + digit * digit
n = (n/10).floor
}
if (sum == 1) return true
if (sum == 89) return false
n = sum
sum = 0
}
}

var ks = [7, 8, 11, 14, 17]
for (k in ks) {
var sums = List.filled(k * 81 + 1, 0)
sums[0] = 1
sums[1] = 0
for (n in 1..k) {
for (i in n*81..1) {
for (j in 1..9) {
var s = j * j
if (s > i) break
sums[i] = sums[i] + sums[i-s]
}
}
}
var count1 = BigInt.zero
for (i in 1..k*81) if (endsWithOne.call(i)) count1 = count1 + sums[i]
var limit = BigInt.ten.pow(k) - 1
System.print("For k = %(k) in the range 1 to %(limit)")
System.print("%(count1) numbers produce 1 and %(limit - count1) numbers produce 89\n")
}</syntaxhighlight>

{{out}}
<pre>
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89

For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89

For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89

For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89

For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89
</pre>
</pre>


=={{header|zkl}}==
=={{header|zkl}}==
{{trans|Ruby}}
{{trans|Ruby}}
<lang zkl>fcn countNumberChains(K){
<syntaxhighlight lang="zkl">fcn countNumberChains(K){
F:=(K+1).pump(List,fcn(n){ (1).reduce(n,'*,1) }); #Some small factorials
F:=(K+1).pump(List,fcn(n){ (1).reduce(n,'*,1) }); #Some small factorials
g:=fcn(n){
g:=fcn(n){
Line 516: Line 769:
println("%,d numbers produce 1 and %,d numbers produce 89".fmt(z,(10).pow(K)-1-z));
println("%,d numbers produce 1 and %,d numbers produce 89".fmt(z,(10).pow(K)-1-z));
z
z
}</lang>
}</syntaxhighlight>
combosKW(k,sequence) is lazy, which, in this case, is quite a bit faster than the non-lazy version.
combosKW(k,sequence) is lazy, which, in this case, is quite a bit faster than the non-lazy version.
<lang zkl>foreach K in (T(7,8,11,14,17)){ countNumberChains(K) }</lang>
<syntaxhighlight lang="zkl">foreach K in (T(7,8,11,14,17)){ countNumberChains(K) }</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>

Latest revision as of 11:35, 20 November 2023

Combinations with repetitions/Square digit chain is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Iterated digits squaring introduces RC the Project Euler Task #92. Combinations with repetitions introduce RC to the concept of generating all the combinations with repetitions of n types of things taken k at a time.

The purpose of this task is to combine these tasks as follows:

The collections of k items will be taken from [0,1,4,9,16,25,36,49,64,81] and must be obtained using code from Combinations with repetitions. The collection of k zeroes is excluded.
For each collection of k items determine if it translates to 1 using the rules from Iterated digits squaring
For each collection which translates to 1 determine the number of different ways, c say, in which the k items can be uniquely ordered.
Keep a running total of all the values of c obtained
Answer the Project Euler Task #92 question (k=7).
Answer the equivalent question for k=8,11,14.
Optionally answer the question for k=17. These numbers will be larger than the basic integer type for many languages, if it is not easy to use larger numbers it is not necessary for this task.

D

This example is in need of improvement:

See talk page

// Count how many number chains for Natural Numbers < 10**K end with a value of 1.
//
import std.stdio, std.range;
 
const struct CombRep {
    immutable uint nt, nc;
    private const ulong[] combVal;
 
    this(in uint numType, in uint numChoice) pure nothrow @safe
    in {
        assert(0 < numType && numType + numChoice <= 64,
               "Valid only for nt + nc <= 64 (ulong bit size)");
    } body {
        nt = numType;
        nc = numChoice;
        if (nc == 0)
            return;
        ulong v  = (1UL << (nt - 1)) - 1;
 
        // Init to smallest number that has nt-1 bit set
        // a set bit is metaphored as a _type_ seperator.
        immutable limit = v << nc;
 
        ulong[] localCombVal;
        // Limit is the largest nt-1 bit set number that has nc
        // zero-bit a zero-bit means a _choice_ between _type_
        // seperators.
        while (v <= limit) {
            localCombVal ~= v;
            if (v == 0)
                break;
            // Get next nt-1 bit number.
            immutable t = (v | (v - 1)) + 1;
            v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
        }
        this.combVal = localCombVal;
    }
 
    uint length() @property const pure nothrow @safe {
        return combVal.length;
    }
 
    uint[] opIndex(in uint idx) const pure nothrow @safe {
        return val2set(combVal[idx]);
    }
 
    int opApply(immutable int delegate(in ref uint[]) pure nothrow @safe dg)
    pure nothrow @safe {
        foreach (immutable v; combVal) {
            auto set = val2set(v);
            if (dg(set))
                break;
        }
        return 1;
    }
 
    private uint[] val2set(in ulong v) const pure nothrow @safe {
        // Convert bit pattern to selection set
        immutable uint bitLimit = nt + nc - 1;
        uint typeIdx = 0;
        uint[] set;
        foreach (immutable bitNum; 0 .. bitLimit)
            if (v & (1 << (bitLimit - bitNum - 1)))
                typeIdx++;
            else
                set ~= typeIdx;
        return set;
    }
}
 
// For finite Random Access Range.
auto combRep(R)(R types, in uint numChoice) /*pure*/ nothrow @safe
if (hasLength!R && isRandomAccessRange!R) {
    ElementType!R[][] result;
 
    foreach (const s; CombRep(types.length, numChoice)) {
        ElementType!R[] r;
        foreach (immutable i; s)
            r ~= types[i];
        result ~= r;
    }
 
    return result;
}
 
void main() {
    int K = 17;
    ulong[] F = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000];
    int[] N = [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0];

    ulong z = 0;
    foreach (const e; combRep([0,1,4,9,16,25,36,49,64,81], K)) {
      int s = 0;
      foreach (const g; e) s += g;
      if (N[s] == 0) continue;
      int [int] n;
      foreach (const g; e) n[g] += 1;
	ulong gn = F[K];
      foreach (const g; n.byValue()) gn /= F[g];
	z += gn;
      }
      writefln ("\n(k=%d) In the range 1 to %d\n%d translate to 1 and %d translate to 89\n", K, (cast (ulong) (10))^^K-1,z,(cast (ulong) (10))^^K-1-z);
}
Output:
//(k=7) In the range 1 to 9999999
//1418853 translate to 1 and 8581146 translate to 89

//(k=8) In the range 1 to 99999999
//14255666 translate to 1 and 85744333 translate to 89

//(k=11) In the range 1 to 99999999999
//15091199356 translate to 1 and 84908800643 translate to 89

//(k=14) In the range 1 to 99999999999999
//13770853279684 translate to 1 and 86229146720315 translate to 89

//(k=17) In the range 1 to 99999999999999999
//12024696404768024 translate to 1 and 87975303595231975 translate to 89

Go

Translation of: Kotlin
package main

import (
    "fmt"
    "math"
)

func endsWithOne(n int) bool {
    sum := 0
    for {
        for n > 0 {
            digit := n % 10
            sum += digit * digit
            n /= 10
        }
        if sum == 1 {
            return true
        }
        if sum == 89 {
            return false
        }
        n = sum
        sum = 0
    }
}

func main() {
    ks := [...]int{7, 8, 11, 14, 17}
    for _, k := range ks {
        sums := make([]int64, k*81+1)
        sums[0] = 1
        sums[1] = 0
        for n := 1; n <= k; n++ {
            for i := n * 81; i > 0; i-- {
                for j := 1; j < 10; j++ {
                    s := j * j
                    if s > i {
                        break
                    }
                    sums[i] += sums[i-s]
                }
            }
        }
        count1 := int64(0)
        for i := 1; i <= k*81; i++ {
            if endsWithOne(i) {
                count1 += sums[i]
            }
        }
        limit := int64(math.Pow10(k)) - 1
        fmt.Println("For k =", k, "in the range 1 to", limit)
        fmt.Println(count1, "numbers produce 1 and", limit-count1, "numbers produce 89\n")
    }
}
Output:
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89

For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89

For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89

For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89

For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89

jq

Translation of: Wren

Works with jq (*)

Works with gojq, the Go implementation of jq

(*) For the given values of k up to and including 14, the C implementation of jq has sufficient precision, but for k==17, the unbounded precision integer arithmetic of gojq would be required. The output shown below is taken from a gojq run. 

# For gojq:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);

def endsWithOne:
  . as $start
  | { n: ., sum: 0 }
  | until(.stop; 
        until(.n <= 0;
             (.n % 10) as $digit
            | .sum +=  $digit * $digit
            | .n = (.n / 10 | floor)
        )
        | if .sum == 1 then .stop = 1
          elif .sum == 89 then .stop = 0
	  else .n = .sum
	  | .sum = 0
	  end )
  | .stop == 1 ;
 
def ks: [7, 8, 11, 14, 17];

ks[] as $k
| {sums: [1,0]}
| reduce range(1; $k+1) as $n (.;
        reduce range( $n*81; 0; -1) as $i (.;
    	    .emit = false
	    | .j = 0
            | until(.emit or (.j == 9);
	        .j+=1
                | (.j * .j) as $s
                | if ($s > $i) then .emit = true
                  else .sums[$i] = .sums[$i] + .sums[$i-$s]
                  end) ))
| .count1 = 0
| reduce range(1; 1 + $k*81) as $i (.; if $i|endsWithOne then .count1 = .count1 + .sums[$i] else . end)
| ((10|power($k)) - 1) as $limit
| "For k = \($k) in the range 1 to \($limit)",
  "\(.count1) numbers produce 1 and \($limit - .count1) numbers produce 89.\n"
Output:
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89.

For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89.

For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89.

For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89.

For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89.

Julia

using Combinatorics

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

function testitersquares(numdigits)
    items =  [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
    onecount, eightyninecount = 0, 0
    for combo in with_replacement_combinations(items, numdigits)
        if any(x -> x != 0, combo)
            pcount = Int(factorial(length(combo)) / 
                prod(y -> factorial(sum(x -> x == y, combo)), unique(combo)))
            if iterate(sum(combo)) == 89
                eightyninecount += pcount
            else
                onecount += pcount
            end
        end
    end
    println("For k = $numdigits, in the range 1 to $("9" ^ numdigits),\n" *
        "$onecount numbers produce 1 and $eightyninecount numbers produce 89.\n")
end

for i in [7, 8, 11, 14, 17]
    testitersquares(i)
end
Output:
For k = 2, in the range 1 to 99,
19 numbers produce 1 and 80 numbers produce 89.

For k = 7, in the range 1 to 9999999,
1418853 numbers produce 1 and 8581146 numbers produce 89.

For k = 8, in the range 1 to 99999999,
14255666 numbers produce 1 and 85744333 numbers produce 89.

For k = 11, in the range 1 to 99999999999,
15091199356 numbers produce 1 and 84908800643 numbers produce 89.

For k = 14, in the range 1 to 99999999999999,
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89.

For k = 17, in the range 1 to 99999999999999999,
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89.

Kotlin

To achieve reasonable performance, the Kotlin entry for the Iterated digits squaring task already used a similar approach to that required by this task for k = 8.

So the following generalizes that code to deal with values of k up to 17 (which requires 64 bit integers) and to count numbers where the squared digits sum sequence eventually ends in 1 rather than 89, albeit the sum of both must of course be 10 ^ k - 1. 

// version 1.1.51

fun endsWithOne(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 == 1) return true
        if (sum == 89) return false
        nn = sum
        sum  = 0
    }
}

fun main(args: Array<String>) {
    val ks = intArrayOf(7, 8, 11, 14, 17)
    for (k in ks) {
        val sums = LongArray(k * 81 + 1)
        sums[0] = 1
        sums[1] = 0
        var s: Int
        for (n in 1 .. k) {
            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 count1 = 0L
        for (i in 1 .. k * 81) if (endsWithOne(i)) count1 += sums[i]
        val limit = Math.pow(10.0, k.toDouble()).toLong() - 1
        println("For k = $k in the range 1 to $limit")
        println("$count1 numbers produce 1 and ${limit - count1} numbers produce 89\n")
    }
}
Output:
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89

For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89

For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89

For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89

For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89

Nim

Translation of: Kotlin
import math, strformat

func endsWithOne(n: Natural): bool =
  var n = n
  while true:
    var sum = 0
    while n > 0:
      let digit = n mod 10
      sum += digit * digit
      n = n div 10
    if sum == 1: return true
    if sum == 89: return false
    n = sum

const Ks = [7, 8, 11, 14, 17]

for k in Ks:
  var sums = newSeq[int64](k * 81 + 1)  # Initialized to 0s.
  sums[0] = 1
  for n in 1..k:
    for i in countdown(n * 81, 1):
      for j in 1..9:
        let s = j * j
        if s > i: break
        sums[i] += sums[i - s]

  var count1 = 0i64
  for i in 1..k*81:
    if i.endsWithOne(): count1 += sums[i]
  let limit = 10^k - 1
  echo &"For k = {k} in the range 1 to {limit}"
  echo &"{count1} numbers produce 1 and {limit - count1} numbers produce 89\n"
Output:
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89

For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89

For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89

For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89

For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89

Perl

Translation of: Raku
use strict;
use warnings;
use feature 'say';
use Math::AnyNum qw(:overload);

sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }

sub endsWithOne {
    my($n) = @_;
    my $digit;
    my $sum = 0;
    my $nn  = $n;
    while () {
        while ($nn > 0) {
            $digit = $nn % 10;
            $sum  += $digit**2;
            $nn    = int $nn / 10;
        }
        return 1 if $sum ==  1;
        return 0 if $sum == 89;
        $nn = $sum;
        $sum = 0;
    }
}

my @ks = <7 8 11 14 17>;

for my $k (@ks) {
    my @sums = <1 0>;
    my $s;
    for my $n (1 .. $k) {
        for my $i (reverse 1 .. $n*81) {
            for my $j (1 .. 9) {
                no warnings 'uninitialized';
                last if ($s = $j**2) > $i;
                $sums[$i] += $sums[$i-$s];
            }
        }
   }
   my $count1 = 0;
   for my $i (1 .. $k*81) { $count1 += $sums[$i] if endsWithOne($i) }
   my $limit = 10**$k - 1;
   say "For k = $k in the range 1 to " . comma $limit;
   say comma($count1) . ' numbers produce 1 and ' . comma($limit-$count1) . " numbers produce 89\n";
}
Output:
For k = 7 in the range 1 to 9,999,999
1,418,853 numbers produce 1 and 8,581,146 numbers produce 89

For k = 8 in the range 1 to 99,999,999
14,255,666 numbers produce 1 and 85,744,333 numbers produce 89

For k = 11 in the range 1 to 99,999,999,999
15,091,199,356 numbers produce 1 and 84,908,800,643 numbers produce 89

For k = 14 in the range 1 to 99,999,999,999,999
13,770,853,279,684 numbers produce 1 and 86,229,146,720,315 numbers produce 89

For k = 17 in the range 1 to 99,999,999,999,999,999
12,024,696,404,768,024 numbers produce 1 and 87,975,303,595,231,975 numbers produce 89

Phix

Translation of: Wren
with javascript_semantics
include mpfr.e

function endsWithOne(integer n)
    integer total = 0
    while true do
        while n>0 do
            integer digit = remainder(n,10)
            total += digit * digit
            n = floor(n/10)
        end while
        if total==1 then return true end if
        if total==89 then return false end if
        n = total
        total = 0
    end while
end function
 
constant ks = {7, 8, 11, 14, 17}
mpz count1 = mpz_init(0),
        si = mpz_init(),
     limit = mpz_init()
for ki=1 to length(ks) do
    integer k = ks[ki]
    sequence sums = repeat(0,k*81+1)
    sums[1] = 1
    sums[2] = 0
    for n=1 to k do
        for i=n*81+1 to 2 by -1 do
            for j=1 to 9 do
                integer s = j * j
                if s>i-1 then exit end if
                sums[i] += sums[i-s]
            end for
        end for
    end for
    mpz_set_si(count1,0)
    for i=1 to k*81 do
        if endsWithOne(i) then
            mpz_set_d(si,sums[i+1])
            mpz_add(count1,count1,si)
        end if
    end for
    mpz_ui_pow_ui(limit, 10, k)
    mpz_sub_si(limit,limit,1)
    mpz_sub(si,limit,count1)
    string l = mpz_get_str(limit,comma_fill:=true),
           c = mpz_get_str(count1,comma_fill:=true),
           s = mpz_get_str(si,comma_fill:=true)
    printf(1,"For k = %d in the range 1 to %s\n",{k,l})
    printf(1,"%s numbers produce 1 and %s numbers produce 89\n\n",{c,s})
end for
Output:
For k = 7 in the range 1 to 9,999,999
1,418,853 numbers produce 1 and 8,581,146 numbers produce 89

For k = 8 in the range 1 to 99,999,999
14,255,666 numbers produce 1 and 85,744,333 numbers produce 89

For k = 11 in the range 1 to 99,999,999,999
15,091,199,356 numbers produce 1 and 84,908,800,643 numbers produce 89

For k = 14 in the range 1 to 99,999,999,999,999
13,770,853,279,684 numbers produce 1 and 86,229,146,720,315 numbers produce 89

For k = 17 in the range 1 to 99,999,999,999,999,999
12,024,696,404,768,024 numbers produce 1 and 87,975,303,595,231,975 numbers produce 89

Also, Iterated_digits_squaring#Phix produces some of the same numbers (just not so high).

Raku

(formerly Perl 6)

Translation of: Kotlin
use v6;

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;
      }
      ($sum == 1) and return True;
      ($sum == 89) and return False;
      $nn = $sum;
      $sum = 0;
   }
}

my @ks = (7, 8, 11, 14, 17);

for @ks -> $k {
   my @sums is default(0) = 1,0;
   my $s;
   for (1 .. $k) -> $n {
      for ($n*81 ... 1) -> $i {
         for (1 .. 9) -> $j {
            $s = $j²;
            if ($s > $i) { last };
            @sums[$i] += @sums[$i-$s];
         }
      }
   }
   my $count1 = 0;
   for (1 .. $k*81) -> $i { if (endsWithOne($i)) {$count1 += @sums[$i]} }
   my $limit = 10**$k - 1;
   say "For k = $k in the range 1 to $limit";
   say "$count1 numbers produce 1 and ",$limit-$count1," numbers produce 89";
}
Output:
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89
For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89
For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89
For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89
For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89

Ruby

# Count how many number chains for Natural Numbers < 10**K end with a value of 1.
#
#  Nigel_Galloway
#  August 26th., 2014.
K = 17
F = Array.new(K+1){|n| n==0?1:(1..n).inject(:*)}   #Some small factorials
g = -> n, gn=[n,0], res=0 { while gn[0]>0
                              gn = gn[0].divmod(10)
                              res += gn[1]**2
                            end
                            return res==89?0:res
                           }
#An array: N[n]==1 means that n translates to 1, 0 means that it does not.
N = (G=Array.new(K*81+1){|n| n==0? 0:(i=g.call(n))==89 ? 0:i}).collect{|n| while n>1 do n = G[n] end; n }
z = 0   #Running count of numbers translating to 1
(0..9).collect{|n| n**2}.repeated_combination(K).each{|n|   #Iterate over unique digit combinations
    next if N[n.inject(:+)] == 0                            #Count only ones
    nn = Hash.new{0}                                        #Determine how many numbers this digit combination corresponds to
    n.each{|n| nn[n] += 1}                                  #and
    z += nn.values.inject(F[K]){|gn,n| gn/F[n]}             #Add to the count of numbers terminating in 1
}
puts "\nk=(#{K}) in the range 1 to #{10**K-1}\n#{z} numbers produce 1 and #{10**K-1-z} numbers produce 89"
Output:
#(k=7) in the range 1 to 9999999
#1418853 numbers produce 1 and 8581146 numbers produce 89

#(k=8) in the range 1 to 99999999
#14255666 numbers produce 1 and 85744333 numbers produce 89

#(k=11) in the range 1 to 99999999999
#15091199356 numbers produce 1 and 84908800643 numbers produce 89

#(k=14) in the range 1 to 99999999999999
#13770853279684 numbers produce 1 and 86229146720315 numbers produce 89

#(k=17) in the range 1 to 99999999999999999
#12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89

Wren

Translation of: Kotlin
Library: Wren-big

As Wren doesn't have 64 bit integers, it is necessary to use BigInt here to process k = 17. 

import "./big" for BigInt

var endsWithOne = Fn.new { |n|
    var sum = 0
    while (true) {
        while (n > 0) {
            var digit = n % 10
            sum = sum + digit * digit
            n = (n/10).floor
        }
        if (sum == 1)  return true
        if (sum == 89) return false
        n = sum
        sum = 0
    }
}

var ks = [7, 8, 11, 14, 17]
for (k in ks) {
    var sums = List.filled(k * 81 + 1, 0)
    sums[0] = 1
    sums[1] = 0
    for (n in 1..k) {
        for (i in n*81..1) {
            for (j in 1..9) {
                var s = j * j
                if (s > i) break
                sums[i] = sums[i] + sums[i-s]
            }
        }
    }
    var count1 = BigInt.zero
    for (i in 1..k*81) if (endsWithOne.call(i)) count1 = count1 + sums[i]
    var limit = BigInt.ten.pow(k) - 1
    System.print("For k = %(k) in the range 1 to %(limit)")
    System.print("%(count1) numbers produce 1 and %(limit - count1) numbers produce 89\n")
}
Output:
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89

For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89

For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89

For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89

For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89

zkl

Translation of: Ruby
fcn countNumberChains(K){
   F:=(K+1).pump(List,fcn(n){ (1).reduce(n,'*,1) });   #Some small factorials
   g:=fcn(n){
      gn,res:=L(n,0),0;
      while(gn[0]>0){ gn=gn[0].divr(10); res+=gn[1].pow(2); }
      if(res==89) 0 else res
   };
   #An array: N[n]==1 means that n translates to 1, 0 means that it does not.
   n,G:=K*81+1,n.pump(List,g);
   N:=n.pump(List,'wrap(n){ n=g(n); while(n>1){ n=G[n] } n });
   z:=([0..9].pump(List,fcn(n){ n*n }):Utils.Helpers.combosKW(K,_)) #combos of (0,1,4,9,16,25,36,49,64,81)
   .reduce('wrap(z,ds){				#Iterate over unique digit combinations
       if(N[ds.sum(0)]==0) return(z);		#Count only ones
       nn:=Dictionary();                        #Determine how many numbers this digit combination corresponds to
       ds.pump(Void,nn.incV);                   #and (eg (0,0,0,0,0,1,9)-->(0:5, 1:1, 9:1)
       z + nn.values.reduce( 			#Add to the count of numbers terminating in 1
	   'wrap(gn,n){ gn/F[n] },F[K]);
   },0);
   println("\nk=(%d) in the range 1 to %,d".fmt(K,(10).pow(K)-1));
   println("%,d numbers produce 1 and %,d numbers produce 89".fmt(z,(10).pow(K)-1-z));
   z
}

combosKW(k,sequence) is lazy, which, in this case, is quite a bit faster than the non-lazy version. 

foreach K in (T(7,8,11,14,17)){ countNumberChains(K) }
Output:
k=(7) in the range 1 to 9,999,999
1,418,853 numbers produce 1 and 8,581,146 numbers produce 89

k=(8) in the range 1 to 99,999,999
14,255,666 numbers produce 1 and 85,744,333 numbers produce 89

k=(11) in the range 1 to 99,999,999,999
15,091,199,356 numbers produce 1 and 84,908,800,643 numbers produce 89

k=(14) in the range 1 to 99,999,999,999,999
13,770,853,279,684 numbers produce 1 and 86,229,146,720,315 numbers produce 89

k=(17) in the range 1 to 99,999,999,999,999,999
12,024,696,404,768,024 numbers produce 1 and 87,975,303,595,231,975 numbers produce 89
Retrieved from "https://rosettacode.org/wiki/Combinations_with_repetitions/Square_digit_chain?oldid=352537"