El número de formas en que un número es una suma de primos consecutivos

15

Dado un número entero mayor que 1, genera el número de formas en que puede expresarse como la suma de uno o más primos consecutivos.

El orden de los sumandos no importa. Una suma puede consistir en un solo número (por lo que la salida de cualquier primo será al menos 1.)

Este es el . Aplican reglas estándar.

Consulte esta wiki de OEIS para obtener información y secuencias relacionadas, incluida la secuencia misma OEIS A054845 .

Casos de prueba

2 => 1
3 => 1
4 => 0
5 => 2
6 => 0
7 => 1
8 => 1
10 => 1
36 => 2
41 => 3
42 => 1
43 => 1
44 => 0
311 => 5
1151 => 4
34421 => 6
ngm
fuente

Respuestas:

9

Jalea ,  6  5 bytes

-1 gracias a dylnan

ÆRẆ§ċ

Un enlace monádico

Pruébalo en línea! O vea el conjunto de pruebas (tenga en cuenta que el caso de prueba final se agotaría a los 60 en TIO).

¿Cómo?

ÆRẆ§ċ - Link: integer, n
ÆR    - primes from 2 to n inclusive
  Ẇ   - all contiguous substrings
   §  - sum each
    ċ - count occurrences of n
Jonathan Allan
fuente
2æRes lo mismo queÆR
dylnan
@dylnan agradable gracias!
Jonathan Allan
8

R , 95 bytes

function(x,P=2){for(i in 2:x)P=c(P,i[all(i%%P)])
for(i in 1:x){F=F+sum(cumsum(P)==x)
P[i]=0}
F}

Pruébalo en línea!

  • ¡-24 bytes gracias a @Giuseppe que básicamente ha revolucionado mi solución que también admite 34421!
digEmAll
fuente
1
¡esa es una forma inteligente de inventar primos x!
Giuseppe
1
97 bytes
Giuseppe
1
@Giuseppe: ¡eso es genial! Hoy estoy enfermo y nunca hubiera podido pensar que ... (tal vez nunca: P) Me siento mal al usar su código ... Volví a la anterior, si publica una nueva respuesta, yo ' ll upvote;)
digEmAll
1
@ngm, ¿cuál es el significado de 34421 ...? Y @digEmAll, realmente no me importa; Realmente no tenía ni idea de cómo usar cumsumy configurar los primeros elementos 0para obtener las sumas principales consecutivas. El primer golf fue solo yo tratando de hacer que el último caso de prueba funcionara, ¡y tuve la suerte de que era más corto que outer! Tengo más que suficientes repeticiones (al menos hasta que obtengamos los requisitos de repeticiones adecuados), ¡y siempre estoy feliz de ayudar a más golfistas R a obtener más visibilidad!
Giuseppe
1
@Giuseppe 34421 es el número más pequeño que es la suma de primos consecutivos en exactamente 6 formas (ver oeis.org/A054859 ). La mayoría de las soluciones publicadas para este desafío se quedan sin tiempo (en TIO) o memoria para ese caso de prueba. Aunque la respuesta de Java incluso obtuvo el siguiente entero en la secuencia también (para 7) pero no para 8.
ngm
4

JavaScript (ES6), 92 bytes

n=>(a=[],k=1,g=s=>k>n?0:!s+g(s>0?s-(p=d=>k%--d?p(d):d<2&&a.push(k)&&k)(++k):s+a.shift()))(n)

Pruébalo en línea!

Comentado

n => (                          // n = input
  a = [],                       // a[] = array holding the list of consecutive primes
  k = 1,                        // k = current number to test
  g = s =>                      // g = recursive function taking s = n - sum(a)
    k > n ?                     //   if k is greater than n:
      0                         //     stop recursion
    :                           //   else:
      !s +                      //     increment the final result if s = 0
      g(                        //     add the result of a recursive call to g():
        s > 0 ?                 //       if s is positive:
          s - (                 //         subtract from s the result of p():
            p = d => k % --d ?  //           p() = recursive helper function looking
              p(d)              //                 for the highest divisor d of k,
            :                   //                 starting with d = k - 1
              d < 2 &&          //           if d is less than 2 (i.e. k is prime):
              a.push(k) &&      //             append k to a[]
              k                 //             and return k (else: return false)
          )(++k)                //         increment k and call p(k)
        :                       //       else:
          s + a.shift()         //         remove the first entry from a[]
                                //         and add it to s
      )                         //     end of recursive call
  )(n)                          // initial call to g() with s = n
