Cálculo de primos de Collatz

21

Defina la función f (n) para un entero positivo n de la siguiente manera:

  • n / 2 , si n es par
  • 3 * n + 1 , si n es impar

Si aplica repetidamente esta función a cualquier n mayor que 0, el resultado siempre parece converger a 1 (aunque todavía nadie ha podido probarlo). Esta propiedad se conoce como la conjetura de Collatz .

Defina el tiempo de detención de un número entero como el número de veces que debe pasarlo a través de la función Collatz f antes de que llegue a 1. Aquí están los tiempos de detención de los primeros 15 enteros:

1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

Llamemos a cualquier conjunto de números con el mismo tiempo de detención que los primos de Collatz . Por ejemplo, 5 y 32 son primos de Collatz, con un tiempo de parada de 5.

Su tarea: escribir un programa o función que tome un número entero no negativo y genere el conjunto de primos de Collatz cuyo tiempo de detención es igual a ese número entero.

Entrada

Un entero S no negativo, dado a través de STDIN, ARGV o argumento de función.

Salida

Una lista de todos los números cuyo tiempo de detención es S, ordenados en orden ascendente . La lista puede ser generada por su programa, o devuelta o generada por su función. El formato de salida es flexible: está separado por espacios, por líneas nuevas o cualquier formato de lista estándar de su idioma, siempre que los números se puedan distinguir fácilmente entre sí.

Requisitos

Su envío debe dar resultados correctos para cualquier S ≤ 30. Debe finalizar en segundos o minutos, no en horas o días.

Ejemplos

0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

Aquí hay un resumen de la salida para S = 30 .

Esto es : el programa más corto en bytes gana. ¡Buena suerte!

DLosc
fuente
¿Qué hay de los ciclos? No vi una mención de evitación del ciclo. Porque para S = 5, hay 3 valores [4, 5, 32] porque puede ir "1 - 2 - 4 - 1 - 2- 4"
JPMC
1
@JPMC Evitar el ciclo está implícito en la definición de tiempo de parada. El tiempo de parada de 4 es 2, no 5, porque 2 es "el número de veces que tiene que pasarlo a través de la función Collatz antes de que llegue a 1."
DLosc
Ah, perdoname. Estaba pensando que un número podría tener múltiples tiempos de detención, ya que múltiples caminos pueden conducir a él. Pero eso fue con respecto a construir desde 1, no trabajar desde N. Lo siento.
JPMC
1
@DLosc Pyth, por supuesto.
isaacg
1
Relacionado, pero no golfizado: math.stackexchange.com/q/470782/20792 y math.stackexchange.com/q/1243841/20792
Pureferret

Respuestas:

7

Pyth, 26 24 21 bytes

Su+yMG-/R3fq4%T6G1Q]1

Este código se ejecuta instantáneamente por S=30. Pruébelo usted mismo: demostración

Gracias a @isaacg por guardar 5 bytes.

Explicación

Mi código comienza 1y deshace la función Collatz. Mapea todos los números ddel S-1paso a 2*dy (d-1)/3. Sin embargo, el último no siempre es válido.

                        implicit: Q = input number
                   ]1   start with G = [1]
 u                Q     apply the following function Q-times to G:
                          update G by
   yMG                      each number in G doubled
  +                       +
          fq4%T6G           filter G for numbers T, which satisfy 4==T%6
       /R3                  and divide them by 3
      -          1          and remove 1, if it is in the list
                            (to avoid jumping from 4 to 1)
S                       sort the result and print
Jakube
fuente
Ese es un hermoso uso de -F.
isaacg
1
Si coloca una - ... 1suma alrededor de la reducción dentro de la reducción, no necesita que la reducción sea una .u, ni el -Fexterior. Guarda 2 caracteres.
isaacg
@isaacg Gracias. De hecho, tuve esto en una versión anterior, pero lo eliminé durante la depuración de un error.
Jakube
3
He tomado prestado @ isaacg para mi propia respuesta. He pasado horas tratando de encontrar el código más corto para eliminar duplicados, pero esta es, con mucho, la solución más elegante. Además, me gusta mucho el uso de una tupla para descartar cocientes no válidos. Lamentablemente, CJam no tiene tuplas, pero logré asignar cocientes inválidos a 1.
Dennis
@Jakube q4%d6es equivalente a !%hhd6, pero 1 carácter más corto.
isaacg
8

