Dugaan Goldbach menyatakan bahwa setiap bilangan genap yang lebih besar dari dua dapat dinyatakan sebagai jumlah dari dua bilangan prima. Sebagai contoh,

4 = 2 + 2
6 = 3 + 3
8 = 5 + 3

Namun, begitu kita sampai ke 10 sesuatu yang menarik terjadi. Tidak hanya 10 dapat ditulis sebagai

5 + 5

tetapi juga dapat ditulis sebagai

7 + 3

Karena 10 dapat dinyatakan sebagai jumlah dari dua bilangan prima dua cara , kita mengatakan bahwa "partisi Goldbach" dari 10 adalah 2. Atau lebih umum,

Partisi Goldbach suatu angka adalah jumlah total cara penulisan yang berbeda di n = p + qmana pdan qmerupakan bilangan prima danp >= q

Tantangan Anda adalah menulis program atau fungsi yang menemukan partisi Goldbach dari sebuah angka. Sekarang, secara teknis istilah "partisi Goldbach" hanya digunakan untuk merujuk ke angka genap. Namun, karena aneh bilangan bulat p + 2 dapat juga dinyatakan sebagai jumlah dari dua bilangan prima jika p> 2 adalah prima, kami akan memperpanjang ini untuk semua bilangan bulat positif ( A061358 ).

Anda dapat dengan aman berasumsi bahwa input Anda akan selalu menjadi bilangan bulat positif, dan Anda dapat mengambil input dan output dalam salah satu metode standar yang diizinkan , misalnya argumen fungsi dan nilai pengembalian, STDIN dan STDOUT, membaca dan menulis ke file, dll.

Partisi Goldbach dari bilangan bulat positif hingga 100 adalah:

0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 1, 2, 1, 3, 0, 3, 1,
3, 0, 2, 0, 3, 1, 2, 1, 4, 0, 4, 0, 2, 1, 3, 0, 4, 1, 3, 1, 4, 0, 5, 1, 4,
0, 3, 0, 5, 1, 3, 0, 4, 0, 6, 1, 3, 1, 5, 0, 6, 0, 2, 1, 5, 0, 6, 1, 5, 1,
5, 0, 7, 0, 4, 1, 5, 0, 8, 1, 5, 0, 4, 0, 9, 1, 4, 0, 5, 0, 7, 0, 3, 1, 6

Seperti biasa, celah standar berlaku, dan jawaban terpendek dalam byte menang!

Jelly , 8 byte

_ÆRÆPSHĊ

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

_ÆRÆPSHĊ  Main link. Argument: n (positive integer)

 ÆR       Prime range; yield [2, 3, 5, ..., n].
_         Subtract all primes in this range from n.
   ÆP     Compute the primality of the resulting differences.
          This returns 1 for each prime p such that n - p is also prime.
     S    Compute the sum of the resulting Booleans.
      H   Divide it by 2, since [p, n - p] and [n - p, p] have both been counted.
       Ċ  Ceil; round the resulting quotient up (needed if n = 2p).

Python 2, 76 byte

g=lambda n,k=2:n/k/2and all(x%i for x in[k,n-k]for i in range(2,x))+g(n,k+1)

Secara rekursif merangkak naik dari k=2ke n/2, menambahkan nilai-nilai di mana kedua kdan n-kyang prima. Akan lebih baik untuk menghitung nmundur pada saat yang sama, tetapi ini memiliki masalah yang k=0dan k=1disebut prime:

g=lambda n,k=0:n/k and all(x%i for x in[k,n]for i in range(2,x))+g(n-1,k+1)

Pemeriksaan primality adalah pembagian-percobaan, disingkat dengan memeriksa keduanya kdan n-kbersama - sama. Saya menemukan ini lebih pendek daripada menggunakan generator Teorema Wilson (79 byte):

f=lambda n,k=1,P=1,l=[]:n/k and P%k*(n-k in l+P%k*[k])+f(n,k+1,P*k*k,l+P%k*[k])

Gagasan untuk yang satu ini adalah untuk menyimpan daftar semua bilangan prima di bagian bawah untuk diperiksa pada saat kita sampai di bagian atas, tetapi untuk titik tengah k=n/2, kita belum punya waktu untuk menambahkan n-kke daftar keluar ketika kita sampai ke k. Versi berulang berkeliling ini, tetapi 82 byte:

n=input()
s=P=k=1;l=[]
while k<n:l+=P%k*[k];s+=P%k*(n-k in l);P*=k*k;k+=1
print~-s

