La conjecture de Goldbach déclare que tout nombre pair supérieur à deux peut être exprimé comme la somme de deux nombres premiers. Par exemple,

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

Cependant, une fois à 10, quelque chose d'intéressant se produit. Non seulement 10 peut être écrit comme

5 + 5

mais il peut aussi s'écrire

7 + 3

Puisque 10 peut être exprimé comme la somme de deux nombres premiers de deux manières , nous disons que la "partition de Goldbach" de 10 est 2. Ou plus généralement,

La partition de Goldbach d'un nombre est le nombre total de façons distinctes d'écrire n = p + qoù pet qsont des nombres premiers etp >= q

Votre défi consiste à écrire un programme ou une fonction qui trouve la partition Goldbach d'un nombre. Or, techniquement, le terme "partition de Goldbach" n'est utilisé que pour désigner les nombres pairs. Cependant, comme l'entier impair p + 2 peut également être exprimé comme la somme de deux nombres premiers si p> 2 est premier, nous allons l'étendre à tous les entiers positifs ( A061358 ).

Vous pouvez supposer en toute sécurité que votre entrée sera toujours un entier positif, et vous pouvez prendre l'entrée et la sortie dans l'une de nos méthodes autorisées par défaut , par exemple les arguments de fonction et la valeur de retour, STDIN et STDOUT, la lecture et l'écriture dans un fichier, etc.

Les partitions de Goldbach des entiers positifs jusqu'à 100 sont:

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

Comme d'habitude, les failles standard s'appliquent et la réponse la plus courte en octets gagne!

Gelée , 8 octets

_ÆRÆPSHĊ

Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça fonctionne

_Æ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 octets

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)

Se déplace récursivement de k=2à n/2, en additionnant les valeurs où les deux ket n-ksont premiers. Ce serait bien de compter nen même temps, mais cela a un problème k=0et k=1est faussement appelé 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)

Le contrôle de primalité est de première instance, raccourci en vérifiant les deux ket n-kensemble. J'ai trouvé que c'était plus court que d'utiliser un générateur de théorème de Wilson (79 octets):

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

L'idée pour celui-ci est de garder une liste de tous les nombres premiers dans la moitié inférieure pour être vérifiée au moment où nous arrivons à la moitié supérieure, mais pour le milieu k=n/2, nous n'avons pas eu le temps d'ajouter n-kà la liste lorsque nous arrivons à k. Une version itérative contourne cela, mais fait 82 octets:

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 octets

tZq&+=Rz

Essayez-le en ligne!

Explication

Considérez la saisie 8comme exemple

      % 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

Il est intéressant d'observer le graphique de la séquence , en utilisant une version légèrement modifiée du code:

:"@       % 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

Pour l'entrée, 10000le résultat est

Vous pouvez l'essayer sur MATL Online (Actualisez la page si le bouton "Exécuter" ne change pas en "Tuer" lorsqu'il est pressé). Il faut plusieurs 25 secondes environ pour produire le graphique en entrée 3000; les entrées supérieures à quelques milliers expireront.

JavaScript (ES6), 77 73 70 octets

Enregistré 3 octets grâce à @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

fest une fonction de test de primalité; la fonction pertinente est g.

ffonctionne en décomptant récursivement à partir de n-1 ; le flux de contrôle à chaque étape se déroule comme suit:

• x<2||Si x <2 , le nombre est premier; retour 1 .
• n%x&&Sinon, si n mod x = 0 , le nombre n'est pas premier; retour n%x.
• f(n,x-1)Sinon, le nombre peut ou non être premier; décrémenter x et réessayer.

gfonctionne de façon similaire, mais avec moins de flux de contrôle. Il fonctionne en multipliant f (b) par f (ab) pour chaque entier b dans la plage [2, étage (a / 2)] , puis en additionnant les résultats. Cela nous donne le nombre de paires qui totalisent un où les deux nombres de la paire sont premiers, ce qui est exactement ce que nous voulons.

05AB1E , 10 8 octets

Extrêmement inefficace.

D!f-pO;î

Essayez-le en ligne! ou Essayez un moyen moins efficace de générer des nombres premiers

Explication

n = 10 utilisé comme exemple.

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 octets

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

Je ne pense pas que GAP ait un chemin plus court que celui évident. Numbercompte le nombre d'éléments d'une liste qui satisfont un prédicat.

L'utiliser pour calculer les 100 premières valeurs:

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 octets

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

Essayez-le en ligne!

Explication

Une transcription directe du problème.

:{                }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 octets

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

Le résultat est fourni comme une fonction anonyme. Essayez de tracer un graphique dessus:

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

Par ailleurs, le code a la même longueur avec la version de fonction du code de démonstration sur OEIS.

Gelée , 12 octets

HRð,_@ÆPð×/S

TryItOnline
1-100

Comment?

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

Raquette 219 octets

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

Non golfé:

(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

Essai:

(f 10)
(f 100)

Production:

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

En fait , 11 octets

;R`p`░@-♂bΣ

Essayez-le en ligne!

Explication:

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

05AB1E , 6 octets

;ÅP-pO

Essayez-le en ligne!

Explication:

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

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]

Exemple d'utilisation: 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].

Implémentation directe de la définition: liez rd'abord tous les nombres premiers jusqu'au nombre d'entrée n, puis prenez un 1pour tous pet qd' roù q<=pet p+q==net additionnez-les.