Produk yang sama dengan jumlah dan sebaliknya

22

Sepasang persamaan yang menyenangkan adalah 1 + 5 = 2 · 3 dan 1 · 5 = 2 + 3 . Ada banyak seperti ini, yang lain adalah 1 + 1 + 8 = 1 · 2 · 5 dan 1 · 1 · 8 = 1 + 2 + 5 . Secara umum produk n bilangan bulat positif sama dengan jumlah n bilangan bulat positif, dan sebaliknya.

Dalam tantangan ini, Anda harus menghasilkan semua kombinasi bilangan bulat positif untuk input n> 1 , tidak termasuk permutasi. Anda dapat menampilkan ini dalam format apa pun yang masuk akal. Sebagai contoh, semua solusi yang mungkin untuk n = 3 adalah:

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

Program yang dapat menghasilkan kombinasi terbanyak untuk n tertinggi dalam satu menit pada RAM 2GB saya , memenangkan laptop Intel Ubuntu 64-bit. Jika jawaban Anda menggunakan lebih dari 2GB RAM atau ditulis dalam bahasa yang saya tidak dapat menguji dengan perangkat lunak yang tersedia secara bebas, saya tidak akan menilai jawaban Anda. Saya akan menguji jawabannya dalam waktu dua minggu dari sekarang dan memilih pemenangnya. Nanti jawaban yang tidak bersaing masih bisa diposting tentunya.

Karena tidak diketahui apa set lengkap solusi untuk semua n itu, Anda diperbolehkan memposting jawaban yang menghasilkan solusi tidak lengkap. Namun jika jawaban lain menghasilkan solusi lengkap (lebih), bahkan jika n maksimumnya lebih kecil , jawaban itu menang.


Untuk memperjelas, inilah proses penilaian untuk menentukan pemenang:

  1. Saya akan menguji program Anda dengan n = 2, n = 3, dll ... Saya menyimpan semua output Anda dan berhenti ketika program Anda membutuhkan lebih dari satu menit atau lebih dari 2GB RAM. Setiap kali program dijalankan untuk input yang diberikan n, itu akan dihentikan jika dibutuhkan lebih dari 1 menit.

  2. Saya melihat semua hasil untuk semua program untuk n = 2. Jika suatu program menghasilkan solusi yang kurang valid daripada yang lain, program itu dihilangkan.

  3. Ulangi langkah 2 untuk n = 3, n = 4, dll ... Program berdiri terakhir menang.

orlp
sumber
1
Jadi tidak ada jawaban dalam bahasa windows-eksklusif?
Conor O'Brien
3
Secara pribadi, saya tidak suka kriteria penilaian. Tidak mungkin untuk mengetahui apakah solusi kami akan berfungsi dan di mana mengatur ambang sampai kami mendapatkan hasil dari tes di komputer Anda. Saya pikir kode-golf sederhana akan membuat pertanyaan yang lebih baik.
musicman523
2
Saya menganggap hardcoding tidak diperbolehkan. Tetapi kemudian pembatasan itu hampir tidak dapat diamati
Luis Mendo
1
@ user202729 Saya tidak, saya harus mencoba setiap program untuk setiap n untuk melihat program mana yang menghasilkan lebih banyak solusi.
orlp
2
"Dua minggu dari sekarang" adalah 3 hari yang lalu.
GB

Jawaban:

4

C (gcc) , n = 50000000 dengan 6499 hasil dalam 59 detik

Untuk menghindari menghasilkan lebih dari satu terabyte output yang terdiri hampir seluruhnya dari 1s, urutan (katakanlah) 49999995 1s disingkat 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;
}

Cobalah online!

Anders Kaseorg
sumber
3

Mathematica, n = 293 dengan 12 solusi

OP mengubah tantangan dan meminta input.
Berikut ini adalah kode baru yang mengambil n sebagai input.
Untuk n = 293 Anda mendapatkan 12 solusi

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


memasukkan

[n]

Anda dapat menguji algoritme ini di Wolfram Sandbox yang merupakan perangkat lunak yang tersedia secara online dan gratis.
Ikuti saja tautannya, tempel kode (ctrl + v), tempel input di akhir kode dan tekan shift + enter untuk menjalankan.
Anda akan mendapatkan semua solusi saya dalam hitungan detik

Ini juga Coba online! dalam C ++ (gcc)
(Terima kasih banyak kepada @ThePirateBay untuk mendukung dan menerjemahkan kode saya ke bahasa gratis)

program ini hanya menghasilkan solusi dari bentuk {a, b, c} {a, b, c}
yang berarti a + b + c = a * b * c

Diperlukan 1 detik untuk menghitung

kedua belas solusi tersebut adalah:

