Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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$). –  Yuval Filmus Dec 1 '10 at 6:39
    
Can you make your example more explicit? Obviously there's some disparity between your intended question and what I understood from the problem statement. –  Yuval Filmus Dec 1 '10 at 6:40

1 Answer 1

up vote 1 down vote accepted

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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