Mathematica, 98 92 89 bytes

Esta solución resuelve S = 30inmediatamente:

(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

Esta es una función sin nombre que toma Scomo único parámetro y devuelve una lista de los primos de Collatz.

El algoritmo es una búsqueda simple de amplitud. Los primos de Collatz para un dado Sson todos los enteros a los que se puede llegar desde los primos de Collatz para S-1vía 2*no números impares que se pueden alcanzar a través de (n-1)/3. También debemos asegurarnos de que solo producimos aquellos enteros que se alcanzaron por primera vez después de los Spasos, para que podamos hacer un seguimiento de todos los primos anteriores py eliminarlos del resultado. Como estamos haciendo eso de todos modos, podemos guardar algunos bytes calculando los pasos de todos los primos anteriores (no solo los de S-1) para guardar algunos bytes (eso lo hace un poco más lento, pero no notablemente para lo requerido S).

Aquí hay una versión un poco más legible:

(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &
Martin Ender
fuente
5

Python 2, 86 83 75 73 71 bytes

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

Llama como f(30). n = 30Es casi instantáneo.

(Gracias a @DLosc por la idea de recurrir ksiendo un número en lugar de una lista de primos y unos pocos bytes. Gracias a @isaacg por dejarlo ~-).

Esta variante es mucho más corta, pero desafortunadamente toma demasiado tiempo debido a la ramificación exponencial:

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))
Sp3000
fuente
Interesante - mi solución original es muy similar, pero (teniendo un par de optimizaciones de la suya) sale 2 bytes más corto: f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]. Es menos eficiente con las llamadas a funciones, pero aún lo hace n = 30en menos de un segundo.
DLosc
1
@DLosc Me gustó tu idea y la hice mejor :)
Sp3000
¡Agradable! Aquí hay 2 bytes más de descuento:f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))
DLosc
@DLosc Ahaha gracias. Aún así juro que debe haber una mejor forma de cortocircuito ...
Sp3000
Creo que ~-es innecesario porque estás usando la división de enteros.
isaacg
5

CJam, 29 26 bytes

Xari{{2*_Cmd8=*2*)}%1-}*$p

El crédito va a @isaacg por su idea de eliminar 1 después de cada iteración, lo que me ahorró dos bytes directamente y otro indirectamente.

Pruébelo en línea en el intérprete de CJam (debería terminar en menos de un segundo).

Cómo funciona

Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient 
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))
Dennis
fuente
4

CJam, 35 bytes

1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p

Explicación próximamente. Esta es una versión mucho más rápida que el enfoque "bastante directo" (ver en el historial de edición).

Pruébelo en línea aquí para N = 30que se ejecuta en cuestión de segundos en la versión en línea y al instante en el compilador de Java

Optimizador
fuente
¿Cuánto tiempo llevará esto para las entradas más grandes? It should finish in seconds or minutes, not hours or days.
DLosc
Ah, ya veo. La versión de Python que escribí parecía tomar alrededor de 5 horas para N = 30.
DLosc
La última versión se ejecuta casi al instante.
Optimizador
66
Hay un error en tu código. El caso de prueba S=15no funciona.
Jakube
3

Java 8, 123

x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray()

Cuando xtiene 30 años, el programa dura 15 minutos y 29 segundos.

Expandido

class Collatz {
    static IntFunction<long[]> f =
            x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> {
                int n = 0;
                for (; i > 1; n++)
                    i = i % 2 < 1 ? i / 2 : 3 * i + 1;
                return n == x;
            }).toArray();

    public static void main(String[] args) {
        System.out.println(Arrays.toString(f.apply(15)));
    }
}
Ypnypn
fuente
Por curiosidad, ¿cuánto tiempo lleva esto para S = 30?
Geobits
Esto solo funciona en Java 8, ¿correcto? Usarlo javac 1.7.0_79en Ubuntu me dio muchos errores de sintaxis.
DLosc
@DLosc Correcto; Lo mencionaré en la publicación.
Ypnypn
Restringir la condición de terminal de bucle a i > 1 && ++n <= x(también puede caer n++) parece ser aún más rápido para solo 5 caracteres más ... unos 3 minutos para S = 30 para mí. Eso también se afeita con seguridad en menos de un minuto si lo .parallel()
incluyo
1

