

A054404


Number of daughters to wait before picking in sultan's dowry problem.


11



0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 26, 26, 26, 27, 27, 27
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

The correct rule can be found in the Gardner reference (p. 60) and in the Wikipedia article (see link): if the number of candidates is n, then the optimal r (the number of candidates to skip) is the r that maximizes (r/n)(1/r+1/(r+1)+...+1/(n1)).  Zvi Mendlowitz (zvi113(AT)zahav.net.il), Jul 12 2007


REFERENCES

M. Gardner, My Best Mathematical and Logic Puzzles, Dover, 1994


LINKS

R. J. Mathar, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Sultans Dowry Problem.
Wikipedia, Secretary problem.


FORMULA

a(n) = the integer r that maximizes (r/n)(1/r+1/(r+1)+...+1/(n1))  Zvi Mendlowitz (zvi113(AT)zahav.net.il), Jul 12 2007


MAPLE

A054404 := proc(n)
local r ;
r := 0 ;
sr := 0 ;
for s from 1 to n do
p := s/n*add(1/i, i=s..n1) ;
if p > sr then
r := s ;
sr := p ;
end if;
end do;
return r;
end proc: # R. J. Mathar, Jun 09 2013


MATHEMATICA

a[n_] := r /. Last[ Maximize[ {(r/n)*Sum[1/k, {k, r, n  1}], 0 <= r < n/2}, r, Integers]]; a[1] = 0; a[2] = 1; Table[a[n], {n, 1, 75}] (* JeanFrançois Alcover, Dec 13 2011, after Zvi Mendlowitz *)
(* The code above may not work in Mma 8 *)
PR[n_, r_] := (r/n)*Sum[1/k, {k, r, n  1}];
maxi[li_] := {Do[If[li[[n + 1]] <
li[[n]], aux = n; Break[]], {n, 1, Length[li]  1}], aux}[[2]];
SEQ[1] = 0; SEQ[2] = 1; SEQ[n_] := maxi[Table[PR[n, i], {i, 1, n  1}]];
Table[SEQ[n], {n, 1, 133}] (* José María Grau Ribas, May 11 2013 *)
a[1]=0; a[2]=1; a[n_] := Block[{r}, r /. Last@ Maximize[{(r/n) * (PolyGamma[0, n]  PolyGamma[0, r]), 1 <= r < n/2}, r, Integers]]; Array[a, 75] (* Giovanni Resta, May 11 2013 *)


CROSSREFS

Sequence in context: A077219 A026405 A226033 * A008671 A199017 A189709
Adjacent sequences: A054401 A054402 A054403 * A054405 A054406 A054407


KEYWORD

nonn


AUTHOR

Eric W. Weisstein


EXTENSIONS

Corrected by Zvi Mendlowitz (zvi113(AT)zahav.net.il), Jul 12 2007


STATUS

approved



