Sube un paso a la cima

24

El título del video más nuevo de Numberphile, 13532385396179 , es un punto fijo de la siguiente función f en los enteros positivos:

Sea n un número entero positivo. Escriba la factorización prima de la manera habitual, por ejemplo, 60 = 2 2 · 3 · 5, en la que los primos se escriben en orden creciente y se omiten los exponentes de 1. Luego lleva los exponentes a la línea y omite todos los signos de multiplicación, obteniendo un número f (n). [...] por ejemplo, f (60) = f (2 2 · 3 · 5) = 2235.

(La definición anterior está tomada del problema 5 de cinco problemas de $ 1,000 - John H. Conway )

Tenga en cuenta que f (13532385396179) = f (13 · 53 2 · 3853 · 96179) = 13532385396179.

Tarea

Tome un entero compuesto positivo ncomo entrada y salida f(n).

Otro ejemplo

48 = 2 4 · 3, entonces f (48) = 243.

Casos de prueba

Más casos de prueba están disponibles aquí .

   4 -> 22
   6 -> 23
   8 -> 23
  48 -> 243
  52 -> 2213
  60 -> 2235
 999 -> 3337
9999 -> 3211101
Monja permeable
fuente
11
+1 Todavía estoy asombrado de que alguien haya encontrado 13532385396179 como prueba de la conjetura. ¡Supongo que el premio de $ 1000 ayudaría a pagar la electricidad utilizada! :)
Wossname
77
Sin seguir el enlace, no estaba claro que la conjetura es que las aplicaciones repetidas de f (n) siempre alcanzarán un primo (y, por supuesto, f (p) = p si p es primo). 13532385396179 refuta la conjetura porque es a la vez compuesta y una opinión fija.
Chris H

Respuestas:

16

Python, 166 162 159 bytes

Ustedes muchachos están mucho mejor. ¡Esto es lo que usé! (el algoritmo que lo resolvió llama a esto)

from primefac import*
def c(n):
 x=factorint(n)
 a=''
 for i in range(len(x)):
  l=min(x.keys())
  a+=str(l)
  if x[l]>1:a+=str(x[l])
  x.pop(l)
 return int(a)
