17
\$\begingroup\$

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 !

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 ] ]
\$\endgroup\$
  • \$\begingroup\$ can we take P and Q instead of N? \$\endgroup\$ – ngn Aug 6 '18 at 15:29
  • \$\begingroup\$ @ngn I'm going to say yes, because factorizing N is not the main part of the challenge. \$\endgroup\$ – Arnauld Aug 6 '18 at 15:33
  • 1
    \$\begingroup\$ May we return the output flattened? \$\endgroup\$ – Erik the Outgolfer Aug 6 '18 at 19:06
  • \$\begingroup\$ @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 \$\endgroup\$ – Mr. Xcoder Aug 6 '18 at 19:08
  • \$\begingroup\$ @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. \$\endgroup\$ – Arnauld Aug 6 '18 at 19:08
4
\$\begingroup\$

K (ngn/k), 66 63 bytes

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

Try it online!

accepts (P;Q) instead of N

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

\$\endgroup\$
3
\$\begingroup\$

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=[[4]]\$) 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]
Ç€                - call last Link (1) as a monad for €ach
    /             - reduce with:
   þ              -   table with:
  ×               -     multiplication
     F            - flatten
      Ṣ           - sort
       ŒṖ         - all partitions
              Ƈ   - filter keep if:
             ɗ    -   last three links as a dyad:
         §        -     sum each
            }     -     use right...
               P  -       ...value: product (i.e. P×Q)
           Ç      -       ...do: call last Link (1) as a monad
          ⁼       -     equal? (non-vectorising so "all equal?")
                Ḣ - head
\$\endgroup\$
3
\$\begingroup\$

Python 2, 261 233 232 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.

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

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]\$.

\$\endgroup\$
  • \$\begingroup\$ Not that it is a problem, but it's not exactly fast, is it? :) \$\endgroup\$ – Arnauld Aug 6 '18 at 18:59
  • \$\begingroup\$ @Arnauld It uses roughly 3 integer partition functions in a single run :) Of course it is not too fast \$\endgroup\$ – Mr. Xcoder Aug 6 '18 at 19:04
  • \$\begingroup\$ 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 \$\endgroup\$ – Mr. Xcoder Aug 6 '18 at 19:15
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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%[]=[]
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))
\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – ბიმო Aug 7 '18 at 21:21
  • \$\begingroup\$ Btw. you should check out the Haskell tips section if you havent. \$\endgroup\$ – ბიმო Aug 7 '18 at 21:22
  • \$\begingroup\$ I had a look at the guard situation again, another 13 bytes off: Try it online! \$\endgroup\$ – ბიმო Aug 7 '18 at 23:15
  • \$\begingroup\$ @OMᗺ, thank you. I'm new to haskell, so this looks for me as magic tricks \$\endgroup\$ – Евгений Новиков Aug 8 '18 at 7:01
  • \$\begingroup\$ No worries :) In case you have questions, feel free to ask in Of Monads and Men. \$\endgroup\$ – ბიმო Aug 8 '18 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.