FA-14986 / Numerics / Open access

Egyptian greedy fraction: unit fraction ordering · case 01

The exact egyptian greedy fraction result violates the stated contract at unit fraction ordering.

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

ROOT CAUSE

The unit fraction ordering step uses out[::-1] instead of out.

VERIFIED REPAIR

Use out at the unit fraction ordering step.

Unsuccessful approach: The partial repair out[:-1] still violates the unit fraction ordering 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[::-1]
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]), ([1, 4], [4]), ([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]), ([1, 5], [5]), ([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, 5], [2, 4, 20]), ([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, 6], [2]), ([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	`[6, 2]`	`[2, 6]`	Failed
explicit oracle 1	`[2]`	`[2]`	Passed
explicit oracle 2	`[633759288, 15922, 107, 8, 3, 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	`[4, 2]`	`[2, 4]`	Failed
explicit oracle 7	`[5]`	`[5]`	Passed

SHA-256 / cf24942b4e81331b4b42bcef3f6ccdafb6dbb864f42645ef49576a22c18ba6ab

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=math.gcd(p,q)
     if not g:return None
     p,q=p//g,q//g
    return out[:-1]
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]), ([1, 4], [4]), ([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]), ([1, 5], [5]), ([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, 5], [2, 4, 20]), ([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, 6], [2]), ([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, 6]`	Failed
explicit oracle 1	`[]`	`[2]`	Failed
explicit oracle 2	`[2, 3, 8, 107, 15922]`	`[2, 3, 8, 107, 15922, 633759288]`	Failed
explicit oracle 3	`[]`	`[3]`	Failed
explicit oracle 4	`[]`	`[4]`	Failed
explicit oracle 5	`[]`	`[2]`	Failed
explicit oracle 6	`[2]`	`[2, 4]`	Failed
explicit oracle 7	`[]`	`[5]`	Failed

SHA-256 / 68617fc5b7b9a5b5a722c169e6a195c1c68019749e4cb1b57285c2b0411a9aa7

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]), ([1, 4], [4]), ([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]), ([1, 5], [5]), ([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, 5], [2, 4, 20]), ([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, 6], [2]), ([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 / 3b93243a96457465d69728feef81d03cbd540846406968be56943be7cc828b07

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

Case digest / 9a67b5fee4a8a3171bdff5186ca77fa170ace5875dcaf3ecd9dbd2088d8ed1e1