MATL , 8 byte

tZq&+=Rz

Cobalah online!

Penjelasan

Pertimbangkan input 8sebagai contoh

      % Take input implicitly
t     % Duplicate
      % STACK: 8, 8
Zq    % All primes up to that number
      % STACK: 8, [2 3 5 7]
&+    % Matrix with all pairwise additions
      % STACK: 8, [4  5  7  9
                   5  6  8 10
                   7  8 10 12
                   9 10 12 14]
=     % True for entries that equal the input
      % STACK: [0 0 0 0
                0 0 1 0
                0 1 0 0
                0 0 0 0]
R     % Extract upper triangular part (including diagonal). 
      % This removes pairs that are equal up to order
      % STACK: [0 0 0 0
                0 0 1 0
                0 0 0 0
                0 0 0 0]
z     % Number of nonzero entries
      % STACK: 1
      % Display implicitly

Sangat menarik untuk mengamati grafik urutannya , menggunakan versi kode yang sedikit dimodifikasi:

:"@       % Input n implicitly. For each k from 1 to n, push k
tZq&+=Rz  % Same code as above. Pushes the result for each k
]v'.'&XG  % End. Concatenate all results into a vector. Plot as dots

Untuk input 10000hasilnya adalah

Anda dapat mencobanya di MATL Online (Refresh halaman jika tombol "Run" tidak berubah menjadi "Bunuh" ketika ditekan). Butuh beberapa sekitar 25 detik untuk menghasilkan grafik untuk input 3000; input di atas beberapa ribu akan habis.

JavaScript (ES6), 77 73 70 byte

Disimpan 3 byte berkat @Arnauld

f=(n,x=n)=>--x<2||n%x&&f(n,x)
g=(a,b=a>>1)=>b>1?f(b)*f(a-b)+g(a,b-1):0

fadalah fungsi tes primality; fungsi yang relevan adalahg .

fbekerja dengan menghitung mundur dari n-1 secara rekursif ; aliran kontrol pada setiap tahap berjalan seperti ini:

• x<2||Jika x <2 , jumlahnya prima; kembali 1 .
• n%x&&Kalau tidak, jika n mod x = 0 , angkanya tidak prima; kembalin%x .
• f(n,x-1)Kalau tidak, jumlahnya mungkin prima atau tidak prima; pengurangan x dan coba lagi.

gbekerja dengan cara yang sama, meskipun dengan aliran kontrol yang tidak begitu banyak. Ia bekerja dengan mengalikan f (b) dengan f (ab) untuk setiap bilangan bulat b dalam kisaran [2, lantai (a / 2)] , lalu menjumlahkan hasilnya. Ini memberi kita jumlah pasangan yang menjumlahkan ke tempat di mana kedua angka dalam pasangan adalah prima, yang persis seperti yang kita inginkan.

05AB1E , 10 8 byte

Sangat tidak efisien.

D!f-pO;î

Cobalah online! atau Coba cara yang kurang efisien untuk menghasilkan bilangan prima

Penjelasan

n = 10 digunakan sebagai contoh.

D          # duplicate
           # STACK: 10, 10 
 !         # factorial
           # STACK: 10, 3628800
  f        # unique prime factors
           # STACK: 10, [2,3,5,7]
   -       # subtract
           # STACK: [8,7,5,3]
    p      # is prime
           # STACK: [0,1,1,1]
     O     # sum
           # STACK: 3
      ;    # divide by 2
           # STACK: 1.5
       î   # round up
           # STACK: 2
           # implicit output

GAP , 57 byte

n->Number([2..QuoInt(n,2)],k->IsPrime(k)and IsPrime(n-k))

Saya tidak berpikir GAP memiliki cara yang lebih pendek daripada yang sudah jelas ini. Numbermenghitung berapa banyak elemen daftar yang memenuhi predikat.

Menggunakannya untuk menghitung 100 nilai pertama:

gap> List([1..100],n->Number([2..QuoInt(n,2)],k->IsPrime(k)and IsPrime(n-k)));
[ 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 1, 2, 1, 3, 0, 3, 1, 
  3, 0, 2, 0, 3, 1, 2, 1, 4, 0, 4, 0, 2, 1, 3, 0, 4, 1, 3, 1, 4, 0, 5, 1, 4, 
  0, 3, 0, 5, 1, 3, 0, 4, 0, 6, 1, 3, 1, 5, 0, 6, 0, 2, 1, 5, 0, 6, 1, 5, 1, 
  5, 0, 7, 0, 4, 1, 5, 0, 8, 1, 5, 0, 4, 0, 9, 1, 4, 0, 5, 0, 7, 0, 3, 1, 6 ]

