A054404 -id:A054404 - cp's OEIS frontend

A245771 Decimal expansion of 'b', an optimal stopping constant associated with the secretary problem when the objective is to maximize the hiree's expected quality.

1, 7, 6, 7, 9, 9, 3, 7, 8, 6, 1, 3, 6, 1, 5, 4, 0, 5, 0, 4, 4, 3, 6, 3, 4, 4, 0, 6, 7, 8, 1, 1, 3, 2, 3, 3, 1, 0, 7, 7, 6, 8, 1, 4, 3, 3, 1, 3, 1, 9, 5, 6, 5, 1, 5, 5, 7, 6, 9, 8, 6, 0, 5, 9, 6, 2, 6, 0, 0, 0, 7, 6, 4, 6, 0, 6, 3, 8, 7, 5, 1, 4, 4, 4, 4, 8, 1, 6, 5, 1, 6, 3, 2, 5, 6, 8, 2, 5, 0

Offset: 1

Jean-François Alcover, Aug 01 2014

			1.767993786136154050443634406781132331077681433131956515576986059626...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.15, p. 362.

Steven Finch, A Deceptively Simple Quadratic Recurrence, arXiv:2409.03510 [math.NT], 2024.
Steven Finch, Exercises in Iterational Asymptotics, arXiv:2411.16062 [math.NT], 2024. See p. 9.
Steven Finch, Half-Iterates of x(1+x), sin(x) and exp(x/e), arXiv:2506.07625 [math.NT], 2025. See p. 4.
Jon E. Schoenfield, Magma program communicated to J.-F. Alcover.
Eric Weisstein's MathWorld, Sultan's Dowry Problem.
Wikipedia, Secretary problem.

Cf. A054404, A242672, A242673, A242674, A243533.

// See the link to Jon E. Schoenfield's program.

nmax = 10^10; dn = 10^6; db = 2*10^-16; b0 = p = 3; q = 10/3; b = q - Log[2]; f = Compile[{n, p, q}, (p*((p-5)*p + 8) + n*(n*p + (2*p-5)*p + 2) + q - 5)/((p-5)*p + n*(n + 2*p - 5) + 7)]; For[n = 3, n <= nmax, n++, If[Divisible[n, dn], b0 = b]; r = f[n, p, q]; b = r - Log[n]; p = q; q = r; If[Divisible[n, dn], Print["n = ", n, " b = ", b]; If[Abs[b - b0] < db, Break[]]]]; RealDigits[b] // First

Q(0) = 0, Q(n) = (1/2)*(1+Q(n-1)^2), Q(n) ~ 1-2/(n+log(n)+b) when n -> infinity.

Extended to 99 digits using Jon E. Schoenfield's evaluation, Sep 05 2016

A282025 a(r) is the maximum number of secretaries for which the first r should be rejected, if selecting the one with the highest or lowest ranking are both considered a success.

Original entry on oeis.org

3, 8, 13, 18, 23, 27, 32, 37, 42, 47, 52, 57, 62, 67, 72, 77, 82, 86, 91, 96, 101, 106, 111, 116, 121, 126, 131, 136, 141, 146, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195, 200, 205, 210, 214, 219, 224, 229, 234, 239, 244, 249, 254, 259, 264, 269, 273, 278, 283

Offset: 0

N. J. A. Sloane, Feb 11 2017

nonn

According to Bayon et al, the probability P(n,r) = 2*r*((r/n-1)+sum_{i=r..n-1} 1/i)/n of success in a generalized Secretary problem for a given number n of applicants has a maximum at some value of r, 1<=r

The Beatty sequence of A106533, b(n) = floor(n*A106533), is a good approximation to r for large n. So the indices n-1 of the steps where b(n) = b(n+1)-1 are an approximation to this sequence.

We added numbers 27, 86 and 91 that are apparently missing in the preprint. R. J. Mathar, Feb 22 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..202
L. Bayon, J. Grau, A. M. Oller-Marcen, M. Ruiz, P. M. Suarez, A variant of the Secretary Problem: the Best or the Worst, arXiv preprint arXiv:1603.03928 [math.PR], 2016.

Cf. A106533, A054404.

