Encuentra un número Rocco

12

Me hicieron esta pregunta en una entrevista, pero no pude encontrar ninguna solución. No sé si la pregunta era correcta o no. Intenté mucho pero no pude encontrar ninguna solución. Hablando honestamente, no se me ocurrió nada.

Rocco números

Un número entero positivo es un número Rocco si se puede representar como o n = p (p-14) , donde p es un número primo.nn=p(p+14)n=p(p14)p

Los primeros 10 números de Rocco son:

32,51,95,147,207,275,351,435,527,627

Tarea

Su código debe aceptar un entero positivo como entrada y determinar si es un número Rocco o no.

Puntos brownie

  • Escriba una función que calcule e imprima el recuento de números Rocco menores o iguales a 1 millón.
  • Escriba una función que calcule e imprima el recuento de números Rocco de la pregunta de bonificación (arriba de uno) que son primos.
vijayscode
fuente
55
Hola y bienvenidos a PPCG. Organizamos desafíos (su aspecto se ve realmente interesante) que tienen una puntuación objetiva y criterios ganadores. Intenta editar tu publicación para incluir eso. Recomiendo el golf de código como objetivo, ya que es el más fácil de acertar. Además, desea evitar esas bonificaciones; solo concéntrate en una tarea clara.
Adám
3
la salida sería un número entero : ¿no te refieres a un booleano para saber si la entrada fue un número Rocco o no?
Adám
55
Bonus 2: print 0. Todos los números Rocco son compuestos (n*..), por lo que no hay números primos en ningún rango.
TFeld
44
Los "puntos de bonificación" pueden ser simplemente valores codificados y no son beneficiosos para el desafío. Recomiendo eliminarlos.
Erik the Outgolfer
55
He editado la pregunta y las etiquetas. Siéntase libre de retroceder o editar más si no está de acuerdo. Como dijo @EriktheOutgolfer, creo que las bonificaciones deberían eliminarse.
Arnauld

Respuestas:

10

05AB1E , 8 bytes

Devuelve si es un número Rocco, o caso contrario.1n0

fDŠ/α14å

Pruébalo en línea!

¿Cómo?

Dado un número entero positivo , probamos si existe un factor primo de tal que:npn

|pnp|=14

Comentado

fDŠ/α14å  # expects a positive integer n as input       e.g. 2655
f         # push the list of unique prime factors of n  -->  2655, [ 3, 5, 59 ]
 D        # duplicate it                                -->  2655, [ 3, 5, 59 ], [ 3, 5, 59 ]
  Š       # moves the input n between the two lists     -->  [ 3, 5, 59 ], 2655, [ 3, 5, 59 ]
   /      # divide n by each prime factor               -->  [ 3, 5, 59 ], [ 885, 531, 45 ]
    α     # compute the absolute differences
          # between both remaining lists                -->  [ 882, 526, 14 ]
     14å  # does 14 appear in there?                    -->  1
Arnauld
fuente
11

JavaScript (ES7), 55 bytes

n=>(g=k=>k>0&&n%--k?g(k):k==1)(n=(49+n)**.5-7)|g(n+=14)

Pruébalo en línea!

¿Cómo?

Dado un entero positivo , estamos buscando un número primo tal que o .nxx(x+14)=nx(x14)=n

De ahí las siguientes ecuaciones cuadráticas:

(1)x2+14xn=0
(2)x214xn=0

La raíz positiva de es:(1)

x0=49+n7

y la raíz positiva de es:(2)

x1=49+n+7

Por lo tanto, el problema es equivalente a probar si o es primo.x0x1

Para hacer eso, utilizamos la clásica función de prueba de primitiva recursiva, con una prueba adicional para asegurarnos de que no se repita para siempre si se le da un número irracional como entrada.

g = k =>    // k = explicit input; this is the divisor
            // we assume that the implicit input n is equal to k on the initial call
  k > 0 &&  // abort if k is negative, which may happen if n is irrational
  n % --k ? // decrement k; if k is not a divisor of n:
    g(k)    //   do a recursive call
  :         // else:
    k == 1  //   returns true if k is equal to 1 (n is prime)
            //   or false otherwise (n is either irrational or a composite integer)

Función de envoltura principal:

n => g(n = (49 + n) ** .5 - 7) | g(n += 14)
Arnauld
fuente
6

Perl 6 , 45 28 bytes

((*+49)**.5+(7|-7)).is-prime

Pruébalo en línea!

Utiliza la construcción de Arnauld , que debe ser primo para que sea ​​un número Rocco.n+49±7n