jchd
fuente
2
¿Por qué alguien rechazó a un recién llegado en lugar de ayudarlo a mejorar su respuesta como lo hizo @LeakyNun? :(
Shaggy
3
Lo siento, eso es realmente lo que usé (encontré el número). Solo pensé que el código horrible sería divertido. Puedes derribarlo.
jchd
99
Bienvenido al sitio. Es realmente agradable que compartas con nosotros tu solución. (para las personas que no saben, Jim Davis fue quien resolvió este problema en primer lugar). Sin embargo, las respuestas a los desafíos deben seguir algunas reglas. Si solo sigue las sugerencias de @LeakyNun, su respuesta será válida. (tal vez eche un vistazo a las otras respuestas para ver cómo se ven generalmente)
Dada
44
Dios mío, no esperaba que el mismo Jim Davis apareciera en este sitio y respondiera a mi desafío ... Me siento tan honrado ahora ...
Leaky Nun
2
ehh, no es un troll por cierto. Mi dirección de correo electrónico está en gladhoboexpress.blogspot.ca/2014/10/climb-to-prime.html ... Dejé la publicación arriba, nadie te inunda con correo electrónico sobre matemáticas.
jchd
9

Brachylog , 8 bytes

ḋoọc;1xc

Pruébalo en línea!

Explicación

Example input: 60

ḋ          Prime decomposition: [5,3,2,2]
 o         Order: [2,2,3,5]
  ọ        Occurences: [[2,2],[3,1],[5,1]]
   c       Concatenate: [2,2,3,1,5,1]
    ;1x    Execute 1s: [2,2,3,5]
       c   Concatenate: 2235

Puede usar ℕ₂ˢ( seleccione todos los enteros mayores o iguales a 2 ) en lugar de ;1x, lo que probablemente sea más legible y esté más en el espíritu de Brachylog.

Fatalizar
fuente
9

Jalea , 6 bytes

ÆFFḟ1V

Pruébalo en línea!

Explicación

ÆF      Get prime factorisation of input as prime-exponent pairs.
  F     Flatten.
   ḟ1   Remove 1s.
     V  Effectively flattens the list into a single integer.
Martin Ender
fuente
V= "concatenar a una sola cadena y evaluar como Jelly"
Erik the Outgolfer
@EriktheOutgolfer Sí, por lo tanto, "efectivamente".
Martin Ender
@MartinEnder ¿Alguna razón en particular que no use (Convertir de decimal a entero)?
disperso el
@Christian Porque la lista puede contener enteros de varios dígitos.
Martin Ender
@ MartinEnder Ah, inteligente. Lo he usado FḌen el pasado, ¡es un buen consejo!
dispersar el
5

Mathematica, 43 36 Bytes

Row@Flatten@FactorInteger@#/. 1->""&

Pruébalo en línea!

J42161217
fuente
2
DeleteCaseses largo, puede usar /.1->""o /.1->##&[](forma alternativa de/.1->Nothing
user202729
3
@ user202729 Todos ellos necesitan un espacio delante del 1para evitar que se analice como ... / (0.1).
Martin Ender
¡Tienes razón! fijo
J42161217
4

CJam , 8 bytes

limF:~1-

Pruébalo en línea!

Explicación

li  e# Read input and convert to integer.
mF  e# Get prime factorisation as prime-exponent pairs.
:~  e# Flatten.
1-  e# Remove 1s.
    e# Implicitly print a flattened representation of the list.
Martin Ender
fuente
Me hubiera acostumbrado e_a aplanar, ya que para eso está, pero no cambia la puntuación.
Peter Taylor
1
@PeterTaylor Hm, sí, nunca puedo decidir cuál usar, pero tiendo a e_usar solo para aplanar profundamente y usar :~siempre que sea solo un nivel.
Martin Ender
4

05AB1E , 10 bytes

Òγʒ¬?gDië?

Pruébalo en línea!

Ò          # Push list of prime factors with duplicates
 γ         # Break into chunks of consecutive elements
  ʒ        # For each
   ¬?      #   Print the first element
     gD    #   Push the length of this chunk twice
       ië  #   If not 1
         ? #     Print the length
Riley
fuente
3

05AB1E , 12 11 bytes

Òγvy¬sgD≠×J

Pruébalo en línea!

Explicación

Ò            # calculate prime factors with duplicates
 γ           # group consecutive equal elements
  vy         # for each group
    ¬        # get the head without popping
     sg      # push the length of the group
       D≠×   # repeat the length (length != 1) times
          J  # join
Emigna
fuente
Falla por 48.
Leaky Nun
2

Pyth, 12 bytes

smjk_>hddr8P

¡Intentalo!

alternativa, 12 bytes

smjk<_AdGr8P

¡Trata eso!

explicación

smjk_>hddr8P
           PQ  # prime factorization (already in correct order) of the implicit input: [3, 3, 11, 101]
         r8    # length encode: [[2, 3], [1, 11], [1, 101]]
 m             # map over the length encoded list (lambda variable: d)
     >hdd      # take the d[0] last elements of d (so only the last for d[0]==1 and all else)
    _          # reverse that list
  jk           # join into a string
s              # conatenate the list of strings
KarlKastor
fuente
2

Python 2 , 99 bytes

n=input()
r=''
p=2
while~-n:
 e=0
 while n%p<1:e+=1;n/=p
 r+=str(p)*(e>0)+str(e)*(e>1);p+=1
print r

Pruébalo en línea!

Si las entradas están restringidas para estar debajo 2147483659, ambas str(...)pueden reemplazarse `...`guardando 6 bytes (¡este programa será muy lento para los números afectados de todos modos!).

Jonathan Allan
fuente
2

Ohm , 11 bytes

o:_]D2<?O;J

Pruébalo en línea!

Explicación

o:_]D2<?O;J
o           # Push prime factors with powers from input (Format [[prime,power],...]
 :          # For each...
  _          # Push current element
   ]         # flatten
    D        # Duplicate power
     2<? ;   # Is the power smaller than 2?
        O     # Delete top of stacks
          J  # Join
Datboi
fuente
1

Japt , 19 bytes

k ó¥ ®¯1 pZlÃc fÉ q

¡Pruébalo en línea!

Explicación

 k ó¥  ®   ¯  1 pZlà c fÉ  q
Uk ó== mZ{Zs0,1 pZl} c f-1 q  // Ungolfed
                              // Implicit: U = input number
Uk                            // Break U into its prime factors.
   ó==                        // Group into runs of equal items.
       mZ{         }          // Map each item Z in this to
          Zs0,1               //   Z.slice(0, 1) (the array of the first item),
                pZl           //   with Z.length added at the end.
                              // This returns an array of prime-exponent pairs (Jelly's ÆF).
                     c        // Flatten.
                       f-1    // Filter to the items X where X - 1 is truthy (removes '1's).
                           q  // Join the resulting array into a single string.
                              // Implicit: output result of last expression
