Seth A. Troisi - cp's OEIS frontend

User: Seth A. Troisi

Seth A. Troisi has authored 2 sequences.

A359210 Number of m^k == 1 (mod p) for 0 < m,k < p where p is the n-th prime.

1, 3, 8, 15, 27, 40, 48, 63, 63, 104, 135, 168, 180, 195, 135, 200, 171, 360, 315, 351, 420, 375, 243, 420, 560, 520, 495, 315, 648, 624, 819, 675, 660, 675, 584, 975, 1000, 891, 495, 680, 531, 1512, 999, 1280, 1064, 1323, 1755, 1095, 675, 1480, 1140, 1287

Offset: 1

Seth A. Troisi, Dec 20 2022

nonn

a(n) is the sum of (p-1) / order(m, p) for all m in Zp for the n-th prime.

			For n=3 the a(3) = 8 numbers with m^k == 1 (mod 5) (the third prime) are (1,1), (1,2), (1,3), (1,4), (2,4), (3,4), (4,2), (4,4).

Cf. A036391, A086145, A174842.

Table[Sum[(p - 1)/MultiplicativeOrder[m, p], {m, 1, p - 1}], {p, Prime[Range[20]]}]

a(n)= my(p=prime(n)); sum(m=1,p-1,(p-1)/znorder(Mod(m,p)))

import sympy
print([sum((p-1) // sympy.ntheory.n_order(m, p) for m in range(1, p)) for p in sympy.primerange(100)])

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))

cp's OEIS Frontend

User: Seth A. Troisi

A359210 Number of m^k == 1 (mod p) for 0 < m,k < p where p is the n-th prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python