Brachylog , 22 byte

:{,A:B>=.:#pa+?,.=}fl

Cobalah online!

Penjelasan

Transkripsi masalah secara langsung.

:{                }f       Find all valid outputs of the predicate in brackets for the Input
                    l      Output is the number of valid outputs found

  ,A:B>=.                  Output = [A, B] with A >= B
         :#pa              Both A and B must be prime numbers
             +?,           The sum of A and B is the Input
                .=         Label A and B as integers that verify those constraints

Mathematica, 52 byte

Count[IntegerPartitions[#,{2}]//PrimeQ,{True,True}]&

Hasilnya disediakan sebagai fungsi anonim. Coba plot grafik di atasnya:

DiscretePlot[
 Count[IntegerPartitions[#, {2}] // PrimeQ, {True, True}] &[i], {i, 1,
   1000}]

Omong-omong, kodenya memiliki panjang yang sama dengan versi fungsi dari kode demo pada OEIS.

Jelly , 12 byte

HRð,_@ÆPð×/S

TryItOnline
1-100

Bagaimana?

HRð,_@ÆPð×/S - Main link: n    e.g. 22
H            - halve
 R           - range          [1,2,3,4,5,6,7,8,9,10,11] (note this will be 1 to n//2)
  ð          - dyadic chain separation
   ,         - pair with
    _@       - n -           [[1,2,3,4,5,6,7,8,9,10,11],[21,20,19,18,17,16,15,14,13,12,11]]
      ÆP     - is prime? (1 if prime 0 if not)
                            [[0,1,1,0,1,0,1,0,0,0,1],[0,0,1,0,1,0,0,0,1,0,1]]
        ð    - dyadic chain separation
         ×/  - reduce with multiplication
                             [0,0,1,0,1,0,0,0,0,0,1]
           S - sum           3

Racket 219 byte

(let*((pl(for/list((i n) #:when(prime? i))i))(ll(combinations(append pl pl)2))(ol'()))(for/list((i ll))(define tl(sort i >))
(when(and(= n(apply + i))(not(ormap(λ(x)(equal? x tl))ol)))(set! ol(cons tl ol))))(length ol))

Tidak Disatukan:

(define(f n)
 (let* ((pl                                   ; create a list of primes till n
          (for/list ((i n) #:when (prime? i))
            i))
         (ll (combinations (append pl pl) 2)) ; get a list of combinations of 2 primes
         (ol '()))                            ; initialize output list
    (for/list ((i ll))                        ; test each combination
      (define tl (sort i >))
      (when (and (= n (apply + i))            ; sum is n
                 (not(ormap (lambda(x)(equal? x tl)) ol))) ; not already in list
        (set! ol (cons tl ol))))              ; if ok, add to list
    (println ol)                              ; print list
    (length ol)))                             ; print length of list

Pengujian:

(f 10)
(f 100)

Keluaran:

'((5 5) (7 3))
2
'((97 3) (89 11) (83 17) (71 29) (59 41) (53 47))
6

Sebenarnya , 11 byte

;R`p`░@-♂bΣ

Cobalah online!

Penjelasan:

;R`p`░@-♂bΣ
 R`p`░       prime values in [1, n]
;     @-     subtract each value from n
        ♂b   convert each value to boolean
          Σ  sum

05AB1E , 6 byte

;ÅP-pO

Cobalah online!

Penjelasan:

                  # implicit input (example: 10)
;                 # divide input by 2 (5)
 ÅP               # primes up to that ([2, 3, 5])
   -              # subtract from the implict input ([8, 7, 5])
    p             # isPrime? ([0, 1, 1])
     O            # sum (2), implicit output

Haskell, 73 byte

f n|r<-[a|a<-[2..n],all((<2).gcd a)[2..a-1]]=sum[1|p<-r,q<-r,q<=p,p+q==n]

Contoh penggunaan: map f [1..25]->[0,0,0,1,1,1,1,1,1,2,0,1,1,2,1,2,0,2,1,2,1,3,0,3,1] .

Implementasi langsung dari definisi: pertama mengikat rsemua bilangan prima hingga nomor input n, kemudian mengambil 1untuk semua pdan qdari rmana q<=pdan p+q==ndan jumlah mereka.