Skip to main content
added 8 characters in body
Source Link
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

Here is another approach which may give some light on estimating your desired quantity (the number of sets of $n$ numbers $r_i$ which are mutually coprime and whose product is less than $p$). I don't see the significance of $p$ being prime, and will replace $p$ with $m^n$.

Let $R$ be a finite subset of the primes, let $P$ be the product of the primes in $R$ and let $q_m(R)$ count those multiples of $P$ at most $m$ which are $R$-smooth. Let $S$ be a partition of $n$ parts of some finite subset of primes, with parts called $R_i$. The number of ways of choosing a number from each part is at least $\prod_i q_m(R_i)$ to get a set of $n$ coprime numbers whose product is at most $m^n$. This can be tweaked to change the $m$ to $m_i$ whose product is at most $m^n$, but then one does some double counting if insufficient care is taken.

Now a lower bound for your count can be written using the notation above (where the sum is over all $S$ which are $n$-part partitions of a subset of enough primes) as $$\sum_S \prod_i q_m(R_i).$$ Note that multiple choices of $r_i$ can result in the same product, so it is not enough to consider smooth numbers less than $m^n$.

While the above may help derive a lower bound, it may be more fruitful to consider for each integer $p\lt m^n$ the number of $n$- part coprime factorizations of $p$, then sum that number from $p=1$ to $m^n$. If I get a good idea for estimation with either scheme, I will add it below.

Gerhard "Happy Father's Day To You" Paseman, 2016.06.19.

Here is another approach which may give some light on estimating your desired quantity (the number of sets of $n$ numbers $r_i$ which are mutually coprime and whose product is less than $p$). I don't see the significance of $p$ being prime, and will replace $p$ with $m^n$.

Let $R$ be a finite subset of the primes, let $P$ be the product of the primes in $R$ and let $q_m(R)$ count those multiples of $P$ at most $m$ which are $R$-smooth. Let $S$ be a partition of $n$ parts of some finite subset of primes, with parts called $R_i$. The number of ways of choosing a number from each part is at least $\prod_i q_m(R_i)$ to get a set of $n$ coprime numbers whose product is at most $m^n$. This can be tweaked to change the $m$ to $m_i$ whose product is at most $m^n$, but then one does some double counting if insufficient care is taken.

Now a lower bound for your count can be written using the notation above (where the sum is over all $S$ which are $n$-part partitions of a subset of enough primes) as $$\sum_S \prod_i q_m(R_i).$$ Note that multiple choices of $r_i$ can result in the same product, so it is not enough to consider smooth numbers less than $m^n$.

While the above may help derive a lower bound, it may be more fruitful to consider for each integer $p\lt m^n$ the number of $n$- part factorizations of $p$, then sum that number from $p=1$ to $m^n$. If I get a good idea for estimation with either scheme, I will add it below.

Gerhard "Happy Father's Day To You" Paseman, 2016.06.19.

Here is another approach which may give some light on estimating your desired quantity (the number of sets of $n$ numbers $r_i$ which are mutually coprime and whose product is less than $p$). I don't see the significance of $p$ being prime, and will replace $p$ with $m^n$.

Let $R$ be a finite subset of the primes, let $P$ be the product of the primes in $R$ and let $q_m(R)$ count those multiples of $P$ at most $m$ which are $R$-smooth. Let $S$ be a partition of $n$ parts of some finite subset of primes, with parts called $R_i$. The number of ways of choosing a number from each part is at least $\prod_i q_m(R_i)$ to get a set of $n$ coprime numbers whose product is at most $m^n$. This can be tweaked to change the $m$ to $m_i$ whose product is at most $m^n$, but then one does some double counting if insufficient care is taken.

Now a lower bound for your count can be written using the notation above (where the sum is over all $S$ which are $n$-part partitions of a subset of enough primes) as $$\sum_S \prod_i q_m(R_i).$$ Note that multiple choices of $r_i$ can result in the same product, so it is not enough to consider smooth numbers less than $m^n$.

While the above may help derive a lower bound, it may be more fruitful to consider for each integer $p\lt m^n$ the number of $n$- part coprime factorizations of $p$, then sum that number from $p=1$ to $m^n$. If I get a good idea for estimation with either scheme, I will add it below.

Gerhard "Happy Father's Day To You" Paseman, 2016.06.19.

Source Link
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

Here is another approach which may give some light on estimating your desired quantity (the number of sets of $n$ numbers $r_i$ which are mutually coprime and whose product is less than $p$). I don't see the significance of $p$ being prime, and will replace $p$ with $m^n$.

Let $R$ be a finite subset of the primes, let $P$ be the product of the primes in $R$ and let $q_m(R)$ count those multiples of $P$ at most $m$ which are $R$-smooth. Let $S$ be a partition of $n$ parts of some finite subset of primes, with parts called $R_i$. The number of ways of choosing a number from each part is at least $\prod_i q_m(R_i)$ to get a set of $n$ coprime numbers whose product is at most $m^n$. This can be tweaked to change the $m$ to $m_i$ whose product is at most $m^n$, but then one does some double counting if insufficient care is taken.

Now a lower bound for your count can be written using the notation above (where the sum is over all $S$ which are $n$-part partitions of a subset of enough primes) as $$\sum_S \prod_i q_m(R_i).$$ Note that multiple choices of $r_i$ can result in the same product, so it is not enough to consider smooth numbers less than $m^n$.

While the above may help derive a lower bound, it may be more fruitful to consider for each integer $p\lt m^n$ the number of $n$- part factorizations of $p$, then sum that number from $p=1$ to $m^n$. If I get a good idea for estimation with either scheme, I will add it below.

Gerhard "Happy Father's Day To You" Paseman, 2016.06.19.