login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A166079 Given a row of n pay-phones, all initially unused, how many people can use the pay-phones, assuming (1) each always chooses one of the most distant pay-phones 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

Hsien-Kuei 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/wp-content/files/2016/12/aat-hhrr-1.pdf. Also 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

LINKS

Table of n, a(n) for n=1..78.

Randall Munroe, Urinal protocol vulnerability

FORMULA

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 06:59 EST 2019. Contains 319188 sequences. (Running on oeis4.)