4
$\begingroup$

Let $$p(n) = \#\{f:\mathbb N \to \{0,1\} \mid n \text{ is the shortest period of } f\}$$ that means $p(n)$ denotes the number of binary sequences of period exactly $n$ (and no less). Is there a way to compute $p(n)$ without just bruteforcing all possibilities?

For an $f$ of period $n$ the values $f(1),f(2),\ldots,f(n)$ already define $f$ completely, so here are some lists of such $f$ for small $n$ (I hope it is correct):

$$ \begin{array}{c|l|l} n & \text{list} & p(n) \\ \hline 1 & (0),(1) & 2 \\ \hline 2 & (0,1),(1,0) & 2 \\ \hline 3 & (0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0) & 6 \\ \hline 4 & (0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0) & 12 \\ & (1,1,1,0),(1,1,0,1),(1,0,1,1),(0,1,1,1) & \\ & (1,0,0,1),(0,1,1,0) ,(1,1,0,0),(0,0,1,1)& \end{array} $$

$\endgroup$
  • $\begingroup$ I haven't read through everything in Primes & Squares yet, but why can't you solve this recusively by taking $2^n$ and subtracting the $f(n)$ for each proper divisor of $n$? $\endgroup$ – Sriotchilism O'Zaic Oct 22 '17 at 21:25
  • $\begingroup$ @DonaldSplutterwit You are right, thanks! $\endgroup$ – flawr Oct 22 '17 at 21:26
  • $\begingroup$ @EpsilonNeighborhoodWatch If I understood you correctly you mean $p(n) = 2^n - \sum_{2\leq k \leq n-1, k|n} p(k)$? This seems to result in $p(3) = 8$. $\endgroup$ – flawr Oct 22 '17 at 21:29
  • $\begingroup$ Nevermind, It does work for the first 4, I made a mistake. Try it online!. That summation is what I meant though. $\endgroup$ – Sriotchilism O'Zaic Oct 22 '17 at 21:33
  • $\begingroup$ Ah you do include $1$ as proper divisor. $\endgroup$ – flawr Oct 22 '17 at 21:35
3
$\begingroup$

Here's one way

$$f(n) = 2^n - \sum_{1\leq i<n,n\mid i} f(i)$$

In English this reads as

The number of aperiodic sequences of length $n$ is $2^n$ minus the number of aperiodic sequences of length $k$ that properly divides $n$

The idea behind this is if we can find the number of length $n$ sequences that are periodic we can find the number of ones that are not, since we know the number of total sequences.

We know that every periodic sequence is composed of some unique aperiodic sequence a number of times and that each of these aperiodic sequences has size $k$ such that $n\mid k$. Thus we are looking for the number of aperiodic sequences sequences of length that divide $n$. This would just be the sum of our function applied to every proper divisor of $n$.

This lends itself to a rather neat little algorithm, which I have implemented in Haskell.

divisors x = filter ((==0).(mod x)) [1..x-1]
f x=2^x - sum(map f$divisors x)

Try it online!

The algorithm is not terribly fast because we are still required to factor $n$, so there is definitely room for improvement.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ It may be worth noting this is an application of the inclusion exclusion principle, so if you have a similar problem, the arguments can still be applied. $\endgroup$ – mdave16 Oct 22 '17 at 22:04
4
$\begingroup$

The "inclusion-exclusion" nature of the problem, as mentioned in mdave16's comment, allows for another, explicit formula by way of Möbius inversion : $\displaystyle\sum_{d|n} f(d)=2^n$ (since the set of all binary sequences of length $n$ is the union of (suitable repetitions of) those whose period is $d$, over all divisors $d$ of $n$), so by the Möbius inversion formula we have $\displaystyle f(n)=\sum_{d|n}\mu(d)2^{(n/d)}$. Here $\mu(d)$ is the Möbius function, which is $0$ unless $d$ is squarefree, and $(-1)^p$ (with $p$ the number of prime divisors of $d$) elsewise.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.