1
$\begingroup$

Erdos usually named a sequence of integers no one of which is divisible by any other as an $M$- sequence (M stands for "multiple-free") or primitive sequence.

For example it is easy to see that $\lfloor \frac{n}{2} \rfloor+1, \lfloor \frac{n}{2} \rfloor+2, \ldots ,n-1, n$ is an $M$- sequence with terms not greater than $n$. Actually we cannot hope from an $M$- sequence to contain more than half of the numbers $\le n$ as Erdos has proved.
My question is:
Are there other examples of non trivial $M$-sequences (prime numbers, squares of primes, etc) in the literature which we can form explicitly?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The set $P_k(n)$ defined by $$ P_k(n)=\{a: 1<a \leq n, \Omega(a)=k \}, \quad k\geq 1 $$ where $\Omega(a)$ counts the number of distinct prime divisors with multiplicity is one such set for each fixed $k.$ Thus $P_2(n)$ is the set of integers in $(1,n]$ which have exactly two prime divisors. The cardinality of these sets can be estimated from the prime number theorem.

Hall's book "Multiples" is a good reference for this.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You don't want that $\omega(a)$ in there, do you? $\endgroup$
    – Gerry Myerson
    Commented Aug 20, 2017 at 11:34
  • $\begingroup$ @GerryMyerson, thanks for that, fixed. $\endgroup$
    – kodlu
    Commented Aug 20, 2017 at 14:14

You must log in to answer this question.

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