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

1, 3, 8, 22, 52, 128, 288, 672, 1472, 3328, 7168, 15872, 33792, 73728, 155648, 335872, 704512, 1507328, 3145728, 6684672, 13893632, 29360128, 60817408, 127926272, 264241152, 553648128, 1140850688, 2382364672, 4898947072, 10200547328, 20937965568, 43486543872

Offset

1,2

Comments

The question originated from a 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

Table of n, a(n) for n=1..32.

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

Formula

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

a(2n-1) = 2*A229278(n).

G.f.: x*(2*x^3-2*x^2+x+1)/((2*x+1)*(2*x-1)^2).

Example

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

Mathematica

a[1]=1; a[n_]:=2^(n-5)*(10*n+3+(-1)^n); Array[a, 32]
(* Alternative: *)
{1}~Join~LinearRecurrence[{2, 4, -8}, {3, 8, 22}, 31]
(* Alternative: *)
Rest[CoefficientList[Series[x*(2*x^3-2*x^2+x+1)/((2*x+1)*(2*x-1)^2), {x, 0, 32}], x]] (* James C. McMahon, May 08 2026 *)

Crossrefs

Cf. A026035, A229278, A110610, A110611, A393145.

Sequence in context: A178525 A266187 A328002 * A202192 A027211 A027235

Adjacent sequences: A395764 A395765 A395766 * A395768 A395769 A395770

Keyword

nonn,easy

Author

Tanya Khovanova and PRIMES STEP junior group, May 05 2026

Status

approved