{"abstract":"Filters are sized far smaller than required for the requested false-positive rate.","category":"Probabilistic sketches","checks":10,"contract":"Input {n, p}. Reject n <= 0 or p outside the open interval (0,1) with \"invalid\". Otherwise m = ceil(-n ln p / (ln 2)^2), k = max(1, round(m/n * ln 2)), bytes = ceil(m/8), and the predicted false-positive rate (1 - e^(-k n / m))^k rounded to 6 decimals. Return [m, k, bytes, fp].","contract_signature":"x","evaluation_group":"w2-probabilistic_sketches-bloom-sizing","failed_approach":"Doubling ln 2 is not its square, so every filter is still mis-sized.","family":"w2-probabilistic_sketches-bloom-sizing-ln2-squared","id":"FA-72876","implementations":{"attempt":{"sha256":"92af19d7e293b40de8f2bcc151368b0f881c7addd6b9ee36d3d1a173f6d276ef","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    n = x['n']\n    p = x['p']\n    if n <= 0 or not (0 < p < 1):\n        return 'invalid'\n    m = math.ceil(-n * math.log(p) / (2 * math.log(2)))\n    k = max(1, round(m / n * math.log(2)))\n    fp = (1 - math.exp(-k * n / m)) ** k\n    return [m, k, (m + 7) // 8, round(fp, 6)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['thousand items one percent', {'n': 1007, 'p': 0.01}, [9653, 7, 1207, 0.010035]],\n  ['small set loose target', {'n': 4, 'p': 0.3}, [11, 2, 2, 0.267056]],\n  ['near-one target clamps probes', {'n': 50, 'p': 0.9}, [11, 1, 2, 0.989385]],\n  ['tight target', {'n': 201, 'p': 0.0001}, [3854, 13, 482, 0.0001]],\n  ['odd bit count', {'n': 38, 'p': 0.05}, [237, 4, 30, 0.050232]],\n  ['medium set', {'n': 17, 'p': 0.02}, [139, 6, 18, 0.019754]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 780, 'p': 0.123}, [3403, 3, 426, 0.122936]],\n  ['fractional ceil', {'n': 10, 'p': 0.07}, [56, 4, 7, 0.067896]]],\n [['thousand items one percent', {'n': 1014, 'p': 0.01}, [9720, 7, 1215, 0.010036]],\n  ['small set loose target', {'n': 5, 'p': 0.3}, [13, 2, 2, 0.287972]],\n  ['near-one target clamps probes', {'n': 100, 'p': 0.9}, [22, 1, 3, 0.989385]],\n  ['tight target', {'n': 202, 'p': 0.0001}, [3873, 13, 485, 0.0001]],\n  ['odd bit count', {'n': 39, 'p': 0.05}, [244, 4, 31, 0.049785]],\n  ['medium set', {'n': 22, 'p': 0.02}, [180, 6, 23, 0.019701]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 783, 'p': 0.123}, [3416, 3, 427, 0.122943]],\n  ['fractional ceil', {'n': 11, 'p': 0.07}, [61, 4, 8, 0.069737]]],\n [['thousand items one percent', {'n': 1021, 'p': 0.01}, [9787, 7, 1224, 0.010036]],\n  ['small set loose target', {'n': 6, 'p': 0.3}, [16, 2, 2, 0.278397]],\n  ['near-one target clamps probes', {'n': 150, 'p': 0.9}, [33, 1, 5, 0.989385]],\n  ['tight target', {'n': 203, 'p': 0.0001}, [3892, 13, 487, 0.0001]],\n  ['odd bit count', {'n': 40, 'p': 0.05}, [250, 4, 32, 0.049931]],\n  ['medium set', {'n': 27, 'p': 0.02}, [220, 6, 28, 0.020034]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 786, 'p': 0.123}, [3429, 3, 429, 0.122949]],\n  ['fractional ceil', {'n': 12, 'p': 0.07}, [67, 4, 9, 0.068452]]],\n [['thousand items one percent', {'n': 1028, 'p': 0.01}, [9854, 7, 1232, 0.010037]],\n  ['small set loose target', {'n': 7, 'p': 0.3}, [18, 2, 3, 0.29222]],\n  ['near-one target clamps probes', {'n': 200, 'p': 0.9}, [44, 1, 6, 0.989385]],\n  ['tight target', {'n': 204, 'p': 0.0001}, [3911, 13, 489, 0.0001]],\n  ['odd bit count', {'n': 41, 'p': 0.05}, [256, 4, 32, 0.05007]],\n  ['medium set', {'n': 32, 'p': 0.02}, [261, 6, 33, 0.019953]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 789, 'p': 0.123}, [3442, 3, 431, 0.122956]],\n  ['fractional ceil', {'n': 13, 'p': 0.07}, [72, 4, 9, 0.069978]]],\n [['thousand items one percent', {'n': 1035, 'p': 0.01}, [9921, 7, 1241, 0.010037]],\n  ['small set loose target', {'n': 8, 'p': 0.3}, [21, 2, 3, 0.284327]],\n  ['near-one target clamps probes', {'n': 250, 'p': 0.9}, [55, 1, 7, 0.989385]],\n  ['tight target', {'n': 205, 'p': 0.0001}, [3930, 13, 492, 0.0001]],\n  ['odd bit count', {'n': 42, 'p': 0.05}, [262, 4, 33, 0.050203]],\n  ['medium set', {'n': 37, 'p': 0.02}, [302, 6, 38, 0.019895]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 792, 'p': 0.123}, [3455, 3, 432, 0.122963]],\n  ['fractional ceil', {'n': 14, 'p': 0.07}, [78, 4, 10, 0.068853]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"8de8e9829a2cf55ce2cab4a8f42c4d4601394df0fb6ee80e87e073c8a118219e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    n = x['n']\n    p = x['p']\n    if n <= 0 or not (0 < p < 1):\n        return 'invalid'\n    m = math.ceil(-n * math.log(p) / math.log(2))\n    k = max(1, round(m / n * math.log(2)))\n    fp = (1 - math.exp(-k * n / m)) ** k\n    return [m, k, (m + 7) // 8, round(fp, 6)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['thousand items one percent', {'n': 1007, 'p': 0.01}, [9653, 7, 1207, 0.010035]],\n  ['small set loose target', {'n': 4, 'p': 0.3}, [11, 2, 2, 0.267056]],\n  ['near-one target clamps probes', {'n': 50, 'p': 0.9}, [11, 1, 2, 0.989385]],\n  ['tight target', {'n': 201, 'p': 0.0001}, [3854, 13, 482, 0.0001]],\n  ['odd bit count', {'n': 38, 'p': 0.05}, [237, 4, 30, 0.050232]],\n  ['medium set', {'n': 17, 'p': 0.02}, [139, 6, 18, 0.019754]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 780, 'p': 0.123}, [3403, 3, 426, 0.122936]],\n  ['fractional ceil', {'n': 10, 'p': 0.07}, [56, 4, 7, 0.067896]]],\n [['thousand items one percent', {'n': 1014, 'p': 0.01}, [9720, 7, 1215, 0.010036]],\n  ['small set loose target', {'n': 5, 'p': 0.3}, [13, 2, 2, 0.287972]],\n  ['near-one target clamps probes', {'n': 100, 'p': 0.9}, [22, 1, 3, 0.989385]],\n  ['tight target', {'n': 202, 'p': 0.0001}, [3873, 13, 485, 0.0001]],\n  ['odd bit count', {'n': 39, 'p': 0.05}, [244, 4, 31, 0.049785]],\n  ['medium set', {'n': 22, 'p': 0.02}, [180, 6, 23, 0.019701]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 783, 'p': 0.123}, [3416, 3, 427, 0.122943]],\n  ['fractional ceil', {'n': 11, 'p': 0.07}, [61, 4, 8, 0.069737]]],\n [['thousand items one percent', {'n': 1021, 'p': 0.01}, [9787, 7, 1224, 0.010036]],\n  ['small set loose target', {'n': 6, 'p': 0.3}, [16, 2, 2, 0.278397]],\n  ['near-one target clamps probes', {'n': 150, 'p': 0.9}, [33, 1, 5, 0.989385]],\n  ['tight target', {'n': 203, 'p': 0.0001}, [3892, 13, 487, 0.0001]],\n  ['odd bit count', {'n': 40, 'p': 0.05}, [250, 4, 32, 0.049931]],\n  ['medium set', {'n': 27, 'p': 0.02}, [220, 6, 28, 0.020034]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 786, 'p': 0.123}, [3429, 3, 429, 0.122949]],\n  ['fractional ceil', {'n': 12, 'p': 0.07}, [67, 4, 9, 0.068452]]],\n [['thousand items one percent', {'n': 1028, 'p': 0.01}, [9854, 7, 1232, 0.010037]],\n  ['small set loose target', {'n': 7, 'p': 0.3}, [18, 2, 3, 0.29222]],\n  ['near-one target clamps probes', {'n': 200, 'p': 0.9}, [44, 1, 6, 0.989385]],\n  ['tight target', {'n': 204, 'p': 0.0001}, [3911, 13, 489, 0.0001]],\n  ['odd bit count', {'n': 41, 'p': 0.05}, [256, 4, 32, 0.05007]],\n  ['medium set', {'n': 32, 'p': 0.02}, [261, 6, 33, 0.019953]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 789, 'p': 0.123}, [3442, 3, 431, 0.122956]],\n  ['fractional ceil', {'n': 13, 'p': 0.07}, [72, 4, 9, 0.069978]]],\n [['thousand items one percent', {'n': 1035, 'p': 0.01}, [9921, 7, 1241, 0.010037]],\n  ['small set loose target', {'n': 8, 'p': 0.3}, [21, 2, 3, 0.284327]],\n  ['near-one target clamps probes', {'n': 250, 'p': 0.9}, [55, 1, 7, 0.989385]],\n  ['tight target', {'n': 205, 'p': 0.0001}, [3930, 13, 492, 0.0001]],\n  ['odd bit count', {'n': 42, 'p': 0.05}, [262, 4, 33, 0.050203]],\n  ['medium set', {'n': 37, 'p': 0.02}, [302, 6, 38, 0.019895]],\n  ['rejects p equal one', {'n': 10, 'p': 1.0}, 'invalid'],\n  ['rejects empty set', {'n': 0, 'p': 0.01}, 'invalid'],\n  ['another sizing', {'n': 792, 'p': 0.123}, [3455, 3, 432, 0.122963]],\n  ['fractional ceil', {'n': 14, 'p': 0.07}, [78, 4, 10, 0.068853]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. 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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-probabilistic_sketches-bloom-sizing-ln2-squared","generated_at":"2026-09-29T14:48:42.568087+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Capacity planning for a Bloom filter decides memory and probe count before any item is inserted; an undersized array silently exceeds the promised false-positive rate.","root_cause":"The denominator of the optimal bit count uses ln 2 rather than (ln 2)^2.","sha256":"0ceae5c0c974122e5efa9c632b08ce08f3a4156866d3c891fcb06f3ccdaf6267","title":"Bloom filter sizing: bit formula divides by ln 2 instead of its square · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":37.488,"exit_code":1,"observations":[{"actual":[3346,2,419,0.204518],"check":"thousand items one percent","expected":[9653,7,1207,0.010035],"passed":false},{"actual":[4,1,1,0.632121],"check":"small set loose target","expected":[11,2,2,0.267056],"passed":false},{"actual":[4,1,1,0.999996],"check":"near-one target clamps probes","expected":[11,1,2,0.989385],"passed":false},{"actual":[1336,5,167,0.041306],"check":"tight target","expected":[3854,13,482,0.0001],"passed":false},{"actual":[83,2,11,0.359698],"check":"odd bit count","expected":[237,4,30,0.050232],"passed":false},{"actual":[48,2,6,0.257592],"check":"medium set","expected":[139,6,18,0.019754],"passed":false},{"actual":"invalid","check":"rejects p equal one","expected":"invalid","passed":true},{"actual":"invalid","check":"rejects empty set","expected":"invalid","passed":true},{"actual":[1180,1,148,0.483674],"check":"another sizing","expected":[3403,3,426,0.122936],"passed":false},{"actual":[20,1,3,0.393469],"check":"fractional ceil","expected":[56,4,7,0.067896],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"thousand items one percent\", \"actual\": [3346, 2, 419, 0.204518], \"expected\": [9653, 7, 1207, 0.010035], \"passed\": false}, {\"check\": \"small set loose target\", \"actual\": [4, 1, 1, 0.632121], \"expected\": [11, 2, 2, 0.267056], \"passed\": false}, {\"check\": \"near-one target clamps probes\", \"actual\": [4, 1, 1, 0.999996], \"expected\": [11, 1, 2, 0.989385], \"passed\": false}, {\"check\": \"tight target\", \"actual\": [1336, 5, 167, 0.041306], \"expected\": [3854, 13, 482, 0.0001], \"passed\": false}, {\"check\": \"odd bit count\", \"actual\": [83, 2, 11, 0.359698], \"expected\": [237, 4, 30, 0.050232], \"passed\": false}, {\"check\": \"medium set\", \"actual\": [48, 2, 6, 0.257592], \"expected\": [139, 6, 18, 0.019754], \"passed\": false}, {\"check\": \"rejects p equal one\", \"actual\": \"invalid\", \"expected\": \"invalid\", \"passed\": true}, {\"check\": \"rejects empty set\", \"actual\": \"invalid\", \"expected\": \"invalid\", \"passed\": true}, {\"check\": \"another sizing\", \"actual\": [1180, 1, 148, 0.483674], \"expected\": [3403, 3, 426, 0.122936], \"passed\": false}, {\"check\": \"fractional ceil\", \"actual\": [20, 1, 3, 0.393469], \"expected\": [56, 4, 7, 0.067896], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":38.881,"exit_code":1,"observations":[{"actual":[6691,5,837,0.041354],"check":"thousand items one percent","expected":[9653,7,1207,0.010035],"passed":false},{"actual":[7,1,1,0.435282],"check":"small set loose target","expected":[11,2,2,0.267056],"passed":false},{"actual":[8,1,1,0.99807],"check":"near-one target clamps probes","expected":[11,1,2,0.989385],"passed":false},{"actual":[2671,9,334,0.001689],"check":"tight target","expected":[3854,13,482,0.0001],"passed":false},{"actual":[165,3,21,0.124162],"check":"odd bit count","expected":[237,4,30,0.050232],"passed":false},{"actual":[96,4,12,0.066354],"check":"medium set","expected":[139,6,18,0.019754],"passed":false},{"actual":"invalid","check":"rejects p equal one","expected":"invalid","passed":true},{"actual":"invalid","check":"rejects empty set","expected":"invalid","passed":true},{"actual":[2359,2,295,0.234081],"check":"another sizing","expected":[3403,3,426,0.122936],"passed":false},{"actual":[39,3,5,0.154535],"check":"fractional ceil","expected":[56,4,7,0.067896],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"thousand items one percent\", \"actual\": [6691, 5, 837, 0.041354], \"expected\": [9653, 7, 1207, 0.010035], \"passed\": false}, {\"check\": \"small set loose target\", \"actual\": [7, 1, 1, 0.435282], \"expected\": [11, 2, 2, 0.267056], \"passed\": false}, {\"check\": \"near-one target clamps probes\", \"actual\": [8, 1, 1, 0.99807], \"expected\": [11, 1, 2, 0.989385], \"passed\": false}, {\"check\": \"tight target\", \"actual\": [2671, 9, 334, 0.001689], \"expected\": [3854, 13, 482, 0.0001], \"passed\": false}, {\"check\": \"odd bit count\", \"actual\": [165, 3, 21, 0.124162], \"expected\": [237, 4, 30, 0.050232], \"passed\": false}, {\"check\": \"medium set\", \"actual\": [96, 4, 12, 0.066354], \"expected\": [139, 6, 18, 0.019754], \"passed\": false}, {\"check\": \"rejects p equal one\", \"actual\": \"invalid\", \"expected\": \"invalid\", \"passed\": true}, {\"check\": \"rejects empty set\", \"actual\": \"invalid\", \"expected\": \"invalid\", \"passed\": true}, {\"check\": \"another sizing\", \"actual\": [2359, 2, 295, 0.234081], \"expected\": [3403, 3, 426, 0.122936], \"passed\": false}, {\"check\": \"fractional ceil\", \"actual\": [39, 3, 5, 0.154535], \"expected\": [56, 4, 7, 0.067896], \"passed\": false}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}