Arnauld
fuente
4

MATL, 15 12 bytes

EZqPYTRYsG=z

Pruébalo en MATL Online

La inicial E(multiplicar por 2) se asegura de que, para la entrada principal, el resultado de la posterior Ys( cumsum) no tenga la entrada principal repitiéndose en la parte puesta a cero de la matriz (por lo tanto, jugando con el conteo).

Explicación:

                % Implicit input, say 5
E               % Double the input
 Zq             % Get list of primes upto (and including) that
                %  Stack: [2 3 5 7]
   P            % Reverse that list
    YT          % Toeplitz matrix of that
                %  Stack: [7 5 3 2
                           5 7 5 3
                           3 5 7 5
                           2 3 5 7]
      R         % `triu` - upper triangular portion of matrix
                %  Stack: [7 5 3 2
                           0 7 5 3
                           0 0 7 5
                           0 0 0 7]
       Ys       % Cumulative sum along each column
                %  Stack: [7  5  3  2
                           7 12  8  5
                           7 12 15 10
                           7 12 15 17]


         G=     % Compare against input - 1s where equal, 0s where not
           z    % Count the number of non-zeros
sundar - Restablecer a Monica
fuente
1
Toeplitz matriz de números primos y parte triangular, muy agradable!
Luis Mendo
4

Brachylog , 14 9 bytes

{⟦ṗˢs+?}ᶜ

Pruébalo en línea!
Múltiples casos de prueba

(-5 bytes completos, gracias a @Kroppeb!)

Explicación:

{⟦ṗˢs+?}ᶜ
{      }ᶜ     Count the number of ways this predicate can succeed:
 ⟦            Range from 0 to input
  ṗˢ          Select only the prime numbers
    s         The list of prime numbers has a substring (contiguous subset)
     +        Whose sum
      ?       Is the input
sundar - Restablecer a Monica
fuente
Puedes jugar golf calculando ⟦ṗˢdentro del bucle. Obtuve este {⟦ṗˢs+;?=}ᶜpaquete de prueba: ¡ Pruébelo en línea!
Kroppeb
Me di cuenta de que puedo reemplazar el ;?=by ?y obtener {⟦ṗˢs+?}ᶜ(9 bytes)
Kroppeb
@Kroppeb ¡Por supuesto! Esa es una respuesta mucho más elegante también. Gracias.
Sundar - Restablecer Monica
3

Retina 0.8.2 , 68 bytes

.+
$*_$&$*
_
$`__¶
A`^(__+)\1+$
m)&`^((_)|¶)+¶[_¶]*(?<-2>1)+$(?(2)1)

Pruébalo en línea! El enlace incluye casos de prueba más rápidos. Explicación:

m)

Ejecute el script completo en modo multilínea ^y $coincida en cada línea.

.+
$*_$&$*

Convierte a unario dos veces, primero usando _s, luego usando 1s.

_
$`__¶

_2norte+1

A`^(__+)\1+$

Eliminar todos los números compuestos en el rango.

&`^((_)|¶)+¶[_¶]*(?<-2>1)+$(?(2)1)

__1norte

Neil
fuente
3

Casco , 9 8 bytes

-1 byte gracias a Mr.Xcoder (¡use un argumento con nombre en ¹lugar de S)!

#¹ṁ∫ṫ↑İp

Pruébalo en línea!

Explicación

#¹ṁ∫ṫ↑İp  -- example input: 3
#¹        -- count the occurrences of 3 in
      İp  -- | primes: [2,3,5,7..]
     ↑    -- | take 3: [2,3,5]
    ṫ     -- | tails: [[2,3,5],[3,5],[5]]
  ṁ       -- | map and flatten
   ∫      -- | | cumulative sums
          -- | : [2,5,10,3,8,5]
          -- : 1
ბიმო
fuente
Como programa completo, #¹ṁ∫ṫ↑İpdebe guardar 1 byte.
Sr. Xcoder
3

MATL , 16 bytes

