# partition of an integer n into atmost k =O(log n) parts

Suppose you have a partition p of n into atmost k parts, say $$\{i_1, i_2, ..., i_j, ..., i_{k-1}\}$$ For example $\{1, 4\}$ is a partition of 10 into 3 parts (in this notation i am specifying the partition points, not the part lengths, i.e {1} , {2,3,4}, {5,6,7,8,9,10} are the three partitions)

Consider $$I(n, k) = min_p \sum_j {\frac {(i_{j+1} - i_j)} {2^{j}}}$$

Can we say anything meaningful about a lower bound on $I(n, k)$? I am specifically interested in the question when k is a function of n that grows slowly, like $log \ n$, or slower than $n^{1/{\epsilon}}$ for any ${\epsilon} > 0$.

I'm actually not sure if anything meaningful can be said here, so any ideas on how to approach this question would be very welcome

Any pointers to literature in this regard or a counter example showing no meaningful bound exists will be great. Intuitively, it seems like if i pick a partition of size $log \ n$ for example, no matter how i choose such a partition I cannot have $I(n, k) = O(1)$ for example. So I would probably guess $I(n,O(log\ n)) = O(log \ n)$.

-
It seems your question is not about partitions of integers but just about sequences $1\le i_1\lt\cdots\lt i_{k-1}\lt n$. For given $k$, the minimum occurs when the sequence is $1,2,\ldots,k{-}1$. But one of us must be missing something. – Brendan McKay Apr 22 '14 at 5:13
I think the problem statement was confusing. Your solution is right as stated. – Ram Apr 22 '14 at 7:11