A166079 Given a row of n payphones, all initially unused, how many people can use the payphones, assuming (1) each always chooses one of the most distant payphones from those in use already, (2) the first person takes a phone at the end, and (3) no people use adjacent phones?

1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33

Offset

1,3

Links

Julian Zbigniew Kuryllowicz-Kazmierczak, Table of n, a(n) for n = 1..20000

H.-K. Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications. Preprint, 2016.

H.-K. Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications. ACM Transactions on Algorithms, 13:4 (2017), #47. DOI:10.1145/3127585

Randall Munroe, Urinal protocol vulnerability

Simon Wundling, About a combinatorial problem with n seats and n people, arXiv:2303.18175 [math.CO], 2023. (German)

Formula

a(n) = 1 + 2^floor(log_2(n-2) - 1) + max(0, n - (3/2) * 2^floor(log_2(n-2)) - 1).

A recurrence is: a(n) = a(m) + a(n-m+1) - 1, with a(1) = a(2) = 1 and a(3)=2, where m = ceiling(n/2). - John W. Layman, Feb 05 2011

a(n) = n - b(n,1) (see A095236 for definition and calculation of b(n,1)). - Simon Wundling, May 21 2023

Example

From Julian Zbigniew Kuryllowicz-Kazmierczak, Feb 20 2024: (Start)
a(8)=4:
1st person takes payphone at the end:           .......1
2nd person takes most distant, the 1st:         2......1
3rd person takes 4th or 5th payphone:           2..3...1  or  2...3..1
4th person must take 6th or 3rd, respectively:  2..3.4.1  or  2.4.3..1
Now each payphone is in use or adjacent to one in use, so a(8)=4.
(End)

Prog

(PARI) A000523(n)=my(t=floor(sizedigit(n)*3.32192809)-5); n>>=t; while(n>3, n>>=2; t+=2); if(n==1, t, t+1);
a(n)=my(t=1<<(A000523(n-2)-1)); max(t+1, n-t-t)
(PARI) a(n) = if(n<3, return(1)); my(L=logint(n-2, 2)-1); 1 + 2^L + max(0, n - 3*2^L - 1) \\ Charles R Greathouse IV, Jan 27 2016

Crossrefs

Cf. A095236, A095912, A095240.

Sequence in context: A334922 A301851 A101646 * A269381 A080677 A344497

Adjacent sequences: A166076 A166077 A166078 * A166080 A166081 A166082

Keyword

easy,nonn

Author

Charles R Greathouse IV, Oct 06 2009

Status

approved