OFFSET
1,2
COMMENTS
a(n) is the least k such that A330858(n,k) > n!/2.
For the "100 Prisoners Problem" with n participants using the loop (cycle) strategy, a(n) is the minimal number of choices per prisoner required for the overall survival probability to exceed 1/2, defining the critical survival threshold at which collective success becomes more likely than failure.
LINKS
Gergely Földvári, Illustrated analysis with first 100 terms.
Solomon W. Golomb, Peter Gaal, On the Number of Permutations on n Objects with Greatest Cycle Length k, Advances In Applied Mathematics, Volume 20, Issue 1, January 1998, Pages 98-107, for "probability that longest cycle has relative length >=1/2", pls. see p. 106.
Wikipedia, 100 prisoners problem.
FORMULA
a(n) = least k >= 1 such that [x^n] exp(Sum_{j=1..k} x^j/j) > 1/2, n >= 1.
EXAMPLE
a(1) = 1 because 1/1! = 1 = 100%, which already exceeds 1/2.
a(2) = 2 because 1/2! = 1/2 for k<=1; with k<=2, 2/2 = 1 > 1/2.
a(3) = 2 because 1/3! < 1/2 for k<=1; with k<=2, 4/6 > 1/2.
a(4) = 3 because 10/4! < 1/2 for k<=2; with k<=3, 15/24 > 1/2.
a(5) = 3 because, as a fraction of the total number of permutations (5!), the 26 possible permutations with cycle length k<=2 (involutions) still fall below the majority (>1/2) threshold (26/5!=26/120=13/60=0.21666... or 21.7%), whereas the number of possible permutations with cycle length k<=3 already rise above it (66/120=11/20=0.55 or 55%).
PROG
(Python)
from math import comb
# Dynamic integer factorials
factorials = [1] # factorials[n] = n!
def fact(n):
while len(factorials) <= n:
factorials.append(factorials[-1] * len(factorials))
return factorials[n]
# Correct A068424 factor for the recurrence
# A068424(n, k) = binomial(n, k) * k!
def A068424(n, k):
if k == 0:
return 0
return comb(n, k) * fact(k)
# Memoized function to calculate P(n, k) via single recurrence
def P(n, k, memo):
if k >= n:
return fact(n)
if n == 0:
return 1
if (n, k) in memo:
return memo[(n, k)]
# recurrence
result = n * P(n - 1, k, memo) - P(n - k - 1, k, memo) * A068424(n - 1, k)
memo[(n, k)] = result
return result
# Generator of sequence a(n)
def generate_a():
n = 1
memo = {}
while True:
nf = fact(n)
for k in range(1, n + 1):
if P(n, k, memo) > nf // 2: # exact integer comparison
yield k
break
n += 1
# Example: first 610 terms
gen = generate_a()
seq = [next(gen) for _ in range(610)]
print(seq)
CROSSREFS
KEYWORD
nonn
AUTHOR
Gergely Földvári, Sep 27 2025
STATUS
approved
