Combinations with repetitions/Square digit chain
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
<lang d> // 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);
} </lang>
- 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
Ruby
<lang 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" </lang>
- 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