Produkte, die einer Summe entsprechen und umgekehrt

22

Ein lustiges Äquivalenzpaar ist 1 + 5 = 2 · 3 und 1 · 5 = 2 + 3 . Es gibt viele wie diese, eine andere ist 1 + 1 + 8 = 1 · 2 · 5 und 1 · 1 · 8 = 1 + 2 + 5 . Im Allgemeinen entspricht ein Produkt von n positiven Ganzzahlen einer Summe von n positiven Ganzzahlen und umgekehrt.

In dieser Challenge müssen Sie alle diese Kombinationen positiver Ganzzahlen für eine Eingabe n> 1 mit Ausnahme von Permutationen generieren . Sie können diese in jedem vernünftigen Format ausgeben. Zum Beispiel sind alle möglichen Lösungen für n = 3 :

(2, 2, 2) (1, 1, 6)
(1, 2, 3) (1, 2, 3)
(1, 3, 3) (1, 1, 7)
(1, 2, 5) (1, 1, 8)

Das Programm, das auf meinem 64-Bit-Intel-Ubuntu-Laptop mit 2 GB RAM die meisten Kombinationen für die höchsten n in einer Minute generiert, gewinnt. Wenn Ihre Antwort mehr als 2 GB RAM belegt oder in einer Sprache verfasst ist, die ich mit frei verfügbarer Software nicht testen kann, werde ich Ihre Antwort nicht bewerten. Ich werde die Antworten in zwei Wochen testen und den Gewinner auswählen. Später nicht konkurrierende Antworten können natürlich noch gepostet werden.

Da nicht bekannt ist, wie viele Lösungen für alle n vollständig sind, können Sie Antworten veröffentlichen, die unvollständige Lösungen generieren. Wenn jedoch eine andere Antwort eine (vollständigere) Lösung erzeugt, gewinnt diese Antwort , selbst wenn ihr Maximum n kleiner ist.


Zur Verdeutlichung folgt der Bewertungsprozess, um den Gewinner zu bestimmen:

  1. Ich werde Ihr Programm mit n = 2, n = 3 usw. testen. Ich speichere alle Ihre Ausgaben und stoppe, wenn Ihr Programm mehr als eine Minute oder mehr als 2 GB RAM benötigt. Jedes Mal, wenn das Programm für eine bestimmte Eingabe n ausgeführt wird, wird es beendet, wenn es länger als 1 Minute dauert.

  2. Ich schaue mir alle Ergebnisse für alle Programme für n = 2 an. Wenn ein Programm weniger gültige Lösungen liefert als ein anderes, wird dieses Programm eliminiert.

  3. Wiederholen Sie Schritt 2 für n = 3, n = 4 usw. Das letzte stehende Programm gewinnt.

orlp
quelle
1
Also keine Antworten in Windows-exklusiven Sprachen?
Conor O'Brien
3
Persönlich mag ich die Bewertungskriterien nicht. Es ist unmöglich zu wissen, ob unsere Lösungen funktionieren und wo die Schwellenwerte festgelegt werden müssen, bis die Ergebnisse der Tests auf Ihrem Computer vorliegen. Ich denke, ein einfaches Code-Golf würde eine bessere Frage stellen.
musicman523
2
Ich gehe davon aus, dass Hardcoding nicht erlaubt ist. Aber dann ist diese Einschränkung so gut wie nicht zu beobachten
Luis Mendo
1
@ user202729 Nein, ich muss jedes Programm für jedes n ausprobieren, um zu sehen, welches Programm mehr Lösungen generiert.
Orlp
2
"In zwei Wochen" ist 3 Tage her.
GB

Antworten:

4

C (gcc) , n = 50000000 mit 6499 ergibt 59 s

Um zu vermeiden, dass mehr als ein Terabyte Ausgabe erzeugt wird, die fast nur aus 1 besteht, wird eine Folge von (beispielsweise) 49999995 1s mit abgekürzt 1x49999995.

#include <stdio.h>
#include <stdlib.h>