:"GZq@:g2&Y+G=vs

¡Pruébalo en MATL Online!

Explicación

:"        % Input (implicit): n. For each k in [1 2 ... n]
  G       %   Push n
  Zq      %   Primes up to that
  @:g     %   Push vector of k ones
  2&Y+    %   Convolution, removing the edges
  G=      %   True for entries that equal n
  v       %   Concatenate vertically with previous results
  s       %   Sum
          % End (implicit). Display (implicit)
Luis Mendo
fuente
2

Limpio , 100 98 bytes

import StdEnv,StdLib
$n=sum[1\\z<-inits[i\\i<-[2..n]|all(\j=i/j*j<i)[2..i-1]],s<-tails z|sum s==n]

Pruébalo en línea!

Define la función $ :: Int -> Intque funciona como se explica a continuación:

$ n                              // the function $ of n is
    = sum [                      // the sum of
        1                        // 1, for every 
        \\ z <- inits [          // prefix z of 
            i                    // i, for every
            \\ i <- [2..n]       // integer i between 2 and n
            | and [              // where every
                i/j*j < i        // j does not divide i
                \\ j <- [2..i-1] // for every j between 2 and i-1
            ]
        ]
        , s <- tails z           // ... and suffix s of the prefix z
        | sum s == n             // where the sum of the suffix is equal to n
    ]

(La explicación es para una versión anterior pero lógicamente idéntica)

Οurous
fuente
1
Elogio especial para obtener salida para 34421.
ngm
2

Perl 6 , 53 bytes

{+grep $_,map {|[\+] $_},[\R,] grep *.is-prime,2..$_}

Pruébalo en línea!

Utiliza el operador de reducción de triángulo dos veces. El último caso de prueba es demasiado lento para TIO.

Explicación

{                                                   } # Anonymous block
                               grep *.is-prime,2..$_  # List of primes up to n
                         [\R,]  # All sublists (2) (3 2) (5 3 2) (7 5 3 2) ...
          map {|[\+] $_},  # Partial sums for each, flattened
 +grep $_,  # Count number of occurrences
nwellnhof
fuente
2

Japt, 17 bytes

¡Debe haber un camino más corto que este!

Maldición en el último caso de prueba.

õ fj x@ZãYÄ x@¶Xx

Pruébalo o ejecuta todos los casos de prueba


Explicación

                      :Implicit input of integer U
õ                     :Range [1,U]
  fj                  :Filter primes
      @               :Map each integer at 0-based index Y in array Z
         YÄ           :  Y+1
       Zã             :  Subsections of Z of that length
             @        :  Map each array X
               Xx     :    Reduce by addition
              ¶       :    Check for equality with U
            x         :  Reduce by addition
     x                :Reduce by addition
Lanudo
fuente
2

Java 10, 195 194 184 182 bytes

n->{var L=new java.util.Stack();int i=1,k,x,s,r=0;for(;i++<n;){for(k=1;i%++k>0;);if(k==i)L.add(i);}for(x=L.size(),i=0;i<x;)for(k=i++,s=0;k<x;r+=s==n?1:0)s+=(int)L.get(k++);return r;}

-1 byte gracias a @ceilingcat .
-10 bytes gracias a @SaraJ .

Pruébalo en línea.

Explicación:

n->{                // Method with integer as both parameter and return-type
  var L=new java.util.Stack();
                    //  List of primes, starting empty
  int i=1,k,x,s,    //  Temp integers
      r=0;          //  Result-counter, starting at 0
  for(;i++<n;){     //  Loop `i` in the range [2, `n`]
    for(k=1;        //   Set `k` to 1
        i%++k>0;);  //   Inner loop which increases `k` by 1 before every iteration,
                    //   and continues as long as `i` is not divisible by `k`
    if(k==i)        //   If `k` is now still the same as `i`; a.k.a. if `i` is a prime:
      L.add(i);}    //    Add the prime to the List
  for(x=L.size(),   //  Get the amount of primes in the List
      i=0;i<x;)     //  Loop `i` in the range [0, amount_of_primes)
    for(s=0,        //   (Re)set the sum to 0
        k=i++;k<x;  //   Inner loop `k` in the range [`i`, amount_of_primes)
        r+=s==n?    //     After every iteration, if the sum is equal to the input:
            1       //      Increase the result-counter by 1
           :        //     Else:
            0)      //      Leave the result-counter the same by adding 0
      s+=(int)L.get(k++);
                    //    Add the next prime (at index `k`) to the sum
  return r;}        //  And finally return the result-counter

