This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A280433 #47 Nov 13 2024 16:41:40
%S A280433 1,3,5,7,10,14,17,20,23,28,33,37,41,45,50,55,60,66,73,78,84,89,94,99,
%T A280433 105,114,121,127,134,140,147,154,161,167,173,183,190,202,210,218,225,
%U A280433 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
%N A280433 The mailbox manufacturer's problem, for the 2-mailbox case.
%C A280433 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.
%C A280433 From _Jon E. Schoenfield_, Jan 11 2017: (Start)
%C A280433 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:
%C A280433 .
%C A280433 n | B=1 B=2 B=3 B=4 B=5 B=6 A007078
%C A280433 ---+------------------------ -------
%C A280433 1 | 1 .. .. .. .. .. 1
%C A280433 2 | 3 .. .. .. .. .. 3
%C A280433 3 | 6 5 .. .. .. .. 5
%C A280433 4 | 10 7 .. .. .. .. 7
%C A280433 5 | 15 10 9 .. .. .. 9
%C A280433 6 | 21 14 12 .. .. .. 12
%C A280433 7 | 28 17 16 15 .. .. 15
%C A280433 8 | 36 20 20 19 .. .. 19
%C A280433 9 | 45 23 .. .. .. .. 23
%C A280433 10 | 55 28 26 .. .. .. 26
%C A280433 11 | 66 33 29 .. .. .. 29
%C A280433 12 | 78 37 32 .. .. .. 32
%C A280433 13 | 91 41 35 .. .. .. 35
%C A280433 14 | 105 45 39 38 .. .. 38
%C A280433 15 | 120 50 45 41 .. .. 41
%C A280433 16 | 136 55 50 45 .. .. 45
%C A280433 17 | 153 60 55 49 .. .. 49
%C A280433 18 | 171 66 60 54 53 .. 53
%C A280433 19 | 190 73 65 61 57 .. 57
%C A280433 20 | 210 78 69 67 62 .. 62
%C A280433 21 | 231 84 73 .. 67 .. 67
%C A280433 22 | 253 89 77 .. 73 72 72
%C A280433 23 | 276 94 81 .. .. 77 77
%C A280433 24 | 300 99 85 .. .. 83 83
%C A280433 25 | 325 105 89 .. .. .. 89
%C A280433 (End)
%H A280433 Joerg Arndt, <a href="/A280433/b280433.txt">Table of n, a(n) for n = 1..9999</a>
%H A280433 Kattis, <a href="https://open.kattis.com/problems/mailbox">The Mailbox Manufacturers Problem</a>, from Norwegian/Swedish Championships 2002.
%F A280433 From _Jon E. Schoenfield_, Jan 10 2017: (Start)
%F A280433 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 A280433 f(L,U,1) = Sum_{k=L+1..U} k = (L+1+U)*(U-L)/2.
%F A280433 For B >= 2 and U > L, we have
%F A280433 f(L,U,B) = min_{k=L+1..U} (k + max(f(k,U,B), f(L,k-1,B-1)))
%F A280433 (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)
%F A280433 and when L=U, we have
%F A280433 f(L,U,B) = 0 (since M has been determined).
%F A280433 Using the above recursive formula, we can compute
%F A280433 a(n) = f(0,n,2). (End)
%F A280433 It looks as though lim_{n->inf} a(n)/n^(3/2) = 0.818... - _Jon E. Schoenfield_, Jan 12 2017
%e A280433 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.
%e A280433 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.
%o A280433 (Python)
%o A280433 seen = {}
%o A280433 def solve(start, end, boxes):
%o A280433 tup = (start, end, boxes)
%o A280433 if boxes == 1 or start >= end-1:
%o A280433 val = (start + end) * (end-start+1) // 2
%o A280433 seen[tup] = val
%o A280433 return val
%o A280433 lowest = 100000000000000000
%o A280433 for x in range(end-1, start, -1):
%o A280433 firstup = (x+1, end, boxes)
%o A280433 first = seen[firstup] if firstup in seen else solve(x+1, end, boxes)
%o A280433 if first >= lowest:
%o A280433 break
%o A280433 secondtup = (start, x-1, boxes-1)
%o A280433 second = seen[secondtup] if secondtup in seen else solve(start, x-1, boxes-1)
%o A280433 if second >= lowest:
%o A280433 break
%o A280433 lowest = min(lowest, x + max(first, second))
%o A280433 seen[tup] = lowest
%o A280433 return lowest
%o A280433 print([solve(1, n, 2) for n in range(1, 40)])
%Y A280433 Cf. A000217, A007078, A180975.
%K A280433 nonn
%O A280433 1,2
%A A280433 _Christofer Ohlsson_, Jan 03 2017
%E A280433 More terms from _Joerg Arndt_, Jan 11 2017