A393145 - OEIS

%I #31 Mar 05 2026 11:17:31

%S 1,3,7,15,26,43,65,95,132,179,235,303,382,475,581,703,840,995,1167,

%T 1359,1570,1803,2057,2335,2636,2963,3315,3695,4102,4539,5005,5503,

%U 6032,6595,7191,7823,8490,9195,9937,10719,11540,12403,13307,14255,15246,16283,17365,18495,19672,20899,22175,23503,24882,26315

%N Minimal voucher cost for n distinct positive integer vouchers v_1, v_2, ..., v_n, where the cost is defined as v_1 + v_1*v_2 + v_2*v_3 + ... + v_(n-1)*v_n.

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

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

%H Paolo Xausa, <a href="/A393145/b393145.txt">Table of n, a(n) for n = 1..10000</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-2,3,-1).

%F a(n) = n*(n^2+8)/6 - (15 - 3*(-1)^n)/12, for n > 1.

%F a(n) = A026035(n) + n - 1, for n > 1.

%F a(n) = A110611(n-1) + n, for n > 1.

%F G.f.: x*(1 + 2*x^3 - 2*x^4 + x^5)/((1 - x)^4*(1 + x)). - _Stefano Spezia_, Feb 20 2026

%F From _Enrique Navarrete_, Feb 25 2026: (Start)

%F For n>1, a(n) = (n^3 + 8*n - 6)/6, n even; a(n) = (n^3 + 8*n - 9)/6, n odd.

%F For n>6, a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5).

%F E.g.f.: 1 + x + (1/12)*((2*x^3 + 6*x^2 + 18*x - 15)*exp(x) + 3*exp(-x)). (End)

%e For n=4, we buy 4 vouchers in the following order 3,2,1,4. The cost is 3+3*2+2*1+1*4=15, which is the smallest possible cost. For contrast, if we buy the vouchers in order 1,2,3,4, the cost is 1+1*2+2*3+3*4 = 21, which is larger. Thus, a(4)=15.

%t A393145[n_] := If[n == 1, 1, n*(n^2+8)/6 + ((-1)^n-5)/4]; Array[A393145, 60] (* or *)

%t LinearRecurrence[{3, -2, -2, 3, -1}, {1, 3, 7, 15, 26, 43}, 60] (* _Paolo Xausa_, Mar 03 2026 *)

%o (PARI) a(n)= (n^3 + 8*n - n%2*3)/6 - (n>1) \\ _Ruud H.G. van Tol_, Mar 03 2026

%Y Cf. A026035, A101986, A110610, A110611.

%K nonn,easy

%O 1,2

%A _Tanya Khovanova_ and PRIMES STEP junior group, Feb 02 2026