Explicación:

 (*+49)**.5                   # Is the sqrt of input+49
           +(7|-7)            # Plus or minus 7
(                 ).is-prime  # Prime?
Jo King
fuente
6

Regex (ECMAScript), 64 62 bytes

Esta expresión regular encuentra dos números y modo que . Si los encuentra, afirma que o es primo. ¡Eso es!aa+14n=a(a+14)aa+14

Utiliza una variante del algoritmo de multiplicación que se describe brevemente en un párrafo de mi publicación de expresiones regulares abundantes . Este es un spoiler . Así que no sigas leyendo si no quieres que se te estropee un poco de magia regex unaria avanzada . Si desea intentar descubrir esta magia usted mismo, le recomiendo comenzar resolviendo algunos problemas en la lista de problemas recomendados etiquetados consecutivamente con spoilers en esta publicación anterior , e intentando encontrar las ideas matemáticas de forma independiente.

El algoritmo de multiplicación se implementa de manera diferente aquí porque estamos afirmando que dos valores conocidos multiplicados juntos equivalen a otro valor conocido (como también se hizo en la versión alternativa de la expresión regular en esta publicación , para probar que un número sea un cuadrado perfecto). En la mayoría de mis otras respuestas de expresiones regulares publicadas hasta ahora, la multiplicación se implementa como un cálculo (no una afirmación, conceptualmente hablando) donde el objetivo es encontrar el producto de dos números conocidos. Ambos métodos funcionan en ambas circunstancias, pero en cuanto al golf, son peores para hacer el trabajo del otro.

^(?=(x((x{14})(x+)))(?=(\1*)\4\2*$)(\1*$\5))\6\3?(?!(xx+)\7+$)

Pruébalo en línea!


 # For the purposes of these comments, the input number = N.
 ^
 # Find two numbers A and A+14 such that A*(A+14)==N.
 (?=
     (x((x{14})(x+)))   # \1 = A+14; \2 = \1-1; \3 = 14; \4 = A-1; tail -= \1
     (?=                # Assert that \1 * (\4+1) == N.
         (\1*)\4\2*$    # We are asserting that N is the smallest number satisfying
                        # two moduli, thus proving it is the product of A and A+14
                        # via the Chinese Remainder Theorem. The (\1*) has the effect
                        # of testing every value that satisfies the "≡0 mod \1"
                        # modulus, starting with the smallest (zero), against "\4\2*$",
                        # to see if it also satisfies the "≡\4 mod \2" modulus; if any
                        # smaller number satisfied both moduli, (\1*) would capture a
                        # nonzero value in \5. Note that this actually finds the
                        # product of \4*\1, not (\4+1)*\1 which what we actually want,
                        # but this is fine, because we already subtracted \1 and thus
                        # \4*\1 is the value of tail at the start of this lookahead.
                        # This implementation of multiplication is very efficient
                        # golf-wise, but slow, because if the number being tested is
                        # not even divisible by \1, the entire test done inside this
                        # lookahead is invalid, and the "\1*$" test below will only
                        # fail after this useless test has finished.
     )
     (\1*$\5)           # Assert that the above test proved \1*(\4+1)==N, by
                        # asserting that tail is divisible by \1 and that \5==0;
                        # \6 = tool to make tail = \1
 )
 # Assert that either A or A+14 is prime.
 \6                     # tail = \1 == A+14
 \3?                    # optionally make tail = A
 (?!(xx+)\7+$)          # Assert tail is prime. We don't need to exclude treating
                        # 1 as prime, because the potential false positive of N==15
                        # is already excluded by requiring \4 >= 1.
 

Código muerto
fuente
3

Brachylog , 13 12 bytes

ṗ;14{+|-};?×

Ingrese el número de candidato como argumento de línea de comando. Salidas trueo false. Pruébalo en línea!

Explicación

El código es un predicado cuya entrada no tiene restricciones y cuya salida es el número que estamos probando.

ṗ             Let the input ? be a prime number
 ;14          Pair it with 14, yielding the list [?, 14]
    {+|-}     Either add or subtract, yielding ?+14 or ?-14
         ;?   Pair the result with the input, yielding [?+14, ?] or [?-14, ?]
           ×  Multiply; the result must match the candidate number

(Los consejos son bienvenidos. Eso {+|-}todavía se siente torpe).

DLosc
fuente
3

Brachylog , 9 bytes

Enfoque diferente a la respuesta de DLosc

Ċ-14&∋ṗ&×

Toma N como salida, devuelve [P, P-14] o [P + 14, P] a través de la entrada (el número más grande primero)

