3
$\begingroup$

Consider the first $k$ primes $p_1 = 2, p_2 = 3, \dots, p_k$. Let $A_k$ be the set of numbers that are divisible by at least one $p_i$. We can represent this set as a generating function:

$$G_k(x) = \sum_{t \in A_k} x^t.$$

Example: $G_2(x) = \frac{1}{1-x^2} + \frac{1}{1-x^3} - \frac{1}{1-x^6}.$

By the inclusion-exclusion principle (as in the previous example), any such $G_k$ can be written as a rational function. However, such a representation with inclusion-exclusion uses $2^k - 1$ terms.

Question: Is there any significantly shorter way to write this series $G_k(x)$ as a rational function?

$\endgroup$
2
  • $\begingroup$ $A_k$ is a finite union of arithmetic progressions with common difference $p_1 \dots p_k$, so the generating function has the form $\frac{P(x)}{1 - x^{p_1 \dots p_k}}$ for some polynomial $P(x)$. The computation of $P(x)$ is exactly the computation of the first $p_1 \dots p_k$ terms of the sequence. I don't know if that's the sort of answer you're looking for. $\endgroup$ Jun 2, 2016 at 6:56
  • $\begingroup$ Yes. This is true. The polynomial $P$ must contain many monomials however. $\endgroup$ Jun 2, 2016 at 7:00

1 Answer 1

2
$\begingroup$

This is probably not what you look for, but you may denote $N=\prod p_i$, $m_i=N/p_i$, then consider a polynomial $$q(x)=\prod_i (x^{m_i}+x^{2m_i}+\dots+x^{(p_i-1)m_i}).$$ Your generating function equals $$\frac1{1-x}-\frac{q(x)\pmod {1-x^{N}}}{1-x^{N}}.$$

Or, if you define a fractional part of a rational function $r=f/g$ as $\{r\}=h/g$, where $h=$(remainder of $f$ modulo $g$), the answer may be rewritten as $$\frac1{1-x}-\left\{ \frac{\prod(x^{m_i}-x^N)}{(1-x^N)\prod(1-x^{m_i})} \right\}.$$

$\endgroup$
2
  • 1
    $\begingroup$ I see. This is the g.f. for the numbers not divisible by any $p_i$. $\endgroup$ Jun 3, 2016 at 2:44
  • $\begingroup$ Of course, fixed now. $\endgroup$ Jun 3, 2016 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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