Es básicamente similar a las respuestas de Jelly o 05AB1E , solo 190 bytes más. XD
Aquí una comparación para cada una de las partes, agregada solo por diversión (y para ver por qué Java es tan detallado y estos lenguajes de golf son tan poderosos):

  1. Tome la entrada: (Jelly: 0 bytes) implícitamente ; (05AB1E: 0 bytes) implícitamente ; (Java 10: 5 bytes)n->{}
  2. Cree una lista de primos en el rango [2, n]: (Jelly: 2 bytes) ÆR; (05AB1E: 2 bytes) ÅP; (Java 10: 95 bytes)var L=new java.util.Stack();int i=1,k,x,s,r=0;for(;i++<n;){for(k=1;i%++k>0;);if(k==i)L.add(i);}
  3. Obtenga todas las sublistas continuas: (Gelatina: 1 byte) ; (05AB1E: 1 byte) Œ; (Java 10: 55 bytes)for(x=L.size(),i=0;i<x;)for(k=i++;k<x;) y(int)L.get(k++);
  4. Suma cada sublista: (Gelatina: 1 byte) §; (05AB1E: 1 byte) O; (Java 10: 9 bytes) ,sy ,s=0ys+=
  5. Cuente los que son iguales a la entrada: (Gelatina: 1 byte) ċ; (05AB1E: 2 bytes) QO; (Java 10: 15 bytes) ,r=0yr+=s==n?1:0
  6. Salida del resultado: (Jelly: 0 bytes) implícitamente ; (05AB1E: 0 bytes) implícitamente ; (Java 10: 9 bytes)return r;
Kevin Cruijssen
fuente
1
Elogio especial para obtener salida para 34421.
ngm
@ngm :) Java puede ser malo en muchas cosas, pero en términos de rendimiento suele ser bastante bueno.
Kevin Cruijssen
1
Incluso funciona en 218918. Tiempo de espera con 3634531.
ngm
1
@ngm De hecho, estoy sorprendido de que todavía sea lo suficientemente rápido como para hacerlo 218918en 12.5 seg tbh, considerando que hará 218918-2 = 218,916iteraciones dentro de un bucle interno de: niteraciones para cada primo; 1 iteración por cada número par; y en algún lugar entre [2,p/2)iteraciones para cada número impar (cerca de dos mil millones de iteraciones), después de lo cual agrega 19518primos a la lista en la memoria. Y luego realizará un bucle adicional sum([0,19518]) = 190,485,921veces en el segundo bucle anidado. 2.223.570.640 iteraciones en total para ser exactos .
Kevin Cruijssen
@ceilingcat Gracias. Pude jugar al golf 12 bytes más con el primer cheque alternativo de @SaraJ , menos el final %iya que estamos revisando el rango [2, n], por lo que no tendré que hacerlo i=1. :)
Kevin Cruijssen
1

Physica , 41 bytes

->x:Count[Sum@Sublists[PrimeQ$$[…x]];x]

Pruébalo en línea!

Cómo funciona

->x:Count[Sum@Sublists[PrimeQ$$[…x]];x] // Full program.
->x:            // Define an anonymous function with parameter x.
    […x]        // Range [0 ... x] (inclusive).
        $$      // Filter-keep those that...
  PrimeQ        // Are prime.
 Sublists[...]  // Get all their sublists.
Sum@            // Then sum each sublist.
Count[...;x]    // Count the number of times x occurs in the result.
Sr. Xcoder
fuente
1

Haskell , 89 bytes

g n=sum[1|a<-[0..n],_<-filter(n==).scanl1(+)$drop a[p|p<-[2..n],all((>0).mod p)[2..p-1]]]

Pruébalo en línea!

Alternativa, 89 bytes

f n=length$do a<-[0..n];filter(n==).scanl1(+)$drop a[p|p<-[2..n],all((>0).mod p)[2..p-1]]

Pruébalo en línea!

ბიმო
fuente