static int n, *a1, k1 = 0, *a2, k2 = 0, s1, p1, *factor;

static void out() {
  if (s1 == p1) {
    for (int i = 0; i < k1 && i < k2; i++) {
      if (a1[i] < a2[i])
        return;
      else if (a1[i] > a2[i])
        break;
    }
  }

  for (int i = 0; i < k1; i++)
    printf("%d ", a1[i]);
  printf("1x%d | ", n - k1);
  for (int i = 0; i < k2; i++)
    printf("%d ", a2[i]);
  printf("1x%d\n", n - k2);
}

static void gen2(int p, int s, int m);

static void gen3(int p, int s, int m, int x, int q) {
  int r = s - n + k2 + 2;
  int d = factor[q];
  do {
    if (x * d <= m)
      x *= d;
    q /= d;
  } while (q % d == 0);
  do {
    if (q == 1) {
      a2[k2++] = x;
      gen2(p / x, s - x, x);
      k2--;
    } else {
      gen3(p, s, m, x, q);
    }
    if (x % d != 0)
      break;
    x /= d;
  } while (p / (x * q) >= r - x * q);
}

static void gen2(int p, int s, int m) {
  int n2 = n - k2;
  if (p == 1) {
    if (s == n2)
      out();
  } else if (n2 >= 1 && m > 1) {
    int r = s - n2 + 1;
    if (r < 2 || p < r)
      return;
    if (m > r)
      m = r;
    if (factor[p] <= m)
      gen3(p, s, m, 1, p);
  }
}

static void gen1(int p, int s, int m) {
  int n1 = n - k1;
  p1 = p;
  s1 = s + n1;
  gen2(s1, p1, s + n1 + 1 - n);
  if (n1 != 0) {
    int *p1 = &a1[k1++];
    for (int x = 2; x <= m && p * x <= s + x + n1 - 1; x++) {
      *p1 = x;
      gen1(p * x, s + x, x);
    }
    k1--;
  }
}

int main(int argc, char **argv) {
  if (argc < 2)
    return 1;
  n = atoi(argv[1]);
  if (n < 2)
    return 1;
  a1 = malloc(n * sizeof(int));
  a2 = malloc(n * sizeof(int));
  factor = calloc(4 * n - 1, sizeof(int));
  for (int p = 2; p < 4 * n - 1; p++)
    if (factor[p] == 0) {
      factor[p] = p;
      for (int i = p; i <= (4 * n - 2) / p; i++)
        factor[p * i] = p;
    } else if (factor[p] < factor[p / factor[p]]) {
      factor[p] = factor[p / factor[p]];
    }
  gen1(1, 0, 3 * n - 1);
  return 0;
}

Probieren Sie es online!

Anders Kaseorg
quelle
3

Mathematica, n = 293 mit 12 Lösungen

OP hat die Herausforderung geändert und fragt nach Eingabe.
Hier ist der neue Code, der ein beliebiges n als Eingabe akzeptiert.
Für n = 293 erhalten Sie die 12 Lösungen

