Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime

Question

This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.

Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to place numbers $1$ to $n^3$ in the unit cubes so that the numbers in any two adjacent unit cubes are co-prime? (Two unit cubes are called adjacent if they have a common face). What about the two dimensional version of this problem in an $n\times n$ square ?

Answer 1

Here is a proof that for any fixed dimension $d$, there is a computable $n_0(d)$ such that for all $n\ge n_0(d)$ we can place the numbers $1, ..., n^d$ in a $d$-dimensional cube of side length $n$ such that any two adjacent numbers are coprime.

The main idea is to use the following lemma:

Lemma 1. If $G = (V,E)$ is a graph with maximum degree $2d$, then for any partition of the vertex set $V$ into parts $V_1, ..., V_m$ such that for each $i$ we have $|V_i| \ge 4ed$, where $e$ is the base of the natural logarithm, we can pick one vertex $v_i$ from each $V_i$ such that for $i\ne j$ vertices $v_i$ and $v_j$ are not adjacent in $G$.

Proof. This is a direct consequence of the Lovász Local Lemma. First assume WLOG that each $V_i$ contains exactly $\lceil 4ed\rceil$ elements. Suppose we randomly select one vertex $v_i$ from each set $V_i$, and for each edge $e_j = (a,b) \in E$ let $A_j$ be the event that both $a,b$ were selected. The probability of $A_j$ occurring is at most $\frac{1}{\lceil 4ed\rceil^2}$, and each event $A_j$ is dependent on at most $2(2d\lceil 4ed\rceil-1)$ other events $A_k$, so in order to apply the Local Lemma we just need to check that $e\cdot \frac{1}{\lceil 4ed\rceil^2}\cdot 2(2d\lceil 4ed\rceil-1) \le 1$, which is obvious. Thus there is a positive probability that none of the events $A_j$ occur.

Next we make a few natural definitions. From here on we set $N = n^d$.

Definition. Let $p_1, ..., p_i$ be the first $i$ prime numbers. We say that a number $v$ has $i$-type $m$ if $\text{gcd}(v,\prod_{j\le i}p_j) = m$. We'll write $\#_N^i(m)$ for the number of numbers $v$ between $1$ and $N$ with $i$-type $m$.

Definition. An $i$-type coloring of the graph $G = (V,E)$ with $|V| = N$ is an assignment of a number $m(v)$ dividing $\prod_{j\le i}p_j$ to each vertex $v$, such that for any adjacent vertices $v,w$ we have $\text{gcd}(m(v),m(w)) = 1$, and for any $m \ne 1$ the number of vertices $v$ with $m(v) = m$ is at least $\#_N^i(m)$.

The idea is to inductively convert an $(i-1)$-type coloring to an $i$-type coloring for sufficiently large $i$ using Lemma 1. To that end, we need the following lemma.

Lemma 2. There is a computable index $i_0$, depending only on $d$, such that for any $i\ge i_0$ and any $N,m$, we have $\#_N^i(mp_i) \le \max(1, \frac{1}{\lceil 4ed\rceil}\#_N^{i-1}(m))$.

Proof. If $\#_N^i(mp_i) \ge 2$, then $N/m \ge 2p_i$. If $2p_i \le N/m < p_i^3$ then we use Chebyshev's weak form of the prime number theorem to see that

$\#_N^{i-1}(m) \ge \pi(N/m) - \pi(p_i) \ge \frac{1}{\log(p_i)}\frac{N}{m}\left(\frac{7}{8}\frac{\log(p_i)}{\log(N/m)}-\frac{9}{8}\frac{p_i}{N/m}\right) \ge \frac{1}{4\log(p_i)}\frac{N}{m},$

while we trivially have $\#_N^i(mp_i) \le \frac{1}{p_i}\frac{N}{m}$. Thus if $N/m < p_i^3$ and $p_i \ge 4\lceil 4ed\rceil\log(p_i)$ then we are done.

If $N/m \ge p_i^3$, then we can, to within a constant factor, estimate the sizes of $\#_N^{i-1}(m)$ and $\#_N^i(mp_i)$ using the fundamental lemma of sieve theory, and for $i_0$ sufficiently large the first will be larger than the second by more than a factor of $\lceil 4ed\rceil$. I'll leave the details to the reader...