ETHproducciones
fuente
1

PHP , 88 bytes

for($i=2;1<$a=&$argn;)$a%$i?$i++:$a/=$i+!++$r[$i];foreach($r as$k=>$v)echo$k,$v<2?"":$v;

Pruébalo en línea!

Jörg Hülsermann
fuente
0

C #, 206 100 bytes

n=>{var r="";for(int d=1,c;++d<=n;){c=0;while(n%d<1){c++;n/=d;}r+=c>0?d+(c>1?c+"":""):"";}return r;}

Versión completa / formateada:

using System;

class P
{
    static void Main()
    {
        Func<int, string> func = n =>
        {
            var r = "";
            for (int d = 1, c; ++d <= n;)
            {
                c = 0;
                while (n % d < 1)
                {
                    c++;
                    n /= d;
                }

                r += c > 0 ? d + (c > 1 ? c + "" : "") : "";
            }

            return r;
        };

        Console.WriteLine(func(4));
        Console.WriteLine(func(6));
        Console.WriteLine(func(8));
        Console.WriteLine(func(48));
        Console.WriteLine(func(52));
        Console.WriteLine(func(60));
        Console.WriteLine(func(999));
        Console.WriteLine(func(9999));

        Console.ReadLine();
    }
}
TheLethalCoder
fuente
0

Javascript - 91 bytes

(x,r='',i=1,n)=>{while(x>i++){for(n=0;x%i<1;n++)x/=i;r+=(n>0?i+'':'')+(n>1?n:'')}return r}

Explicación

(x,r='',i=1,n)=>(          // input x is the number to process, r, i, n are default values only
    while(x>i++){          // iterate over i until x
        for(n=0;x%i<1;n++) // iterate over n until i is not a factor of x
            x/=i;          // factor i out of x
        r+=(n>0?i+'':'')   // append i to r if n > 0
            +(n>1?n:'')    // append n to r if n > 1
                           // i+'' prevents adding i and n before appending to r
    }
    return r               // return r by comma-operator and arrow function syntax
)
asgallant
fuente
0

Java 8, 103 caracteres

Solución bastante sencilla.

n->{String r="";int d=2,c;while(n>1){c=0;while(n%d<1){c++;n/=d;}if(c>0)r+=d;if(c>1)r+=c;d++;}return r;}

Sin golf:

private static Function<Integer, String> f = n->{
    String result = "";
    int divisor = 2, count;
    while (n>1) {
        count = 0;
        while (n % divisor < 1) {
            count++;
            n /= divisor;
        }
        if (count > 0) result += divisor;
        if (count > 1) result += count;
        divisor++;
    }
    return result;
};
Computronium
fuente
91 bytes
techo
0

Octava , 69 bytes

@(a)printf('%d',(f=[[~,c]=hist(b=factor(a),d=unique(b));d](:))(f~=1))

Pruébalo en línea!

Terminó siendo bastante largo, pero esto generará la salida deseada.

Esencialmente, utilizamos la función de histograma para contar el número de ocurrencias de los valores únicos en la factorización prima del valor de entrada.

  • El resultado de la factor()función da los factores primos en orden ascendente
  • luego encontramos unique()valores en esa matriz
  • hist() devuelve el número de ocurrencias

Una vez que tenemos las dos matrices (una para factores únicos, otra para recuentos), concatenamos las matrices verticalmente (una encima de la otra) y luego se aplanan. Esto intercala los factores con recuentos.

Finalmente, mostramos el resultado como una cadena que garantiza omitir cualquier 1 en la matriz final. El único momento en que puede aparecer 1 es si el recuento fue 1 porque 1 nunca será un factor primo. Esta eliminación se realiza antes de convertir a una cadena para que no afecte cosas como el número 10.

Tom Carpenter
fuente
0

Pyth - 16 bytes

V{PQpNK/PQNItKpK

Intentalo

Otra solución:

sm`d-.nm(d/PQd){PQ1
Maria
fuente
1
Uno puede reemplazar FNpor V.
Leaky Nun
1
Además, r8(codificación de longitud de ejecución) parece ser útil.
Leaky Nun
0

R , 72 bytes

x=rle(pracma::factors(scan()));x$l[x$l<2]='';paste0(x$v,x$l,collapse='')

Requiere el pracmapaquete, que no está instalado en TIO.

Giuseppe
fuente