Calcular una secuencia entera derivada de factores primos

10

Cree una función, expresión o programa que haga lo siguiente:

  1. Toma los factores primos de cualquier número y súmalos. Por ejemplo, los factores primos de 28 son 2 2 7, sumados a 11.
  2. Multiplique el resultado por el número de factores primos para el número dado. Por ejemplo, 28 tiene 3 factores primos que suman 11. 11 * 3 es 33.
  3. Repita el proceso de forma recursiva, almacenando la lista resultante (que comienza con el número original), hasta llegar a un número que ya está incluido en la lista. Deténgase sin agregar ese número final, de modo que la lista no contenga duplicados. La progresión para 28 es 28 33, porque 33 resulta en 28 nuevamente.
  4. Cuente los elementos en la lista resultante. En el caso de 28, la respuesta es 2.

Aquí están los resultados para 0<n<=10que pueda verificar su algoritmo.

2 1 1 10 1 11 1 9 5 10

(Como señaló Balpha, la respuesta para higley(1)es 2, de la lista 1 0. Originalmente tenía 1, debido a un error en mi algoritmo original escrito en J.)

Como soy un SOB engreído y no he encontrado esto en OEIS , llamemos a esto la "secuencia de Higley", al menos durante la duración de esta ronda de golf de código. Como un bono adicional, encuentre los dos primeros que ntienen el más bajo higley(n)donde nno es primo y n>1. (Creo que solo hay dos, pero no puedo probarlo).

Este es un código de golf estándar, por lo que, como es habitual, ganan la menor cantidad de pulsaciones de teclas, pero le pido que vote por favor las respuestas inteligentes en otros idiomas, incluso si son detalladas.

Gregory Higley
fuente
44
¿Por qué es highley(1) == 1? Uno no tiene factores primos, por lo que la lista resultante en 4) es [1, 0], así highley(1) == 2como lo veo.
balpha
¿Podemos suponer que el número de entrada y los valores intermedios no serán mayores que 2 ^ 31-1 (es decir, cabe en un entero de 32 bits con signo)?
Peter Taylor
@Peter Taylor Claro.
Gregory Higley
En caso de que alguien lo encuentre útil, las secuencias OEIS que están vagamente relacionadas y pueden proporcionar algo de inspiración son A001414, A001222 y A002217.
Peter Taylor
1
dado que no ha comentado, supongo que no se ha dado cuenta: probé que solo hay dos puntos de fijación no principales y lo agregué como apéndice a mi publicación.
Peter Taylor

Respuestas:

6

J, 47 45

#@((~.@,[:(+/@{:*+/@:*/)2 p:{:)^:_)`2:@.(=&1)

Es posible que esto sea mucho más corto sin usar ^:_, pero mi cerebro ya está lo suficientemente frito.

Editar: (47-> 45) Día de cupón doble.

Uso:

   higley =: #@((~.@,(+/@{:*+/@:*/)@(2&p:)@{:)^:_)`2:@.(=&1)
   higley 1
2
   higley"0 (1 + i. 10)
