

A263991


a(n) is the number of uniform consecutive subintervals of the unit interval each of size 2^(ceiling(log_2(n))) that are completely covered by one of the n uniform consecutive subintervals (of size 1/n each) of the unit interval.


0



1, 2, 2, 4, 4, 4, 2, 8, 8, 8, 6, 8, 4, 4, 2, 16, 16, 16, 14, 16, 12, 12, 10, 16, 8, 8, 6, 8, 4, 4, 2, 32, 32, 32, 30, 32, 28, 28, 26, 32, 24, 24, 22, 24, 20, 20, 18, 32, 16, 16, 14, 16, 12, 12, 10, 16, 8, 8, 6, 8, 4, 4, 2, 64, 64, 64, 62, 64, 60, 60, 58, 64, 56, 56, 54, 56, 52, 52, 50, 64, 48, 48, 46, 48, 44, 44, 42, 48, 40, 40, 38, 40, 36, 36, 34, 64, 32, 32, 30
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

For n > 1, we know that 2 <= a(n) <= n. The lower bound of 2 is because [0, 2^(ceiling(log_2(n)))] will always be covered by [0, 1/n] and [1  2^(ceiling(log_2(n))), 1] will always be covered by [1  1/n, 1]. The upper bound of n is because each of the n consecutive subintervals (of size 1/n each) can only completely cover up to 1 of the 2^(ceiling(log_2(n))) consecutive subintervals (of size 2^(ceiling(log_2(n))) each). In the case that n is a power of 2, a(n) = n.


LINKS

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


EXAMPLE

For n=5, the 4 solutions are these intervals: [0, 1/8] is covered completely by [0, 1/5], [1/4, 3/8] is covered completely by [1/5, 2/5], [5/8, 3/4] is covered completely by [3/5, 4/5], and [7/8, 1] is covered completely by [4/5, 1].


PROG

(Python)
def getNumber(n):
y = int(math.ceil(math.log(n, 2)))
smallIncrement = 0.5 ** y
marker = 0
nMarker = 0
toReturn = 0
while marker < 1:
newMarker = marker + smallIncrement
if (nMarker + 1) / n < newMarker:
nMarker += 1
if nMarker / n <= marker and (nMarker + 1) / n >= newMarker:
toReturn += 1
marker = newMarker
return toReturn


CROSSREFS

Cf. A029837, A062383.
Sequence in context: A037202 A227091 A165956 * A065285 A302437 A179932
Adjacent sequences: A263988 A263989 A263990 * A263992 A263993 A263994


KEYWORD

nonn


AUTHOR

Apoorv Khandelwal, Oct 31 2015


STATUS

approved



