A394572 Minimal value of Sum_{i=1..n} p(i)*p((i mod n)+1), as p ranges over all permutations of powers of 2 {1,2,4,...,2^(n-1)}.

0, 1, 4, 14, 36, 96, 224, 544, 1216, 2816, 6144, 13824, 29696, 65536, 139264, 303104, 638976, 1376256, 2883584, 6160384, 12845056, 27262976, 56623104, 119537664, 247463936, 520093696, 1073741824, 2248146944, 4630511616, 9663676416, 19864223744, 41339060224, 84825604096, 176093659136, 360777252864, 747324309504, 1529008357376

Offset

0,3

Comments

The question originated from generalization of the first puzzle 'Low Budget' in the book Mathematical Puzzles and Curiosities.

References

I. David, T. Khovanova, and Y. Shpilman, Mathematical Puzzles and Curiosities, World Scientific, 2026, p.2.

Links

Paolo Xausa, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (2,4,-8).

Formula

a(n) = 2^(n-4)*(10*n - 3 - (-1)^n) for n>=1.

G.f.: x*(2*x^2+2*x+1)/((2*x+1)*(2*x-1)^2). - Alois P. Heinz, May 26 2026

Example

For n=4, one permutation that realizes the minimum value is 2,4,1,8. So a(4) = 2*4 + 4*1 + 1*8 + 8*2 = 36. Thus, a(4) = 36.

Mathematica

A394572[n_] := Ceiling[2^(n - 4)*(10*n - 3 - (-1)^n)];
Array[A394572, 50, 0] (* Paolo Xausa, Jun 08 2026 *)

Crossrefs

Cf. A026035, A076024, A080675, A110610, A110611, A136412, A395767, A395770.

Sequence in context: A332834 A128758 A341384 * A258343 A317148 A027166

Adjacent sequences: A394569 A394570 A394571 * A394573 A394574 A394575

Keyword

nonn,easy

Author

Tanya Khovanova and PRIMES STEP junior group, May 25 2026

Status

approved