0%

Problem 538


Problem 538


Maximum quadrilaterals

Consider a positive integer sequence S=(s1,s2,…,sn).

Let f(S) be the perimeter of the maximum-area quadrilateral whose side lengths are 4 elements (si, sj, sk, sl) 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 un=2B(3n)+3B(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 u5=24+32+2=27.

Also, let Un be the sequence (u1,u2,…,un).
For example, U10=(8,9,14,9,27,16,36,9,27,28).

It can be shown that f(U5)=59, f(U10)=118, f(U150)=3223.
It can also be shown that Σf(Un)=234761 for 4≤n≤150.
Find Σf(Un) for 4≤n≤3000000.


最大四边形

考虑一个正整数序列S=(s1,s2,…,sn)。

在S中取4个元素(si, sj, sk, sl)(其中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。

令un=2B(3n)+3B(2n)+B(n+1),其中B(k)是数k的二进制表示中数字1的个数。
例如,B(6)=2,B(10)=2,B(15)=4,因此u5=24+32+2=27。

再令Un为数列(u1,u2,…,un)。
例如,U10=(8,9,14,9,27,16,36,9,27,28)。

已知f(U5)=59,f(U10)=118,f(U150)=3223。
还已知对于4≤n≤150有Σf(Un)=234761。
对于4≤n≤3000000,求Σf(Un)。