Rosetta Code

Fraction reduction: Difference between revisions

Page Discussion

Fraction reduction (view source)

Revision as of 10:53, 6 December 2023

58,148 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(31 intermediate revisions by 11 users not shown)
Line 69:
:*   Wikipedia entry:   [https://en.wikipedia.org/wiki/Anomalous_cancellation anomalous cancellation and/or accidental cancellation].
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F indexOf(haystack, needle)
V idx = 0
L(straw) haystack
I straw == needle
R idx
E
idx++
R -1
 
F getDigits(=n, =le, &digits)
L n > 0
V r = n % 10
I r == 0 | indexOf(digits, r) >= 0
R 0B
le--
digits[le] = r
n = Int(n / 10)
R 1B
 
F removeDigit(digits, le, idx)
V pows = [1, 10, 100, 1000, 10000]
V sum = 0
V pow = pows[le - 2]
V i = 0
L i < le
I i == idx
i++
L.continue
sum = sum + digits[i] * pow
pow = Int(pow / 10)
i++
R sum
 
V lims = [ [ 12, 97 ], [ 123, 986 ], [ 1234, 9875 ], [ 12345, 98764 ] ]
V count = [0] * 5
V omitted = [[0] * 10] * 5
 
V i = 0
L i < lims.len
V n = lims[i][0]
L n < lims[i][1]
V nDigits = [0] * (i + 2)
V nOk = getDigits(n, i + 2, &nDigits)
I !nOk
n++
L.continue
V d = n + 1
L d <= lims[i][1] + 1
V dDigits = [0] * (i + 2)
V dOk = getDigits(d, i + 2, &dDigits)
I !dOk
d++
L.continue
V nix = 0
L nix < nDigits.len
V digit = nDigits[nix]
V dix = indexOf(dDigits, digit)
I dix >= 0
V rn = removeDigit(nDigits, i + 2, nix)
V rd = removeDigit(dDigits, i + 2, dix)
I (1.0 * n / d) == (1.0 * rn / rd)
count[i]++
omitted[i][digit]++
I count[i] <= 12
print(‘#./#. = #./#. by omitting #.'s’.format(n, d, rn, rd, digit))
nix++
d++
n++
print()
i++
 
i = 2
L i <= 5
print(‘There are #. #.-digit fractions of which:’.format(count[i - 2], i))
V j = 1
L j <= 9
I omitted[i - 2][j] == 0
j++
L.continue
print(‘#6 have #.'s omitted’.format(omitted[i - 2][j], j))
j++
print()
i++</syntaxhighlight>
 
{{out}}
<pre>
16/64 = 1/4 by omitting 6's
19/95 = 1/5 by omitting 9's
26/65 = 2/5 by omitting 6's
49/98 = 4/8 by omitting 9's
 
132/231 = 12/21 by omitting 3's
134/536 = 14/56 by omitting 3's
134/938 = 14/98 by omitting 3's
136/238 = 16/28 by omitting 3's
138/345 = 18/45 by omitting 3's
139/695 = 13/65 by omitting 9's
143/341 = 13/31 by omitting 4's
146/365 = 14/35 by omitting 6's
149/298 = 14/28 by omitting 9's
149/596 = 14/56 by omitting 9's
149/894 = 14/84 by omitting 9's
154/253 = 14/23 by omitting 5's
 
1234/4936 = 124/496 by omitting 3's
1239/6195 = 123/615 by omitting 9's
1246/3649 = 126/369 by omitting 4's
1249/2498 = 124/248 by omitting 9's
1259/6295 = 125/625 by omitting 9's
1279/6395 = 127/635 by omitting 9's
1283/5132 = 128/512 by omitting 3's
1297/2594 = 127/254 by omitting 9's
1297/3891 = 127/381 by omitting 9's
1298/2596 = 128/256 by omitting 9's
1298/3894 = 128/384 by omitting 9's
1298/5192 = 128/512 by omitting 9's
 
12349/24698 = 1234/2468 by omitting 9's
12356/67958 = 1236/6798 by omitting 5's
12358/14362 = 1258/1462 by omitting 3's
12358/15364 = 1258/1564 by omitting 3's
12358/17368 = 1258/1768 by omitting 3's
12358/19372 = 1258/1972 by omitting 3's
12358/21376 = 1258/2176 by omitting 3's
12358/25384 = 1258/2584 by omitting 3's
12359/61795 = 1235/6175 by omitting 9's
12364/32596 = 1364/3596 by omitting 2's
12379/61895 = 1237/6185 by omitting 9's
12386/32654 = 1386/3654 by omitting 2's
 
There are 4 2-digit fractions of which:
2 have 6's omitted
2 have 9's omitted
 
There are 122 3-digit fractions of which:
9 have 3's omitted
1 have 4's omitted
6 have 5's omitted
15 have 6's omitted
16 have 7's omitted
15 have 8's omitted
60 have 9's omitted
 
There are 660 4-digit fractions of which:
14 have 1's omitted
25 have 2's omitted
92 have 3's omitted
14 have 4's omitted
29 have 5's omitted
63 have 6's omitted
16 have 7's omitted
17 have 8's omitted
390 have 9's omitted
 
There are 5087 5-digit fractions of which:
75 have 1's omitted
40 have 2's omitted
376 have 3's omitted
78 have 4's omitted
209 have 5's omitted
379 have 6's omitted
591 have 7's omitted
351 have 8's omitted
2988 have 9's omitted
</pre>
 
=={{header|Ada}}==
{{trans|Python}}
<syntaxhighlight lang="ada">with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Ada.Text_IO; use Ada.Text_IO;
procedure Fraction_Reduction is
 
type Int_Array is array (Natural range <>) of Integer;
 
function indexOf(haystack : Int_Array; needle : Integer) return Integer is
idx : Integer := 0;
begin
for straw of haystack loop
if straw = needle then
return idx;
else
idx := idx + 1;
end if;
end loop;
return -1;
end IndexOf;
function getDigits(n, le : in Integer;
digit_array : in out Int_Array) return Boolean is
n_local : Integer := n;
le_local : Integer := le;
r : Integer;
begin
while n_local > 0 loop
r := n_local mod 10;
if r = 0 or indexOf(digit_array, r) >= 0 then
return False;
end if;
le_local := le_local - 1;
digit_array(le_local) := r;
n_local := n_local / 10;
end loop;
return True;
end getDigits;
 
function removeDigit(digit_array : Int_Array;
le, idx : Integer) return Integer is
sum : Integer := 0;
pow : Integer := 10 ** (le - 2);
begin
for i in 0 .. le - 1 loop
if i /= idx then
sum := sum + digit_array(i) * pow;
pow := pow / 10;
end if;
end loop;
return sum;
end removeDigit;
 
lims : constant array (0 .. 3) of Int_Array (0 .. 1) :=
((12, 97), (123, 986), (1234, 9875), (12345, 98764));
count : Int_Array (0 .. 4) := (others => 0);
omitted : array (0 .. 4) of Int_Array (0 .. 9) :=
(others => (others => 0));
begin
Ada.Integer_Text_IO.Default_Width := 0;
for i in lims'Range loop
declare
nDigits, dDigits : Int_Array (0 .. i + 1);
digit, dix, rn, rd : Integer;
begin
for n in lims(i)(0) .. lims(i)(1) loop
nDigits := (others => 0);
if getDigits(n, i + 2, nDigits) then
for d in n + 1 .. lims(i)(1) + 1 loop
dDigits := (others => 0);
if getDigits(d, i + 2, dDigits) then
for nix in nDigits'Range loop
digit := nDigits(nix);
dix := indexOf(dDigits, digit);
if dix >= 0 then
rn := removeDigit(nDigits, i + 2, nix);
rd := removeDigit(dDigits, i + 2, dix);
-- 'n/d = rn/rd' is same as 'n*rd = rn*d'
if n*rd = rn*d then
count(i) := count(i) + 1;
omitted(i)(digit) :=
omitted(i)(digit) + 1;
if count(i) <= 12 then
Put (n);
Put ("/");
Put (d);
Put (" = ");
Put (rn);
Put ("/");
Put (rd);
Put (" by omitting ");
Put (digit);
Put_Line ("'s");
end if;
end if;
end if;
end loop;
end if;
end loop;
end if;
end loop;
end;
New_Line;
end loop;
for i in 2 .. 5 loop
Put ("There are ");
Put (count(i - 2));
Put (" ");
Put (i);
Put_Line ("-digit fractions of which:");
for j in 1 .. 9 loop
if omitted(i - 2)(j) /= 0 then
Put (omitted(i - 2)(j), Width => 6);
Put (" have ");
Put (j);
Put_Line ("'s omitted");
end if;
end loop;
New_Line;
end loop;
end Fraction_Reduction;</syntaxhighlight>
 
=={{header|C}}==
{{trans|C#}}
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
Line 208 ⟶ 500:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
Line 291 ⟶ 583:
=={{header|C sharp|C#}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="csharp">using System;
 
namespace FractionReduction {
Line 384 ⟶ 676:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
Line 467 ⟶ 759:
=={{header|C++}}==
{{trans|D}}
<langsyntaxhighlight lang="cpp">#include <array>
#include <iomanip>
#include <iostream>
Line 572 ⟶ 864:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
Line 655 ⟶ 947:
=={{header|D}}==
{{trans|C#}}
<langsyntaxhighlight lang="d">import std.range;
import std.stdio;
 
Line 745 ⟶ 1,037:
writeln;
}
}</langsyntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
Line 825 ⟶ 1,117:
351 have 8's omitted
2988 have 9's omitted</pre>
=={{header|Delphi}}==
 
See [[#Pascal]].
=={{header|Go}}==
===Version 1===
This produces the stats for 5-digit fractions in less than 25 seconds but takes a much longer 15.5 minutes to process the 6-digit case. Timings are for an Intel Core i7-8565U machine.
<langsyntaxhighlight lang="go">package main
 
import (
Line 929 ⟶ 1,222:
}
fmt.Printf("Took %s\n", time.Since(start))
}</langsyntaxhighlight>
 
{{out}}
Line 1,042 ⟶ 1,335:
{{trans|Phix}}
Rather than iterate through all numbers in the n-digit range and check if they contain unique non-zero digits, this generates all such numbers to start with which turns out to be a much more efficient approach - more than 20 times faster than before.
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,161 ⟶ 1,454:
}
fmt.Printf("Took %s\n", time.Since(start))
}</langsyntaxhighlight>
 
{{out}}
Line 1,229 ⟶ 1,522:
Took 42.251172302s
</pre>
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">class FractionReduction {
static void main(String[] args) {
for (int size = 2; size <= 5; size++) {
reduce(size)
}
}
 
private static void reduce(int numDigits) {
System.out.printf("Fractions with digits of length %d where cancellation is valid. Examples:%n", numDigits)
 
// Generate allowed numerator's and denominator's
int min = (int) Math.pow(10, numDigits - 1)
int max = (int) Math.pow(10, numDigits) - 1
List<Integer> values = new ArrayList<>()
for (int number = min; number <= max; number++) {
if (isValid(number)) {
values.add(number)
}
}
 
Map<Integer, Integer> cancelCount = new HashMap<>()
int size = values.size()
int solutions = 0
for (int nIndex = 0; nIndex < size - 1; nIndex++) {
int numerator = values.get(nIndex)
// Must be proper fraction
for (int dIndex = nIndex + 1; dIndex < size; dIndex++) {
int denominator = values.get(dIndex)
for (int commonDigit : digitsInCommon(numerator, denominator)) {
int numRemoved = removeDigit(numerator, commonDigit)
int denRemoved = removeDigit(denominator, commonDigit)
if (numerator * denRemoved == denominator * numRemoved) {
solutions++
cancelCount.merge(commonDigit, 1, { v1, v2 -> v1 + v2 })
if (solutions <= 12) {
println(" When $commonDigit is removed, $numerator/$denominator = $numRemoved/$denRemoved")
}
}
}
}
}
println("Number of fractions where cancellation is valid = $solutions.")
List<Integer> sorted = new ArrayList<>(cancelCount.keySet())
Collections.sort(sorted)
for (int removed : sorted) {
println(" The digit $removed was removed ${cancelCount.get(removed)} times.")
}
println()
}
 
private static int[] powers = [1, 10, 100, 1000, 10000, 100000]
 
// Remove the specified digit.
private static int removeDigit(int n, int removed) {
int m = 0
int pow = 0
while (n > 0) {
int r = n % 10
if (r != removed) {
m = m + r * powers[pow]
pow++
}
n /= 10
}
return m
}
 
// Assumes no duplicate digits individually in n1 or n2 - part of task
private static List<Integer> digitsInCommon(int n1, int n2) {
int[] count = new int[10]
List<Integer> common = new ArrayList<>()
while (n1 > 0) {
int r = n1 % 10
count[r] += 1
n1 /= 10
}
while (n2 > 0) {
int r = n2 % 10
if (count[r] > 0) {
common.add(r)
}
n2 /= 10
}
return common
}
 
// No repeating digits, no digit is zero.
private static boolean isValid(int num) {
int[] count = new int[10]
while (num > 0) {
int r = num % 10
if (r == 0 || count[r] == 1) {
return false
}
count[r] = 1
num /= 10
}
return true
}
}</syntaxhighlight>
 
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Control.Monad (guard)
import Data.List (intersect, unfoldr, delete, nub, group, sort)
import Text.Printf (printf)
 
type Fraction = (Int, Int)
type Reduction = (Fraction, Fraction, Int)
 
validIntegers :: [Int] -> [Int]
validIntegers xs = [x | x <- xs, not $ hasZeros x, hasUniqueDigits x]
where
hasZeros = elem 0 . digits 10
hasUniqueDigits n = length ds == length ul
where
ds = digits 10 n
ul = nub ds
 
possibleFractions :: [Int] -> [Fraction]
possibleFractions = (\ys -> [(n,d) | n <- ys, d <- ys, n < d, gcd n d /= 1]) . validIntegers
 
digits :: Integral a => a -> a -> [a]
digits b = unfoldr (\n -> guard (n /= 0) >> pure (n `mod` b, n `div` b))
 
digitsToIntegral :: Integral a => [a] -> a
digitsToIntegral = sum . zipWith (*) (iterate (*10) 1)
 
findReductions :: Fraction -> [Reduction]
findReductions z@(n1, d1) = [ (z, (n2, d2), x)
| x <- digits 10 n1 `intersect` digits 10 d1,
let n2 = dropDigit x n1
d2 = dropDigit x d1
decimalWithDrop = realToFrac n2 / realToFrac d2,
decimalWithDrop == decimal ]
where dropDigit d = digitsToIntegral . delete d . digits 10
decimal = realToFrac n1 / realToFrac d1
 
findGroupReductions :: [Int] -> [Reduction]
findGroupReductions = (findReductions =<<) . possibleFractions
 
showReduction :: Reduction -> IO ()
showReduction ((n1,d1),(n2,d2),d) = printf "%d/%d = %d/%d by dropping %d\n" n1 d1 n2 d2 d
 
showCount :: [Reduction] -> Int -> IO ()
showCount xs n = do
printf "There are %d %d-digit fractions of which:\n" (length xs) n
mapM_ (uncurry (printf "%5d have %d's omitted\n")) (countReductions xs) >> printf "\n"
where
countReductions = fmap ((,) . length <*> head) . group . sort . fmap (\(_, _, x) -> x)
 
main :: IO ()
main = do
mapM_ (\g -> mapM_ showReduction (take 12 g) >> printf "\n") groups
mapM_ (uncurry showCount) $ zip groups [2..]
where
groups = [ findGroupReductions [10^1..99], findGroupReductions [10^2..999]
, findGroupReductions [10^3..9999], findGroupReductions [10^4..99999] ]</syntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by dropping 6
19/95 = 1/5 by dropping 9
26/65 = 2/5 by dropping 6
49/98 = 4/8 by dropping 9
 
132/231 = 12/21 by dropping 3
134/536 = 14/56 by dropping 3
134/938 = 14/98 by dropping 3
136/238 = 16/28 by dropping 3
138/345 = 18/45 by dropping 3
139/695 = 13/65 by dropping 9
143/341 = 13/31 by dropping 4
146/365 = 14/35 by dropping 6
149/298 = 14/28 by dropping 9
149/596 = 14/56 by dropping 9
149/894 = 14/84 by dropping 9
154/253 = 14/23 by dropping 5
 
1234/4936 = 124/496 by dropping 3
1239/6195 = 123/615 by dropping 9
1246/3649 = 126/369 by dropping 4
1249/2498 = 124/248 by dropping 9
1259/6295 = 125/625 by dropping 9
1279/6395 = 127/635 by dropping 9
1283/5132 = 128/512 by dropping 3
1297/2594 = 127/254 by dropping 9
1297/3891 = 127/381 by dropping 9
1298/2596 = 128/256 by dropping 9
1298/3894 = 128/384 by dropping 9
1298/5192 = 128/512 by dropping 9
 
12349/24698 = 1234/2468 by dropping 9
12356/67958 = 1236/6798 by dropping 5
12358/14362 = 1258/1462 by dropping 3
12358/15364 = 1258/1564 by dropping 3
12358/17368 = 1258/1768 by dropping 3
12358/19372 = 1258/1972 by dropping 3
12358/21376 = 1258/2176 by dropping 3
12358/25384 = 1258/2584 by dropping 3
12359/61795 = 1235/6175 by dropping 9
12364/32596 = 1364/3596 by dropping 2
12379/61895 = 1237/6185 by dropping 9
12386/32654 = 1386/3654 by dropping 2
 
There are 4 2-digit fractions of which:
2 have 6's omitted
2 have 9's omitted
 
There are 122 3-digit fractions of which:
9 have 3's omitted
1 have 4's omitted
6 have 5's omitted
15 have 6's omitted
16 have 7's omitted
15 have 8's omitted
60 have 9's omitted
 
There are 660 4-digit fractions of which:
14 have 1's omitted
25 have 2's omitted
92 have 3's omitted
14 have 4's omitted
29 have 5's omitted
63 have 6's omitted
16 have 7's omitted
17 have 8's omitted
390 have 9's omitted
 
There are 5087 5-digit fractions of which:
75 have 1's omitted
40 have 2's omitted
376 have 3's omitted
78 have 4's omitted
209 have 5's omitted
379 have 6's omitted
591 have 7's omitted
351 have 8's omitted
2988 have 9's omitted</pre>
 
=={{header|J}}==
The algorithm generates all potential rational fractions of given size in base 10 and successively applies conditions to restrict the candidates. By avoiding boxing and rational numbers this version is much quicker than that which may be found in the page history.
<syntaxhighlight lang="j">
<lang J>
Filter=: (#~`)(`:6)
assert 'ac' -: 1 0 1"_ Filter 'abc'
Line 1,286 ⟶ 1,818:
result
)
</syntaxhighlight>
</lang>
<pre>
Line 1,341 ⟶ 1,873:
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
Line 1,450 ⟶ 1,982:
 
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,535 ⟶ 2,067:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Combinatorics
 
toi(set) = parse(Int, join(set, ""))
Line 1,578 ⟶ 2,110:
 
testfractionreduction()
</langsyntaxhighlight>{{out}}
<pre>
For 2 digits, there were 4 fractions with anomalous cancellation.
Line 1,662 ⟶ 2,194:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">fun indexOf(n: Int, s: IntArray): Int {
for (i_j in s.withIndex()) {
if (n == i_j.value) {
Line 1,765 ⟶ 2,297:
println()
}
}</langsyntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
Line 1,845 ⟶ 2,377:
351 have 8's omitted
2988 have 9's omitted</pre>
 
=={{header|Lua}}==
{{trans|C++}}
<syntaxhighlight lang="lua">function indexOf(haystack, needle)
for idx,straw in pairs(haystack) do
if straw == needle then
return idx
end
end
 
return -1
end
 
function getDigits(n, le, digits)
while n > 0 do
local r = n % 10
if r == 0 or indexOf(digits, r) > 0 then
return false
end
le = le - 1
digits[le + 1] = r
n = math.floor(n / 10)
end
return true
end
 
function removeDigit(digits, le, idx)
local pows = { 1, 10, 100, 1000, 10000 }
 
local sum = 0
local pow = pows[le - 2 + 1]
for i = 1, le do
if i ~= idx then
sum = sum + digits[i] * pow
pow = math.floor(pow / 10)
end
end
return sum
end
 
function main()
local lims = { {12, 97}, {123, 986}, {1234, 9875}, {12345, 98764} }
local count = { 0, 0, 0, 0, 0 }
local omitted = {
{ 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, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
}
 
for i,_ in pairs(lims) do
local nDigits = {}
local dDigits = {}
for j = 1, i + 2 - 1 do
nDigits[j] = -1
dDigits[j] = -1
end
 
for n = lims[i][1], lims[i][2] do
for j,_ in pairs(nDigits) do
nDigits[j] = 0
end
local nOk = getDigits(n, i + 2 - 1, nDigits)
if nOk then
for d = n + 1, lims[i][2] + 1 do
for j,_ in pairs(dDigits) do
dDigits[j] = 0
end
local dOk = getDigits(d, i + 2 - 1, dDigits)
if dOk then
for nix,_ in pairs(nDigits) do
local digit = nDigits[nix]
local dix = indexOf(dDigits, digit)
if dix >= 0 then
local rn = removeDigit(nDigits, i + 2 - 1, nix)
local rd = removeDigit(dDigits, i + 2 - 1, dix)
if (n / d) == (rn / rd) then
count[i] = count[i] + 1
omitted[i][digit + 1] = omitted[i][digit + 1] + 1
if count[i] <= 12 then
print(string.format("%d/%d = %d/%d by omitting %d's", n, d, rn, rd, digit))
end
end
end
end
end
end
end
end
 
print()
end
 
for i = 2, 5 do
print("There are "..count[i - 2 + 1].." "..i.."-digit fractions of which:")
for j = 1, 9 do
if omitted[i - 2 + 1][j + 1] > 0 then
print(string.format("%6d have %d's omitted", omitted[i - 2 + 1][j + 1], j))
end
end
print()
end
end
 
main()</syntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
19/95 = 1/5 by omitting 9's
26/65 = 2/5 by omitting 6's
49/98 = 4/8 by omitting 9's
 
132/231 = 12/21 by omitting 3's
134/536 = 14/56 by omitting 3's
134/938 = 14/98 by omitting 3's
136/238 = 16/28 by omitting 3's
138/345 = 18/45 by omitting 3's
139/695 = 13/65 by omitting 9's
143/341 = 13/31 by omitting 4's
146/365 = 14/35 by omitting 6's
149/298 = 14/28 by omitting 9's
149/596 = 14/56 by omitting 9's
149/894 = 14/84 by omitting 9's
154/253 = 14/23 by omitting 5's
 
1234/4936 = 124/496 by omitting 3's
1239/6195 = 123/615 by omitting 9's
1246/3649 = 126/369 by omitting 4's
1249/2498 = 124/248 by omitting 9's
1259/6295 = 125/625 by omitting 9's
1279/6395 = 127/635 by omitting 9's
1283/5132 = 128/512 by omitting 3's
1297/2594 = 127/254 by omitting 9's
1297/3891 = 127/381 by omitting 9's
1298/2596 = 128/256 by omitting 9's
1298/3894 = 128/384 by omitting 9's
1298/5192 = 128/512 by omitting 9's
 
12349/24698 = 1234/2468 by omitting 9's
12356/67958 = 1236/6798 by omitting 5's
12358/14362 = 1258/1462 by omitting 3's
12358/15364 = 1258/1564 by omitting 3's
12358/17368 = 1258/1768 by omitting 3's
12358/19372 = 1258/1972 by omitting 3's
12358/21376 = 1258/2176 by omitting 3's
12358/25384 = 1258/2584 by omitting 3's
12359/61795 = 1235/6175 by omitting 9's
12364/32596 = 1364/3596 by omitting 2's
12379/61895 = 1237/6185 by omitting 9's
12386/32654 = 1386/3654 by omitting 2's
 
There are 4 2-digit fractions of which:
2 have 6's omitted
2 have 9's omitted
 
There are 122 3-digit fractions of which:
9 have 3's omitted
1 have 4's omitted
6 have 5's omitted
15 have 6's omitted
16 have 7's omitted
15 have 8's omitted
60 have 9's omitted
 
There are 660 4-digit fractions of which:
14 have 1's omitted
25 have 2's omitted
92 have 3's omitted
14 have 4's omitted
29 have 5's omitted
63 have 6's omitted
16 have 7's omitted
17 have 8's omitted
390 have 9's omitted
 
There are 5087 5-digit fractions of which:
75 have 1's omitted
40 have 2's omitted
376 have 3's omitted
78 have 4's omitted
209 have 5's omitted
379 have 6's omitted
591 have 7's omitted
351 have 8's omitted
2988 have 9's omitted</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[AnomalousCancellationQ2]
AnomalousCancellationQ2[frac : {i_?Positive, j_?Positive}] :=
Module[{samedigits, idig, jdig, ff, p, q, r, tmp},
idig = IntegerDigits[i];
jdig = IntegerDigits[j];
samedigits = Intersection[idig, jdig];
ff = i/j;
If[samedigits != {},
r = {};
Do[
p = Flatten[Position[idig, s]];
q = Flatten[Position[jdig, s]];
p = FromDigits[Delete[idig, #]] & /@ p;
q = FromDigits[Delete[jdig, #]] & /@ q;
tmp = Select[Tuples[{p, q}], #[[1]]/#[[2]] == ff &];
If[Length[tmp] > 0,
r = Join[r, Join[#, {i, j, s}] & /@ tmp];
];
,
{s, samedigits}
];
r
,
{}
]
]
ijs = Select[Select[Range[1, 9999], IntegerDigits /* FreeQ[0]], IntegerDigits /* DuplicateFreeQ];
res = Reap[
Do[
Do[
num = ijs[[i]];
den = ijs[[j]];
out = AnomalousCancellationQ2[{num, den}];
If[Length[out] > 0,
Sow[out]
]
,
{i, 1, j - 1}
]
,
{j, Length[ijs]}
]
][[2, 1]];
 
tmp = Catenate[res];
 
sel = Sort@Select[tmp, IntegerLength[#[[3]]] == IntegerLength[#[[4]]] == 2 &];
Length[sel]
t = Take[sel, UpTo[12]];
Column[Row[{#3, "/", #4, " = ", #1, "/", #2, " by removing ", #5}] & @@@ t]
SortBy[Tally[sel[[All, -1]]], First]
 
sel = Sort@Select[tmp, IntegerLength[#[[3]]] == IntegerLength[#[[4]]] == 3 &];
Length[sel]
t = Take[sel, UpTo[12]];
Column[Row[{#3, "/", #4, " = ", #1, "/", #2, " by removing ", #5}] & @@@ t]
SortBy[Tally[sel[[All, -1]]], First]
 
sel = Sort@Select[tmp, IntegerLength[#[[3]]] == IntegerLength[#[[4]]] == 4 &];
Length[sel]
t = Take[sel, UpTo[12]];
Column[Row[{#3, "/", #4, " = ", #1, "/", #2, " by removing ", #5}] & @@@ t]
SortBy[Tally[sel[[All, -1]]], First]</syntaxhighlight>
{{out}}
<pre>4
16/64 = 1/4 by removing 6
19/95 = 1/5 by removing 9
26/65 = 2/5 by removing 6
49/98 = 4/8 by removing 9
{{6,2},{9,2}}
 
122
132/231 = 12/21 by removing 3
162/648 = 12/48 by removing 6
143/341 = 13/31 by removing 4
163/652 = 13/52 by removing 6
139/695 = 13/65 by removing 9
193/965 = 13/65 by removing 9
194/291 = 14/21 by removing 9
154/253 = 14/23 by removing 5
149/298 = 14/28 by removing 9
154/352 = 14/32 by removing 5
146/365 = 14/35 by removing 6
154/451 = 14/41 by removing 5
{{3,9},{4,1},{5,6},{6,15},{7,16},{8,15},{9,60}}
 
660
1623/6492 = 123/492 by removing 6
1239/6195 = 123/615 by removing 9
1923/9615 = 123/615 by removing 9
1324/2317 = 124/217 by removing 3
1249/2498 = 124/248 by removing 9
1234/4936 = 124/496 by removing 3
1259/6295 = 125/625 by removing 9
1925/9625 = 125/625 by removing 9
1246/3649 = 126/369 by removing 4
1297/2594 = 127/254 by removing 9
1297/3891 = 127/381 by removing 9
1279/6395 = 127/635 by removing 9
{{1,14},{2,25},{3,92},{4,14},{5,29},{6,63},{7,16},{8,17},{9,390}}</pre>
 
=={{header|MiniZinc}}==
===The Model===
<syntaxhighlight lang="minizinc">
<lang MiniZinc>
%Fraction Reduction. Nigel Galloway, September 5th., 2019
include "alldifferent.mzn"; include "member.mzn";
Line 1,864 ⟶ 2,683:
 
output [show(n)++"/"++show(i)++" becomes "++show(e)++"/"++show(g)++" when "++show(w)++" is omitted"]
</syntaxhighlight>
</lang>
===The Tasks===
;Displaying 12 solutions
Line 2,007 ⟶ 2,826:
<pre>
%%%mzn-stat: nSolutions=5087
</pre>
 
=={{header|Nim}}==
{{trans|Phix}}
Using Phix algorithm with some adaptations.
<syntaxhighlight lang="nim">
# Fraction reduction.
 
import strformat
import times
 
type Result = tuple[n: int, nine: array[1..9, int]]
 
template find[T; N: static int](a: array[1..N, T]; value: T): int =
## Return the one-based index of a value in an array.
## This is needed as "system.find" returns a 0-based index even if the
## array lower bound is not null.
system.find(a, value) + 1
 
func toNumber(digits: seq[int]; removeDigit: int = 0): int =
## Convert a list of digits into a number.
var digits = digits
if removeDigit != 0:
let idx = digits.find(removeDigit)
digits.delete(idx)
for d in digits:
result = 10 * result + d
 
func nDigits(n: int): seq[Result] =
var digits = newSeq[int](n + 1) # Allocating one more to work with one-based indexes.
var used: array[1..9, bool]
for i in 1..n:
digits[i] = i
used[i] = true
var terminated = false
while not terminated:
var nine: array[1..9, int]
for i in 1..9:
if used[i]:
nine[i] = digits.toNumber(i)
result &= (n: digits.toNumber(), nine: nine)
block searchLoop:
terminated = true
for i in countdown(n, 1):
let d = digits[i]
doAssert(used[d], "Encountered an inconsistency with 'used' array")
used[d] = false
for j in (d + 1)..9:
if not used[j]:
used[j] = true
digits[i] = j
for k in (i + 1)..n:
digits[k] = used.find(false)
used[digits[k]] = true
terminated = false
break searchLoop
 
 
let start = gettime()
 
for n in 2..6:
let rs = nDigits(n)
var count = 0
var omitted: array[1..9, int]
for i in 1..<rs.high:
let (xn, rn) = rs[i]
for j in (i + 1)..rs.high:
let (xd, rd) = rs[j]
for k in 1..9:
let yn = rn[k]
let yd = rd[k]
if yn != 0 and yd != 0 and xn * yd == yn * xd:
inc count
inc omitted[k]
if count <= 12:
echo &"{xn}/{xd} => {yn}/{yd} (removed {k})"
 
echo &"{n}-digit fractions found: {count}, omitted {omitted}\n"
echo &"Took {gettime() - start}"
</syntaxhighlight>
 
{{out}}
<pre>
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]
 
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)
1324/2317 => 124/217 (removed 3)
4-digit fractions found: 659, omitted [14, 25, 91, 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]
 
123459/617295 => 12345/61725 (removed 9)
123468/493872 => 12468/49872 (removed 3)
123469/173524 => 12469/17524 (removed 3)
123469/193546 => 12469/19546 (removed 3)
123469/213568 => 12469/21568 (removed 3)
123469/283645 => 12469/28645 (removed 3)
123469/493876 => 12469/49876 (removed 3)
123469/573964 => 12469/57964 (removed 3)
123479/617395 => 12347/61735 (removed 9)
123495/172893 => 12345/17283 (removed 9)
123548/679514 => 12348/67914 (removed 5)
123574/325786 => 13574/35786 (removed 2)
6-digit fractions found: 9778, omitted [230, 256, 921, 186, 317, 751, 262, 205, 6650]
 
Took 45 seconds, 500 milliseconds, 988 microseconds, and 524 nanoseconds
</pre>
 
Line 2,013 ⟶ 2,978:
Using a permutation k out of n with k <= n<BR>
Inserting a record with this number and all numbers with one digit removed of that number.So only once calculated.Trade off is big size and no cache friendly local access.
<langsyntaxhighlight lang="pascal">
program FracRedu;
{$IFDEF FPC}
Line 2,259 ⟶ 3,224:
writeln;
end;
end.</langsyntaxhighlight>
{{out}}
<pre>
Line 2,418 ⟶ 3,383:
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 2,455 ⟶ 3,420:
printf " %s => %s removed %s\n", substr($f,0,$digit*2+1), $reduced{$f}, substr($f,-1)
}
}</langsyntaxhighlight>
{{out}}
<pre>4 2-digit reducible fractions:
Line 2,516 ⟶ 3,481:
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>function to_n(sequence digits, integer remove_digit=0)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
if remove_digit!=0 then
<span style="color: #008080;">function</span> <span style="color: #000000;">to_n</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">remove_digit</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
integer d = find(remove_digit,digits)
<span style="color: #008080;">if</span> <span style="color: #000000;">remove_digit</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
digits[d..d] = {}
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">remove_digit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span>
integer res = digits[1]
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">..</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for i=2 to length(digits) do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
res = res*10+digits[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
return res
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
 
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
function ndigits(integer n)
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
-- generate numbers with unique digits efficiently
-- and store them in an array for multiple re-use,
<span style="color: #008080;">function</span> <span style="color: #000000;">ndigits</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
-- along with an array of the removed-digit values.
<span style="color: #000080;font-style:italic;">-- generate numbers with unique digits efficiently
sequence res = {},
-- and store them in an array for multiple re-use,
digits = tagset(n),
-- along with an array of the removed-digit values.</span>
used = repeat(1,n)&repeat(0,9-n)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
while true do
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
sequence nine = repeat(0,9)
<span style="color: #000000;">used</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</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;">9</span><span style="color: #0000FF;">-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
for i=1 to length(used) do
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
if used[i] then
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nine</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;">9</span><span style="color: #0000FF;">)</span>
nine[i] = to_n(digits,i)
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">used</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end if
<span style="color: #008080;">if</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
end for
<span style="color: #000000;">nine</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;">to_n</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
res = append(res,{to_n(digits),nine})
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
bool found = false
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for i=n to 1 by -1 do
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">to_n</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">),</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">})</span>
integer d = digits[i]
<span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
if not used[d] then ?9/0 end if
<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: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
used[d] = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
for j=d+1 to 9 do
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if not used[j] then
<span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
used[j] = 1
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">d</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>
digits[i] = j
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
for k=i+1 to n do
<span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
digits[k] = find(0,used)
<span style="color: #000000;">digits</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;">j</span>
used[digits[k]] = 1
<span style="color: #008080;">for</span> <span style="color: #000000;">k</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;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">used</span><span style="color: #0000FF;">)</span>
found = true
<span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
exit
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
end for
if found then exit end if <span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if not found then exit end if
<span style="color: #008080;">if</span> <span style="color: #000000;">found</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>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return res
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</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>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
atom t0 = time(),
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
t1 = time()+1
for n=2 to 6 do
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span>
sequence d = ndigits(n)
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
integer count = 0
<span style="color: #000080;font-style:italic;">--for n=2 to 6 do</span>
sequence omitted = repeat(0,9)
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
for i=1 to length(d)-1 do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndigits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
{integer xn, sequence rn} = d[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for j=i+1 to length(d) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">omitted</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;">9</span><span style="color: #0000FF;">)</span>
{integer xd, sequence rd} = d[j]
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
for k=1 to 9 do
<span style="color: #0000FF;">{</span><span style="color: #004080;">integer</span> <span style="color: #000000;">xn</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">rn</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
integer yn = rn[k], yd = rd[k]
<span style="color: #008080;">for</span> <span style="color: #000000;">j</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;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if yn!=0 and yd!=0 and xn/xd = yn/yd then
<span style="color: #0000FF;">{</span><span style="color: #004080;">integer</span> <span style="color: #000000;">xd</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">rd</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
count += 1
<span style="color: #008080;">for</span> <span style="color: #000000;">k</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>
omitted[k] += 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">yn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">yd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
if count<=12 then
<span style="color: #008080;">if</span> <span style="color: #000000;">yn</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">yd</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">xn</span><span style="color: #0000FF;">/</span><span style="color: #000000;">xd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">yn</span><span style="color: #0000FF;">/</span><span style="color: #000000;">yd</span> <span style="color: #008080;">then</span>
printf(1,"%d/%d => %d/%d (removed %d)\n",{xn,xd,yn,yd,k})
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
elsif time()>t1 then
<span style="color: #000000;">omitted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
printf(1,"working (%d/%d)...\r",{i,length(d)})
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">12</span> <span style="color: #008080;">then</span>
t1 = time()+1
<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;">"%d/%d =&gt; %d/%d (removed %d)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">xn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">})</span>
end if
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
end if
<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;">"working (%d/%d)...\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)})</span>
end for
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
printf(1,"%d-digit fractions found:%d, omitted %v\n\n",{n,count,omitted})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
?elapsed(time()-t0)</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"%d-digit fractions found:%d, omitted %v\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">omitted</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,661 ⟶ 3,631:
"10 minutes and 13s"
</pre>
Note the code is now limited to 4 digits, which is almost mandatory for running under pwa/p2js unless you like staring at a blank screen.
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">def indexOf(haystack, needle):
idx = 0
for straw in haystack:
Line 2,749 ⟶ 3,720:
return None
 
main()</langsyntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
Line 2,834 ⟶ 3,805:
Racket's generator is horribly slow, so I roll my own more efficient generator. Pretty much using continuation-passing style, but then using macro to make it appear that we are writing in the direct style.
 
<langsyntaxhighlight lang="racket">#lang racket
 
(require racket/generator
Line 2,893 ⟶ 3,864:
(stats 5))
 
(main)</langsyntaxhighlight>
 
{{out}}
Line 2,981 ⟶ 3,952:
{{works with|Rakudo|2019.07.1}}
;[[wp:Anomalous cancellation|Anomalous Cancellation]]
<syntaxhighlight lang="raku" perl6line>my %reduced;
my $digits = 2..4;
 
Line 3,024 ⟶ 3,995:
say " {.key.substr(0, $digit * 2 + 1)} => {.value} removed {.key.substr(* - 1)}"
for %d.pairs.pick(12).sort;
}</langsyntaxhighlight>
{{out|Sample output}}
<pre>(4) 2 digit reduceable fractions:
Line 3,085 ⟶ 4,056:
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX pgm reduces fractions by "crossing out" matching digits in nominator&denominator.*/
parse arg high show . /*obtain optional arguments from the CL*/
if high=='' | high=="," then high= 4 /*Not specified? Then use the default.*/
Line 3,127 ⟶ 4,098:
hasDup: parse arg x; /* if L<2 then return 0 */ /*L will never be 1.*/
do i=1 for L-1; if pos(substr(x,i,1), substr(x,i+1)) \== 0 then return 1
end /*i*/; return 0</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 5 &nbsp; 12 </tt>}}
<pre>
Line 3,212 ⟶ 4,183:
For 5-digit fractions, there are 2988 with crossed-out 9's.
</pre>
 
=={{header|Ruby}}==
{{trans|Python}}
<syntaxhighlight lang="ruby">def indexOf(haystack, needle)
idx = 0
for straw in haystack
if straw == needle then
return idx
else
idx = idx + 1
end
end
return -1
end
 
def getDigits(n, le, digits)
while n > 0
r = n % 10
if r == 0 or indexOf(digits, r) >= 0 then
return false
end
le = le - 1
digits[le] = r
n = (n / 10).floor
end
return true
end
 
POWS = [1, 10, 100, 1000, 10000]
def removeDigit(digits, le, idx)
sum = 0
pow = POWS[le - 2]
i = 0
while i < le
if i == idx then
i = i + 1
next
end
sum = sum + digits[i] * pow
pow = (pow / 10).floor
i = i + 1
end
return sum
end
 
def main
lims = [ [ 12, 97 ], [ 123, 986 ], [ 1234, 9875 ], [ 12345, 98764 ] ]
count = Array.new(5, 0)
omitted = Array.new(5) { Array.new(10, 0) }
 
i = 0
for lim in lims
n = lim[0]
while n < lim[1]
nDigits = [0] * (i + 2)
nOk = getDigits(n, i + 2, nDigits)
if not nOk then
n = n + 1
next
end
d = n + 1
while d <= lim[1] + 1
dDigits = [0] * (i + 2)
dOk = getDigits(d, i + 2, dDigits)
if not dOk then
d = d + 1
next
end
nix = 0
while nix < nDigits.length
digit = nDigits[nix]
dix = indexOf(dDigits, digit)
if dix >= 0 then
rn = removeDigit(nDigits, i + 2, nix)
rd = removeDigit(dDigits, i + 2, dix)
if (1.0 * n / d) == (1.0 * rn / rd) then
count[i] = count[i] + 1
omitted[i][digit] = omitted[i][digit] + 1
if count[i] <= 12 then
print "%d/%d = %d/%d by omitting %d's\n" % [n, d, rn, rd, digit]
end
end
end
nix = nix + 1
end
d = d + 1
end
n = n + 1
end
print "\n"
i = i + 1
end
 
i = 2
while i <= 5
print "There are %d %d-digit fractions of which:\n" % [count[i - 2], i]
j = 1
while j <= 9
if omitted[i - 2][j] == 0 then
j = j + 1
next
end
print "%6s have %d's omitted\n" % [omitted[i - 2][j], j]
j = j + 1
end
print "\n"
i = i + 1
end
end
 
main()</syntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
19/95 = 1/5 by omitting 9's
26/65 = 2/5 by omitting 6's
49/98 = 4/8 by omitting 9's
 
132/231 = 12/21 by omitting 3's
134/536 = 14/56 by omitting 3's
134/938 = 14/98 by omitting 3's
136/238 = 16/28 by omitting 3's
138/345 = 18/45 by omitting 3's
139/695 = 13/65 by omitting 9's
143/341 = 13/31 by omitting 4's
146/365 = 14/35 by omitting 6's
149/298 = 14/28 by omitting 9's
149/596 = 14/56 by omitting 9's
149/894 = 14/84 by omitting 9's
154/253 = 14/23 by omitting 5's
 
1234/4936 = 124/496 by omitting 3's
1239/6195 = 123/615 by omitting 9's
1246/3649 = 126/369 by omitting 4's
1249/2498 = 124/248 by omitting 9's
1259/6295 = 125/625 by omitting 9's
1279/6395 = 127/635 by omitting 9's
1283/5132 = 128/512 by omitting 3's
1297/2594 = 127/254 by omitting 9's
1297/3891 = 127/381 by omitting 9's
1298/2596 = 128/256 by omitting 9's
1298/3894 = 128/384 by omitting 9's
1298/5192 = 128/512 by omitting 9's
 
12349/24698 = 1234/2468 by omitting 9's
12356/67958 = 1236/6798 by omitting 5's
12358/14362 = 1258/1462 by omitting 3's
12358/15364 = 1258/1564 by omitting 3's
12358/17368 = 1258/1768 by omitting 3's
12358/19372 = 1258/1972 by omitting 3's
12358/21376 = 1258/2176 by omitting 3's
12358/25384 = 1258/2584 by omitting 3's
12359/61795 = 1235/6175 by omitting 9's
12364/32596 = 1364/3596 by omitting 2's
12379/61895 = 1237/6185 by omitting 9's
12386/32654 = 1386/3654 by omitting 2's
 
There are 4 2-digit fractions of which:
2 have 6's omitted
2 have 9's omitted
 
There are 122 3-digit fractions of which:
9 have 3's omitted
1 have 4's omitted
6 have 5's omitted
15 have 6's omitted
16 have 7's omitted
15 have 8's omitted
60 have 9's omitted
 
There are 660 4-digit fractions of which:
14 have 1's omitted
25 have 2's omitted
92 have 3's omitted
14 have 4's omitted
29 have 5's omitted
63 have 6's omitted
16 have 7's omitted
17 have 8's omitted
390 have 9's omitted
 
There are 5087 5-digit fractions of which:
75 have 1's omitted
40 have 2's omitted
376 have 3's omitted
78 have 4's omitted
209 have 5's omitted
379 have 6's omitted
591 have 7's omitted
351 have 8's omitted
2988 have 9's omitted</pre>
 
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Module Module1
 
Function IndexOf(n As Integer, s As Integer()) As Integer
Line 3,310 ⟶ 4,471:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>16/64 = 1/4 by omitting 6's
Line 3,390 ⟶ 4,551:
351 have 8's omitted
2988 have 9's omitted</pre>
 
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-fmt}}
A translation of Go's second version which is itself based on the Phix entry.
 
Have still needed to restrict to 5-digit fractions which finishes in just under 2 minutes on my machine.
<syntaxhighlight lang="wren">import "./dynamic" for Struct
import "./fmt" for Fmt
 
var Result = Struct.create("Result", ["n", "nine"])
 
var toNumber = Fn.new { |digits, removeDigit|
var digits2 = digits.toList
if (removeDigit != 0) {
var d = digits2.indexOf(removeDigit)
digits2.removeAt(d)
}
var res = digits2[0]
var i = 1
while (i < digits2.count) {
res = res * 10 + digits2[i]
i = i + 1
}
return res
}
 
var nDigits = Fn.new { |n|
var res = []
var digits = List.filled(n, 0)
var used = List.filled(9, false)
for (i in 0...n) {
digits[i] = i + 1
used[i] = true
}
while (true) {
var nine = List.filled(9, 0)
for (i in 0...used.count) {
if (used[i]) nine[i] = toNumber.call(digits, i+1)
}
res.add(Result.new(toNumber.call(digits, 0), nine))
var found = false
for (i in n-1..0) {
var d = digits[i]
if (!used[d-1]) {
Fiber.abort("something went wrong with 'used' array")
}
used[d-1] = false
var j = d
while (j < 9) {
if (!used[j]) {
used[j] = true
digits[i] = j + 1
for (k in i + 1...n) {
digits[k] = used.indexOf(false) + 1
used[digits[k]-1] = true
}
found = true
break
}
j = j + 1
}
if (found) break
}
if (!found) break
}
return res
}
 
for (n in 2..5) {
var rs = nDigits.call(n)
var count = 0
var omitted = List.filled(9, 0)
for (i in 0...rs.count-1) {
var xn = rs[i].n
var rn = rs[i].nine
for (j in i + 1...rs.count) {
var xd = rs[j].n
var rd = rs[j].nine
for (k in 0..8) {
var yn = rn[k]
var yd = rd[k]
if (yn != 0 && yd != 0 && xn/xd == yn/yd) {
count = count + 1
omitted[k] = omitted[k] + 1
if (count <= 12) {
Fmt.print("$d/$d => $d/$d (removed $d)", xn, xd, yn, yd, k+1)
}
}
}
}
}
Fmt.print("$d-digit fractions found:$d, omitted $s\n", n, count, omitted)
}</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|zkl}}==
{{trans|Phix}}
<langsyntaxhighlight 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 });
Line 3,451 ⟶ 4,758:
println("%d-digit fractions found: %d, omitted %s\n"
.fmt(n,count,omitted.concat(",")));
}</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

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