cp's OEIS Frontend

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?

%I A166079 #58 Oct 05 2024 16:29:16
%S A166079 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,
%T A166079 16,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,18,19,20,21,22,
%U A166079 23,24,25,26,27,28,29,30,31,32,33,33,33,33,33,33,33,33,33,33,33,33,33,33
%N 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?
%H A166079 Julian Zbigniew Kuryllowicz-Kazmierczak, <a href="/A166079/b166079.txt">Table of n, a(n) for n = 1..20000</a>
%H A166079 H.-K. Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>. Preprint, 2016.
%H A166079 H.-K. Hwang, S. Janson, and T.-H. Tsai, <a href="http://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>. ACM Transactions on Algorithms, 13:4 (2017), #47. DOI:10.1145/3127585
%H A166079 Randall Munroe, <a href="http://blag.xkcd.com/2009/09/02/urinal-protocol-vulnerability/">Urinal protocol vulnerability</a>
%H A166079 Simon Wundling, <a href="https://arxiv.org/abs/2303.18175">About a combinatorial problem with n seats and n people</a>, arXiv:2303.18175 [math.CO], 2023. (German)
%F A166079 a(n) = 1 + 2^floor(log_2(n-2) - 1) + max(0, n - (3/2) * 2^floor(log_2(n-2)) - 1).
%F A166079 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
%F A166079 a(n) = n - b(n,1) (see A095236 for definition and calculation of b(n,1)). - _Simon Wundling_, May 21 2023
%e A166079 From _Julian Zbigniew Kuryllowicz-Kazmierczak_, Feb 20 2024: (Start)
%e A166079 a(8)=4:
%e A166079 1st person takes payphone at the end:           .......1
%e A166079 2nd person takes most distant, the 1st:         2......1
%e A166079 3rd person takes 4th or 5th payphone:           2..3...1  or  2...3..1
%e A166079 4th person must take 6th or 3rd, respectively:  2..3.4.1  or  2.4.3..1
%e A166079 Now each payphone is in use or adjacent to one in use, so a(8)=4.
%e A166079 (End)
%t A166079 a[n_]:= If[n<3,1,1 + 2^Floor[Log2[n-2] - 1] + Max[0, n - (3/2) * 2^Floor[Log2[n-2]]- 1]]; Array[a,78] (* _Stefano Spezia_, Oct 05 2024 *)
%o A166079 (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);
%o A166079 a(n)=my(t=1<<(A000523(n-2)-1)); max(t+1,n-t-t)
%o A166079 (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
%Y A166079 Cf. A095236, A095912, A095240.
%K A166079 easy,look,nonn
%O A166079 1,3
%A A166079 _Charles R Greathouse IV_, Oct 06 2009