Detailed mathematical approach

Problem Summary

For each positive integer \(n\), consider the poset of divisors of \(n\) ordered by divisibility. Let \(f(n)\) be the maximum possible size of an antichain in that poset. The implementations in this repository compute

$S(N)=\sum_{n=1}^{N} f(n)$

for \(N=10^8\). The key simplification is that \(f(n)\) can be read from the middle rank of the divisor lattice, and those middle-rank divisors can be counted by grouping integers according to \(\Omega(n)\), the total number of prime factors with multiplicity.

Mathematical Approach

Step 1: Rank the divisor lattice by \(\Omega\)

Write the prime factorization of \(n\) as

$n=\prod_{i=1}^{r} p_i^{e_i},\qquad \Omega(n)=e_1+\cdots+e_r.$

Every divisor of \(n\) has the form

$d=\prod_{i=1}^{r} p_i^{a_i},\qquad 0\le a_i\le e_i.$

If we rank divisors by the sum of their exponents, then the rank of \(d\) is exactly

$\operatorname{rank}(d)=a_1+\cdots+a_r=\Omega(d).$

Therefore the number of divisors of rank \(m\) is the coefficient of \(x^m\) in the generating polynomial

$P_n(x)=\prod_{i=1}^{r}(1+x+\cdots+x^{e_i}).$

Step 2: The largest antichain is a middle rank

Each factor \(1+x+\cdots+x^{e_i}\) is symmetric and unimodal, and the product of symmetric unimodal polynomials is again symmetric and unimodal. So the coefficient sequence of \(P_n(x)\) increases up to the middle and then decreases symmetrically.

The divisor lattice is a product of chains, so a classical Sperner-type result implies that its width equals the size of its largest rank. If \(t=\Omega(n)\), then the largest coefficient of \(P_n(x)\) occurs at the middle rank:

$f(n)=\#\{d\mid n:\Omega(d)=\lfloor t/2\rfloor\}.$

When \(t\) is odd, the ranks \((t-1)/2\) and \((t+1)/2\) have the same size by symmetry, so either middle rank can be used.

Step 3: Turn middle-rank divisors into ordered factor pairs

Fix a divisor \(d\mid n\) from the middle rank and write \(b=n/d\). Since exponents add,

$\Omega(d)+\Omega(b)=\Omega(n).$

If \(\Omega(n)=2k\), then every middle-rank divisor satisfies \(\Omega(d)=k\), hence also \(\Omega(b)=k\). Thus \(f(n)\) equals the number of ordered factorizations

$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k.$

If \(\Omega(n)=2k+1\), choose the lower middle rank. Then

$n=a b,\qquad \Omega(a)=k,\quad \Omega(b)=k+1.$

Summing over all \(n\le N\) gives a global counting identity:

$S(N)=\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k\}+\sum_{k\ge 0}\#\{(a,b):ab\le N,\ \Omega(a)=k,\ \Omega(b)=k+1\}.$

This is exactly what the code counts.

Step 4: Group integers by degree

Define

$G_k=\{m\le N:\Omega(m)=k\}.$

The smallest-prime-factor sieve provides the recurrence

$\Omega(1)=0,\qquad \Omega(i)=\Omega\!\left(\frac{i}{\operatorname{spf}(i)}\right)+1.$

Because the programs process integers in increasing order, every list \(G_k\) is already sorted. The formula above then becomes two kinds of pair counts for each \(k\): pairs inside \(G_k\), and pairs between \(G_k\) and \(G_{k+1}\).

Step 5: Two-pointer counting

For two sorted lists \(A\) and \(B\), we must count pairs \((a,b)\in A\times B\) satisfying \(ab\le N\). If we scan \(a\) from left to right, the largest valid index in \(B\) can only move left, never right. So one monotone two-pointer pass counts all valid pairs in \(O(|A|+|B|)\) time.

The implementations perform this scan once for \((G_k,G_k)\) and once for \((G_k,G_{k+1})\). Summing over all \(k\) produces \(S(N)\).

Worked Examples

For \(n=36=2^2\cdot 3^2\),

$P_{36}(x)=(1+x+x^2)^2=1+2x+3x^2+2x^3+x^4.$

The largest coefficient is \(3\), so \(f(36)=3\). The middle-rank divisors are \(4,6,9\), giving the ordered factorizations

$(4,9),\qquad (6,6),\qquad (9,4).$

All three have \(\Omega=2\) on both sides, matching the even case.

For \(n=12=2^2\cdot 3\),

$P_{12}(x)=(1+x+x^2)(1+x)=1+2x+2x^2+x^3.$

Now \(f(12)=2\), coming from the lower middle rank divisors \(2\) and \(3\), which correspond to

$(2,6),\qquad (3,4),$

with degree pattern \((1,2)\). This is the odd case counted between consecutive groups.

How the Code Works

The C++ and Python versions build an SPF table, compute \(\Omega(i)\) from the recurrence, and append each integer to by_degs[d]. The Java version first counts how many values fall into each degree, allocates exact arrays, and fills them in a second pass, which avoids list overhead.

All three implementations then run the same two-pointer loops. Since \(2^{26}\le 10^8<2^{27}\), the maximum possible value of \(\Omega(n)\) is \(26\), so the small fixed-size Java arrays are sufficient.

Complexity Analysis

Building the SPF sieve costs \(O(N\log\log N)\) time. Computing \(\Omega(i)\) and distributing integers into degree groups costs \(O(N)\). The total cost of all two-pointer scans is linear in the total size of the groups, so the overall running time remains \(O(N\log\log N)\). The memory usage is \(O(N)\) for the sieve, the degree array, and the grouped integers.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=386
2. Prime omega function: Wikipedia - Prime omega function
3. Antichain and Sperner-type background: Wikipedia - Sperner's theorem
4. Unimodal sequences: Wikipedia - Unimodality
5. Two-pointers technique: cp-algorithms - Two Pointers Method