Now the inductive step doesn't quite work because of the existence of certain "bad pairs" $(m,p_i)$.

Definition. We call the pair $(m,p_i)$ bad if $\#_N^{i-1}(m) < \lceil 4ed\rceil$ and $\#_N^i(mp_i) = 1$ and $i \ge i_0$ and $p_i < N/2$.

We will fix this problem by taking primes between $N/2$ and $N$ and letting them pretend to be multiples of $m$ but not of $mp_i$. In order for this to work, we need to show that there are not too many bad pairs $(m,p_i)$.

Bad pairs need to satisfy all of the following constraints:

• $m$ can't have more than $\lceil 4ed\rceil-2$ prime factors: for any prime factor $q$ of $m$, $mq$ has $i$-type $m$.
• no prime factor $q$ of $m$ can be below $p_i^{\frac{1}{\lceil 4ed\rceil}}$: otherwise, all of $m, mq, mq^2, ..., mq^{\lceil 4ed\rceil}$ would have $i$-type $m$ and be below $mp_i \le N$.
• the number of primes between $p_i$ and $N/m$ must be bounded above by $\lceil 4ed\rceil$: for any prime $q$ between $p_i$ and $N/m$, $mq$ has $i$-type $m$ and is below $N$.

By the first bullet point, we see that we must have $p_i \ge N^{\frac{1}{\lceil 4ed\rceil}}$, and then by the second bullet point we see that each prime factor of $m$ must be at least $N^{\frac{1}{\lceil 4ed\rceil^2}}$. By the third bullet point and the prime number theorem, $mp_i$ must be between $N(1-O(1/\log(N)^2))$ and $N$ (in fact we can get better bounds here).

Putting this all together, we see that the number of bad pairs is at most $O(N/\log(N)^2)$, where the implied constant depends only on $d$.

For the precise description of how we artificially inflate the number of multiples of $m$ for bad pairs $(m,p_i)$, we can invent a pretending function $F_N^i(m)$ for $p_i < N/2$ satisfying the following constraints:

• $F_N^{i-1}(m) = F_N^i(m) + F_N^i(mp_i)$
• $F_N^{i-1}(m) \ge \lceil 4ed\rceil F_N^i(mp_i)$ for $i\ge i_0$.
• $F_N^i(m) \ge \#_N^i(m)$ for $m \ne 1$, $F_N^i(1) \ge 0$.

You can easily check (using the fact that $m$ has at most $\lceil 4ed\rceil$ prime factors if $m$ is part of a bad pair) that such a pretending function exists as long as $\lceil 4ed\rceil^{\lceil 4ed\rceil}$ times the number of bad pairs is at most the number of primes between $N/2$ and $N$, and for $N$ sufficiently large this will be the case. Then you can define a strong $i$-type coloring to be a coloring in which the number of vertices colored with the color $m$ is at least $F_N^i(m)$, and inductively use Lemma 1 to prove strong $i$-type colorings exist.

In order to start the inductive process, we need to come up with an $i_0$-type coloring of our hypercube (note that for $N$ large, a strong $i_0$-type coloring is the same as an ordinary $i_0$-type coloring, since there will be no bad pairs $(m,p_i)$ where $m$ has a prime factor below $p_{i_0}$). This is fairly easy as long as $n$ is large compared to $2^{i_0}$. Basically, one can start with something like this (if $n$ was $11$ and $i_0$ was 3):

$\begin{array}{ccccccccccc} 30 & 1 & 2 & 15 & 2 & 1 & 10 & 3 & 2 & 5 & 6\\ 1 & 30 & 1 & 2 & 15 & 2 & 3 & 10 & 1 & 6 & 5\\ 30 & 1 & 2 & 15 & 2 & 1 & 10 & 3 & 2 & 5 & 6\\ \vdots & & & & & & & & & & \vdots\\ 1 & 30 & 1 & 2 & 15 & 2 & 3 & 10 & 1 & 6 & 5\\ 30 & 1 & 2 & 15 & 2 & 1 & 10 & 3 & 2 & 5 & 6\end{array}$

and then fix it so there aren't quite so many $30$s, etc.

Answer 2

One strategy would be to prove that from solutions to the cases $m$ and $n$ which are coprime, one can produce a solution for $m\cdot n$, and to construct solutions for prime power cases (maybe using a solution for $p^{k-1}$ to construct the solution for $p^k$). Then the following is one step of the solution:

