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?

Improve this question
$\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$
    – Qiaochu Yuan
    Commented Jun 2, 2016 at 6:56
  • $\begingroup$ Yes. This is true. The polynomial $P$ must contain many monomials however. $\endgroup$
    – Danny Nguyen
    Commented Jun 2, 2016 at 7:00

1 Answer 1

Reset to default
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\}.$$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I see. This is the g.f. for the numbers not divisible by any $p_i$. $\endgroup$
    – Danny Nguyen
    Commented Jun 3, 2016 at 2:44
  • $\begingroup$ Of course, fixed now. $\endgroup$
    – Fedor Petrov
    Commented Jun 3, 2016 at 5:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .