La rana principal 🐸

44

La "rana prima" es un animal extraño que salta entre enteros, hasta que llega el 3 o 19 ...


Su programa debe aceptar un número entero ncomo entrada y salida del resultado del algoritmo siguiente ( 3o 19).

Para un entero dado n >= 2:

  1. Dejar fser la posición de la rana. Inicialmente se establece enn
  2. if f = 3or f = 19: la rana deja de saltar: detiene el programa y la salida f.
  3. si fes primo: la rana salta a la posición 2×f-1. Regrese al paso 2.
  4. si fes compuesto: dejar que dsea f's divisor primo mayor. La rana salta a la posición f-d. Regrese al paso 2.

Ejemplos:

Un ejemplo con n = 5:

5 > 9 > 6 > 3 stop

El programa debería salir 3.

Otro ejemplo con n = 23:

23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop

De nuevo, el programa debería salir 3.

Casos de prueba:

10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19

Puede suponer 1 < n < 1000000(he comprobado que el programa termina con estos valores).

Arnaud
fuente
3
3 bucles son [3 5 9 6 3] y 19 bucles son [19 37 73 145 116 87 58 29 57 38 19]
Arnaud
8
Genial variación de Collatz.
Arthur
3
Si no podemos demostrar que la rana siempre llega a 3o 19, podríamos cambiar el elemento 2. en el algoritmo para decir que si la rana ha entrado en un bucle (ha encontrado una posición que ha visto antes), entonces deja de saltar y devuelve el más pequeño miembro de ese ciclo.
Jeppe Stig Nielsen
44
@PyRulez Si llega a eso, probablemente deberías decirle al OP.
mbomb007
3
@KeyuGan Quizás sea bueno publicar esto en Math.SE.
mbomb007

Respuestas:

16

Python 2 , 101 93 92 90 88 87 85 bytes

import sympy
n=input()
while~16&n-3:m=max(sympy.factorint(n));n-=[1-n,m][m<n]
print n

Pruébalo en línea!

TFeld
fuente
1
while~16&n!=3Guarda un byte.
Lynn
66
¡Oh, ~16&n-3incluso funciona!
Lynn
12

C (gcc),  87  65 bytes

i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);n=~16&n-3?f(n-k?:n+n-1):n;}

Pruébalo en línea!

Explicación:

i,k;
f(n)
{
    for (i=n; i>1;)              // Loop until `k` is prime (the largest positive
                                 // `i` inequal to `k` that divides `k` is 1).
        for (k=i; k%--i;);       // Find the largest factor `k`

    n =                          // Returning like this is undefined behaviour,
                                 // but happens to work with gcc. This can be
                                 // replaced with `return` at the cost of 4 bytes.

        ~16&n-3                  // If `n` is 3 or 19, this expression equals 0 and
                                 // the algorithm halts. Otherwise the function
                                 // calls itself to perform the next iteration.

        ? f(n-k ?: n+n-1)        // If `n-k` is non-zero, n is not prime.
                                 // In this case call `f` with the value of `n-k`.
                                 // (Omitting the second `n-k` between `?` and `:`
                                 // is a gcc extension)
                                 // Otherwise call `f` with `2*n-1`.

        : n;                     // All done, `n` is returned.
}

Versión portátil (72 bytes):

i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);return~16&n-3?f(n-k?n-k:n+n-1):n;}

Pruébalo en línea!

Con nombres de variables más apropiados:

f,r;o(g){for(f=g;f>1;)for(r=f;r%--f;);g=~16&g-3?o(g-r?:g+g-1):g;}

Pruébalo en línea!

Steadybox
fuente
55
Me encanta jugar con la palabra rana y tus variables. +1.
rayryeng - Restablecer Monica
10

Retina , 63 62 bytes

Gracias a Neil por guardar 1 byte.

{`^(11+)(?<!^\2+(11+))(?=\1+$)

^(?!(11+)\1+$|111$|1{19}$)1
$_

Pruébalo en línea!

Entrada y salida en unario (el conjunto de pruebas usa decimal por conveniencia). Esta solución se vuelve increíblemente lenta para entradas más grandes. El 9983caso de prueba expira en TIO.

Explicación

Debido a esto {, ambas etapas del programa simplemente se ejecutan en un bucle hasta que ya no afectan a la cadena. Alternamos entre una etapa de procesamiento de compuestos y una etapa de procesamiento de primos. Eso nos permite evitar un condicional real (que realmente no existe en Retina). Si el valor actual es del tipo incorrecto para la etapa, la etapa simplemente no hace nada.

^(11+)(?<!^\2+(11+))(?=\1+$)

Esto procesa compuestos. Emparejamos un divisor potencial con (11+), pero luego verificamos que no está compuesto con (?<!^\2+(11+)), por lo que solo consideramos factores primos. Debido a la codicia de +, esto prioriza el factor más importante. Luego verificamos que este divisor potencial es un divisor real tratando de hacer coincidir el resto de la cadena con repeticiones de la misma (?=\1+$). Este divisor simplemente se elimina de la cadena, que es cómo restas algo en unario.

^(?!(11+)\1+$|111$|1{19}$)1
$_

Esto procesa primos, excepto 3 y 19 . La anticipación negativa asegura que la entrada no sea compuesta, ni 3 ni 19 . Luego hacemos coincidir un solo 1y lo reemplazamos con toda la cadena. Esta es una forma unaria de computación n - 1 + n , que por supuesto es 2n-1 .

Una vez que tocamos 3 o 19 , ninguna etapa puede coincidir con la cadena y ya no se cambiará.

Martin Ender
fuente
1
¿No es lo 1$'mismo que $_?
Neil
44
@Neil Sí ......
Martin Ender
8

Casco , 15 bytes

Ω€p57§|o←DṠ-o→p

Pruébalo en línea!

Explicación

Ω€p57§|o←DṠ-o→p  Implicit input n.
Ω                Do this to n until
 €p57            you get a prime factor of 57 (which are 3 and 19):
            o→p   Take last element of the prime factors of n
          Ṡ-      and subtract it from n,
     §|           or if this gives 0 (so n is prime),
       o←D        double and decrement n.
Zgarb
fuente
8

Jalea , 12 bytes

_ÆfṂoḤ’$µÐḶṂ

Pruébalo en línea!

Cómo funciona

_ÆfṂoḤ’$µÐḶṂ  Maink link. Argument: n

        µ     Combine the links to the left into a chain.
         ÐḶ   Repeatedly call the chain monadically until the results are no longer
              unique. Yield the loop, i.e., the first occurrence of the first
              repeated integer, up to and excluding the repetition.
              Let's call the argument of the chain k.
_Æf             Subtract all prime factors of k from k.
   Ṃ            Take the minimum of the differences. This yields 0 iff k is prime.
     Ḥ’$        Compute 2k-1.
    o           Take the logical OR of the results.
              The result is now a rotation of either [3, 5, 9, 6] or
              [19, 37, 73, 145, 116, 87, 58, 29, 57, 38].
          Ṃ   Take the minimum, yielding either 3 or 19.
Dennis
fuente
7

Wolfram Language (Mathematica) , 6566 68 bytes

#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
  • -1 bytes, gracias a Misha Lavrov!
  • -2 bytes, gracias a Martin!

Pruébalo en línea!

Inspirado en la punta . Básicamente, solo recrea el algoritmo.

//.es RepeatedReplacey /;es Condition. Entonces, el código reemplazará i_(una sola cantidad) con If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i], hasta que se i!=3&&!=19evalúe True.

Punto de referencia:

punto de referencia

Keyu Gan
fuente
3
Dato 10000000010maximum number of iterations is 2^16 (= 65536)
curioso
1
Una forma un poco más corta de verificar 3 y 19 es#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
Misha Lavrov el
@MishaLavrov pero el resultado es incorrecto?
Keyu Gan el
@KeyuGan Para mí, las dos funciones dan exactamente el mismo resultado para los enteros del 1 al 1000.
Misha Lavrov
1
Posiblemente, el problema que tiene es que se insertan caracteres no imprimibles cuando copia y pega los comentarios, lo que a veces sucede.
Misha Lavrov
6

05AB1E , 19 18 17 bytes

[ÐƵηfså#pi·<ëDfθ-

Pruébalo en línea!

Explicación

[      #            # loop until
 Ð   så             # a copy of the current value is contained in
  Ƶηf               # the unique prime factors of 171
        pi          # if the current value is prime
          ·<        # double and decrement
            ë   -   # else subtract
             Dfθ    # the largest prime factor of a copy of the current value
Emigna
fuente
44
+1 por tener una rana real en tu código fuente
Arnaud
Por 57991 más de 1 minuto
RosLuP
@RosLuP: es mejor que ejecutes casos de prueba muy largos sin conexión;)
Emigna
5

JavaScript (ES6), 73 71 69 bytes

f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38

Casos de prueba

Formateado y comentado

f = n =>                 // given n
  57 % n ?               // if n is neither 3, 19 or 57 (and assuming that n is > 1):
    f(                   //   do a recursive call to f() with:
      n -                //     n minus
      (g = (k, d = 1) => //     the result of the recursive function g():
        ++d < k ?        //       increment d; if d is less than k:
          k % d ?        //         if d is not a divisor of k:
            g(k, d)      //           recursive call to g() with k and d unchanged
          :              //         else:
            g(k / d)     //           recursive call to g() with k = k / d, d = 1
        :                //       else, d is now the highest prime divisor of n:
          d < n ?        //         if d is less than n:
            d            //           n is composite: return d, which results in f(n - d)
          :              //         else:
            1 - n        //           n is prime: return 1 - n, which results in f(2n - 1)
      )(n)               //     initial call to g()
    )                    //   end of recursive call to f()
  :                      // else:
    n % 38               //   return n % 38 (gives 19 as expected if n = 57)
Arnauld
fuente
1
Inteligente, usando 57%ny en n%38lugar de n==3|n==19. También guardé 1 byte en mi respuesta Java , ¡así que gracias!
Kevin Cruijssen
En ideone 57991 la entrada genera prog.js: 2: 26 InternalError: demasiada recursión
RosLuP
En tio f = n => 57% n? F (n- (g = (k, d = 1) => ++ d <k? K% d? G (k, d): g (k / d) : d <n? d: 1-n) (n)): n% 38 print (f (57991)) generar parada programa no salida, me parece
RosLuP
1
@RosLuP Este es un desafío de código de golf sin ninguna restricción específica. El consenso actual es que las limitaciones de velocidad o memoria (como el tamaño de la pila de llamadas) pueden ignorarse a menos que se indique explícitamente lo contrario en la pregunta. Doy por sentado que el límite de 1000000 es solo informativo porque la secuencia no se probó más allá de eso. Por cierto, su solución de 70 bytes está perfectamente bien y probablemente sea más relevante que la versión de 93 bytes para un desafío de código de golf.
Arnauld
4

Jalea , 23 19 bytes

-4 bytes de millas . Sin embargo, aún más largo que 05AB1E

Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿

Pruébalo en línea!

usuario202729
fuente
1
Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿usando un bucle while en su lugar y algunos reordenamientos
millas del
4

Python 2 , 110 105 103 101 bytes

-2 bytes gracias a @Lynn

f=lambda n,i=2,k=0:i/n and(n*(n&~16==3)or f((2*i-1,k-i)[k>0]))or n%i and f(n,i+1,k)or f(n/i,2,k or n)

Pruébalo en línea!


Python 2 , 116 112 105 bytes

f=lambda n,i=2:i/n*i or n%i and f(n,i+1)or f(n/i)
n=input()
while~16&n-3:n=[2*n-1,n-f(n)][f(n)<n]
print n

Pruébalo en línea!

ovs
fuente
1
…n*(n&~16==3)or…ahorra 2 bytes.
Lynn
Para entrada 57991 sys.setrecursionlimit (20000)
RosLuP
4

MATL , 22 21 bytes

¡Gracias a @Giuseppe por eliminar 1 byte!

`tZp?Eq}tYfX>-]tI19h-

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

`           % Do...while
  t         %   Duplicate. Takes (implicit) input the first time
  Zp        %   Is it prime? 
  ?         %   If so
    Eq      %     Times 2, minus 1
  }         %   Else
    t       %     Duplicate
    YfX>-   %     Prime divisors, maximum, subtract
  ]         %   End
  t         %   Duplicate
  I19h      %   Push array [3 19]
  -         %   Subtract, element-wise. The result is truthy if and only if
            %   it doesn't contain any zero
            % End (implicit). Next iteraton if top of the stack is truthy
            % Display (implicit)
Luis Mendo
fuente
4

Haskell - 154 bytes

f 3=3
f 19=19
f n
 |(c==[1])=f$2*n-1
 |True=f$n-head c
 where c=z n;v b=reverse[x|x<-[1..(b-1)],b`rem`x==0];z j=case v j of[1]->[1];s->filter((==[1]).v)$s

Probablemente faltan algunos trucos de golf aquí, este es mi primer intento en Haskell Golf.

Gremlin de hierro
fuente
Hola y bienvenidos al sitio. No necesita las nuevas líneas y espacios para guardias de patrones. También se puede utilizar 1>0para Truela mayoría de las veces, pero a menudo puede ser que sea mejor usar una asignación, por ejemplo c<-z n.
Wheat Wizard
1
[x|x<-[b-1,b-2..1],rem b x==0]También es corto que reverse[x|x<-[1..(b-1)],brem x==0].
Wheat Wizard
2
Y una última cosa, si desea hablar sobre el golf haskell, puede unirse a nosotros en Of Monads and Men .
Wheat Wizard
3

Neim , 17 16 bytes

ͻY𝐏𝕚÷D𝐌Ξᚫ<#D𝐏𝐠𝕊

Explicación:

ͻ                   Start infinite loop
 D                  Duplicate
  Y                 Push 57
   𝐏                Prime factors: [3 19]
     𝕚              If the second-to-top of stack is in the list
      ÷             Break the loop
       D            Duplicate
        𝐌Ξᚫ<       If prime, double and decrement
            #D𝐏𝐠𝕊   Otherwise, subtract the largest prime factor

Pruébalo en línea!

Okx
fuente
3

Números R + , 102 99 bytes

function(n){while(!n%in%c(3,19))n="if"(isPrime(n),2*n-1,n-max(primeFactors(n)))
n}
library(numbers)

Pruébalo en línea!

R no es conocido por sus complementos cortos, ¡e incluso los paquetes hacen lo mismo!

Giuseppe
fuente
3

Java 8, 140 135 134 94 bytes

n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;t/=m=f);return n%38;}

-5 bytes que convierten el método recursivo Java 7 a Java 8 lambda con bucle.
-1 byte implícito gracias a la respuesta de JavaScript de @Arnauld cambiando n!=3&n!=19y return n;hacia 57%n>0y return n%38;.
Creo que debería ser posible de alguna manera combinar los dos bucles y verificar si nes primo, y obtener su mayor factor primo al mismo tiempo, pero no puedo resolverlo (todavía). Entonces esta será la versión inicial por ahora.
-40 enormes bytes gracias a @Nevay, haciendo lo que no pude hacer: combinando los bucles para verificar los primos y el factor primo más grande a la vez.

Explicación:

Pruébelo aquí (se ejecuta incluso 999999en menos de 1 segundo).

n->{                  // Method with integer as both parameter and return-type
  for(int f,          //  Flag-integer
          t,          //  Temp-integer
          m=1;        //  Max prime factor integer, starting at 0
      57%n>0;         //  Loop (1) as long as `n` is not 3, not 19 and not 57:
      n=f>n?          //    After every iteration: if `f` is larger than `n`:
         2*n-1        //     Change `n` to `2*n-1`
        :             //    Else:
         n-m)         //     Change `n` to `n-m`
    for(t=n,          //   Reset `t` to `n`
        f=1;          //   Reset `f` to 1
        f++<t;)       //   Inner loop (2) from 2 to `t` (inclusive)
      for(;t%f<1;     //    Inner loop (3) as long as `t` is divisible by `f`
        t/=m=f;       //     Set `m` to `f`, and set `t` to `t/f`
      );              //    End of inner loop (3)
                      //   End of inner loop (2) (implicit / single-line body)
                      //  End of loop (1) (implicit / single-line body)
  return n%38;        //  Return `n%38`, which is now either 3 or 19
}                     // End of method
Kevin Cruijssen
fuente
1
1 personaje menos de ser un políglota C # :(
Ian H.
@IanH. Jeje, sí, ese suele ser el caso: en n=>lugar de n->. Y a veces llamadas en minúsculas / mayúsculas. ;)
Kevin Cruijssen
1
94 bytes:n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;)t/=m=f;return n%38;}
Nevay
@Nevay ¡Gracias! Simplemente sabía que debería ser posible combinar los bucles, pero no pude resolverlo. ¡La friolera de 40 bytes guardados gracias a ti!
Kevin Cruijssen
3

Bash, 73 bytes

((57%$1))&&$0 $[(x=$1-`factor $1|sed 's/.* //'`)?x:2*$1-1]||echo $[$1%38]

Pruébalo en línea! Modificado ligeramente para trabajar en TIO.

Recursivamente llama a su propio archivo de script utilizando $0, que no funciona en TIO porque debe ejecutarse como./filename.sh . Acepta entradas como argumento de línea de comandos.

Utiliza el mismo truco de módulo que la respuesta JS de @ Arnauld .

Casos de prueba

$ for t in 5 23 10 74 94 417 991 9983;{ echo -n "$t -> "; ./prime-frog.sh $t; }
5 -> 3
23 -> 3
10 -> 3
74 -> 19
94 -> 3
417 -> 3
991 -> 19
9983 -> 19
Justin Mariner
fuente
2

Python 3 , 97 bytes

f=lambda n:n*(n&-17==3)or f(n-max(k*all(n%k<k%j for j in range(2,k))for k in range(n+1))or 2*n-1)

Pruébalo en línea!

Dennis
fuente
Para 57991 la entrada de 1 minuto no fue suficiente
RosLuP
1

Pyth , 19 bytes

.W!/P57H?P_ZtyZ-ZeP

¡Verifique todos los casos de prueba!

La respuesta de Husk me inspiró a guardar 2 bytes ( ,3 19para P57).

Como funciona esto

.W! / P57H? P_ZtyZ-ZeP - Programa completo.

.W - Funcional mientras. Mientras que A (valor) es verdadero, valor = B (valor). Devuelve el último valor.
    P57 - Los factores primos de 57 ([3, 19]).
   / H: cuenta las ocurrencias del valor actual.
  ! - Lógico NO. 0 -> Verdad, cualquier otra cosa -> Falsy.
        ? P_Z - Si el valor actual es primo, entonces:
            tyZ: duplica el valor actual, decremento.
               -ZeP - De lo contrario, resta el factor primo máximo del valor actual de sí mismo.
                     - Imprimir implícitamente.
Sr. Xcoder
fuente
1

PowerShell , 150 126 bytes

for($n="$args";57%$n){$a=$n;$d=for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}};if($n-in$d){$n+=$n-1}else{$n-=$d[-1]}}$n%38

Pruébalo en línea! (advertencia: lento para números más grandes)

Método iterativo PowerShell no tiene incorporados factores primos de factorización, por lo que toma prestado el código de mi respuesta en Prime Factors Buddies .

Primero es nuestro forbucle. La configuración se establece $ncomo el valor de entrada, y el condicional mantiene el ciclo en marcha siempre que 57%$nno sea cero (gracias a Arnauld por ese truco). Dentro del ciclo, primero obtenemos una lista de factores primos de $a(establecido en $n). Este es el código prestado de Prime Factors Buddies. Si la entrada $aya es primo, esto devolverá solo $a(importante más adelante). Eso (potencialmente solo $a) se almacena en $d.

El siguiente es un if/ elsecondicional. Por el iflado, verificamos si $nes así -in $d. Si es así, eso significa que $nes primo, así que tomamos $n=2*$n-1o $n+=$n-1. De lo contrario, es compuesto, por lo que necesitamos encontrar el factor primo más grande. Eso significa que necesitamos tomar el último [-1]de $dy restarlo de $ncon $n-=. Esto funciona porque estamos haciendo un bucle 2y, por lo tanto, el último elemento $dya será el más grande.

Una vez que terminamos de hacer un bucle, simplemente colocamos $n%38(nuevamente, gracias Arnauld) en la tubería y la salida está implícita.

AdmBorkBork
fuente
1

APL (Dyalog Unicode) , 113 90 59 bytes

CY 'dfns'
g←{1pco ⍵:f(2×⍵)-1f⍵-⊃⌽3pco ⍵}
f←{⍵∊3 19:⍵⋄g ⍵}

Pruébalo en línea!

TIO funciona con valores de hasta ~ 3200. Probado en mi PC para el último caso de prueba. Para probar en TIO, simplemente agregue f valueal final del código. Ya no se aplica, gracias a @ Adám por señalar que mi algoritmo de comprobación de primalidades era realmente malo y me proporcionó un reemplazo; También para el guardado de 23 bytes.

Editado para arreglar el conteo de bytes.

Cómo funciona

CY 'dfns'                      # Imports every Defined Function, which is shorter than importing just the function I used (pco).

g←{1pco ⍵:f(2×⍵)-1f⍵-⊃⌽3pco ⍵} 
g                              # define g as
   1pco ⍵:                      # if the argument ⍵ is prime
          f(2×⍵)-1              # Call f over 2×⍵-1
                  f            # else, call f over
                               # the first element of the
                      3pco     # list of prime factors of ⍵
                               # reversed

f←{⍵∊3 19:⍵⋄g ⍵}
f                              # Define f as
        :                      # if the argument ⍵
                               # is in
     3 19                       # the list [3, 19]
                               # return the argument ⍵
                               # else
            g                  # call g over the argument ⍵
J. Sallé
fuente
1

Axioma, 93 bytes

h(n)==(repeat(n=3 or n=19 or n<2=>break;prime? n=>(n:=2*n-1);n:=n-last(factors(n)).factor);n)

prueba:

(4) -> [[i,h(i)] for i in [10,74,94,417,991,9983]]
   (4)  [[10,3],[74,19],[94,3],[417,3],[991,19],[9983,19]]
                                                  Type: List List Integer

Habría 68 bytes de función

q x==(n<4=>3;n=19=>n;prime? n=>q(2*n-1);q(n-last(factors n).factor))

pero para n = 57991 (si mal no recuerdo) sale el espacio reservado de la pila.

RosLuP
fuente