3
$\begingroup$

Suppose I take $n$ sets $\{S_i\}$ where each $S_i$ is some subset of integers. Let $P$ indicate a set of integers obtainable by drawing exactly one factor from each $\{S_i\}$ and multiplying them together. What conditions on these sets do I need to ensure that

  1. $P$ forms a contiguous interval
  2. Each element of $P$ has a unique expansion of this form

This is probably a well known problem, so any keyword pointers are welcome

  • 0
    The representation won't be unique, e.g. $2 = 2 \cdot 1 = 1 \cdot 2$, and the range is not at interval, e.g. either $2^n + 1$ or $2^n + 2$ is not representable (depending on the parity of $n$).2010-12-01
  • 0
    Can you make your example more explicit? Obviously there's some disparity between your intended question and what I understood from the problem statement.2010-12-01

1 Answers 1

1

Let's assume that all the integers are in fact at least $1$.

Let $\max(P) = \prod_i s_i$. If $\max(P) \neq \min(P)$ then $\max(P)-1$ must be representable. Now $(s_1 - 1) \prod_{i>1} s_i = \prod_i s_i - \prod_{i>1} s_i$, so there must be an index $I$ such that $S_i = \{1\}$ for $i \neq I$. $S_I$ itself is of course of the form $\{1,\ldots,\max(P)\}$.

Summarizing, we have found two solutions: $|S_i|=1$ for all $i$ (the sets are otherwise arbitrary), and $S_i = \{1\}$ apart for one set which is an interval.

If the sets are infinite (i.e. $\max(P) = \infty$) then for each prime $p$ take the set $S_p = \{p^k : k \geq 0\}$. There are other solutions: you can decompose the set of primes arbitrarily as the disjoint union $\bigcup P_i$ and then take as $S_i$ all numbers whose prime factors are in $P_i$. All these use the convention that you only select finitely many numbers which are not $1$.

Open question: are these the only solutions?