Python 2, 118 bytes

Bueno, pensé que no alcanzaría el mejor puntaje de Python después de ver la solución de @ Sp3000. Pero parecía un pequeño problema divertido, así que de todos modos quería probar una solución independiente:

s={1}
for k in range(input()):
 p,s=s,set()
 for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3)
print sorted(s)

Lo mismo antes de eliminar espacios en blanco:

s={1}
for k in range(input()):
    p,s=s,set()
    for t in p:
        s.add(2 * t)
        t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3)
print sorted(s)

Esta es una implementación muy directa de una primera búsqueda amplia. En cada paso, tenemos el conjunto con el tiempo de detención k, y derivamos el conjunto con el tiempo de detención k + 1agregando los posibles predecesores de cada valor ten el conjunto del paso k:

  • 2 * t siempre es un posible predecesor.
  • Si tpuede escribirse como 3 * u + 1, donde uhay un número impar que no lo es 1, entonces también ues un predecesor.

Tarda unos 0.02 segundos en ejecutarse N = 30en mi MacBook Pro.

Reto Koradi
fuente
En general, s.add(x)es innecesario en un golf, ya que generalmente se puede hacer en su s|={x}lugar. Además, usar en ~-xlugar de (x+1)guardar en corchetes. Pero por lo demás, buen trabajo :)
Sp3000
@ Sp3000 Gracias. No puedo reemplazar fácilmente el segundo s.add()porque se convierte en una tarea y ya no puedo ser parte de la expresión. Funciona para el primero. Los forbucles basados ​​en contadores también son siempre bastante detallados. Pensé que podría acortarlo usando un whilebucle, pero resultó ser exactamente el mismo de la misma longitud.
Reto Koradi
En lugar de un forbucle, ya que no utiliza la entrada de ninguna otra manera, probablemente pueda hacerlo en su exec"..."*input()lugar :)
Sp3000
1

PHP 5.4+, 178 bytes

La función

function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

Prueba y salida

echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

S (30) se ejecuta en 0.24 segundos * , devuelve 732 elementos. Una pareja son

86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

* Para ahorrar en bytes, tuve que agregar ksorty array_keysen cada paso. La única otra opción que tuve fue hacer una pequeña función de envoltura que llama c()y luego llama array_keysy ksortsobre el resultado una vez. Pero debido a que el tiempo aún es decentemente ágil, decidí tomar el rendimiento a bajo recuento de bytes. Sin la clasificación y el procesamiento adecuados, el tiempo es de 0.07 segundos en promedio para S (30).

Si alguien tiene alguna manera inteligente de obtener el procesamiento adecuado solo una vez sin demasiados bytes adicionales, ¡hágamelo saber! (Almaceno mis números como teclas de matriz, de ahí el uso de array_keysy ksort)

JPMC
fuente
0

Lenguaje C

#include <stdio.h>
#include <limits.h>    
const int s = 30;

bool f(long i)
{
    int r = 0;
    for(;;)
        if (i < 0 || r > s) return false;
        else if (i == 1) break;
        else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
    return (r==s);
}

void main(){
    for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}
Ventoso
fuente
55
Hola y bienvenidos a PPCG! Como se trata de una competencia de código de golf , querrás que tu código sea lo más corto posible. Además, incluya el nombre del idioma en su publicación.
Alex A.
Puede presionar el {}botón para formatear su código, lo que he hecho por usted. Pero como dice Alex, agregue el nombre del idioma (C?) E intente jugarlo :) ¡Pero bienvenido!
Sp3000
@ Sp3000 gracias por ayudar a formatear el código
ventoso
La función fno se comporta correctamente. Con s=5, obtengo un montón de resultados incorrectos. if (r == s)return true;debería ser return (r==s), ya fque no devolverá ningún significado significativo cuando (r < s). Además, creo que se debe declarar ien la fque long, desde que se desbordará con bastante rapidez para algunos valores.
Dennis
@ Dennis gracias :) debería serreturn (r==s);
ventoso