Decomposing factorial of 300K as the product of 300K factors larger than 100K
将 300K! 分解为大于 100K 的 300K 个因子的乘积
2025 年 4 月 8 日
将 300K! 分解为大于 100K 的 300K 个因子的乘积
几天前，Terence Tao 提出了一个挑战，将 300K! 分解为大于 100K 的 300K 个因子的乘积。一个较小的例子是将 10! 分解为大于等于 3 的 10 个因子的乘积。
10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
10! = 3 * 3 * 4 * 4 * 4 * 5 * 5 * 6 * 6 * 7
他能够展示 300K! 分解为大于 90K 的 300K 个因子的乘积，并提出了一种尝试使用更大数字的方法。这是证明一个猜想的一部分，所以完整的问题更通用，但让我们尝试解决这个例子。
我们将固定 N=300K，这是 Tao 在文章中分析的情况。Tao 的想法是从一个奇数 B 开始，它是大于 100K 的 300K 个奇数的乘积，并尝试修复差异。重要的一点是 300! 是偶数，所以想法是尝试使用 2 来帮助完成这项任务。
他定义了 B-heavy 素数，它们在 B 中出现的次数多于在 N!=300! 中出现的次数，以及 N!-heavy 素数，它们在 N!=300! 中出现的次数多于在 B 中出现的次数。想法是用更大的 N!-heavy 素数 n 乘以 2 的幂，或者纯粹是 2 的幂来替换每个 B-heavy 素数。这将增加 B 的因子，我们将得到请求的分解。重要的是尽可能少地使用 2，这样我们就不会用完它们。所有这些在 Tao 的文章 中有更好的解释，所以值得阅读。
他能够应用这种方法得到一个分解，数字大于 90K，但映射和 2 的使用不是最优的，所以对于 100K 来说还不够好。我们将找到执行此映射的最佳方法，并获得一个数字大于 100K 的分解。
前言
我们将使用 Racket。首先，我们将尝试重现 90K 的结果。
我们将固定 N=300K，并编写一个记忆化的 factorize 版本，因为因式分解很困难且很慢，并且我们将重复使用相同的数字很多次。
#lang racket
(require math/number-theory)
(define N 300000)
(define secret-factorize-cache (make-hash))
(define (factorize/cache n)
(hash-ref! secret-factorize-cache n (lambda () (factorize n))))
N!=300K! 的因式分解
最好分解每个数字并收集因式分解，而不是使用内置的阶乘并尝试分解结果，这可能需要很长时间（或者失败，因为分解大数字很困难）。
(define (hash-add-factorization! h f)
(for ([pair (in-list f)])
(define p (car pair))
(define m (cadr pair))
(hash-update! h p {lambda (x) (+ x m)} 0)))
(define (hash->factorization h)
(define l (for/list ([(p m) (in-hash h)]) (list p m)))
(sort l < #:key car))
(define (factorize-factorial N)
(define h (make-hash))
(for ([n (in-range N)])
(hash-add-factorization! h (factorize/cache (add1 n))))
(hash->factorization h))
(define (factorization-total N)
(define t 0)
(for([pm (in-list N)])
(set! t (+ t (cadr pm))))
t)
(display "N! factorization calculation (N=300000): ")
(define Nf2-factorization (time (factorize-factorial N)))
(display "Number of primes including 2: ")
(displayln (length Nf2-factorization))
(display "Number of primes with multiplicitry including 2: ")
(displayln (factorization-total Nf2-factorization))
(display "Multiplicity of 2: ")
(define Nf-2multiplicity (if (and (not (null? Nf2-factorization)) (= (caar Nf2-factorization) 2)) (cadar Nf2-factorization) 0))
(displayln Nf-2multiplicity)
(display "Should be 299992. Difference: ")
(displayln (- 299992 Nf-2multiplicity))
(displayln "N! factorization excluding 2: ")
(define Nf-factorization (if (and (not (null? Nf2-factorization)) (= (caar Nf2-factorization) 2)) (cdr Nf2-factorization) Nf2-factorization))
(display "Number of primes excluding 2: ")
(displayln (length Nf-factorization))
(display "Number of primes with multiplicity excluding 2: ")
(displayln (factorization-total Nf-factorization))
(display "Partial list excluding 2: ")
(displayln (append (take Nf-factorization 7) (list "...") (take-right Nf-factorization 3)))
(newline)
输出是
N! factorization calculation (N=300000): cpu time: 4828 real time: 4825 gc time: 406
Number of primes including 2: 25997
Number of primes with multiplicity including 2: 1059501
Multiplicity of 2: 299992
Should be 299992. Difference: 0
N! factorization excluding 2:
Number of primes excluding 2: 25996
Number of primes with multiplicity excluding 2: 759509
Partial list excluding 2: ((3 149995) (5 74998) (7 49996) (11 29997) (13 24997) (17 18749) (19 16665) ... (299977 1) (299983 1) (299993 1))
计算因式分解需要大约 4 秒，并且我们得到的 2 的数量与 Tao 相同。（很多 2。）
B 的因式分解 (L=90K, A=50)
为了重现结果，我们将使用与 Tao 相同的 L 和 A，所以数字 B 是 50 个 90K 和 102K 之间的奇数的副本。该计算考虑了数字 A 不除 N 的情况，我决定从 L 开始添加更多奇数。
(define (factorize-B-number N L size)
(define h (make-hash))
(define from (if (odd? L) L (add1 L)))
(for ([n (in-range N)])
(hash-add-factorization! h (factorize/cache (+ from (* (remainder n size) 2)))))
(hash->factorization h))
(display "B factorization calculation (L=90000, A=50): ")
(define B-factorization (time (factorize-B-number N 90000 (quotient N 50))))
(display "Number of primes: ")
(displayln (length B-factorization))
(display "Number of primes with multiplicity: ")
(displayln (factorization-total B-factorization))
(display "Partial list: ")
(displayln (append (take B-factorization 7) (list "...") (take-right B-factorization 3)))
(newline)
(display "B has more primes than N!, with multiplicity excluding 2: ")
(displayln (- (factorization-total B-factorization) (factorization-total Nf-factorization)))
(display "Should be 14891. Difference: ")
(displayln (- (- (factorization-total B-factorization) (factorization-total Nf-factorization)) 14891))
(newline)
输出是
B factorization calculation (L=90000, A=50): cpu time: 531 real time: 534 gc time: 46
Number of primes: 3099
Number of primes with multiplicity: 774450
Partial list: ((3 150000) (5 75000) (7 50000) (11 29900) (13 25000) (17 18700) (19 16600) ... (101977 50) (101987 50) (101999 50))
B has more primes than N!, with multiplicity excluding 2: 14941
Should be 14891. Difference: 50
它更快，只需要半秒钟，因为因式分解是记忆化的，我得到了 50 个更多素数（包括重数）。我过去使用了一种复杂的方法来计算重复的奇数，但我将其更改为简单而缓慢的方法，但额外的 50 个素数并没有消失。欢迎任何见解或错误报告。
N!-heavy 和 B-heavy
现在我们比较 N! 和 B 的因式分解，删除重复的素数（包括重数）。
(define (factorization-split N B)
(define h (make-hash))
(for ([pm (in-list N)])
(hash-update! h (car pm) {lambda (x) (+ x (cadr pm))} 0))
(for ([pm (in-list B)])
(hash-update! h (car pm) {lambda (x) (- x (cadr pm))} 0))
(define hN (make-hash))
(define hB (make-hash))
(for ([(p m) (in-hash h)])
(cond
[(> m 0) (hash-update! hN p {lambda (x) (+ x m)} 0)]
[(< m 0) (hash-update! hB p {lambda (x) (- x m)} 0)]
[else #;(= m 0) (void)]))
(values (hash->factorization hN) (hash->factorization hB)))
(define-values (Nf-heavy B-heavy) (factorization-split Nf-factorization B-factorization))
(display "--------------------------")
(newline)
(displayln "N! heavy part excluding 2: ")
(display "Number of primes excluding 2: ")
(displayln (length Nf-heavy))
(display "Number of primes with multiplicity excluding 2: ")
(displayln (factorization-total Nf-heavy))
(display "Partial list excluding 2: ")
(displayln (append (take Nf-heavy 7) (list "...") (take-right Nf-heavy 3)))
(displayln "B heavy part: ")
(display "Number of primes: ")
(displayln (length Nf-heavy))
(display "Number of primes with multiplicity: ")
(displayln (factorization-total B-heavy))
(display "Partial list excluding 2: ")
(displayln (append (take B-heavy 7) (list "...") (take-right B-heavy 3)))
(newline)
(display "B-heavy has more primes than N!-heavy, with multiplicity excluding 2: ")
(displayln (- (factorization-total B-factorization) (factorization-total Nf-factorization)))
(display "Should be 14891. Difference: ")
(displayln (- (- (factorization-total B-heavy) (factorization-total Nf-heavy)) 14891))
(newline)
输出是
N! heavy part excluding 2:
Number of primes excluding 2: 23334
Number of primes with multiplicity excluding 2: 76915
Partial list excluding 2: ((11 97) (17 49) (19 65) (23 85) (29 12) (31 49) (37 32) ... (299977 1) (299983 1) (299993 1))
B heavy part:
Number of primes: 23334
Number of primes with multiplicity: 91856
Partial list excluding 2: ((3 5) (5 2) (7 4) (13 3) (43 9) (47 31) (61 1) ... (101977 48) (101987 48) (101999 48))
B-heavy has more primes than N!-heavy, with multiplicity excluding 2: 14941
Should be 14891. Difference: 50
毫不奇怪，我再次获得了比预期数量多 50 个（包括重数）的素数。
按顺序平衡素数
现在我们尝试用更大的 N!-heavy 素数 n 乘以 2 的幂，或者纯粹是 2 的幂来替换每个 B-heavy 素数。我无法编写 Tao 解释的方法，所以我做了自己的方法。只需按顺序匹配素数（包括重数）。
B 中的素数（包括重数）多于 N! 中的素数，所以我们用 1 填充列表。尽管 1 不是素数，但我们会将其添加到因式分解列表中来惹恼数学家并使程序稍微简单一些... 我们可以将 1 放在开头或结尾，所以有两个结果。
每个函数的结果是未使用的 2 的数量，所以 0 或正数是好的，我们可以任意分配它们或为未来的问题保存它们:)。我们还获得了 B 中 heavy 素数与 N! 中 heavy 素数（包括重数，可能包括 1）和 2 的幂的替换表。这使得验证更容易。
(display "--------------------------")
(newline)
(define(multi-cons v n l) (if (zero? n) l (multi-cons v (sub1 n) (cons v l))))
(define (do-balance/inorder Nh Bh m2)
(unless (= (factorization-total Nh) (factorization-total Bh)) (error))
(let loop ([Nh Nh] [Bh Bh] [m2 m2] [rtable '()])
(cond
[(null? Bh) (values m2 (reverse rtable))]
[else
(define Np (caar Nh))
(define Nm (cadar Nh))
(define Bp (caar Bh))
(define Bm (cadar Bh))
(define q2 (max 0 (inexact->exact (ceiling (log (/ Bp Np) 2)))))
(unless (>= (* (expt 2 q2) Np) Bp) (error))
(define new-rtable (multi-cons (list Bp (* Np (expt 2 q2))) (min Nm Bm) rtable))
(cond
[(> Nm Bm) (loop (cons (list Np (- Nm Bm)) (cdr Nh)) (cdr Bh) (- m2 (* Bm q2)) new-rtable)]
[(< Nm Bm) (loop (cdr Nh) (cons (list Bp (- Bm Nm)) (cdr Bh)) (- m2 (* Nm q2)) new-rtable)]
[else (loop (cdr Nh) (cdr Bh) (- m2 (* Bm q2)) new-rtable)])])))
(define (balance/inorder/first Nh Bh m2)
(define dif (- (factorization-total Bh) (factorization-total Nh)))
(define eNh (if (> dif 0) (reverse (cons (list 1 dif) (reverse Nh))) Nh))
(define eBh (if (< dif 0) (reverse (cons (list 1 (- dif)) (reverse Bh))) Bh))
(do-balance/inorder eNh eBh m2))
(define (balance/inorder/last Nh Bh m2)
(define dif (- (factorization-total Bh) (factorization-total Nh)))
(define eNh (if (> dif 0) (cons (list 1 dif) Nh) Nh))
(define eBh (if (< dif 0) (cons (list 1 (- dif)) (reverse Bh)) Bh))
(do-balance/inorder eNh eBh m2))
(displayln "Balance primes / match first primes: ")
(define-values (leftover2/first table/first) (balance/inorder/first Nf-heavy B-heavy Nf-2multiplicity))
(display "leftover 2 multiplicity: ")
(displayln leftover2/first)
(displayln "Compare with 6853 or 6003")
(displayln "Partial conversion table: ")
(displayln (append (take table/first 7) (list "...") (take-right table/first 3)))
(newline)
(displayln "Balance primes / match last primes: ")
(define-values (leftover2/last table/last) (balance/inorder/last Nf-heavy B-heavy Nf-2multiplicity))
(display "leftover 2 multiplicity: ")
(displayln leftover2/last)
(displayln "Compare with 6853 or 6003")
(displayln "Partial conversion table: ")
(displayln (append (take table/last 7) (list "...") (take-right table/last 3)))
(newline)
输出是
Balance primes / match first primes:
leftover 2 multiplicity: 6108
Compare with 6853 or 6003
Partial conversion table: ((3 11) (3 11) (3 11) (3 11) (3 11) (5 11) (5 11) ... (101999 131072) (101999 131072) (101999 131072))
Balance primes / match last primes:
leftover 2 multiplicity: 6497
Compare with 6853 or 6003
Partial conversion table: ((3 4) (3 4) (3 4) (3 4) (3 4) (5 8) (5 8) ... (101999 299977) (101999 299983) (101999 299993))
我们得到了 6108 和 6497 个未使用的 2，所以第二种方法更好。我不确定为什么，但有趣的是第一种方法用 11 替换 3，第二种方法用 4 替换，这不太浪费。
我们可以将结果与 Tao 用他的方法获得的 6853 进行比较。但是我们有 50 个更多素数（包括重数），所以我们可以将它们与 6853+50*17=6003 进行比较。它们是相似的，我将单方面宣布成功重现。
验证转换表
我无法想象之前的代码中有错误，但以防万一，让我们验证转换表是否具有与 B-heavy 和 N!-heavy 相同的素数以及正确的 2 的幂。
验证下一个不直接的方法将很有用。
(define (conversion-table->factorizations t)
(define hN (make-hash))
(define hB (make-hash))
(for ([x (in-list t)]) ; Reverse order of N! and B. Sorry.
(define pN (cadr x))
(define pB (car x))
(hash-add-factorization! hN (factorize/cache pN))
(hash-add-factorization! hB (factorize/cache pB)))
(define m2 (hash-ref hN 2 0))
(hash-remove! hN 2)
(values m2 (hash->factorization hN) (hash->factorization hB)))
(display "--------------------------")
(newline)
(displayln "Balance primes / match first primes: ")
(define-values (m2/fisrt/v Nf-heavy/first/v B-heavy/first/v) (conversion-table->factorizations table/first))
(display "Check 2 multiplicity: ")
(displayln (= m2/fisrt/v (- Nf-2multiplicity leftover2/first)))
(display "Check N!-heavy primes excluding 2: ")
(displayln (equal? Nf-heavy/first/v Nf-heavy))
(display "Check B-heavy primes: ")
(displayln (equal? B-heavy/first/v B-heavy))
(newline)
(displayln "Balance primes / match first primes: ")
(define-values (m2/last/v Nf-heavy/last/v B-heavy/last/v) (conversion-table->factorizations table/last))
(display "Check 2 multiplicity: ")
(displayln (= m2/last/v (- Nf-2multiplicity leftover2/last)))
(display "Check N!-heavy primes excluding 2: ")
(displayln (equal? Nf-heavy/last/v Nf-heavy))
(display "Check B-heavy primes: ")
(displayln (equal? B-heavy/last/v B-heavy))
(newline)
输出是
Balance primes / match first primes:
Check 2 multiplicity: #t
Check N!-heavy primes excluding 2: #t
Check B-heavy primes: #t
Balance primes / match first primes:
Check 2 multiplicity: #t
Check N!-heavy primes excluding 2: #t
Check B-heavy primes: #t
All #rt，完全成功。
一种优化匹配的新方法
现在我们将尝试找到一种优化且高效的方法来进行此匹配。首先是优化部分。
不是用 N!-heavy 素数 n 和 2 的幂或纯粹的非负 2 的幂来替换每个 B-heavy 素数 b，使得 b <= n * 2^a，我们将反其道而行之。我们将用 B-heavy 素数 b 除以一个非负 2 的幂来替换每个 N!-heavy 素数 n，使得 n >= b/2^a。一切都包括重数。在这里，我们再次用 1 扩展了 N!-heavy 素数的列表，1 不是素数，但非常适合该算法，并避免了添加另一个特殊情况的必要性。（如果需要，我们也可以用 1 扩展 B-heavy 素数的列表。）
主要思想非常好且简单，我们用最大的可能 b/2^a 替换 N!-heavy 列表中最大的 n，其中 b 是 B-heavy 列表中的素数或 1，a 是一个非负整数。这是贪婪的，所以我们不需要回溯，我们可以一次解决一个数字，从最大的一个开始。困难的部分是证明这个顺序给出了最佳结果，就使用尽可能少的 2 的总幂而言。我不得不丑化该方法来证明这是最佳的。:(
证明：
出于稍后会清楚的晦涩原因，请耐心等待，在 B-heavy 素数（或 1）的列表中，我们将允许素数（或 1）除以非负 2 的幂。所以该列表包括素数、素数除以正 2 的幂、数字 1 和 1 除以正 2 的幂，一切都包括重数。所以目标是用 B-heavy 事物列表中的数字 b/2^c 替换这个 N!-heavy 事物列表中的每个素数（或 1）n，使得 n >= (b/2^c)/2^a，其中 c 和 a 是非负的，b 可能是素数或 1，如果需要，一切都包括重数。
如果我们将 1（包括重数）添加到 N!-heavy 事物或 B-heavy 事物的列表中，以获得相同的元素数量（包括重数）。在这个初始步骤中，所有它们都是整数，并且它们都没有被 2 的幂除，但它包含在 B-heavy 事物列表可能包括二进制分数的常见情况中。
我们取 N!-heavy 数字列表中最大的数字 n。我们必须分析两种情况。
情况 1： 如果 B-heavy 事物列表中最大的数字 b 大于 n，则 b 大于 N!-heavy 数字列表中的所有数字。所以在任何替换中，我们都必须将 b 除以 2 才能使用它。所以我们将 B-heavy 事物列表中的 b 替换为 b/2，并再次尝试使用递归。（我们应该在其他地方跟踪我们将数字 b 除以 2 的次数。）在重复此步骤几次之后，很明显 B-heavy 列表中的所有事物都将小于 n，所以我们不会永远卡在这个步骤中。
情况 2： 如果 B-heavy 事物列表中最大的数字 b 小于或等于 n，则 B-heavy 事物列表中的所有数字都小于或等于 n。
让我们假设我们选择一个从当前 N!-heavy 数字列表到当前 B-heavy 事物列表的任意映射，如果需要，将其除以 2 的幂。特别是我们关心每个列表 n 和 b 中最大的一个，并假设 n 没有映射到 b/2^a。
然后 n 映射到 b'（这里不需要额外的 2 的幂），n' 映射到 b/2^a，所以特别地 n>=b/2^a（其中 a 为 0 或正数）。
我们可以交换映射并使 n 映射到 b，n' 映射到 b'/2^a 吗？
由于 b <= n，因此将 n 映射到 b 是可以的（这里也不需要额外的 2 的幂）。
由于 b>=b'，则 n >= b/2^a >= b'/2^a，所以我们得到 n>=b'/2^a，我们可以将 n 映射到 b'/2^a。
所以代替将 n 映射到 b'，n' 映射到 b/2^a，我们也可以考虑映射 n 到 b，n' 到 b'/2^a。此外，可能可以改进此映射并使用小于 a 的数字，因此在交换后，我们使用相同的或更小的 2 的总幂。
因此，要找到最佳映射，只需考虑将最大的 N!-heavy 数字 n 映射到最大的 B-heavy 事物 b 的映射就足够了。一旦固定了最大的数字映射（包括重数），我们就可以尝试映射 N!-heavy 和 B-heavy 列表中剩余的 K-1 个元素。
在重复这些 2 种情况足够多次后，我们得到 N!-heavy 和 B-heavy 的空列表，我们就完成了。所以通过这种贪婪的方法，我们得到了最佳映射之一。
算法：
第二个问题是如何高效地实现它。我们将 N!-heavy 列表从大到小排序，所以找到最大的 n 是很简单的。
现在我们必须选择最大的可能 b/2^a，其中 b 在 B-heavy 数字列表中。我们必须拆分该列表。
我们将小于 n 的数字保存在一个从大到小排序的列表中，所以很容易找到最大的一个并在使用后将其删除。
我们将大于 n 的数字保存在一个 treelist 中，该 treelist 按 b 的以 2 为底的对数的非整数部分排序，即 key(b) = {log_2(b)} = log_2(b) - [log_2(b)] 我们将原始素数（或 1）b 存储在 treelist 中（不除以 2 的幂）。如果我们除以 2 的幂，嘿会以相同的顺序排列，但这样我们实际上不必每次得到一个较小的 n 时都除以它们。
Treelist 是假装是列表的 RRB 树，或者秘密实现为 RRB 树的列表。所以我们得到 O(log(K)) 插入到确定位置，删除确定位置和在确定位置位置查找。
我们也会保持 treelist 的排序，所以我们可以使用二分查找来获得 O(log^2(K)) 插入到正确顺序中，并查找该顺序中最近的较小数字。（使用假装是一棵树的树，我们可以用 O(log(K) 做所有这些，但我们必须使用 Racket 的一个包，所以为了节省几分钟的安装时间，让我们只使用一个 treelist。）
在 treelist 中，我们搜索小于 n 的项，并且在该顺序中更接近（这环绕 0）。我们使用以 2 为底的对数的非整数部分，所以我们可以计算出当我们使用它时，我们必须将其除以 2 的次数。
所以我们只需查看两个列表，并比较每个列表中最好的一个，以找到在当场调整 2 的幂后的最大数字 b，而不是跟踪它或每次更改每个较大数字的幂。
随着 N!-heavy 列表中最大的数字减少，我们将从较小的 B-heavy 列表中删除未使用的较大数字，并将它们插入到最大的 B-heavy 列表中。
所以所有过程都可以在 O(K log^2(K)) 时间内完成（或者使用一棵真正的树 O(K log(K))，其中 K 是初始 N!-heavy 列表中素数的数量。
代码：
(require racket/treelist)
(define (treelist->factorization h) (sort (treelist->list h) < #:key car))
(define (treelist-factorization-total N) (define t 0) (for([pm (in-treelist N)]) (set! t (+ t (cadr pm)))) t)
(define (key pm) (define l (log (car pm) 2)) (- l (floor l)))
(define (treelist-find-prev/ordered l n)
(define key-n (key n))
(cond
[(treelist-empty? l) -1]
[(< key-n (key (treelist-first l))) -1]
[(< (key (treelist-last l)) key-n) (sub1 (treelist-length l))]
[else
(let loop ([first 0] [last (sub1 (treelist-length l))])
(cond
[(= (- last first) 1) first]
[else
(define mid (quotient (+ first last) 2))
(cond
[(< key-n (key (treelist-ref l mid))) (loop first mid)]
[else (loop mid last)])]))]))
(define (treelist-insert/ordered l n) (treelist-insert l (add1 (treelist-find-prev/ordered l n)) n))
(define (balance/optimal Nh Bh m2)
(define dif (- (factorization-total Bh) (factorization-total Nh)))
(let loop ([rNh (reverse (cons (list 1 dif) Nh))]
[rBh-smaller (reverse Bh)]
[tBh-bigger (treelist)]
[m2 m2]
[rtable '()])
(cond
[(null? rNh) ; And we are done ...
(values m2 (reverse rtable))]
[(and (not (null? rBh-smaller)) (> (caar rBh-smaller) (caar rNh))) ; If (caar rBh-smaller) is smaller than (caar rNh) then
; move it from rBh-smaller to tBh-bigger
(loop rNh (cdr rBh-smaller) (treelist-insert/ordered tBh-bigger (car rBh-smaller)) m2 rtable)]
[else
(define Np (caar rNh))
(define Nm (cadar rNh))
(define-values (Bp/s Bm/s q2/s Bv/s pos/s)
(cond
[(null? rBh-smaller) (values #f #f #f #f #f)]
[else (define pm (car rBh-smaller)) (values (car pm) (cadr pm) 0 (car pm) #f)]))
(define-values (Bp/b Bm/b q2/b Bv/b pos/b)
(cond
[(treelist-empty? tBh-bigger) (values #f #f #f #f #f)]
[else
(define pos (modulo (treelist-find-prev/ordered tBh-bigger (car rNh)) (treelist-length tBh-bigger)))
(define pm (treelist-ref tBh-bigger pos))
(define Bp (car pm))
(define Bm (cadr pm))
(define q2 (inexact->exact (ceiling (log (/ Bp Np) 2))))
(unless (>= q2 0) (error))
(values Bp Bm q2 (/ Bp (expt 2 q2)) pos)]))
(cond
[(and Bv/s (or (not Bv/b) (>= Bv/s Bv/b))) ; We must remove one of the smaller ones
; No changes to m2
(unless (>= Np Bv/s) (error))
(unless (>= Np Bp/s) (error))
(unless (= q2/s 0) (error))
(define new-rtable (multi-cons (list Bp/s Np) (min Nm Bm/s) rtable))
(cond
[(> Nm Bm/s) (loop (cons (list Np (- Nm Bm/s)) (cdr rNh)) (cdr rBh-smaller) tBh-bigger m2 new-rtable)]
[(< Nm Bm/s) (loop (cdr rNh) (cons (list Bp/s (- Bm/s Nm)) (cdr rBh-smaller)) tBh-bigger m2 new-rtable)]
[else (loop (cdr rNh) (cdr rBh-smaller) tBh-bigger m2 new-rtable)])]
[else ; We must use one of the bigger ones
(unless (>= Np Bv/b) (error))
(unless