FA-14981 / Numerics / Open access

Egyptian greedy fraction: residual gcd cancellation · case 01

The exact egyptian greedy fraction result violates the stated contract at residual gcd cancellation.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The residual gcd cancellation step uses abs(p) instead of math.gcd(p,q).

VERIFIED REPAIR

Use math.gcd(p,q) at the residual gcd cancellation step.

Unsuccessful approach: The partial repair q still violates the residual gcd cancellation invariant.

Case contract

Input [p,q], 0<p<q<=100; return greedy unit fraction denominators whose sum is p/q. Bounds: q<=31.

Why this case matters

Exact discrete arithmetic with observable algorithmic state; no floating point approximation is used.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    p,q=x;out=[]
    for _ in range(20):
     if p==0:break
     if abs(q).bit_length()>512:return None
     d=(q+p-1)//p
     if d<=0:return None
     out.append(d)
     p,q=p*d-q,q*d
     g=abs(p)
     if not g:return None
     p,q=p//g,q//g
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([1, 2], [2]), ([2, 3], [2, 6]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([1, 3], [3]), ([1, 4], [4]), ([2, 4], [2]), ([3, 4], [2, 4]), ([1, 5], [5])], [([1, 3], [3]), ([3, 5], [2, 10]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([3, 7], [3, 11, 231]), ([4, 7], [2, 14]), ([5, 7], [2, 5, 70]), ([6, 7], [2, 3, 42])], [([2, 3], [2, 6]), ([5, 6], [2, 3]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([7, 9], [2, 4, 36]), ([8, 9], [2, 3, 18]), ([1, 10], [10]), ([2, 10], [5])], [([1, 4], [4]), ([4, 7], [2, 14]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([7, 11], [2, 8, 88]), ([8, 11], [2, 5, 37, 4070]), ([9, 11], [2, 4, 15, 660]), ([10, 11], [2, 3, 14, 231])], [([2, 4], [2]), ([3, 8], [3, 24]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([3, 13], [5, 33, 2145]), ([4, 13], [4, 18, 468]), ([5, 13], [3, 20, 780]), ([6, 13], [3, 8, 312])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`None`	`[2]`	Failed
explicit oracle 1	`None`	`[2, 6]`	Failed
explicit oracle 2	`None`	`[2, 3, 8, 107, 15922, 633759288]`	Failed
explicit oracle 3	`None`	`[3]`	Failed
explicit oracle 4	`None`	`[4]`	Failed
explicit oracle 5	`None`	`[2]`	Failed
explicit oracle 6	`None`	`[2, 4]`	Failed
explicit oracle 7	`None`	`[5]`	Failed

SHA-256 / b2d83b85135d679357eea9f224694f9ce65a3b48dce5f24f6d2119a9dcdc81da

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    p,q=x;out=[]
    for _ in range(20):
     if p==0:break
     if abs(q).bit_length()>512:return None
     d=(q+p-1)//p
     if d<=0:return None
     out.append(d)
     p,q=p*d-q,q*d
     g=q
     if not g:return None
     p,q=p//g,q//g
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([1, 2], [2]), ([2, 3], [2, 6]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([1, 3], [3]), ([1, 4], [4]), ([2, 4], [2]), ([3, 4], [2, 4]), ([1, 5], [5])], [([1, 3], [3]), ([3, 5], [2, 10]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([3, 7], [3, 11, 231]), ([4, 7], [2, 14]), ([5, 7], [2, 5, 70]), ([6, 7], [2, 3, 42])], [([2, 3], [2, 6]), ([5, 6], [2, 3]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([7, 9], [2, 4, 36]), ([8, 9], [2, 3, 18]), ([1, 10], [10]), ([2, 10], [5])], [([1, 4], [4]), ([4, 7], [2, 14]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([7, 11], [2, 8, 88]), ([8, 11], [2, 5, 37, 4070]), ([9, 11], [2, 4, 15, 660]), ([10, 11], [2, 3, 14, 231])], [([2, 4], [2]), ([3, 8], [3, 24]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([3, 13], [5, 33, 2145]), ([4, 13], [4, 18, 468]), ([5, 13], [3, 20, 780]), ([6, 13], [3, 8, 312])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`[2]`	`[2]`	Passed
explicit oracle 1	`[2]`	`[2, 6]`	Failed
explicit oracle 2	`[2]`	`[2, 3, 8, 107, 15922, 633759288]`	Failed
explicit oracle 3	`[3]`	`[3]`	Passed
explicit oracle 4	`[4]`	`[4]`	Passed
explicit oracle 5	`[2]`	`[2]`	Passed
explicit oracle 6	`[2]`	`[2, 4]`	Failed
explicit oracle 7	`[5]`	`[5]`	Passed

SHA-256 / 907f9f7fed7907cbc10c259cd967d365b5c3126e1bc9f9773f8586bddb614af1

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    p,q=x;out=[]
    for _ in range(20):
     if p==0:break
     if abs(q).bit_length()>512:return None
     d=(q+p-1)//p
     if d<=0:return None
     out.append(d)
     p,q=p*d-q,q*d
     g=math.gcd(p,q)
     if not g:return None
     p,q=p//g,q//g
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([1, 2], [2]), ([2, 3], [2, 6]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([1, 3], [3]), ([1, 4], [4]), ([2, 4], [2]), ([3, 4], [2, 4]), ([1, 5], [5])], [([1, 3], [3]), ([3, 5], [2, 10]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([3, 7], [3, 11, 231]), ([4, 7], [2, 14]), ([5, 7], [2, 5, 70]), ([6, 7], [2, 3, 42])], [([2, 3], [2, 6]), ([5, 6], [2, 3]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([7, 9], [2, 4, 36]), ([8, 9], [2, 3, 18]), ([1, 10], [10]), ([2, 10], [5])], [([1, 4], [4]), ([4, 7], [2, 14]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([7, 11], [2, 8, 88]), ([8, 11], [2, 5, 37, 4070]), ([9, 11], [2, 4, 15, 660]), ([10, 11], [2, 3, 14, 231])], [([2, 4], [2]), ([3, 8], [3, 24]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([3, 13], [5, 33, 2145]), ([4, 13], [4, 18, 468]), ([5, 13], [3, 20, 780]), ([6, 13], [3, 8, 312])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`[2]`	`[2]`	Passed
explicit oracle 1	`[2, 6]`	`[2, 6]`	Passed
explicit oracle 2	`[2, 3, 8, 107, 15922, 633759288]`	`[2, 3, 8, 107, 15922, 633759288]`	Passed
explicit oracle 3	`[3]`	`[3]`	Passed
explicit oracle 4	`[4]`	`[4]`	Passed
explicit oracle 5	`[2]`	`[2]`	Passed
explicit oracle 6	`[2, 4]`	`[2, 4]`	Passed
explicit oracle 7	`[5]`	`[5]`	Passed

SHA-256 / 86ec4052ed3ecc6902be3f5ea7a95dffcc770bd1e0c803fc5a20f9d6c95df012

Verification & scope

A deterministic bounded teaching model. Inputs are restricted to the explicit contract; this is not a production algebra library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:39:22.280492+00:00.

Case digest / 3154ca8deaa6a1922c6fc9205000c2c5f9c88ff951ec83d8e3ab713eb52e1b10