P := proc(n,
    option remember;
    local i;
    2*r/n*((r/n-1)+add(1/i,i=r..n-1)) ;
end proc:
Pmax := proc(n)
    option remember;
    local r;
    for r from 1 to n-1 do
        if P(n,r+1) < P(n,r) then
            return r ;
        end if;
    end do:
end proc:
A282025 := proc(r)
    local n ;
    if r = 0 then
        return 3;
    end if;
    for n from r+1 do
        if Pmax(n+1) = r+1 then
            return n;
        end if;
    end do:
    return -1 ;
end proc:
seq(A282025(r),r=0..80) ; # R. J. Mathar, Feb 22 2017

P[n_, r_] := 2 r ((r/n - 1) + Sum[ 1/i, {i, r, n - 1}])/n; Function[s, {3}~Join~Map[-1 + Position[s, #][[1, 1]] &, Range@ Max@ s]]@ Map[Length@ TakeWhile[#, # == 0 &] &, Table[If[P[n, k + 1] < P[n, k], k, 0], {n, 300}, {k, n - 1}]] (* Michael De Vlieger, Feb 22 2017, after Maple *)

A226046 Number of daughters to wait before picking in sultan's dowry problem with an unknown number of daughters between 1 and n with equal probability.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11

Offset: 1

José María Grau Ribas, May 24 2013

nonn

Cf. A054404.

PR[n_, r_] := Sum[r/((k - 1)i n), {i, 1, n}, {k, r + 1, i}]; 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}]

A330250 Unreduced numerator of expected rank of applicant in average rank secretary problem.

Original entry on oeis.org

1, 3, 10, 45, 246, 1596, 11472, 96768, 905760, 9282240, 104328000, 1285502400, 17030200320, 242650598400, 3685666037760, 60059908823040, 1032474885120000, 18781151090688000, 360710540426880000, 7302919022138880000, 154603891182698496000, 3423234952360194048000

Offset: 1

Seth A. Troisi, Dec 06 2019

a(n) is the numerator of the expected rank of applicant in the secretary problem when minimizing average rank, the denominator is n!.
Lim_{n -> infinity} a(n)/n! = A242672 = 3.8695...
a(n) can be calculated in linear time by recursively backtracking, the expected value of not selecting the j-th best candidate, seen so far, at step i.

			For a(3) = 10 the optimal strategy is to never accept the 1st applicant, accept the 2nd applicant if there are better (lower ranked) than the 1st applicant otherwise accept the 3rd applicant. This strategy selects the rank 1 applicant when the applicants are ordered 213, 231, 312 the rank 2 applicant from orderings 132, 321 and the rank 3 applicant from ordering 123. The numerator of the average rank is thus 1+1+1+2+2+3 = 10.
a(10)/10! = 3223/1260 = 2.558.

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.15, p. 362.

Y. S. Chow, S. Moriguti, H. Robbins, and S. M. Samuels, Optimal selection based on relative rank (the “secretary problem”), Israel J. Math. 2, 81-90 (1964).
Thomas S. Ferguson, Optimal Stopping and Applications
Eric Weisstein's MathWorld, Sultan's Dowry Problem.
Wikipedia, Secretary problem.

Cf. A054404, A242672.

function a(n)
    r, c = BigInt(n), BigInt(n + 1) // 2
    for i = n-1:-1:1
        q = (i + 1) // (n + 1)
        s = floor(q * c)
        k = (i - s) * c + (s * (s + 1)) // (2 * q)
        c = k // i
        r *= i
    end
numerator(r * c) end
[a(n) for n in 1:22] |> println # Peter Luschny, Jan 05 2020

Table[ci = (n + 1)/2; Do[ratio = (i + 1)/(n + 1); si = Floor[ratio*ci]; ci = 1/i*(1/ratio*(si*(si + 1)/2) + (i - si)*ci);, {i, n-1, 1, -1}];  Numerator[ci*n!], {n, 1, 25}] (* Vaclav Kotesovec, Jan 04 2020 *)

a(n) = {my(ci = (n+1)/2, r, si); forstep(i=n-1, 1, -1, r = (i+1)/(n+1); si = floor(r*ci); ci = ((si * (si + 1)/(2*r) + (i - si) * ci )/i);); numerator(ci*n!);}
for(n=1, 20, print1(a(n), ", ")) \\ Michel Marcus and Vaclav Kotesovec, Jan 04 2020

from fractions import Fraction
from math import factorial
def a(n):
  c_i = Fraction(n + 1, 2)
  for i in reversed(range(1, n)):
    ratio = Fraction(i+1, n+1)
    s_i = int( ratio * c_i )
    c_i = Fraction( (s_i * (s_i + 1) // 2) / ratio + (i - s_i) * c_i, i)
  return (c_i*factorial(n)).numerator
for n in range(1, 20):
    print(a(n))

Previous Showing 11-14 of 14 results.

cp's OEIS Frontend

A245771 Decimal expansion of 'b', an optimal stopping constant associated with the secretary problem when the objective is to maximize the hiree's expected quality.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A282025 a(r) is the maximum number of secretaries for which the first r should be rejected, if selecting the one with the highest or lowest ranking are both considered a success.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A226046 Number of daughters to wait before picking in sultan's dowry problem with an unknown number of daughters between 1 and n with equal probability.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A330250 Unreduced numerator of expected rank of applicant in average rank secretary problem.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

Mathematica

PARI

Python