Detailed mathematical approach

Problem Summary

The sequence is defined by

$u_n=2^{B(3n)}+3^{B(2n)}+B(n+1),$

where \(B(m)\) denotes the number of \(1\)-bits in the binary expansion of \(m\). For each prefix multiset \(\{u_1,\dots,u_n\}\) with \(n\ge4\), we choose four values \(a\le b\le c\le d\) and form the quadrilateral with maximum possible area from those side lengths. If several choices have the same maximal area, we keep the one with larger perimeter \(a+b+c+d\). Let \(f(n)\) be that perimeter. The task is to compute

$\sum_{n=4}^{3000000} f(n).$

Mathematical Approach

A brute-force search over all quadruples of every prefix is hopeless. The implementation works because the geometric score has a strong monotonicity property: once the largest side is fixed, the other three sides should be as large as possible. That turns the problem into maintaining only consecutive 4-blocks in the sorted prefix.

Step 1: Generate the sequence and state the optimization target

Write the sorted prefix as

$x_1\le x_2\le \cdots \le x_n.$

Any candidate for the prefix \(n\) is a quadruple

$x_i\le x_j\le x_k\le x_\ell,\qquad 1\le i<j<k<\ell\le n.$

Because the input is a multiset, equal values are allowed and must be counted with their multiplicities. The objective for each prefix is not merely to find a valid quadrilateral, but to find the valid quadrilateral whose area is maximal, using perimeter only as a tie-breaker.

Step 2: Replace area by an integer score

For sorted sides \(a\le b\le c\le d\), a non-degenerate quadrilateral exists exactly when

$d<a+b+c.$

Among all quadrilaterals with those four side lengths, the maximal area is attained by a cyclic quadrilateral. If

$s=\frac{a+b+c+d}{2},$

then Brahmagupta's formula gives

$A^2=(s-a)(s-b)(s-c)(s-d).$

Multiplying by \(16\) removes the fractions, so the implementations compare the integer score

$Q(a,b,c,d)= \begin{cases} (a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d), & d<a+b+c,\\ 0, & d\ge a+b+c. \end{cases}$

Since \(Q=16A^2\), maximizing area is equivalent to maximizing \(Q\). If two candidates have the same \(Q\), the larger perimeter

$P=a+b+c+d$

wins.

Step 3: For a fixed largest side, the best choice is a consecutive 4-block

Fix the largest chosen side \(d\). Inside the valid region \(d<a+b+c\), consider \(Q(a,b,c,d)\) while \(d\) is fixed. For example, with \(b,c,d\) fixed,

$\frac{\partial}{\partial a}\log Q =-\frac{1}{b+c+d-a} +\frac{1}{a-b+c+d} +\frac{1}{a+b-c+d} +\frac{1}{a+b+c-d}.$

Because \(a\le b\le c\le d\), each denominator in the positive terms is at most \(b+c+d-a\). Therefore the derivative is positive, so \(Q\) increases as \(a\) increases. The same one-line monotonicity check works for \(b\) and \(c\) as well.

So once the largest selected value is \(x_t\), the score is maximized by taking the three largest available predecessors:

$\bigl(x_{t-3},x_{t-2},x_{t-1},x_t\bigr).$

If even this consecutive block fails the inequality \(x_t<x_{t-3}+x_{t-2}+x_{t-1}\), then every other choice with largest side \(x_t\) also fails, because the sum of the other three sides can only get smaller. Hence every optimal candidate in a prefix is one of the consecutive sorted blocks

$\bigl(x_i,x_{i+1},x_{i+2},x_{i+3}\bigr),\qquad 1\le i\le n-3.$

Step 4: After one insertion, only four starts can be new

Suppose the next value is inserted into the sorted prefix at position \(p\) using \(0\)-based indexing. All consecutive 4-blocks that do not contain this new element are unchanged, so the previous best remains valid unless one of the new blocks beats it.

The only consecutive 4-blocks containing position \(p\) are those starting at

$s\in \{p-3,p-2,p-1,p\}\cap [0,n-4].$

Every one of those blocks lies inside the seven-element window

$[\max(0,p-3),\ \min(n-1,p+3)].$

Therefore each update needs only a constant-size neighborhood: extract that tiny sorted window, test at most four blocks, and compare them with the running global best.

Step 5: Worked example for \(n=5\)

The first five sequence values are

$u_1=8,\qquad u_2=9,\qquad u_3=14,\qquad u_4=9,\qquad u_5=27.$

So the sorted prefix is

$8,9,9,14,27.$

The consecutive candidates are \((8,9,9,14)\) and \((9,9,14,27)\).

For \((8,9,9,14)\),

$Q=12\cdot 22\cdot 22\cdot 24=139392,\qquad P=40.$

For \((9,9,14,27)\),

$Q=5\cdot 31\cdot 41\cdot 41=260555,\qquad P=59.$

So the second block wins, and therefore

$f(5)=59.$

This is exactly the kind of local comparison performed at each insertion.

How the Code Works

The C++, Python, and Java implementations first generate all values \(u_n\) up to \(N=3000000\). They precompute the small tables of powers of \(2\) and \(3\), because only the population counts vary from one index to the next.

Next, the implementations coordinate-compress all generated values. The sorted prefix multiset is then maintained by an order-statistics Fenwick tree over the compressed ranks. This supports three operations in logarithmic time: insert the next value, count how many current elements are strictly smaller, and recover the value at any requested sorted position.

After each insertion, the implementation finds the new sorted position \(p\), extracts the window from \(p-3\) to \(p+3\), evaluates the at most four consecutive 4-blocks that contain the new element, and updates the global best by comparing first the score \(Q\) and then the perimeter. The winning perimeter for the current prefix is added to the final sum.

The score \(Q\) is a product of four potentially large factors, so the implementations use sufficiently wide integer arithmetic when performing that comparison.

Complexity Analysis

Generating the sequence costs \(O(N)\). Coordinate compression requires sorting the generated values, so preprocessing costs \(O(N\log N)\) time. During the sweep, each Fenwick-tree insertion and each order-statistics query costs \(O(\log M)\), where \(M\) is the number of distinct sequence values, and only a constant number of candidate blocks are tested per prefix. Thus the overall running time is \(O(N\log N)\), and the memory usage is \(O(N)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=538
2. Brahmagupta's formula: Wikipedia — Brahmagupta's formula
3. Population count: Wikipedia — Hamming weight
4. Fenwick tree: cp-algorithms — Fenwick Tree