Wir definieren $V(x)$ als die Liste der unterschiedlichen Potenzen von $2$ , die sich zu summieren $x$. Zum Beispiel ist $V(35)=[32,2,1]$ .

Gemäß der Konvention werden die Kräfte hier vom höchsten zum niedrigsten Wert sortiert. Dies hat jedoch keinen Einfluss auf die Logik der Herausforderung und die erwarteten Lösungen.

Aufgabe

Ersetzen Sie bei einem Semiprime $N$ jeden Term in $V(N)$ durch eine andere Liste von Potenzen von $2$ , die sich zu diesem Term summieren, so dass die Vereinigung aller resultierenden Teillisten eine exakte Abdeckung der Matrix $M$ definiert ist als:

wobei und Q die Primfaktoren von N sind .$P$$Q$$N$

Dies ist anhand einiger Beispiele viel einfacher zu verstehen.

Beispiel 1

Für haben wir:$N=21$

• $V(N)=[16,4,1]$
• und V ( P ) = [ 4 , 2 , 1 $P=7$$V(P)=[4,2,1]$
• und V ( Q ) = [ 2 , 1 $Q=3$$V(Q)=[2,1]$
• $M=\pmatrix{8&4&2\\4&2&1}$

Um in eine exakte Abdeckung von M zu verwandeln , können wir 16 in 8 + aufteilen$V(N)$$M$$16$ und 4 in 2 + 2, während 1 unverändert bleibt. Eine mögliche Ausgabe ist also:$8+4+4$$4$$2+2$$1$

Eine andere gültige Ausgabe ist:

Beispiel # 2

Für haben wir:$N=851$

• $V(N)=[512,256,64,16,2,1]$
• und V ( P ) = [ 32 , 4 , 1 $P=37$$V(P)=[32,4,1]$
• und V ( Q ) = [ 16 , 4 , 2 , 1 $Q=23$$V(Q)=[16,4,2,1]$
• $M=\pmatrix{512&64&16\\128&16&4\\64&8&2\\32&4&1}$

Eine mögliche Ausgabe ist:

Regeln

• Da das Faktorisieren von nicht der Hauptteil der Herausforderung ist, können Sie alternativ P und Q als Eingabe verwenden.$N$$P$$Q$
• Wenn mehrere mögliche Lösungen vorhanden sind, können Sie entweder nur eine oder alle zurückgeben.
• Sie können alternativ die Exponenten der Potenzen (z. B. anstelle von [ [ 8 , $[[3,2,2],[1,1],[0]]$ ).$[[8,4,4],[2,2],[1]]$
• Die Reihenfolge der Unterlisten spielt keine Rolle, ebenso die Reihenfolge der Begriffe in jeder Unterliste.
• Für einige Semiprimes müssen Sie keinen Begriff teilen, da bereits eine perfekte Abdeckung von M ist (siehe A235040 ). Sie müssen jedoch noch eine Liste von (Singleton-) Listen zurückgeben, z. B. [ [ 8 ] , [ 4 ] $V(N)$$M$ für N = 15 zurückgeben .$[[8],[4],[2],[1]]$$N=15$
• Das ist Code-Golf !

Testfälle

 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 ] ]

K (NGN / k) , 66 63 Bytes

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

Probieren Sie es online!

akzeptiert (P; Q) anstelle von N

Algorithmus:

• berechne A als die Teilsummen von V (P * Q)

• multiplizieren Sie jedes V (P) mit jedem V (Q), sortieren Sie die Produkte in absteigender Reihenfolge (nennen wir das R) und berechnen Sie ihre Teilsummen B

• finde die Positionen der Elemente in B, die auch in A vorkommen; schneiden Sie R direkt nach diesen Positionen

Gelee , 24 Bytes

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

Ein monadischer Link, der eine Liste mit zwei ganzen Zahlen akzeptiert, [P, Q]was eine mögliche Liste von Listen ergibt, wie in der Frage beschrieben.

Probieren Sie es online!(Die Fußzeile gibt eine Zeichenfolgendarstellung aus, um die Liste so anzuzeigen, wie sie wirklich ist.)

Oder schauen Sie sich die Testsuite an (eine Liste von N nehmen und die Ergebnisse neu anordnen, damit sie denen in der Frage entsprechen).

Wie?

Wir können die Elemente von von der niedrigsten bis zur gierigsten aufteilen (entweder gibt es eine 1 in M oder wir hatten eine Eingabe von 4 , wenn M = [ [ 4 ] $M$$1$$M$$4$$M=[[4]]$ ), um eine Lösung zu finden.

^{Hinweis: Der Code fasst alle (eine!) Derartigen Lösungen in einer Liste zusammen und nimmt dann das (einzige) Kopfergebnis auf - dh der endgültige Kopf ist erforderlich, da die Partitionen nicht von allen möglichen Ordnungen sind.}

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

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

Probieren Sie es online!

1 Byte von Jo King ; und ein weiteres Byte von Kevin Cruijssen .

Nimmt als Eingabe p,q. Verfolgt den gierigen Algorithmus.

Jelly , 41 Bytes

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

Probieren Sie es online!

ÇIP$Ƈ$[P, Q]$

Jelly , 34 Bytes

BṚT’2*
PÇŒṗæḟ2⁼ƊƇ€ŒpẎṢ⁼Ṣ}ʋƇÇ€×þ/ẎƊ

Probieren Sie es online!

Eingabeformat: [P, Q] (der TIO-Link oben akzeptiert dies nicht, sondern eine einzelne Zahl, um die Testfälle zu vereinfachen).

Ausgabeformat: Liste aller Lösungen (als Rasterdarstellung der 3D-Liste über TIO dargestellt).

Geschwindigkeit: Schildkröte.

Pyth , 27 Bytes

Inspiriert von Jonathan Allans Zerkleinerung meiner Jelly-Lösung . Nimmt$N$ als Eingabe.

L^2x1jb2;hfqyQsMT./S*M*FyMP

Probieren Sie es hier aus!

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))