Fraction reduction: Difference between revisions

Content added Content deleted

Inline

@@ Line 205: / Line 205: @@
         printf("\n");
+    }
+    return 0;
+}</lang>
+{{out}}
+<pre>16/64 = 1/4 by omitting 6's
+/95 = 1/5 by omitting 9's
+/65 = 2/5 by omitting 6's
+/98 = 4/8 by omitting 9's
+/231 = 12/21 by omitting 3's
+/536 = 14/56 by omitting 3's
+/938 = 14/98 by omitting 3's
+/238 = 16/28 by omitting 3's
+/345 = 18/45 by omitting 3's
+/695 = 13/65 by omitting 9's
+/341 = 13/31 by omitting 4's
+/365 = 14/35 by omitting 6's
+/298 = 14/28 by omitting 9's
+/596 = 14/56 by omitting 9's
+/894 = 14/84 by omitting 9's
+/253 = 14/23 by omitting 5's
+/4936 = 124/496 by omitting 3's
+/6195 = 123/615 by omitting 9's
+/3649 = 126/369 by omitting 4's
+/2498 = 124/248 by omitting 9's
+/6295 = 125/625 by omitting 9's
+/6395 = 127/635 by omitting 9's
+/5132 = 128/512 by omitting 3's
+/2594 = 127/254 by omitting 9's
+/3891 = 127/381 by omitting 9's
+/2596 = 128/256 by omitting 9's
+/3894 = 128/384 by omitting 9's
+/5192 = 128/512 by omitting 9's
+/24698 = 1234/2468 by omitting 9's
+/67958 = 1236/6798 by omitting 5's
+/14362 = 1258/1462 by omitting 3's
+/15364 = 1258/1564 by omitting 3's
+/17368 = 1258/1768 by omitting 3's
+/19372 = 1258/1972 by omitting 3's
+/21376 = 1258/2176 by omitting 3's
+/25384 = 1258/2584 by omitting 3's
+/61795 = 1235/6175 by omitting 9's
+/32596 = 1364/3596 by omitting 2's
+/61895 = 1237/6185 by omitting 9's
+/32654 = 1386/3654 by omitting 2's
+There are 4 2-digit fractions of which:
+have 6's omitted
+have 9's omitted
+There are 122 3-digit fractions of which:
+have 3's omitted
+have 4's omitted
+have 5's omitted
+have 6's omitted
+have 7's omitted
+have 8's omitted
+have 9's omitted
+There are 660 4-digit fractions of which:
+have 1's omitted
+have 2's omitted
+have 3's omitted
+have 4's omitted
+have 5's omitted
+have 6's omitted
+have 7's omitted
+have 8's omitted
+have 9's omitted
+There are 5087 5-digit fractions of which:
+have 1's omitted
+have 2's omitted
+have 3's omitted
+have 4's omitted
+have 5's omitted
+have 6's omitted
+have 7's omitted
+have 8's omitted
+have 9's omitted</pre>
+=={{header|C++}}==
+{{trans|D}}
+<lang cpp>#include <array>
+#include <iomanip>
+#include <iostream>
+#include <vector>
+int indexOf(const std::vector<int> &haystack, int needle) {
+    auto it = haystack.cbegin();
+    auto end = haystack.cend();
+    int idx = 0;
+    for (; it != end; it = std::next(it)) {
+        if (*it == needle) {
+            return idx;
+        }
+        idx++;
+    }
+    return -1;
+}
+bool getDigits(int n, int le, std::vector<int> &digits) {
+    while (n > 0) {
+        auto r = n % 10;
+        if (r == 0 || indexOf(digits, r) >= 0) {
+            return false;
+        }
+        le--;
+        digits[le] = r;
+        n /= 10;
+    }
+    return true;
+}
+int removeDigit(const std::vector<int> &digits, int le, int idx) {
+    static std::array<int, 5> pows = { 1, 10, 100, 1000, 10000 };
+    int sum = 0;
+    auto pow = pows[le - 2];
+    for (int i = 0; i < le; i++) {
+        if (i == idx) continue;
+        sum += digits[i] * pow;
+        pow /= 10;
+    }
+    return sum;
+}
+int main() {
+    std::vector<std::pair<int, int>> lims = { {12, 97}, {123, 986}, {1234, 9875}, {12345, 98764} };
+    std::array<int, 5> count;
+    std::array<std::array<int, 10>, 5> omitted;
+    std::fill(count.begin(), count.end(), 0);
+    std::for_each(omitted.begin(), omitted.end(),
+        [](auto &a) {
+            std::fill(a.begin(), a.end(), 0);
+        }
+    );
+    for (size_t i = 0; i < lims.size(); i++) {
+        std::vector<int> nDigits(i + 2);
+        std::vector<int> dDigits(i + 2);
+        for (int n = lims[i].first; n <= lims[i].second; n++) {
+            std::fill(nDigits.begin(), nDigits.end(), 0);
+            bool nOk = getDigits(n, i + 2, nDigits);
+            if (!nOk) {
+                continue;
+            }
+            for (int d = n + 1; d <= lims[i].second + 1; d++) {
+                std::fill(dDigits.begin(), dDigits.end(), 0);
+                bool dOk = getDigits(d, i + 2, dDigits);
+                if (!dOk) {
+                    continue;
+                }
+                for (size_t nix = 0; nix < nDigits.size(); nix++) {
+                    auto digit = nDigits[nix];
+                    auto dix = indexOf(dDigits, digit);
+                    if (dix >= 0) {
+                        auto rn = removeDigit(nDigits, i + 2, nix);
+                        auto rd = removeDigit(dDigits, i + 2, dix);
+                        if ((double)n / d == (double)rn / rd) {
+                            count[i]++;
+                            omitted[i][digit]++;
+                            if (count[i] <= 12) {
+                                std::cout << n << '/' << d << " = " << rn << '/' << rd << " by omitting " << digit << "'s\n";
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        std::cout << '\n';
+    }
+    for (int i = 2; i <= 5; i++) {
+        std::cout << "There are " << count[i - 2] << ' ' << i << "-digit fractions of which:\n";
+        for (int j = 1; j <= 9; j++) {
+            if (omitted[i - 2][j] == 0) {
+                continue;
+            }
+            std::cout << std::setw(6) << omitted[i - 2][j] << " have " << j << "'s omitted\n";
+        }
+        std::cout << '\n';
     }