

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?


2



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


LINKS



FORMULA

a(n) = 1 + 2^floor(log_2(n2)  1) + max(0, n  (3/2) * 2^floor(log_2(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



KEYWORD

easy,nonn


AUTHOR



STATUS

approved



