I'm doing some coding problems, and I came across a combinatorics problem that I thought should be quite easy but turns out to be tricky:
Let $f_n:\mathcal{B}\to\mathcal{B}_{n}$ be a function from the set of bitstrings to the set of bitstrings of length $n$ be given by $$f_n(b_1 b_2...b_k) = [b_1b_2...b_kb_1b_2...b_k b_1 b_2...b_k...]_1^n.$$ In other words, repeat the input bitstring a bunch of times and spit back the first $n$ digits of the resulting sequence. Clearly, $f_n$ is not one-to-one. For example, $f_n(00)=f_n(0)$.
Call a bitstring $b$ minimal with respect to $f_n$ if there are no shorter bitstrings $b'$ with $f_n(b)=f_n(b')$. Denote the number of minimal bitstrings of length $k$ by $\phi(n,k)$. I'm trying to find a closed-form expression for $\phi(n,k)$.
My initial thought was that $\phi(n,k) = 2^k - \sum_{k': k'\mid k} \phi(n, k')$, subtracting off all the minimal bitstrings whose length divides $k$ since they could be repeated to form a bitstring of length $k$. And this is correct for $k\leq\frac{n}{2}$, but it's not true for higher $k$, so $\phi$ should depend on $n$.
Here's an example of the problem: $f_4(100) = f_4(1001)$, and $100$ is minimal yet $3$ does not divide $4$. Any ideas for how to compute $\phi(n,k)$?