Solution for the 2D case and $n=p$ an odd prime: Start with the "standard" enumeration

$\begin{matrix} 1&2&3&4&...&p\\ p+1&p+2&p+3&...&... &2p\\ 2p+1&...&...&...&...&3p\\ ...&...&...&...&...&4p\\ ...&...&...&...&...&...\\ ...& ... & ...&...&...& p^2 \end{matrix}$

The problem is only the last column where every entry is divisible by $p$. Now one can put "half" of the multiples of $p$ in the first row:

$\begin{matrix} 1&2p&3&4p&...&(p-1)p&p\\ p+1&p+2&p+3&...&...&... &2\\ ...&...&...&...&...&...&3p\\ ...&...&...&...&...&...&4\\ ...&...&...&...&...&...&...\\ ...& ... & ...&...&...&...& p^2 \end{matrix}$

The only problem remaining is the last two entries of the first line. It suffices now to choose a prime number $q$ such that $2p<q<p^2$ and switch the positions of $p$ and $q$.

Answer 3

Latest (and likely final) edit: Fixing a typo, rewording the introduction

Multiples of $2$ are placed in a checkerboard fashion: This is the parity condition, and is essential if there are an even number of total lattice sites. This answer sketches a proof that it is possible to place multiples of $3$ in all rectangular arrays in arbitrary dimension, with the exception of $2^4$ and $2^6$, and argues that higher primes can also be incorporated. Thus I conjecture that these two examples are the only cases where a solution is impossible. For lower dimensions there are many explicit solutions.

2D: All $(k,l)$ with $kl\leq 50$. These are from a numerical search (using parity but no other symmetries), except for $(21,2)$ and $(24,2)$ for which Masked Avenger (MA) found a Hamiltonian path in the comments below (in "first three exceptions" of previous version).

All squares up to 25 numerically, except for 24. nsrt's answer gives an example for all odd primes.

3D: All $(k,l,m)$ with $klm\leq 50$ with $m=2$, numerically except for MA's final "exception" $(12,2,2)$. Explicit non-Hamiltonian solution for $(3,3,3)$:

$\left(\begin{array}{ccc}27&10&9\\20&3&8\\21&4&15\end{array}\right) \left(\begin{array}{ccc}14&13&22\\11&2&1\\16&7&26\end{array}\right) \left(\begin{array}{ccc}5&6&23\\12&25&24\\17&18&19\end{array}\right)$

A numerical solution for $(4,4,3)$. Peter Mueller's answer gives solutions for $(4,3,3)$, $(5,3,3)$ and $(4,4,4)$.

4D: $(2,2,2,2)$ is impossible as per Zack Wolske's comment. $(3,2,2,2)$ has a solution: $\left(\begin{array}{ccc}1&6&13\\8&11&24\end{array}\right) \left(\begin{array}{ccc}4&7&8\\21&10&23\end{array}\right)$

$\left(\begin{array}{ccc}2&5&12\\15&14&19\end{array}\right) \left(\begin{array}{ccc}3&22&17\\16&9&20\end{array}\right)$

5D: $(2,2,2,2,2)$ has a solution:

$\left(\begin{array}{cc}23&14\\24&19\end{array}\right) \left(\begin{array}{cc}28&3\\25&4\end{array}\right)\qquad \left(\begin{array}{cc}22&15\\7&16\end{array}\right) \left(\begin{array}{cc}27&32\\26&21\end{array}\right)$

$\left(\begin{array}{cc}12&5\\1&6\end{array}\right) \left(\begin{array}{cc}17&2\\18&11\end{array}\right)\qquad \left(\begin{array}{cc}29&8\\30&13\end{array}\right) \left(\begin{array}{cc}20&9\\31&10\end{array}\right)$

6D: $(2,2,2,2,2,2)$ is impossible, also due to placing multiples of $3$. There are $11$ odd multiples and $10$ even multiples to place. So if the domain is split in half, at least one half must have $11$ or more multiples of $3$. Now for a 5D domain: either (a) there are none of a given parity, in which case there can be up to $16$ of the other, or (b) there is one of a given parity, which has $5$ neighbours, hence restricting the other parity to $11$, or (c) the total of both parities is restricted to $10$ or less (by detailed checking). Thus for each of the six ways in which the 6D domain can be split, there are are zero or one of one parity and $10$ or more of the other. Losing at most one site at each of the remaining five splittings, we find at least $5$ in the intersection of the halves, a single site, which is a contradiction.

General idea: For the remaining lattices, if one of the lengths is at least $3$ use checkerboard arrangements for all odd and even multiples of $3$ on opposite sides, as in the $(3,3,3)$ example above. For larger examples, these fill several layers on each side (total filling $2/3$ of the volume). If multiples of $15$ are placed as close together as possible, the remaining $13/15$ of the volume is available for other multiples of $5$, amongst the multiples of $3$ or in the empty space in the middle. Similarly with $7$ and higher primes, which become increasingly easy to add. So I conjecture that the only impossible cases are of the form $2^d$.

But which $d$? Rather than opposite faces we now concentrate on corners. If we place odd multiples of 3 at distances $\{o_i\}$ from a specified corner and even multiples of 3 at distances $\{e_i\}$ from that corner, such that all $\{o_i\}$ are odd and all $\{e_i\}$ are even, it is possible to ensure that none are adjacent if $d\not\in\{4,6,8,10,12\}$. For example, the solution for $d=14$ is $o_i=1,3,5,11,13$ with a total of (binomial coefficients) $14+364+2002+364+14=2758$ locations, and $e_i=8$ with $3003$ locations. In this case we need $2731$ (roughly $2^{14}/6$) odd and $2730$ even.

The remaining cases $8,10,12$ can be filled with multiples of 3 using the following construction: Choose a $2\times 2$ block, then odd multiples of 3 are at odd locations (required by parity) a distance $\delta=0,1,\ldots (d/2)-2$ from this block, and even multiples of 3 are at even locations at distances $\delta=(d/2),(d/2)+1,\ldots,d-2$. In each case the number of such locations is

$2\sum_{\delta=0}^{d/2-2} \left(\begin{array}{c}d-2\\\delta\end{array}\right)$

so for example for $d=8$ we have $2+12+30=44$ for $\delta=0,1,2$ which is slightly more than sufficient as we need to place $43$ odd multiples of $3$ and $42$ even multiples. Thus, assuming that multiples of higher primes can be incorporated as above, the only counterexamples are $2^4$ and $2^6$.

Answer 4

It's more a comment to Carl's answer, but too long as a comment. Using a very naive binary linear program formulation (see below) one gets solutions for \begin{equation} (k,l,m)=(4,3,3):\; \left(\begin{array}{rrr} 32 & 25 & 6 \\ 5 & 36 & 7 \\ 12 & 35 & 24 \end{array}\right), \left(\begin{array}{rrr} 15 & 28 & 31 \\ 26 & 17 & 30 \\ 29 & 8 & 1 \end{array}\right), \left(\begin{array}{rrr} 2 & 23 & 18 \\ 21 & 16 & 11 \\ 10 & 33 & 14 \end{array}\right), \left(\begin{array}{rrr} 3 & 22 & 19 \\ 20 & 13 & 4 \\ 9 & 34 & 27 \end{array}\right) \end{equation} \begin{equation} (k,l,m)=(5,3,3):\; \left(\begin{array}{rrr} 38 & 45 & 14 \\ 15 & 26 & 29 \\ 16 & 25 & 6 \end{array}\right), \left(\begin{array}{rrr} 21 & 34 & 5 \\ 22 & 31 & 36 \\ 19 & 42 & 37 \end{array}\right), \left(\begin{array}{rrr} 40 & 13 & 24 \\ 3 & 20 & 7 \\ 35 & 11 & 30 \end{array}\right), \left(\begin{array}{rrr} 27 & 44 & 17 \\ 4 & 43 & 18 \\ 33 & 32 & 41 \end{array}\right), \left(\begin{array}{rrr} 8 & 9 & 28 \\ 39 & 10 & 1 \\ 2 & 23 & 12 \end{array}\right) \end{equation} and \begin{equation} (k,l,m)=(4,4,4):\; \left(\begin{array}{rrrr} 10 & 21 & 16 & 27 \\ 19 & 40 & 1 & 8 \\ 12 & 7 & 36 & 35 \\ 23 & 60 & 29 & 44 \end{array}\right), \left(\begin{array}{rrrr} 33 & 2 & 37 & 50 \\ 62 & 11 & 6 & 49 \\ 61 & 54 & 5 & 48 \\ 30 & 31 & 46 & 53 \end{array}\right), \left(\begin{array}{rrrr} 64 & 13 & 24 & 43 \\ 9 & 32 & 17 & 18 \\ 22 & 59 & 26 & 41 \\ 47 & 20 & 63 & 4 \end{array}\right), \left(\begin{array}{rrrr} 45 & 14 & 25 & 42 \\ 34 & 3 & 58 & 55 \\ 39 & 28 & 15 & 56 \\ 38 & 51 & 52 & 57 \end{array}\right) \end{equation} Here is the algorithm: Let $c$ index the $n=klm$ unit cubes, and let $j$ run from $1$ to $n$. Let $x_{c,j}$ be $n^2$ binary variables, where $x_{c,j}=1$ means that the cube $c$ carries the entry $j$. The question is equivalent to a binary solution of the following system: \begin{align} \sum_cx_{c,j} &= 1\text{ for each }j\\ \sum_jx_{c,j} &= 1\text{ for each }c\\ x_{c,i}+x_{d,j} &\leq 1\text{ whenever $c$ and $d$ are adjacent and gcd$(i,j)\ge2$} \end{align} I used Sage and the backend gurobi to solve this system.

Answer 5

Intrigued by the notion in other posts and comments that there might be solutions to this problem involving Hamiltonian paths, I wrote a program to do breadth-first enumeration of such paths for the 3x3x3 case, and got some interesting results. One nice aspect is that on bipartite graphs, no checking for divisibility by 2 of adjacent pairs is needed, and as a result the number of divisibility checks is halved (so vertices labeled 3 and 9 will never be adjacent).

The results are unverified; the current output is

! 1145801 -19-22-25-26-23-20-21-24-27-18-15-12-3-6-9-8-17-14-11-10-13-16-7-4-1-2-5-

! 1145802 -21-24-27-26-23-20-19-22-25-16-13-10-1-4-7-8-17-14-11-12-15-18-9-6-3-2-5-

! 1145803 -19-22-25-26-23-20-21-24-27-18-15-12-3-6-9-8-7-4-1-10-13-16-17-14-11-2-5-

! 1145804 -21-24-27-26-23-20-19-22-25-16-13-10-1-4-7-8-9-6-3-12-15-18-17-14-11-2-5-

! 1145805 -21-24-27-18-15-12-3-6-9-8-7-4-1-10-13-16-25-22-19-20-23-26-17-14-11-2-5-

! 1145806 -19-22-25-16-13-10-1-4-7-8-9-6-3-12-15-18-27-24-21-20-23-26-17-14-11-2-5-

where the output corresponds to a path based on my enumeration of the vertices. Solution 1145801 corresponds to:

3 2 15 # 8 9 16 # 27 22 21

4 1 14 # 7 10 17 # 26 23 20

5 12 13 # 6 11 18 # 25 24 19

I have not checked all the results, but I believe there are 4 non-isomorphic solutions, all starting with 1 in the middle of the bottom square. I invite verification of this. I also took some statistics on paths of intermediate lengths. I can't properly normalize them, but they suggest interesting growth patterns which are likely a consequence of the gcd restriction. I wonder if growth patterns from such enumerations of partial structures have been studied, and if a solution can be predicted from such growth patterns. In particular, can one predict that there would be a small number of nonisomorphic solutions in this case.

Based on other small examples, I have found Hamilton path enumerations for all of them and would like to see a conjecture on (the shape of parameters for) a grid graph that has a solution which is non Hamiltonian, and no Hamiltonian solutions.

I will update this with some more results.

Update 1: It turns out there are three distinct solutions, all with a terminating 3x3x1 block containing the numbers 19 through 27. The basic problem is in enumerating a 3x3x2 block with the numbers 1 through 18 that allows the last "layer" to be added. Also, a (2x3x1) layer is involved which contains the numbers 13-18 or 12-17. I suspect an approach similar to nsrt's modified for Hamilton paths may show that nx3x3 enumerations will exist for n sufficiently large, as one may be able to arrange layers so that all small (and thus all) gcd relations are observed. I suspect the answer to the original question for three dimensions will be yes, and in a Hamiltonian fashion. It should not be too hard in addition to find conditions on bipartite graphs (e.g. degree conditions) which would constitute obstructions to a coprime Hamiltonian labelling. Indeed, one of the 3x3x3 solutions has a path in a 2x3x3 subgraph which is extendable to a cycle (so 1 and 18 are adjacent in this solution).

