5
$\begingroup$

Say two positive integers are "peers" if they are divisible by precisely the same set of primes, such as 12 and 18 (both divisible by 2 and 3), or 70 and 350 (both divisible by 2, 5 and 7).

What are the best estimates known for the number of pairwise non-peers not greater than an arbitrary positive integer N?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Your count equals the number of square-free numbers up to $N$. This is because a set of positive integers are pairwise "non-peers" if any only if their radicals are distinct. This is a well-studied problem in analytic number theory, see in particular Walfisz's estimate here.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Now I see it, as the count of pairs is not being asked. Ignore "I'm not seeing this. Nonpeer pairs would include 2^a and 2^b3^c. If you take (N-1) choose 2 and subtract off the peer pairs, then you get the count Bernardo asks. The number of peer pairs is related to but different from the set of square free numbers. " Gerhard "Or Is Non Peer Different?" Paseman, 2019.09.04. $\endgroup$
    – Gerhard Paseman
    Commented Sep 5, 2019 at 2:55
  • $\begingroup$ @GerhardPaseman: The OP is not talking about the number of peer or non-peer pairs. Instead, he is talking about the maximal number of integers one can choose from $\{1,\dots,N\}$ such that no two of them are peers, i.e., no two of them have the same square-free radical. So any good subset $S\subset\{1,\dots,N\}$ gives rise to a subset $T\subset\{1,\dots,N\}$ of square-free integers with $|S|=|T|$. To obtain $T$ from $S$, simply replace each element of $S$ by its radical. The conclusion in my post follows. $\endgroup$
    – GH from MO
    Commented Sep 5, 2019 at 3:18
  • 3
    $\begingroup$ Yes, thank you. Gerhard "Will Try Thinking More Slowly" Paseman, 2019.09.04. $\endgroup$
    – Gerhard Paseman
    Commented Sep 5, 2019 at 4:08

You must log in to answer this question.

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