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$?



Slicing up $\mathbb{N}\setminus\{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](https://mathoverflow.net/questions/360063/slicing-up-mathbbn-setminus-1/360069#comment906934_360069), 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] …

```

