login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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.
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
Sequence in context: A037202 A227091 A165956 * A065285 A302437 A179932
KEYWORD
nonn
AUTHOR
Apoorv Khandelwal, Oct 31 2015
STATUS
approved