A279685 The maximum number of coins that can be processed in n weighings of an adaptive strategy that all are real (and identical) except for one LHR-coin starting in an unknown state.

1, 1, 3, 6, 16, 39, 91, 216, 499, 1144, 2651, 6152, 14227, 32904, 76187, 176376, 408179, 944728, 2186779, 5061544, 11715219, 27116008, 62762971, 145270808, 336242675, 778266424, 1801373403, 4169451080, 9650594451, 22337231432, 51701672731

Offset: 0

Author

Tanya Khovanova and Konstantin Knop, Dec 16 2016

Keywords

• nonn
• easy

Comments

An LHR-coin is a coin that can change its weight periodically from light to heavy to real to light.

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Tanya Khovanova and Konstantin Knop, Coins that Change Their Weights, arXiv:1611.09201 [math.CO], 2016.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,5,-4).

Crossrefs

Cf. A279673, A279674, A279682, A279684.

Programs

PARI

Vec((1 - 2*x + 3*x^2 - 5*x^3 + 6*x^4 - 2*x^5 + 4*x^6 + 4*x^7 - 7*x^8 - 4*x^9) / ((1 - x)*(1 - 2*x + x^2 - 4*x^3)) + O(x^40)) \\ Colin Barker, Dec 17 2016

Formula

a(n) = (A279673(n-1) + 1)/2 + A279673(n-2), for n > 6.

From Colin Barker, Dec 17 2016: (Start)

a(n) = 3*a(n-1) - 3*a(n-2) + 5*a(n-3) - 4*a(n-4) for n>9.

G.f.: (1 - 2*x + 3*x^2 - 5*x^3 + 6*x^4 - 2*x^5 + 4*x^6 + 4*x^7 - 7*x^8 - 4*x^9) / ((1 - x)*(1 - 2*x + x^2 - 4*x^3)).

(End)