Fraction reduction: Difference between revisions

{{trans|Phix}}

<lang zkl>fcn toInt(digits,remove_digit=0){

if(remove_digit!=0) digits=digits.copy().del(digits.index(remove_digit));

digits.reduce(fcn(s,d){ s*10 + d });

}

fcn nDigits(n){

//-- generate numbers with unique digits efficiently

//-- and store them in an array for multiple re-use,

//-- along with an array of the removed-digit values.

res,digits := List(), n.pump(List(),'+(1)); // 1,2,3,4..n

used := List.createLong(n,1).extend(List.createLong(9-n,0));

while(True){

nine:=List.createLong(9,0);

foreach i in (used.len()){ if(used[i]) nine[i]=toInt(digits,i+1) }

res.append(T(toInt(digits),nine));

found:=False;

foreach i in ([n-1..0, -1]){

d:=digits[i];

if(not used[d-1]) println("ack!");

used[d-1]=0;

foreach j in ([d..8]){

if(not used[j]){

used[j]=1;

digits[i]=j+1;

foreach k in ([i+1..n-1]){

digits[k] = used.find(0) + 1;

used[digits[k] - 1]=1;

}

found=True;

break;

}

}

if(found) break;

}//foreach i

if(not found) break;

}//while

res

}

foreach n in ([2..5]){

rs,rsz,count,omitted := nDigits(n),rs.len()-1, 0, List.createLong(9,0);

foreach i in (rsz){

xn,rn := rs[i];

foreach j in ([i+1..rsz]){

xd,rd := rs[j];

foreach k in ([0..8]){

yn,yd := rn[k],rd[k];

if(yn!=0 and yd!=0 and

xn.toFloat()/xd.toFloat() == yn.toFloat()/yd.toFloat()){

count+=1;

omitted[k]+=1;

if(count<=12)

println("%d/%d --> %d/%d (removed %d)".fmt(xn,xd,yn,yd,k+1));

}

}

}

}

println("%d-digit fractions found: %d, omitted %s\n"

.fmt(n,count,omitted.concat(",")));

}</lang>

16/64 --> 1/4 (removed 6)

19/95 --> 1/5 (removed 9)

26/65 --> 2/5 (removed 6)

49/98 --> 4/8 (removed 9)

2-digit fractions found: 4, omitted 0,0,0,0,0,2,0,0,2

132/231 --> 12/21 (removed 3)

134/536 --> 14/56 (removed 3)

134/938 --> 14/98 (removed 3)

136/238 --> 16/28 (removed 3)

138/345 --> 18/45 (removed 3)

139/695 --> 13/65 (removed 9)

143/341 --> 13/31 (removed 4)

146/365 --> 14/35 (removed 6)

149/298 --> 14/28 (removed 9)

149/596 --> 14/56 (removed 9)

149/894 --> 14/84 (removed 9)

154/253 --> 14/23 (removed 5)

3-digit fractions found: 122, omitted 0,0,9,1,6,15,16,15,60

1234/4936 --> 124/496 (removed 3)

1239/6195 --> 123/615 (removed 9)

1246/3649 --> 126/369 (removed 4)

1249/2498 --> 124/248 (removed 9)

1259/6295 --> 125/625 (removed 9)

1279/6395 --> 127/635 (removed 9)

1283/5132 --> 128/512 (removed 3)

1297/2594 --> 127/254 (removed 9)

1297/3891 --> 127/381 (removed 9)

1298/2596 --> 128/256 (removed 9)

1298/3894 --> 128/384 (removed 9)

1298/5192 --> 128/512 (removed 9)

4-digit fractions found: 660, omitted 14,25,92,14,29,63,16,17,390

12349/24698 --> 1234/2468 (removed 9)

12356/67958 --> 1236/6798 (removed 5)

12358/14362 --> 1258/1462 (removed 3)

12358/15364 --> 1258/1564 (removed 3)

12358/17368 --> 1258/1768 (removed 3)

12358/19372 --> 1258/1972 (removed 3)

12358/21376 --> 1258/2176 (removed 3)

12358/25384 --> 1258/2584 (removed 3)

12359/61795 --> 1235/6175 (removed 9)

12364/32596 --> 1364/3596 (removed 2)

12379/61895 --> 1237/6185 (removed 9)

12386/32654 --> 1386/3654 (removed 2)

5-digit fractions found: 5087, omitted 75,40,376,78,209,379,591,351,2988