Primitive bit strings
How many strings of [tex]n[/tex] [tex]0[/tex]'s and [tex]1[/tex]'s are primitive, in the sense that such a string is not expressible as a concatenation of several identical smaller strings (for instance, 100100100 is not primitive, but 1101 is)?
Risposte
"Rigel":
$P(n) = \sum_{d|n} 2^d \mu(\frac{n}{d})$
Ok, this the closed form I wanted! Why bothering with all those sums while having the [tex]$\mu(\cdot)$[/tex] function?
I tought you had reached the previous formula by another reasoning.
All those products are a subset of the divisors of $n$.
In that formula we are assuming that $n = \Pi_{i=1}^k p_i^{a_i}$ is the usual decomposition of $n$ in terms of prime numbers.
My reasoning is the following:
let us start from the relation
$\sum_{d|n} P(d) = 2^n$,
where the summation is extended over all divisors $d$ of $n$.
Then we use the Moebius inversion formula obtaining
$P(n) = \sum_{d|n} 2^d \mu(\frac{n}{d})$,
where $\mu$ is the Moebius function.
After some computation we get the formula of my previous post.
In that formula we are assuming that $n = \Pi_{i=1}^k p_i^{a_i}$ is the usual decomposition of $n$ in terms of prime numbers.
My reasoning is the following:
let us start from the relation
$\sum_{d|n} P(d) = 2^n$,
where the summation is extended over all divisors $d$ of $n$.
Then we use the Moebius inversion formula obtaining
$P(n) = \sum_{d|n} 2^d \mu(\frac{n}{d})$,
where $\mu$ is the Moebius function.
After some computation we get the formula of my previous post.
Correct, but not closed enough 
All those products of prime factors look like the divisors of [tex]$n$[/tex]...
All those products of prime factors look like the divisors of [tex]$n$[/tex]...
I don't know if this form is "sufficiently closed"...
Anyway, let $p_1, ..., p_r$ be the distinct prime divisors of $n$.
Then the required number is (?)
$P(n) = 2^n -\sum 2^{n/p_i} + \sum 2^{n/(p_i p_j)} - \sum 2^{n/(p_i p_j p_k)} + \ldots + (-1)^r 2^{n/(p_1\cdots p_r)}$.
Here in a term such as $\sum 2^{n/(p_i p_j)$ it is understood that we consider all possible products $p_i p_j$ of distinct prime factors of $n$ taken two at a time.
Anyway, let $p_1, ..., p_r$ be the distinct prime divisors of $n$.
Then the required number is (?)
$P(n) = 2^n -\sum 2^{n/p_i} + \sum 2^{n/(p_i p_j)} - \sum 2^{n/(p_i p_j p_k)} + \ldots + (-1)^r 2^{n/(p_1\cdots p_r)}$.
Here in a term such as $\sum 2^{n/(p_i p_j)$ it is understood that we consider all possible products $p_i p_j$ of distinct prime factors of $n$ taken two at a time.
The solution can be expressed in closed form.
search you a formula that is not recursive?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo