Slicing up $\mathbb{N}\setminus\{1\}$

Question

Let $\mathbb{N}$ denote the set of positive integers. For any prime $p\in\mathbb{N}$ let $p\mathbb{N} = \{np: n\in \mathbb{N}\}$. Is there a partition ${\cal P}$ of $\mathbb{N}\setminus\{1\}$ such that for all $B \in {\cal P}$ and every prime $p\in\mathbb{N}$ we have $|B \cap p\mathbb{N}|=1$?

Answer 1

Recursively define a sequence of $B$'s as follows. Initially, each is empty. At each step $n > 1$, place $n$ in the first $B$ that contains only elements coprime to $n$. Clearly, for each prime $p$, there is no $B$ that contains two distinct multiples of $p$. Now fix a prime $p$ and a natural number $N > 1$, and consider the first $B$ that contains no multiple of $p$ after step $N$ has completed. The first power $p^k$ of $p$ that is larger than $N$ cannot be placed in any earlier $B$ (since all have a multiple of $p$), so it will be placed in $B$ if no multiple $p d$ of $p$ with $N < p d < p^k$ has been.

As @StevenStadnicki points out, it's interesting to investigate the structure of these sets. (I started to do it by hand, and found it sort of addictive.) Here's some Haskell code to allocate the first $N$ numbers (doubtless both inefficient and unidiomatic, but it seems to work):

insert N [] = [(N, [N])]
insert N ((c,bs):bss) = if gcd c N == 1 then (N*c,N:bs):bss else (c,bs):(insert N bss)
insertTo 1 = []
insertTo N = insert N $ insertTo (N - 1)

One runs it as

map snd $ insertTo 1000

(for example), whose output starts

[[997,991,983,977,971,967,953,947,941,937,929,919,911,907,887,883,881,877,863,859,857,853,839,829,827,823,821,811,809,797,787,773,769,761,757,751,743,739,733,727,719,709,701,691,683,677,673,661,659,653,647,643,641,631,619,617,613,607,601,599,593,587,577,571,569,563,557,547,541,523,521,509,503,499,491,487,479,467,463,461,457,449,443,439,433,431,421,419,409,401,397,389,383,379,373,367,359,353,349,347,337,331,317,313,311,307,293,283,281,277,271,269,263,257,251,241,239,233,229,227,223,211,199,197,193,191,181,179,173,167,163,157,151,149,139,137,131,127,113,109,107,103,101,97,89,83,79,73,71,67,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2],
[961,841,529,361,289,169,121,49,25,9,4],
[667,323,143,35,6],[899,437,221,77,15,8],
[713,247,187,21,10],[551,391,91,55,12],
[851,493,209,65,27,14],[299,133,85,33,16],
[377,253,119,95,18],[703,527,319,161,39,20],
[989,779,629,403,203,45,22],
[893,731,533,407,217,115,24],
[943,817,341,259,125,51,26],
[799,481,451,145,57,28],
[901,611,589,473,287,30] …

Answer 2

Place each $n$ that is not a prime power into its own $B=B(n)$. Then fill the rest of $B(n)$ with powers of primes that do not divide $n$.