login
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