A185456 Payphone packing sequence.

1, 3, 5, 8, 9, 14, 15, 16, 17, 26, 27, 28, 29, 30, 31, 32, 33, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124

Offset: 1

Author

Craig B. Daniel, Feb 04 2011

Keywords

• easy
• nonn

Comments

Assume that the first person to use a bank of payphones selects one at the end, and all subsequent users select the phone which puts them farthest from the current phone users. U(n) is the smallest number of phones such that n may be used without any two adjacent phones being used.

Examples

			For 4 phones, only the outer two will be used. For a fifth phone, however, a third person may come along and use the middle phone without any two being adjacent; thus U(3)=5. A seventh phone will not lead to a fourth being used without adjacent people, but an eighth will, hence U(4)=8.
		

Formula

a(n) is the index of the n-th record in A166079, which is given by the recurrence y(n) = y(m) + y(n-m+1) - 1, with y(1) = y(2) = 1 and y(3) = 2, where m = ceiling(n/2). - John W. Layman, Feb 05 2011

From Nathaniel Johnston, Apr 12 2011: (Start)

a(n) = a(n-1) + n - 1 if n = 2^k + 2 for some natural number k, a(n) = a(n-1) + 1 otherwise, for n >= 3.

a(n) = n + 2^(1+floor(log_2(n-2))) for n >= 3. (End)

Extensions

Terms 26,27,...,114 added by John W. Layman, Feb 05 2011

Edited by N. J. A. Sloane, Feb 07 2011

a(51) - a(60) from Nathaniel Johnston, Apr 12 2011