Problem 538

Maximum quadrilaterals

Consider a positive integer sequence S=(s₁,s₂,…,s_n).

Let f(S) be the perimeter of the maximum-area quadrilateral whose side lengths are 4 elements (s_i, s_j, s_k, s_l) of S (all i, j, k, l distinct). If there are many quadrilaterals with the same maximum area, then choose the one with the largest perimeter.

For example, if S=(8,9,14,9,27), then we can take the elements (9,14,9,27) and form an isosceles trapezium with parallel side lengths 14 and 27 and both leg lengths 9. The area of this quadrilateral is 127.611470879… It can be shown that this is the largest area for any quadrilateral that can be formed using side lengths from S. Therefore, f(S)=9+14+9+27=59.

Let u_n=2^B(3n)+3^B(2n)+B(n+1), where B(k) is the number of 1 bits of k in base 2.
For example, B(6)=2, B(10)=2 and B(15)=4, and u₅=2⁴+3²+2=27.

Also, let U_n be the sequence (u₁,u₂,…,u_n).
For example, U₁₀=(8,9,14,9,27,16,36,9,27,28).

It can be shown that f(U₅)=59, f(U₁₀)=118, f(U₁₅₀)=3223.
It can also be shown that Σf(U_n)=234761 for 4≤n≤150.
Find Σf(U_n) for 4≤n≤3000000.

最大四边形

考虑一个正整数序列S=(s₁,s₂,…,s_n)。

在S中取4个元素(s_i, s_j, s_k, s_l)（其中i、j、k、l互不相同）构成四边形，记所有这样的四边形中面积最大的四边形的周长为f(S)。若面积最大的四边形有多个，则选择其中周长最长的一个。

举例而言，如果S=(8,9,14,9,27)，我们可以选择其中的元素(9,14,9,27)，组成一个等腰梯形 ，底边长为14和27，两腰长为9。这样一个四边形的面积是127.611470879… 通过计算可知这是所有使用S中元素作为边长构成的四边形的最大面积，因此f(S)=9+14+9+27=59。

令u_n=2^B(3n)+3^B(2n)+B(n+1)，其中B(k)是数k的二进制表示中数字1的个数。
例如，B(6)=2，B(10)=2，B(15)=4，因此u₅=2⁴+3²+2=27。

再令U_n为数列(u₁,u₂,…,u_n)。
例如，U₁₀=(8,9,14,9,27,16,36,9,27,28)。

已知f(U₅)=59，f(U₁₀)=118，f(U₁₅₀)=3223。
还已知对于4≤n≤150有Σf(U_n)=234761。
对于4≤n≤3000000，求Σf(U_n)。