explicación

Ċ              # The 'input' is a pair of numbers
 -14           #   where the 2nd is 14 smaller then the first
    &∋ṗ        #   and the pair contains a prime
       &×      #   and the numbers multiplied give the output (N)

Pruébalo en línea!

Kroppeb
fuente
2

Pyth, 22 20 bytes

}Qsm*Ld+Ld_B14fP_TSh

Pruébelo en línea aquí .

}Qsm*Ld+Ld_B14fP_TShQ   Implicit: Q=eval(input())
                        Trailing Q inferred
                  ShQ   Range [1-(Q+1)]
              fP_T      Filter the above to keep primes
   m                    Map the elements of the above, as d, using:
          _B14            [14, -14]
       +Ld                Add d to each
    *Ld                   Multiply each by d
  s                     Flatten result of map
}Q                      Is Q in the above? Implicit print

Editar: los 3 bytes guardados como entrada siempre serán positivos, por lo que no es necesario filtrar los valores negativos de la lista. También se corrigió un error para las entradas 1y 2costaba 1 byte. Versión previa:}Qsm*Ld>#0+Ld_B14fP_TU

Sok
fuente
2

05AB1E , 16 15 14 bytes

Ahorré 1 byte calculando 14 con en lugar de žvÍ(no puedo creer que no haya pensado en esto en primer lugar).

Guardado 1 byte gracias a Emigna

ÅPε7·D(‚+y*Q}Z

Pruébalo en línea! o Probar todas las entradas

Explicación

                 # Implicit input n
ÅP               # Push a list of primes up to n
  ε         }    # For each prime in the list...
   7·            # Push 14 (by doubling 7)
     D(‚         # Push -14 and pair them together to get [14,-14]
        +        # Add [14,-14] to the prime
         y*      # Multiply the prime to compute p(p-14) and p(p+14)
           Q     # Check if the (implicit) input is equal to each element
             Z   # Take the maximum
Wisław
fuente
1
Puede guardar un byte cambiando }˜såpara Q}Zutilizar la entrada implícita. Tu Test-Suite tendría que cambiarse un poco a algo como esto para que funcione. Además, una forma más obvia de escribir žvÍo sería 14;)
Emigna
¡Gracias! ¿Por qué hacerlo fácil cuando puedes empujar 14 de la manera más complicada / facepalm :)
Wisław
2

Retina 0.8.2 , 61 bytes

.+
$*
^((1{14})1(1)+)(?<=(?<!^\4+(..+))\2?)(?<-3>\1)+$(?(3)1)

Pruébalo en línea! Explicación:

.+
$*

Convierte a unario.

^((1{14})1(1)+)

\1captura el mayor de los dos factores. \2captura la constante 14, guardando un byte. \3captura el menor de los dos factores, menos 1. Esto también asegura que ambos factores sean al menos 2.

(?<=(?<!^\4+(..+))\2?)

Verifique los dos factores para asegurarse de que al menos uno de ellos sea primo. La idea de usar \2?fue robada descaradamente de la respuesta de @ Deadcode.

(?<-3>\1)+

Repita el mayor de los dos factores varias veces igual a uno menos que el menor de los dos factores. Como ya hemos capturado el factor más grande una vez que esto termina capturando el producto de los dos factores.

$(?(3)1)

Asegúrese de que el producto sea igual al número dado.

Una traducción directa a Retina 1 al reemplazar $*con *1tendría el mismo conteo de bytes, pero un byte podría guardarse reemplazando todos los 1s con _sy luego *1podría reemplazarse con en *lugar de *_. Respuesta anterior de Retina 1 para 68 bytes:

.+
*
Lw$`^(__+)(?=(\1)+$)
$1 _$#2*
Am` (__+)\1+$
(_+) \1

0m`^_{14}$

Pruébalo en línea! Explicación:

.+
*

Convierte a unario.

Lw$`^(__+)(?=(\1)+$)
$1 _$#2*

Encuentra todos los pares de factores.

Am` (__+)\1+$

Asegúrese de que uno sea primo.

(_+) \1

Toma la diferencia absoluta.

0m`^_{14}$

Comprueba si hay 14.

Neil
fuente
1

JavaScript (nodo de Babel) , 69 bytes

Maldición, pensé que iba a superar la respuesta de Arnaulds pero no .....: c

x=>[...Array(x)].some((a,b)=>x/(a=(p=n=>--b-1?n%b&&p(n):n)(b))-a==14)

Pruébalo en línea!