{1,1 ..., 1,1,1,2,293} {1,1 ..., 1,1,1,2,293}
{1,1 ..., 1,1,1,3,147} {1 , 1 ..., 1,1,1,3,147}
{1,1 ..., 1,1,1,5,54} {1,1 ..., 1,1,1,5,574}
{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
sumber
1
"Jika jawaban Anda [...] ditulis dalam bahasa yang tidak dapat saya uji dengan perangkat lunak yang tersedia secara bebas, saya tidak akan menilai jawaban Anda."
Leaky Nun
4
@ GB "Anda diizinkan memposting jawaban yang menghasilkan solusi tidak lengkap"
user202729
1
program saya "..menghasilkan kombinasi terbanyak untuk n tertinggi dalam satu menit" .Ini bukan hardcoded. Itu hanya menemukan 12 solusi "termudah" pertama dalam waktu kurang dari satu menit
J42161217
1
Bisa jadi lebih jelas bahwa n seharusnya menjadi input. Saya mengklarifikasi itu sekarang. Tampaknya program Anda tidak mengambil input n .
orlp
2
@ atau Tetap! Program saya mengambil n sebagai input. Untuk n = 293 Anda mendapatkan 12 solusi. tolong hapuskan suaranya jika karena semuanya berfungsi!
J42161217
2

Python 2 , n = 175, 28 menghasilkan 59s

Jadikan sedikit lebih lambat menggunakan faktor reduksi 2, tetapi dapatkan lebih banyak solusi dimulai dengan n = 83

Saya mendapatkan hasil untuk n hingga 92 pada TIO dalam sekali jalan.

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

Cobalah online!

GB
sumber
1
"simpan 5 elemen [1..2] dan batasi 3n ..." Saya senang Anda menyukai algoritme saya ;-)
J42161217
Saya sudah melakukan sesuatu yang serupa di versi Ruby, dan sekarang saya mencoba untuk menghapus batasan itu.
GB
Untuk yang diberikan, berapa banyak solusi yang dikodekan dalam algoritma Anda?
J42161217
Tidak benar-benar hardcoded: 2 solusi standar dapat dihasilkan dengan menggunakan jalan pintas (kecuali untuk n = 2 di mana mereka adalah kombinasi yang sama), dan dengan melewatkan ini, saya dapat membatasi rentang ke 2n bukan 3n. Jika ini dianggap hardcoded, saya akan mengubahnya.
GB
1
Untuk 61 hasil saya akan menjadi 28 Anda, saya ingat itu 27 ... Mungkin saya membuat beberapa kesalahan
RosLuP
1

Ruby , n = 12 mendapat 6 solusi

Setidaknya pada TIO, hasil yang biasa untuk 1 hingga 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(&:+)
  }
}

Cobalah online!

Dapatkan 10 hasil di bawah satu menit untuk n = 13 di laptop saya.

GB
sumber
1

Mathematica, n = 19 dengan 11 solusi

ini jawaban baru saya sesuai dengan kriteria baru 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])&

jika Anda memberi input [n] di akhir, program menampilkan solusinya

berikut ini adalah hasil saya (pada laptop lama saya 64-bit 2.4GHz)

n-> solusi
2 -> 2
3 -> 4
4 -> 3
5 -> 5
6 -> 4
7 -> 6
8 -> 5
9 -> 7
10 -> 7
11 -> 8
12 -> 8 12 -> 6 (dalam 17 dtk)
13 -> 10 (dalam 20 dtk)
14 -> 7 (dalam 25 dtk)
15 -> 7 (dalam 29 dtk)
16 -> 9 (dalam 34 dtk)
17 -> 10 (dalam 39 dtk)
18 - > 9 (dalam 45 detik)
19 -> 11 (dalam 51 detik)
20 -> 7 (dalam 58 detik)

J42161217
sumber
1

Haskell, banyak solusi cepat

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

fmenghitung solusinya, mainfungsi ini menambah input dari baris perintah dan beberapa format dan penghitungan.

Sievers Kristen
sumber
Kompilasi seperti ini: ghc -O3 -o prodsum prodsum.hsdan jalankan dengan argumen baris perintah:./prodsum 6
Christian Sievers
0

Haskell , n = 10 dengan 2 solusi


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)

Ini melakukan seperti omong kosong, tapi saya setidaknya memperbaikinya sehingga saya benar-benar mengatasi tantangan sekarang!

Cobalah online!

maple_shaft
sumber
untuk n = 2 Anda mendapatkan ["[3,3] [2,3]", "[2,2] [2,2]", "[1,3] [2,2]", "[1, 2] [1,3] "," [1,1] [1,2] "] yang salah
J42161217
Semua solusi tampaknya salah sebenarnya
GB
@ Jenny_mathy Bagaimana ini salah? 3 + 3 adalah 6 dan 2 * 3 adalah 6. Apakah saya salah memahami pertanyaan.
maple_shaft
Anda kehilangan "sebaliknya"
J42161217
@Jenny_mathy Kesalahan bodoh di pihak saya! Saya memperbaikinya, harus bekerja sekarang.
maple_shaft
0

Aksioma, n = 83 dalam 59 detik di sini

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

hasil:

 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

Cara untuk menjalankan teks di atas dalam Aksioma, akan, salin semua teks dalam file, simpan file dengan nama: Name.input, dalam jendela Aksioma gunakan ") baca absolutepath / Name".
hasil: (# f (i) menemukan panjang array f (i), yaitu jumlah solusi)

RosLuP
sumber