

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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


REFERENCES

HsienKuei Hwang, S Janson, TH 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; http://140.109.74.92/hk/wpcontent/files/2016/12/aathhrr1.pdf. Also Exact and Asymptotic Solutions of a DivideandConquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585


LINKS

Table of n, a(n) for n=1..78.
Randall Munroe, Urinal protocol vulnerability


FORMULA

a(n) = 1 + 2^floor(lg(n2)  1) + max(0, n  3/2 * 2^floor(lg(n2))  1)
A recurrence is: a(n) = a(m) + a(nm+1)  1, with a(1) = a(2) = 1 and a(3)=2, where m = ceiling(n/2).  John W. Layman, Feb 05 2011


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(n2)1)); max(t+1, ntt)
(PARI) a(n) = if(n<3, return(1)); my(L=logint(n2, 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: A135646 A301851 A101646 * A269381 A080677 A316628
Adjacent sequences: A166076 A166077 A166078 * A166080 A166081 A166082


KEYWORD

easy,nonn


AUTHOR

Charles R Greathouse IV, Oct 06 2009


STATUS

approved



