FA-14976 / Numerics / Open access

Egyptian greedy fraction: residual denominator · case 01

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

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

ROOT CAUSE

The residual denominator step uses q+d instead of q*d.

VERIFIED REPAIR

Use q*d at the residual denominator step.

Unsuccessful approach: The partial repair d still violates the residual denominator 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=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 = [[([2, 3], [2, 6]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([1, 3], [3]), ([1, 4], [4]), ([2, 4], [2]), ([3, 4], [2, 4]), ([1, 5], [5])], [([3, 4], [2, 4]), ([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, 5], [3, 15]), ([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])], [([3, 5], [2, 10]), ([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])], [([4, 5], [2, 4, 20]), ([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, 5]`	`[2, 6]`	Failed
explicit oracle 1	`[2]`	`[2]`	Passed
explicit oracle 2	`[2, 2, 2, 3]`	`[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, 3]`	`[2, 4]`	Failed
explicit oracle 7	`[5]`	`[5]`	Passed

SHA-256 / 25c356f303a1544dd507e0695200c8dd7082a17be2c37017aa4c68cb39c75966

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,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 = [[([2, 3], [2, 6]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([1, 3], [3]), ([1, 4], [4]), ([2, 4], [2]), ([3, 4], [2, 4]), ([1, 5], [5])], [([3, 4], [2, 4]), ([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, 5], [3, 15]), ([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])], [([3, 5], [2, 10]), ([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])], [([4, 5], [2, 4, 20]), ([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]`	`[2, 6]`	Failed
explicit oracle 1	`[2]`	`[2]`	Passed
explicit oracle 2	`[2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]`	`[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, 1]`	`[2, 4]`	Failed
explicit oracle 7	`[5]`	`[5]`	Passed

SHA-256 / 9d76515c64b8600d9f274c8a2b9190e46927f6df9e85ea6c3dd5316d0bfa4286

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 = [[([2, 3], [2, 6]), ([1, 2], [2]), ([30, 31], [2, 3, 8, 107, 15922, 633759288]), ([1, 3], [3]), ([1, 4], [4]), ([2, 4], [2]), ([3, 4], [2, 4]), ([1, 5], [5])], [([3, 4], [2, 4]), ([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, 5], [3, 15]), ([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])], [([3, 5], [2, 10]), ([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])], [([4, 5], [2, 4, 20]), ([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, 6]`	`[2, 6]`	Passed
explicit oracle 1	`[2]`	`[2]`	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 / 7189eeed0f08f175bd02b5f82bdb8109380a7ff1443c42b5e6ae84b55ad25f46

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.057141+00:00.

Case digest / 76aaf4836e904d32ceef982c24999733da736bbe4e89d122b1106ad93be2414f