Quiero deshacerme de la x=>[...Array(x)].some(parte usando la recursión para que pueda acortarse con el tiempo

Explicación

x=>[...Array(x)]                                                              Creates a range from 0 to x-1 and map:

                .some((a,b)=>                                                 Returns True if any of the following values is true
                             x/                                              Input number divided by
                                (a=(p=n=>--b-1?n%b&&p(n):n)(b))               recursive helper function. Receives a number (mapped value) as parameters and returns 
                                                                              the same number if it is prime, otherwise returns 1. Take this value
                                                                              and assign to variable a
                                                               -a            Subtract a from the result  
                                                                     ==14    Compare result equal to 14

Utiliza la fórmula

n/pp==14

Luis felipe De jesus Munoz
fuente
1

APL (NARS) 16 caracteres, 32 bytes

{14=∣r-⍵÷r←↑⌽π⍵}

{π⍵} encontraría la factorización de su argumento y suponemos que el último elemento de su resultado (la lista de divisores de n) es el máximo divisor primo de n; Aquí suponemos que una definición equivalente de número Rocco es: n es un número Rocco <=> factor primo máximo de n: r es tal que es verdadero 14 = ∣rn ÷ r [para el pseudocódigo C como 14 == abs (rn / r) esta definición de número de Rocco parece estar bien en el rango 1..1000000]; el rango del valor ok sería 1..maxInt; prueba:

 f←{14=∣r-⍵÷r←↑⌽π⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨1..10000
32  51  95  147  207  275  351  435  527  627  851  1107  1247  1395  1551  1887  2067  2255  2451  2655  2867  3551  4047  4307  4575  5135  5427  5727  6035  6351  6675  7347  8051  8787  9167  9951   
RosLuP
fuente
1

C # (compilador interactivo de Visual C #) , 99 bytes

n=>Enumerable.Range(2,n).Any(p=>Enumerable.Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

Pruébalo en línea!

Enumerable.Range ataca de nuevo :) Usando el indicador del compilador loco, puedes reducir las cosas bastante, aunque soy un fanático de la solución de vainilla.

C # (compilador interactivo de Visual C #) + /u:System.Linq.Enumerable, 77 bytes

n=>Range(2,n).Any(p=>Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

Pruébalo en línea!

A continuación se muestra un puerto de la solución de Arnauld que parecía bastante genial. Actualmente es el más largo, pero probablemente se pueda jugar golf.

C # (compilador interactivo de Visual C #) , 101 bytes

n=>{bool g(int k)=>--k<2?n>1:n%k>0&g(k);var d=Math.Sqrt(n+49)-7;return(n=(int)d)==d&(g(n)|g(n+=14));}

Pruébalo en línea!

dana
fuente
0

APL (NARS) 30 caracteres, 60 bytes

{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}

Aquí 0π es la función decir si un número es primo, prueba:

 f←{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨0..700
32  51  95  147  207  275  351  435  527  627
RosLuP
fuente
0

F #, 2 respuestas (sin competencia)

Realmente me gustaron las respuestas de @Arnauld, así que las traduje.

123 bytes , basado en la respuesta de JavaScript

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||)

Explicación:

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||) //Lambda which takes an integer, n
       let t=int<|sqrt(float n+49.)                                                                                         //let t be n, converted to float, add 49 and get square root, converted back to int (F# type restrictions)
                                   in                                                                                       //in the following...
                                                                                                  [t-7;t+7]                 //Subtract and add 7 to t in a list of 2 results (Lists and Seqs can be interchanged various places)
                                      Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)                          //See if either are prime (here, if either result has 2 and only 2 divisors)
                                                                                                           |>Seq.reduce(||) //And logically OR the resulting sequence

125 bytes , basado en la respuesta 05AB1E

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14

Explicación:

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14  //Lambda which takes an integer, n
       let l=Seq.filter(fun i->n%i=0)[2..n-1]                                                                                  //let l be the list of n's primes 
                                             in                                                                                //in...
                                                let m=Seq.map(fun i->n/i)l                                                     //m, which is n divided by each of l's contents
                                                                           in                                                  //and then...
                                                                              Seq.map2(fun a b->abs(a-b))l m                   //take the absolute difference between each pair of items in the two sequences to make a new sequence
                                                                                                            |>Seq.contains 14  //and does the resulting sequence contain the number 14?
LSM07
fuente
0

Python 2 , 58 bytes

Salidas por código de salida, falla ( 1) para números Rocco.

P=k=1.
n=input()
exec"P*=k*k;k+=1;P%k*abs(n/k-k)==14>y;"*n

Pruébalo en línea!

ovs
fuente