If[#<5,Union[Sort/@Select[Tuples[{1,2,3,4,5,6,7,8,9},{#}],Tr@#==Times@@#&]],For[a=1,a<3,a++,For[b=a,b<3,b++,For[c=b,c<5,c++,For[d=c,d<10,d++,For[e=d,e<300,e++,If[Tr[s=Join[Table[1,#-5],{a,b,c,d,e}]]==Times@@s,Print[s]]]]]]]]&


Eingang

[n]

Sie können diesen Algorithmus auf Wolfram Sandbox testen, einer online frei verfügbaren Software.
Folgen Sie einfach dem Link, fügen Sie den Code ein (Strg + V), fügen Sie die Eingabe am Ende des Codes ein und drücken Sie Umschalt + Eingabetaste, um die Anwendung auszuführen.
Sie erhalten alle meine Lösungen in Sekunden

Hier geht es auch online! in C ++ (gcc)
(Vielen Dank an @ThePirateBay für die Unterstützung und Übersetzung meines Codes in eine freie Sprache)

Dieses Programm erzeugt nur Lösungen der Form {a, b, c} {a, b, c},
was a + b + c = a * b * c bedeutet

Die Berechnung dauert 1 Sekunde

Die zwölf Lösungen sind:

{1,1 ..., 1,1,1,2,293} {1,1 ..., 1,1,1,293}
{1,1 ..., 1,1,1,3,147} {1 , 1 ..., 1,1,1,3,147}
{1,1 ..., 1,1,1,5,74} {1,1 ..., 1,1,1,5,74}
{1,1 ..., 1,1,2,2,98} {1,1 ..., 1,1,2,2,98}
{1,1 ..., 1,1,2, 3,59} {1,1 ..., 1,1,2,3,59}
{1,1 ..., 1,1,2,5,33} {1,1 ..., 1, 1,2,5,33}
{1,1 ..., 1,1,2,7,23} {1,1 ..., 1,1,2,7,23}
{1,1 .. ., 1,1,2,8,20} {1,1 ..., 1,1,2,8,20}
{1,1 ..., 1,1,3,3,37} {1 , 1 ..., 1,1,3,3,37}
{1,1 ..., 1,1,3,4,27} {1,1 ..., 1,1,3,4, 27}
{1,1 ..., 1,1,3,7,15} {1,1 ..., 1,1,3,7,15}
{1,1 ..., 1,2, 2,6,13} {1,1 ..., 1,2,2,6,13}

J42161217
quelle
1
"Wenn Ihre [...] Antwort in einer Sprache verfasst ist, die ich mit frei verfügbarer Software nicht testen kann, werde ich Ihre Antwort nicht bewerten."
Undichte Nonne
4
@ GB "Sie dürfen Antworten veröffentlichen, die unvollständige Lösungen generieren"
user202729
1
Mein Programm "..generiert die meisten Kombinationen für die höchsten n in einer Minute". Es ist nicht fest codiert. Es findet nur die ersten 12 "einfachsten" Lösungen in
weniger als
1
Es könnte klarer sein, dass n eine Eingabe sein sollte. Das habe ich jetzt geklärt. Es scheint nicht, dass Ihr Programm eine Eingabe n annimmt .
Orlp
2
@orlp behoben! Mein Programm nimmt ein beliebiges n als Eingabe. Für n = 293 erhalten Sie die 12 Lösungen. bitte abstimmen wenn da alles klappt!
J42161217
2

Python 2 , n = 175, 28 ergibt 59s

Es wurde mit einem Reduktionsfaktor von 2 etwas langsamer gemacht, es werden jedoch mehr Lösungen ab n = 83 erhalten

Ich erhalte Ergebnisse für n bis zu 92 bei TIO in einem einzigen Lauf.

def submats(n, r):
    if n == r:
        return [[]]
    elif r > 6:
        base = 1
    else:
        base = 2
    mx = max(base, int(n*2**(1-r)))

    mats = []
    subs = submats(n, r+1)
    for m in subs:
        if m:
            mn = m[-1]
        else:
            mn = 1
        for i in range(mn, mx + 1):
            if i * mn < 3*n:
                mats += [m + [i]]
    return mats

def mats(n):
    subs = []
    for sub in submats(n, 0):
        sum = 0
        prod = 1
        for m in sub:
            sum += m
            prod *= m
        if prod > n and prod < n*3:
            subs += [[sub, sum, prod]]
    return subs

def sols(n):
    mat = mats(n)
    sol = [
        [[1]*(n-1)+[3*n-1],[1]*(n-2)+[2,2*n-1]],
    ]
    if n > 2:
        sol += [[[1]*(n-1)+[2*n+1],[1]*(n-2)+[3,n]]]
    for first in mat:
        for second in mat:
            if first[2] == second[1] and first[1] == second[2] and [second[0], first[0]] not in sol:
                sol += [[first[0], second[0]]];
    return sol

Probieren Sie es online!

GB
quelle
1
"behalte 5 Elemente [1..2] und beschränke 3n ..." Ich bin froh, dass dir mein Algorithmus gefallen hat
;-)
Ich habe bereits in der Ruby-Version etwas Ähnliches gemacht, und jetzt versuche ich, diese Einschränkung aufzuheben.
GB
Wie viele Lösungen sind für ein gegebenes n in Ihrem Algorithmus fest codiert?
J42161217
Nicht wirklich hartcodiert: Mit einer Verknüpfung können 2 Standardlösungen generiert werden (außer n = 2, wenn sie dieselbe Kombination sind). Wenn Sie diese überspringen, kann der Bereich auf 2n anstatt auf 3n begrenzt werden. Wenn dies als hartcodiert gilt, werde ich es ändern.
GB
1
Für 61 würde mein Ergebnis 28 sein. Ich erinnere mich, dass es 27 ist. Möglicherweise habe ich einen Fehler gemacht
RosLuP
1

