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
KEYWORD
nonn
AUTHOR
Apoorv Khandelwal, Oct 31 2015
STATUS
approved