2 1 1 10 1 11 1 9 5 10
Jesse Millikan
fuente
¡Guauu! Solución AJ que es más corta que una solución GolfScript. El primero que he visto. (Soy un gran admirador de J.)
Gregory Higley
3
Puede acortar esto considerablemente utilizando un algoritmo ligeramente diferente: #@((~.@,((+/*#)@:q:)@{:)^:_)`2:@.(=&1)que tiene 38 caracteres.
Gregory Higley
Wow, traté de descubrir cómo hacerlo con q: pero estaba tratando de manipularlo en mi solución 2 p: así que no lo entendí. Obvio en retrospectiva.
Jesse Millikan
El hecho de que puedas mirar esa explosión de personajes y decirlo " obvio en retrospectiva " simplemente me deja sin aliento. Uno de estos días debería revisar Golfscript o J.
Casey
@Casey Me sentí de la misma manera, pero cuanto más aprendes y usas, más "te salta a la vista", aunque todavía veo cosas que tengo que resolver. Una cosa útil que debe saber sobre J es que si agrega un. o bien: después de un símbolo, se crea un nuevo símbolo, por ejemplo, {, {., y {:todas las cosas malas diferentes, pero {-(por ejemplo) es sin duda una secuencia de dos cosas, {y -.
Gregory Higley
5

Golfscript, 68 67 62 61 caracteres

[.]({[.2@{1$1$%{)}{\1$/1$}if}*;;].,*0+{+}*.2$?@@.@+\@)!}do;,(

Esta es una expresión: toma nla pila y deja el resultado en la pila. Para convertirlo en un programa que tome nde stdin e imprima el resultado en stdout, reemplace el encabezado [con~

El corazón de esto es [.2@{1$1$%{)}{\1$/1$}if}*;;](28 caracteres) que toma el número superior en la pila y (mediante un algoritmo increíblemente ineficiente) genera una lista de sus factores primos. Pseudocódigo de estilo C equivalente:

ps = [], p = 2;
for (int i = 0; i < n; i++) {
    if (n % p == 0) {
        ps += p;
        n /= p;
    }
    else p++;
}

Lo 0+justo antes {+}*es manejar el caso especial n==1, porque a Golfscript no le gusta doblar una operación binaria sobre la lista vacía.

Uno de los puntos de fijación no primos es 27; Encontré esto sin usar el programa al considerar el mapeo (p a -> a 2 p), que es un punto de referencia si a == p (a-1) / 2 , y probar pequeño a. ( a==1da la fijación de primos).

Al buscar con el programa aparece un segundo punto fijo: 30 = (2 + 3 + 5) * 3


Apéndice: prueba de que solo hay dos puntos de fijación no primos

Notación: sopfr(x)es la suma de factores primos de x, con repetición (A001414). Omega(x)es el número de factores primos de x(A001222). Entonces la función sucesora de Higley esh(x) = sopfr(x) Omega(x)

Supongamos que tenemos un punto fijo N = h(N)que es un producto de n=Omega(N)primos.

N = p_0 ... p_{n-1} = h(N) = n (p_0 + ... + p_{n-1})

Teoría básica de números: se ndivide en p_0 ... p_{n-1}, por lo que w=Omega(n)esos primos son los factores primos de n. Wlog los llevaremos a ser los últimos w. Entonces podemos dividir ambos lados entre ny obtener

p_0 ... p_{n-w-1} = p_0 + ... + p_{n-1}

o

p_0 ... p_{n-w-1} = p_0 + ... + p_{n-w-1} + sopfr(n)

Dado que todos los números primos p_0a p_{n-w-1}son mayores que 1, el aumento de cualquiera de ellos aumenta la LHS más que el RHS. Entonces, para un determinado n, podemos enumerar todas las soluciones candidatas.

En particular, no puede haber soluciones si el LHS es mayor que el RHS configurando todos los primos "libres" a 2. Es decir, no hay soluciones si

2^{n-w} > 2 (n-w) + sopfr(n)

Como sopfr(n) <= n(con igualdad solo para n = 4 o n primo), podemos hacer la afirmación más débil de que no hay puntos de fijación si

2^{n-w} > 3 n - 2 w

Manteniendo wfijo podemos seleccionar diferentes valores de nsatisfacción w=Omega(n). El más pequeño nes 2^w. Tenga en cuenta que si 2^{n-w}es al menos 3 (es decir n-w>1, si , lo cual es cierto si n>2), entonces aumentar nmientras se mantiene wconstante aumentará el LHS más que el RHS. Tenga en cuenta también que para w>2y tomando la menor cantidad posible, nse satisface la desigualdad y no hay puntos de fijación.

Eso nos deja con tres casos: w = 0 y n = 1; w = 1y nes primo; o w = 2y nes semi-prime.

Caso w = 0. n = 1, así Nes cualquier primo.

Caso w = 1. Si n = 2entonces N = 2py requerimos p = p + 2, que no tiene soluciones. Si n = 3entonces tenemos pq = p + q + 3y dos soluciones, (p=2, q=5)y(p=3, q=3) . Si es n = 5así 2^4 > 3 * 5 - 2 * 1, entonces no hay más soluciones con w = 1.

Caso w = 2. Si n = 4entonces N = 4pqy requerimos pq = p + q + 4. Esto tiene solución enterap=2, q=6 , pero no tiene soluciones principales. Si es n = 6así 2^4 > 3 * 6 - 2 * 2, entonces no hay más soluciones con w = 2.

Todos los casos están agotados, por lo que los únicos puntos de fijación no primos son 27 y 30.

Peter Taylor
fuente
1
Encontré esos dos mismos puntos de fijación usando lápiz y papel: 27 y 30. Estoy de acuerdo con OP, parece que esos son los únicos dos.
mellamokb
1
La siguiente pregunta interesante podría ser. ¿Hay infinitamente muchos higley (x) = 2? ¿Qué tal hay una manera de generar arbitrariamente higley (x), como higley (x) = 100?
mellamokb
¡Muy agradable! Soy un chico J pero quizás tenga que aprender GolfScript.
Gregory Higley
@mellamokb Creo que hay una serie de preguntas interesantes con esta secuencia. Por ejemplo, si consideramos la secuencia de números generados para cada uno nantes de que se cuente, ¿hay algún no primo ndespués de 49 para el que dicha secuencia no termine en 28?
Gregory Higley
2
Otra pregunta interesante es si hay una función simple de los nlímites higley(n)anteriores. (Eso permitiría simplificar considerablemente el ciclo, solo iterar f(n)veces y luego descartar duplicados)
Peter Taylor
4

Ruby, 92 caracteres

f=->i{r=[i];(x=s=0;(2..i).map{|j|(s+=j;x+=1;i/=j)while i%j<1};r<<i=s*x)until r.uniq!;r.size}

Esta solución supone que higley (1) es en realidad 2, no 1 (ver el comentario de balpha arriba):

(1..10).map &f
=> [2, 1, 1, 10, 1, 11, 1, 9, 5, 10]
Ventero
fuente
2

Octava - 109 caracteres

l=[input('')];while size_equal(unique(l),l);n=factor(l(1));l=[sum(n)*length(n) l];endwhile;disp(length(l)-1);
Juan
fuente