A007078 -id:A007078 - cp's OEIS frontend

A007077 Optimal cost of search tree for searching an ordered array of n elements with cost k of probing element k.

1, 4, 10, 19, 31, 47, 68, 92, 120, 153, 190, 232, 279, 332, 392, 454, 521, 593, 670, 753, 841, 936, 1036, 1141, 1252, 1370, 1494, 1625, 1763, 1909, 2063, 2216, 2376, 2542, 2713, 2890, 3074, 3264, 3460, 3663, 3872, 4088, 4310, 4540, 4776, 5021

Offset: 1

N. J. A. Sloane, Mira Bernstein

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. V. Connolly and W. J. Knight, Search in an array in which probe costs grow exponentially or factorially, Preprint. (Annotated scanned copy)
William J. Knight, Search in an ordered array having variable probe cost, SIAM J. Comput. 17 (1988), no. 6, 1203-1214.
W. J. Knight, Letter to N. J. A. Sloane, Jul. 1991
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A007078.

a(n) = m(n, 0) where m(0, d) = 0 and for n > 0, m(n, d) = min_{1 <= r <= n} {(r+d) * n + m(r-1, d) + m(n-r, r+d)} [from Knight]. - Sean A. Irvine, Oct 07 2017

More terms from Sean A. Irvine, Oct 07 2017

A280433 The mailbox manufacturer's problem, for the 2-mailbox case.

Original entry on oeis.org

1, 3, 5, 7, 10, 14, 17, 20, 23, 28, 33, 37, 41, 45, 50, 55, 60, 66, 73, 78, 84, 89, 94, 99, 105, 114, 121, 127, 134, 140, 147, 154, 161, 167, 173, 183, 190, 202, 210, 218, 225, 232, 240, 247, 254, 261, 268, 276, 290, 301, 310, 318, 327, 335, 343, 353, 362, 371, 380, 390, 399, 408, 417, 430, 443, 455, 466, 476, 485, 496, 506

Offset: 1

Christofer Ohlsson, Jan 03 2017

nonn

Given two identical mailboxes, each of which can hold up to n firecrackers, let M be the maximum number of firecrackers that can be simultaneously exploded in a mailbox without bursting it (and making it unusable for further testing). Assume that each mailbox can withstand an unlimited number of explosions of M or fewer firecrackers at a time. a(n) is the number of firecrackers needed to determine M, in the worst case, using an optimal strategy.
From Jon E. Schoenfield, Jan 11 2017: (Start)
As the number of mailboxes B increases without limit, the sequences appear to converge to A007078 (Optimal cost of search tree); the first 25 terms for cases B=1 (A000217), B=2 (this sequence), B=3 through B=6, and A007078 are as follows, where dots indicate a repeat of the value to the left:
.
   n | B=1 B=2 B=3 B=4 B=5 B=6  A007078
  ---+------------------------  -------
|   1  ..  ..  ..  ..  ..        1
|   3  ..  ..  ..  ..  ..        3
|   6   5  ..  ..  ..  ..        5
|  10   7  ..  ..  ..  ..        7
|  15  10   9  ..  ..  ..        9
|  21  14  12  ..  ..  ..       12
|  28  17  16  15  ..  ..       15
|  36  20  20  19  ..  ..       19
|  45  23  ..  ..  ..  ..       23
|  55  28  26  ..  ..  ..       26
|  66  33  29  ..  ..  ..       29
|  78  37  32  ..  ..  ..       32
|  91  41  35  ..  ..  ..       35
| 105  45  39  38  ..  ..       38
| 120  50  45  41  ..  ..       41
| 136  55  50  45  ..  ..       45
| 153  60  55  49  ..  ..       49
| 171  66  60  54  53  ..       53
| 190  73  65  61  57  ..       57
| 210  78  69  67  62  ..       62
| 231  84  73  ..  67  ..       67
| 253  89  77  ..  73  72       72
| 276  94  81  ..  ..  77       77
| 300  99  85  ..  ..  83       83
| 325 105  89  ..  ..  ..       89
(End)

			For n = 3, the optimal strategy uses 2 firecrackers for the first test, and in the worst case, the mailbox holds up and we need to try 3 firecrackers, for a(3) = 2 + 3 = 5 in total.
For n = 6, the optimal strategy uses 3 firecrackers for the first test. In the worst case, the mailbox holds up and we try a second test with 5. Again, the worst case is that the mailbox withstands the test, so the third test uses 6, for a final sum of a(6) = 3 + 5 + 6 = 14.

Joerg Arndt, Table of n, a(n) for n = 1..9999
Kattis, The Mailbox Manufacturers Problem, from Norwegian/Swedish Championships 2002.

Cf. A000217, A007078, A180975.

seen = {}
def solve(start, end, boxes):
    tup = (start, end, boxes)
    if boxes == 1 or start >= end-1:
        val = (start + end) * (end-start+1) // 2
        seen[tup] = val
        return val
    lowest = 100000000000000000
    for x in range(end-1, start, -1):
        firstup = (x+1, end, boxes)
        first = seen[firstup] if firstup in seen else solve(x+1, end, boxes)
        if first >= lowest:
            break
        secondtup = (start, x-1, boxes-1)
        second = seen[secondtup] if secondtup in seen else solve(start, x-1, boxes-1)
        if second >= lowest:
            break
        lowest = min(lowest, x + max(first, second))
    seen[tup] = lowest
    return lowest
print([solve(1, n, 2) for n in range(1, 40)])

From Jon E. Schoenfield, Jan 10 2017: (Start)
Let f(L,U,B) be the number of firecrackers needed to determine M (in the worst case, using an optimal strategy), given that M is known to be in the closed interval [L, U] and B mailboxes remain available for testing. Then if B=1, we must sequentially test each integer number k of firecrackers from L+1 upward until the mailbox fails (since a failure will destroy our only remaining mailbox), and in the worst case (largest total number of firecrackers used) we will use L+1 + L+2 + ... + U firecrackers, so
   f(L,U,1) = Sum_{k=L+1..U} k = (L+1+U)*(U-L)/2.
For B >= 2 and U > L, we have
   f(L,U,B) = min_{k=L+1..U} (k + max(f(k,U,B), f(L,k-1,B-1)))
(where the minimum gives the best strategy (minimizing the total number of firecrackers needed), and max(f(k,U,B), f(L,k-1,B-1)) is the worst-case result from the outcomes of mailbox success and failure at a k-firecracker test)
and when L=U, we have
   f(L,U,B) = 0 (since M has been determined).
Using the above recursive formula, we can compute
   a(n) = f(0,n,2). (End)
It looks as though lim_{n->inf} a(n)/n^(3/2) = 0.818... - Jon E. Schoenfield, Jan 12 2017

More terms from Joerg Arndt, Jan 11 2017

cp's OEIS Frontend

A007077 Optimal cost of search tree for searching an ordered array of n elements with cost k of probing element k.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A280433 The mailbox manufacturer's problem, for the 2-mailbox case.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions