17
We define \$V(x)\$ as the list of distinct powers of \$2\$ that sum to \$x\$. For instance, \$V(35)=[32,2,1]\$.
By convention, powers are sorted here from highest to lowest. But it does not affect the logic of the challenge, nor the expected solutions.
Task
Given a semiprime \$N\$, replace each term in \$V(N)\$ with another list of powers of \$2\$ that sum to this term, in such a way that the union of all resulting sub-lists is an exact cover of the matrix \$M\$ defined as:
$$M_{i,j}=V(P)_i \times V(Q)_j$$
where \$P\$ and \$Q\$ are the prime factors of \$N\$.
This is much easier to understand with some examples.
Example #1
For \$N=21\$, we have:
- \$V(N)=[16,4,1]\$
- \$P=7\$ and \$V(P)=[4,2,1]\$
- \$Q=3\$ and \$V(Q)=[2,1]\$
- \$M=\pmatrix{8&4&2\\4&2&1}\$
To turn \$V(N)\$ into an exact cover of \$M\$, we may split \$16\$ into \$8+4+4\$ and \$4\$ into \$2+2\$, while \$1\$ is left unchanged. So a possible output is:
$$[ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]$$
Another valid output is:
$$[ [ 8, 4, 2, 2 ], [ 4 ], [ 1 ] ]$$
Example #2
For \$N=851\$, we have:
- \$V(N)=[512,256,64,16,2,1]\$
- \$P=37\$ and \$V(P)=[32,4,1]\$
- \$Q=23\$ and \$V(Q)=[16,4,2,1]\$
- \$M=\pmatrix{512&64&16\\128&16&4\\64&8&2\\32&4&1}\$
A possible output is:
$$[ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]$$
Rules
- Because factorizing \$N\$ is not the main part of the challenge, you may alternately take \$P\$ and \$Q\$ as input.
- When several possible solutions exist, you may either return just one of them or all of them.
- You may alternately return the exponents of the powers (e.g. \$[[3,2,2],[1,1],[0]]\$ instead of \$[[8,4,4],[2,2],[1]]\$).
- The order of the sub-lists doesn't matter, nor does the order of the terms in each sub-list.
- For some semiprimes, you won't have to split any term because \$V(N)\$ already is a perfect cover of \$M\$ (see A235040). But you still have to return a list of (singleton) lists such as \$[[8],[4],[2],[1]]\$ for \$N=15\$.
- This is code-golf!
Test cases
Input | Possible output
-------+-----------------------------------------------------------------------------
9 | [ [ 4, 2, 2 ], [ 1 ] ]
15 | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
21 | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
51 | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
129 | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
159 | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
161 | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
201 | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
403 | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
851 | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
2307 | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]
can we take P and Q instead of N? – ngn – 2018-08-06T15:29:49.473
@ngn I'm going to say yes, because factorizing N is not the main part of the challenge. – Arnauld – 2018-08-06T15:33:17.123
1May we return the output flattened? – Erik the Outgolfer – 2018-08-06T19:06:36.783
@EriktheOutgolfer ... The output flattened is just a partition of the input (1+2+2+4=9, for example). I don't think it should be allowed – Mr. Xcoder – 2018-08-06T19:08:10.877
@EriktheOutgolfer I don't think it could be unambiguous this way, as the last term of a sub-list may be the same as the first term of the next one. – Arnauld – 2018-08-06T19:08:21.003
@Arnauld It will surely not be, I just asked if it's allowed. – Erik the Outgolfer – 2018-08-06T19:08:59.303
@EriktheOutgolfer So, no it's not. – Arnauld – 2018-08-06T19:09:38.353