Update 2014.04.10: An unverified run suggests there are NO Hamilton path solutions for the 4x4x2 brick. After adding code to detect multiple vertices not yet on the path with only one neighbor, the search visited a little over 1.27 million candidates before failing to find a compatible path of length 30, much less one of length 32. I am now considering an argument involving configurations of numbers divisible by 3 in a potential path in order to get a combinatorial proof of impossibility. It is easy to determine that a 2x2x2 corner section has either 2 or 3 such numbers, and in the case of three, they must all be the same parity. However I have not completed it to show impossibility. If I do, this is the first example (4,4,2) I know which would have only non Hamiltonian solutions.

Gerhard "Ask Me About Sloppy Coding" Paseman, 2014.04.07

Answer 6

This is not an answer, but a braindump of things that came up today (mainly focussing on the two-dimensional case, but most of it generalises to higher dimensions):

• In a random configuration approximately $\frac{6}{\pi^2} \approx 61\%$ of the adjacent cubes are coprime.

One can consider groups that naturally act on the set $C$ of configurations (such that they respect the property of a configuration being correct).

• Obviously the symmetry group of the square ($D_{4}$) acts on this set $C$.
• If $P$ denotes the set of primes $p$ such that $\frac{1}{2}n^{2} < p < n^{2}$, then $\mathrm{Sym}(P \cup \{1\})$ acts on $C$. (All numbers $1, \ldots, n^{2}$ are coprime to elements of $P \cup \{1\}$; hence we can permute this elements in a given solution.)
• Let $\mathrm{rad} \colon \{1, \ldots, N\} \to \mathbb{N}$ denote the radical function, taking $\prod_{i} p_{i}^{e_{i}}$ to $\prod_{i: e_{i}>0} p_{i}$. This function defines a partition on $\{1, \ldots, N\}$. Let $\mathrm{R}^N_{r} = \mathrm{rad}^{-1}(r)$ denote such a partition. Then $\mathrm{Sym}(\mathrm{R}^{n^2}_{r})$ acts on $C$. (This is because to numbers are coprime iff their radicals are coprime.)

I do not know a good way of estimating the size of $\mathrm{R}^{N}_{r}$, or more precisely:

Given $N$, what is (approximately) the size of the largest $\mathrm{R}^{N}_{r}$?

These groups show that there is essentially a unique solution are essentially $4$ solutions (thanks @Carl!) for the $3 \times 3$ problem. One has:

• $P \cup \{1\} = \{1,5,7\}$
• $\mathrm{R}_{2} = \{2,4,8\}$

• $\mathrm{R}_{3} = \{3,9\}$.

  1. By the parity condition mentioned in the comments, $6$ has to be at the middle of an edge, First consider the case that $6$ is at the middle of an edge, and by the $D_{4}$-action, it does not matter which edge we choose. Next, we place $2,4,8$ on the other middles of edges. Then, $3,9$ go in the corners not adjacent to $6$. Finally $P \cup \{1\}$ is placed in the remaining squares.

  2. Next, observe that $6$ cannot be in the middle of the $3 \times 3$ square. After all, $\mathrm{R}_{2} \cup \mathrm{R}_{3}$ cannot be adjacent to $6$, but we can't fit those $5$ elements in the $4$ corners.

  3. This leaves us with the case that $6$ is in a corner, say $(1,1)$. Observe that we cannot place an element of $\mathrm{R}_{2}$ in $(2,3)$ or $(3,2)$. Up to the aforementioned symmetries, this leaves us with $3$ possible configurations to place $\mathrm{R}_{2}$ in the squares $\{ (1,3), (2,2), (3,1), (3,3) \}$. In all cases $\mathrm{R}_{3}$ have to be placed in the squares $\{ (2,3), (3,2) \}$. The remaining squares are filled with $P \cup \{1\}$.

---

Ok, got to leave now. Hope this helps someone.