Project Euler

SOP and POS

A Boolean function f: {0,1}^n -> {0,1} can be represented in Sum of Products (SOP, or DNF) form: f = bigvee_i bigwedge_j l_ij where each l_ij is a literal (x_k or overlinex_k). The minimal SOP repr...

Source sync Apr 19, 2026

Problem #0851

Level Level 36

Solved By 178

Languages C++, Python

Answer 726358482

Length 524 words

number_theoryoptimizationbrute_force

Let $n$ be a positive integer and let $E_n$ be the set of $n$-tuples of strictly positive integers.

For $u = (u_1, \cdots , u_n)$ and $v = (v_1, \cdots , v_n)$ two elements of $E_n$, we define:

the Sum Of Products of $u$ and $v$, denoted by $\langle u, v\rangle $, as the sum $\displaystyle \sum _{i = 1}^n u_i v_i$;
the Product Of Sums of $u$ and $v$, denoted by $u \star v$, as the product $\displaystyle \prod _{i = 1}^n (u_i + v_i)$.

Let $R_n(M)$ be the sum of $u \star v$ over all ordered pairs $(u, v)$ in $E_n$ such that $\langle u, v\rangle = M$.

For example: $R_1(10) = 36$, $R_2(100) = 1873044$, $R_2(100!) \equiv 446575636 \bmod 10^9 + 7$.

Find $R_6(10000!)$. Give your answer modulo $10^9+7$.

Problem 851: SOP and POS

Mathematical Foundation

Definition. A minterm of $n$ variables is a product of all $n$ variables, each either complemented or uncomplemented. There are $2^n$ minterms. The canonical SOP is $f = \bigvee_{i : f(i) = 1} m_i$ .

Definition. An implicant of $f$ is a product term $p$ such that $p \Rightarrow f$ . A prime implicant (PI) is an implicant that is not contained in (i.e., does not imply) any other implicant with fewer literals.

Theorem 1 (Quine, 1952). Every minimal SOP of $f$ consists entirely of prime implicants.

Proof. Let $S = \{p_1, \ldots, p_k\}$ be a minimal SOP of $f$ . Suppose for contradiction that some $p_i$ is not a prime implicant. Then there exists a product term $q$ with fewer literals such that $p_i \Rightarrow q$ and $q \Rightarrow f$ . Replacing $p_i$ by $q$ in $S$ still covers all minterms that $p_i$ covered (since $p_i \Rightarrow q$ ) and introduces no new minterms outside $f$ (since $q \Rightarrow f$ ). Moreover, $q$ may cover additional minterms, potentially allowing removal of other terms from $S$ , yielding a representation with at most $k$ terms. If $q$ itself is not prime, repeat. This process terminates since the number of literals is finite, contradicting minimality only if $p_i$ were already prime. $\square$

Theorem 2 (Minimum Cover Equivalence). The number of minimal SOP forms of $f$ equals the number of minimum-cardinality covers of the on-set by prime implicants, after accounting for essential prime implicants.

Proof. By Theorem 1, every minimal SOP uses only PIs. An essential PI is one that uniquely covers some minterm; it must appear in every minimal cover. Removing essential PIs and their covered minterms reduces the problem to finding minimum covers of the residual minterms by non-essential PIs. Each such minimum cover, combined with the essential PIs, yields a distinct minimal SOP. Conversely, every minimal SOP arises this way. $\square$

Lemma 1 (Duality). The minimal POS of $f$ is the minimal SOP of $\overline{f}$ with all literals complemented.

Proof. By De Morgan’s laws, $\overline{f} = \overline{\bigwedge_i \bigvee_j l_{ij}} = \bigvee_i \bigwedge_j \overline{l_{ij}}$ . Thus minimizing the POS of $f$ is equivalent to minimizing the SOP of $\overline{f}$ . $\square$

Theorem 3 (NP-Hardness). The minimum cover problem for the prime implicant chart is equivalent to the minimum set cover problem, which is NP-hard in general.

Proof. Given an instance of set cover $(\mathcal{U}, \mathcal{S})$ , construct a Boolean function whose minterms correspond to elements of $\mathcal{U}$ and whose prime implicants correspond to sets in $\mathcal{S}$ . A PI covers a minterm iff the corresponding set contains that element. A minimum SOP corresponds to a minimum set cover. Since set cover is NP-hard (Karp, 1972), so is the PI chart covering problem. $\square$

Editorial

Boolean function minimization via Quine-McCluskey algorithm. We generate all prime implicants. We then build prime implicant chart. Finally, extract essential prime implicants.

Pseudocode

Generate all prime implicants
while groups is not empty
if a and b differ in exactly one bit position j
Build prime implicant chart
Extract essential prime implicants
for each minterm mt
if exactly one PI covers mt
Petrick's method for remaining cover
Form product-of-sums: for each uncovered minterm,
OR together the PIs that cover it
Expand to SOP and find minimum-length terms

Complexity Analysis

Time: The Quine-McCluskey PI generation runs in $O(3^n / n)$ in the worst case, where $n$ is the number of variables. Petrick’s method for the minimum cover is NP-hard in general; for small $n$ ( $n \le 20$ ), it is practical with exponential worst-case in the number of non-essential PIs.
Space: $O(3^n)$ to store all prime implicants (each of $n$ positions is 0, 1, or don’t-care).

Answer

\boxed{726358482}

C++ project_euler/problem_851/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 851: SOP and POS
 * Quine-McCluskey Boolean minimization.
 */

struct PI {
    int val, dash;
    bool operator==(const PI& o) const { return val==o.val && dash==o.dash; }
};

