# Split the bits!

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.

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],]$ instead of $[[8,4,4],[2,2],]$).
• 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 $[,,,]$ for $N=15$.
• This is !

### 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
Aug 6, 2018 at 15:29
• @ngn I'm going to say yes, because factorizing N is not the main part of the challenge. Aug 6, 2018 at 15:33
• May we return the output flattened? Aug 6, 2018 at 19:06
• @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 Aug 6, 2018 at 19:08
• @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. Aug 6, 2018 at 19:08

# K (ngn/k), 66 63 bytes

{(&1,-1_~^(+\*|a)?+\b)_b:b@>b:,/*/:/2#a:{|*/'(&|2\x)#'2}'x,*/x}


Try it online!

algorithm:

• compute A as the partial sums of V(P*Q)

• multiply each V(P) with each V(Q), sort the products in descending order (let's call that R), and compute their partial sums B

• find the positions of those elements in B that also occur in A; cut R right after those positions

# Jelly, 24 bytes

BṚT’2*
Ç€×þ/FṢŒṖ§⁼Ç}ɗƇPḢ


A monadic link accepting a list of two integers [P, Q] which yields one possible list of lists as described in the question.

Try it online! (footer prints a string representation to show the list as it really is)

Or see the test-suite (taking a list of N and reordering results to be like those in the question)

### How?

We may always slice up the elements of $M$ from lowest up, greedily (either there is a $1$ in $M$ or we had an input of $4$, when $M=[]$) in order to find a solution.

Note: the code collects all (one!) such solutions in a list and then takes the head (only) result - i.e. the final head is necessary as the partitions are not of all possible orderings.

BṚT’2* - Link 1, powers of 2 that sum to N: integer, N    e.g. 105
B      - binary                                                [1,1,0,1,0,0,1]
Ṛ     - reverse                                               [1,0,0,1,0,1,1]
T    - truthy indices                                        [1,4,6,7]
’   - decrement                                             [0,3,5,6]
2  - literal two                                           2
* - exponentiate                                          [1,8,32,64]

Ç€×þ/FṢŒṖ§⁼Ç}ɗƇPḢ - Main Link: list of two integers, [P,Q]
/             - reduce with:
þ              -   table with:
×               -     multiplication
F            - flatten
Ṣ           - sort
ŒṖ         - all partitions
Ƈ   - filter keep if:
§        -     sum each
}     -     use right...
P  -       ...value: product (i.e. P×Q)
⁼       -     equal? (non-vectorising so "all equal?")


# Python 2, 261233232 231 bytes

g=lambda n,r=[],i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
V=[[v]for v in g(p*q)];i=j=0
for m in sorted(-a*b for a in g(p)for b in g(q)):
v=V[i]
while-m<v[j]:v[j:j+1]=[v[j]/2]*2
i,j=[i+1,i,0,j+1][j+1<len(v)::2]
return V


Try it online!

1 byte from Jo King; and another 1 byte due to Kevin Cruijssen.

Takes as input p,q. Pursues the greedy algorithm.

• -k-1 can be ~k. Aug 7, 2018 at 14:33
• The i,j assignment can be i,j=[i+1,i,0,j+1][j+1<len(v)::2] for -1 byte
– Jo King
Aug 8, 2018 at 7:20
• @Jo King: Hahaha! That is twisted! Aug 8, 2018 at 7:24
• while v[j]>-m can be while-m<v[j] Aug 8, 2018 at 7:29
• @Kevin Cruijssen: Yes, indeed. Thx! Aug 8, 2018 at 7:32

# Jelly, 41 bytes

Œṗl2ĊƑ$Ƈ PÇIP$ƇṪÇ€Œpµ³ÇIP$ƇṪƊ€ŒpZPṢ⁼FṢ$µƇ


Try it online!

Should probably be much shorter (some parts feel very repetitive; especially ÇIP$Ƈ, but I don't know how to golf it). Explanation to come after further golfing. Returns all possible solutions in case multiple exist and takes input as $[P, Q]$. • Not that it is a problem, but it's not exactly fast, is it? :) Aug 6, 2018 at 18:59 • @Arnauld It uses roughly 3 integer partition functions in a single run :) Of course it is not too fast Aug 6, 2018 at 19:04 • Now waiting to be outgolfed. I think it's possible in sub-35/30, but I don't think I'll be able to do anything much shorter Aug 6, 2018 at 19:15 # Jelly, 34 bytes BṚT’2* PÇŒṗæḟ2⁼ƊƇ€ŒpẎṢ⁼Ṣ}ʋƇÇ€×þ/ẎƊ  Try it online! Input format: [P, Q] (the TIO link above doesn't accept this, but a single number instead, to aid with the test cases). Output format: List of all solutions (shown as grid representation of 3D list over TIO). Speed: Turtle. # Pyth, 27 bytes Inspired by Jonathan Allan's crushing of my Jelly solution. Takes $N$ as input. L^2x1jb2;hfqyQsMT./S*M*FyMP  Try it here! # Haskell, 281 195 bytes import Data.List r=reverse.sort n#0=[] n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=[]
m!x=m!!0:tail m!(x-m!!0)
m%[]=[]

• Here are some tips: Defining operators instead of binary functions is cheaper, rearranging guards and pattern-matching can save you (==), use 1>0 instead of True and don't use where. Also n' can be shortened.. With this you can save 72 bytes: Try it online! Aug 7, 2018 at 21:21