Combinations with repetitions/Square Digit Chain

From Rosetta Code
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[edit]

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

Phix[edit]

There is a solution to this on the Iterated_digits_squaring page

Ruby[edit]

 
# 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

zkl[edit]

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