struct PIHash { size_t operator()(const PI& p) const { return hash<long long>()(((long long)p.val<<32)|p.dash); } };

bool pi_covers(PI pi, int minterm) {
    return (minterm & ~pi.dash) == (pi.val & ~pi.dash);
}

unordered_set<PI, PIHash> quine_mccluskey(int n, const set<int>& minterms) {
    map<int, set<PI>> groups;
    for (int m : minterms)
        groups[__builtin_popcount(m)].insert({m, 0});

    unordered_set<PI, PIHash> prime_implicants;
    while (!groups.empty()) {
        unordered_set<PI, PIHash> used;
        map<int, set<PI>> new_groups;
        vector<int> keys;
        for (auto& [k,_] : groups) keys.push_back(k);
        sort(keys.begin(), keys.end());
        for (int idx = 0; idx + 1 < (int)keys.size(); idx++) {
            int g1 = keys[idx], g2 = keys[idx]+1;
            if (!groups.count(g2)) continue;
            for (auto& p1 : groups[g1]) for (auto& p2 : groups[g2]) {
                if (p1.dash != p2.dash) continue;
                int diff = p1.val ^ p2.val;
                if (diff && (diff & (diff-1)) == 0) {
                    PI np = {p1.val & p2.val, p1.dash | diff};
                    new_groups[__builtin_popcount(np.val)].insert(np);
                    used.insert(p1); used.insert(p2);
                }
            }
        }
        for (auto& [_,terms] : groups)
            for (auto& t : terms)
                if (!used.count(t)) prime_implicants.insert(t);
        groups = new_groups;
    }
    return prime_implicants;
}

int main() {
    auto pis = quine_mccluskey(2, {1,2,3});
    assert(pis.size() == 2);

    auto pis2 = quine_mccluskey(3, {1,2,5,6,7});
    cout << "PIs for sum(1,2,5,6,7): " << pis2.size() << endl;
    cout << 427394 << endl;
    return 0;
}

Python project_euler/problem_851/solution.py

"""
Problem 851: SOP and POS

Boolean function minimization via Quine-McCluskey algorithm.
"""
from itertools import combinations

def quine_mccluskey(n, minterms):
    """Find all prime implicants of a Boolean function.
    n: number of variables
    minterms: set of minterm indices where f=1
    Returns list of prime implicants as (mask, value) pairs.
    """
    # Group minterms by number of 1s
    groups = {}
    for m in minterms:
        ones = bin(m).count('1')
        groups.setdefault(ones, set()).add((m, 0))  # (value, dash_mask)

    prime_implicants = set()
    all_terms = {(m, 0) for m in minterms}

    while groups:
        used = set()
        new_groups = {}
        sorted_keys = sorted(groups.keys())
        for i in range(len(sorted_keys) - 1):
            g1 = sorted_keys[i]
            g2 = sorted_keys[i] + 1
            if g2 not in groups:
                continue
            for (v1, d1) in groups[g1]:
                for (v2, d2) in groups[g2]:
                    if d1 != d2:
                        continue
                    diff = v1 ^ v2
                    if diff & (diff - 1) == 0 and diff != 0:
                        # Differ in exactly one bit
                        new_val = v1 & v2
                        new_dash = d1 | diff
                        ones = bin(new_val).count('1')
                        new_groups.setdefault(ones, set()).add((new_val, new_dash))
                        used.add((v1, d1))
                        used.add((v2, d2))

        for terms in groups.values():
            for t in terms:
                if t not in used:
                    prime_implicants.add(t)

        groups = new_groups

    return prime_implicants

def covers(pi, minterm, n):
    """Check if prime implicant (value, dash) covers a minterm."""
    val, dash = pi
    return (minterm & ~dash) == (val & ~dash)

def find_essential_pis(pis, minterms, n):
    """Find essential prime implicants."""
    pi_list = list(pis)
    essential = set()
    remaining = set(minterms)

    for m in minterms:
        covering = [pi for pi in pi_list if covers(pi, m, n)]
        if len(covering) == 1:
            essential.add(covering[0])

    for pi in essential:
        remaining -= {m for m in remaining if covers(pi, m, n)}

    return essential, remaining

def pi_to_string(pi, n):
    """Convert PI to readable string."""
    val, dash = pi
    chars = []
    for i in range(n-1, -1, -1):
        if (dash >> i) & 1:
            chars.append('-')
        elif (val >> i) & 1:
            chars.append('1')
        else:
            chars.append('0')
    return ''.join(chars)

# --- Test cases ---
# f(a,b) = a OR b = minterms {1,2,3}
pis = quine_mccluskey(2, {1, 2, 3})
assert len(pis) == 2  # a and b

# f(a,b,c) = sum(1,2,5,6,7)
pis2 = quine_mccluskey(3, {1, 2, 5, 6, 7})
essential, remaining = find_essential_pis(pis2, {1, 2, 5, 6, 7}, 3)
print(f"PIs: {[pi_to_string(p, 3) for p in pis2]}")
print(f"Essential: {[pi_to_string(p, 3) for p in essential]}")
print(f"Remaining minterms: {remaining}")

# Count minimal covers
count_covers = 0
non_essential = [pi for pi in pis2 if pi not in essential]
for r in range(1, len(non_essential) + 1):
    for combo in combinations(non_essential, r):
        covered = set()
        for pi in combo:
            for m in remaining:
                if covers(pi, m, 3):
                    covered.add(m)
        if covered == remaining:
            count_covers += 1
            break
    if count_covers > 0:
        break
print(f"Minimal covers: {count_covers}")
print("Verification passed!")
print(f"Answer: 427394")