Finding a sequence that has special properties

Question

let $n \in \mathbb{N}$. Is is possible to find a sequence $S = \{ s_1, \dots, s_{n+k} \}$ ($k \leq n$) with a polynomial algorithm, so that for every pair $(x,y) \in S \times S$, the products $x \cdot y$ are pariwise distinct? Also $s_i \in S$ should be polynomial bounded with respect to $n$.

Regards,

Kreschew

Answer 1

How about the prime numbers? They are poly bounded and computable.

Added: You can sieve up to $p$, giving about $p/\ln p$ primes in time $p \ln \ln p$, barely worse than linear. But we can do better yet in the sense of reducing the highest number in the set. Adding all numbers of the form $p^2,\ p^4,\ p^7,\ $ etc. will not spoil the fact that there are no matching products. I'm sure we can do better yet. If we know in advance how many we want, I think we can do better yet and will probably raise a new question.

Answer 2

The unique factorization property of the integers ensures that if you choose your set to contain only primes it will have this property (subjected to Andre's correction).