Ruby , n = 12 ergibt 6 Lösungen

Zumindest auf TIO, übliche Ergebnisse für 1 bis 11

->n{
  arr=[*1..n*3].product(*(0..n-2).map{|x|
    [*1..[n/3**x,2].max]|[1]
  }).select{|a|
    a.count(1) >= n-4
  }.map(&:sort).uniq
  arr.product(arr).map(&:sort).uniq.select{|r|
    r[0].reduce(&:+) == r[1].reduce(&:*) &&
    r[0].reduce(&:*) == r[1].reduce(&:+)
  }
}

Probieren Sie es online!

Erhält 10 Ergebnisse unter einer Minute für n = 13 auf meinem Laptop.

GB
quelle
1

Mathematica, n = 19 mit 11 Lösungen

Das ist meine neue Antwort nach den neuen Kriterien von OP

(SOL = {};
For[a = 1, a < 3, a++, 
For[b = a, b < 3, b++, 
For[c = b, c < 5, c++, 
 For[d = c, d < 6, d++, 
  For[e = d, e < 3#, e++, 
   For[k = 1, k < 3, k++, 
    For[l = k, l < 3, l++, 
     For[m = l, m < 5, m++, 
      For[n = m, n < 6, n++, For[o = n, o < 3#, o++,
        s = Join[Table[1, # - 5], {a, b, c, d, e}];
        t = Join[Table[1, # - 5], {k, l, m, n, o}];            
        If[Tr[s[[-# ;;]]] == Times @@ t[[-# ;;]] && 
          Tr[t[[-# ;;]]] == Times @@ s[[-# ;;]], 
         AppendTo[SOL,{s[[-#;;]],t[[-#;;]]}]]]]]]]]]]]];
Union[SortBy[#,Last]&/@SOL])&

Wenn Sie am Ende eine Eingabe [n] eingeben, zeigt das Programm die Lösungen an

Hier sind meine Ergebnisse (auf meinem alten Laptop 64-Bit 2,4 GHz)

n -> Lösungen
2 -> 2
3 -> 4
4 -> 3
5 -> 5
6 -> 4
7 -> 6
8 -> 5
9 -> 7
10 -> 7
11 -> 8
12 -> 6 (in 17 Sekunden)
13 -> 10 (in 20 Sekunden)
14 -> 7 (in 25 Sekunden)
15 -> 7 (in 29 Sekunden)
16 -> 9 (in 34 Sekunden)
17 -> 10 (in 39 Sekunden)
18 - > 9 (in 45 Sekunden)
19 -> 11 (in 51 Sekunden)
20 -> 7 (in 58 Sekunden)

J42161217
quelle
1

Haskell, viele Lösungen schnell

import System.Environment

pr n v = prh n v v

prh 1 v l = [ [v] | v<=l ]
prh n 1 _ = [ take n $ repeat 1 ]
prh _ _ 1 = []
prh n v l = [ d:r | d <-[2..l], v `mod` d == 0, r <- prh (n-1) (v`div`d) d ]

wo n v = [ (c,k) | c <- pr n v, let s = sum c, s>=v,
                   k <- pr n s, sum k == v, s>v || c>=k ]

f n = concatMap (wo n) [n+1..3*n]

main = do [ inp ] <- getArgs
          let results = zip [1..] $ f (read inp)
          mapM_ (\(n,s) -> putStrLn $ (show n) ++ ": " ++ (show s)) results

fBerechnet die Lösungen, mainfügt die Funktion hinzu, die Eingabe von der Befehlszeile und einige Formatierungen und Zählungen zu erhalten.

Christian Sievers
quelle
Kompilieren Sie wie ghc -O3 -o prodsum prodsum.hsfolgt : und führen Sie das Kommandozeilenargument aus:./prodsum 6
Christian Sievers
0

Haskell , n = 10 mit 2 Lösungen


import           Data.List

removeDups = foldl' (\seen x -> if x `elem` seen then seen else x : seen) []
removeDups' = foldl' (\seen x -> if x `elem` seen then seen else x : seen) []

f n= removeDups $ map sort filterSums
  where maxNumber = 4
        func x y = if (((fst x) == (fst.snd$y)) && ((fst y) == (fst.snd$x)))
                     then [(snd.snd$x),(snd.snd$y)]
                     else [[],[]]
        pOf = removeDups' $ (map sort (mapM (const [1..maxNumber]) [1..n]))
        sumOf = map (\x->((sum x),((product x), x))) pOf
        filterSums = filter (\x-> not$(x == [[],[]])) (funcsumOfsumOf)

Das funktioniert wie Scheiße, aber ich habe es zumindest behoben, sodass ich mich jetzt der Herausforderung annehme!

Probieren Sie es online!

maple_shaft
quelle
für n = 2 erhält man ["[3,3] [2,3]", [2,2] [2,2] "," [1,3] [2,2] "," [1, 2] [1,3] "," [1,1] [1,2] "], was falsch ist
J42161217
Alle Lösungen scheinen tatsächlich falsch zu sein
GB
@Jenny_mathy Wie ist es falsch? 3 + 3 ist 6 und 2 * 3 ist 6. Verstehe ich die Frage falsch?
maple_shaft
Ihnen fehlt die "umgekehrt"
J42161217
@Jenny_mathy Blöder Fehler meinerseits! Ich habe es behoben, sollte jetzt funktionieren.
maple_shaft
0

Axiom, n = 83 in 59 Sekunden hier

-- copy the below text in the file name "thisfile.input" 
-- and give something as the command below in the Axiom window:
-- )read C:\Users\thisuser\thisdirectory\thisfile

)cl all
)time on

-- controlla che l'array a e' formato da elementi  a.i<=a.(i+1)
tv(a:List PI):Boolean==(for i in 1..#a-1 repeat if a.i> a.(i+1) then return false;true)

-- funzione incremento: incrementa a, con #a=n=b/3,sotto la regola di "reduce(+,a)+#a-1>=reduce(*,a)"
-- e che n<reduce(*,a)<3*n ed reduce(+,a)<3*n 
inc3(a:List PI):INT==
   i:=1; n:=#a; b:=3*n
   repeat
      if i>n  then return 0
      x:=reduce(*,a)
      if x>=b then a.i:=1
      else
          y:=reduce(+,a)
          if y>b then a.i=1
          else if y+n-1>=x then
                      x:=x quo a.i
                      a.i:=a.i+1
                      x:=x*a.i
                      if tv(a) then break
                      else a.i:=1
          else a.i:=1
      i:=i+1
   if x<=n then return inc3(a) -- x<=n non va
   x

-- ritorna una lista di liste di 4 divisori di n
-- tali che il loro prodotto e' n
g4(n:PI):List List PI==
  a:=divisors(n)
  r:List List PI:=[]
  for i in 1..#a repeat
     for j in i..#a repeat
        x:=a.i*a.j
        if x*a.j>n then break
        for k in j..#a repeat
            y:=x*a.k
            if y*a.k>n then break
            for h in k..#a repeat
                z:=y*a.h
                if z=n  then r:=cons([a.h,a.k,a.j,a.i],r)
                if z>=n then break 
  r

-- ritorna una lista di liste di 3 divisori di n
-- tali che il loro prodotto e' n
g(n:PI):List List PI==
  a:=divisors(n)
  r:List List PI:=[]
  for i in 1..#a repeat
     for j in i..#a repeat
        x:=a.i*a.j
        if x*a.j>n then break
        for k in j..#a repeat
            y:=x*a.k
            if y=n  then r:=cons([a.k,a.j,a.i],r)
            if y>=n then break
  r

-- cerca che [a,b] nn si trovi gia' in r
searchr(r:List List List PI,a:List PI,b:List PI):Boolean==
  aa:=sort(a); bb:=sort(b)
  for i in 1..#r repeat
      x:=sort(r.i.1);y:=sort(r.i.2)
      if x=aa and y=bb then return false
      if x=bb and y=aa then return false
  true

-- input n:PI
-- ritorna r, tale che se [a,b] in r
-- allora #a=#b=n
--        ed reduce(+,a)=reduce(*,b) ed reduce(+,b)=reduce(*,a)
f(n:PI):List List List PI==
  n>100000 or n<=1 =>[]
  a:List PI:=[]; b:List PI:=[]; r:List List List PI:=[]
  for i in 1..n repeat(a:=cons(1,a);b:=cons(1,b))
  if n~=72 and n<86 then  m:=min(3,n)
  else                    m:=min(4,n) 
  q:=reduce(*,a) 
  repeat
    w:=reduce(+,a)
    if n~=72 and n<86 then x:= g(w)
    else                   x:=g4(w)
    if q=w then r:=cons([copy a, copy a],r)
    for i in 1..#x repeat
           for j in 1..m repeat
                  b.j:=(x.i).j
           -- per costruzione abbiamo che reduce(+,a)= prodotto dei b.i=reduce(*,b)
           -- manca solo di controllare che reduce(+,b)=reduce(*,a)=q
           if reduce(+,b)=q and searchr(r,a,b) then r:=cons([copy a, copy b],r)
    q:=inc3(a)
    if q=0 then break
  r

Ergebnisse:

 for i in 2..83 repeat output [i, # f(i)]
   [2,2][3,4][4,3][5,5][6,4][7,6][8,5][9,7][10,7][11,8][12,6][13,10][14,7][15,7]
   [16,10][17,10][18,9][19,12][20,7][21,13][22,9][23,14][24,7][25,13][26,11]
   [27,10][28,11][29,15][30,9][31,16][32,11][33,17][34,9][35,9][36,13][37,19]
   [38,11][39,14][40,12][41,17][42,11][43,20][44,12][45,16][46,14][47,14][48,13]
   [49,16][50,14][51,17][52,11][53,20][54,15][55,17]
   [56,14][57,20][58,17][59,16][60,15][61,28][62,15][63,16][64,17][65,18]
   [66,14][67,23][68,20][69,19][70,13][71,18][72,15][73,30][74,15][75,17][76,18]
   [77,25][78,16][79,27][80,9][81,23][82,17][83,26]


 f 3
    [[[1,2,5],[8,1,1]],[[1,3,3],[7,1,1]],[[1,2,3],[1,2,3]],[[2,2,2],[6,1,1]]]
                                     Type: List List List PositiveInteger
                                   Time: 0.07 (IN) + 0.05 (OT) = 0.12 sec

Die Möglichkeit, Text in Axiom zu überschreiben, besteht darin, den gesamten Text in eine Datei zu kopieren und die Datei unter folgendem Namen zu speichern: Name.input. Verwenden Sie in einem Axiom-Fenster ") read absolutepath / Name".
Ergebnisse: (# f (i) ermittelt die Länge des Arrays f (i), dh die Anzahl der Lösungen)

RosLuP
quelle