Introducción

Considere una secuencia de enteros f definida como sigue:

1. f (2) = 2
2. Si n es un primo impar, entonces f (n) = (f (n-1) + f (n + 1)) / 2
3. Si n = p · q es compuesto, entonces f (n) = f (p) · f (q)

No es muy difícil ver que f (n) = n por cada n ≥ 2 , y por lo tanto calcular f no sería un desafío muy interesante. Hagamos un giro a la definición: reducir a la mitad el primer caso y duplicar el segundo caso. Obtenemos una nueva secuencia g definida de la siguiente manera:

1. g (2) = 1
2. Si n es un primo impar, entonces g (n) = g (n-1) + g (n + 1)
3. Si n = p · q es compuesto, entonces g (n) = g (p) · g (q)

La tarea

Su tarea es tomar un número entero n ≥ 2 como entrada y producir g (n) como salida. No tiene que preocuparse por el desbordamiento de enteros, pero debería poder calcular g (1025) = 81 correctamente, y su algoritmo debería funcionar teóricamente para entradas arbitrariamente grandes.

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana.

Ejemplo

Afirmé anteriormente que g (1025) = 81 , así que calculemos a mano. La factorización prima de 1025 da

1025 = 5*5*41 => g(1025) = g(5)*g(5)*g(41)

Como 41 es primo, obtenemos

g(41) = g(40) + g(42)

A continuación, calculamos las factorizaciones primas de 40 y 42 :

40 = 2*2*2*5 => g(40) = g(2)*g(2)*g(2)*g(5) = g(5)
42 = 2*3*7 => g(42) = g(2)*g(3)*g(7) = g(3)*g(7)

Para estos pequeños primos obtenemos

g(3) = g(2) + g(4) = 1 + 1 = 2
g(5) = g(4) + g(6) = 1 + 2 = 3
g(7) = g(6) + g(8) = 2 + 1 = 3

Esto significa que

g(41) = g(40) + g(42) = g(5) + g(3)*g(7) = 3 + 2*3 = 9

y

g(1025) = g(5)*g(5)*g(41) = 3*3*9 = 81

Casos de prueba

Aquí están los valores de g hasta 50 .

2 -> 1
3 -> 2
4 -> 1
5 -> 3
6 -> 2
7 -> 3
8 -> 1
9 -> 4
10 -> 3
11 -> 5
12 -> 2
13 -> 5
14 -> 3
15 -> 6
16 -> 1
17 -> 5
18 -> 4
19 -> 7
20 -> 3
21 -> 6
22 -> 5
23 -> 7
24 -> 2
25 -> 9
26 -> 5
27 -> 8
28 -> 3
29 -> 9
30 -> 6
31 -> 7
32 -> 1
33 -> 10
34 -> 5
35 -> 9
36 -> 4
37 -> 11
38 -> 7
39 -> 10
40 -> 3
41 -> 9
42 -> 6
43 -> 11
44 -> 5
45 -> 12
46 -> 7
47 -> 9
48 -> 2
49 -> 9
50 -> 9

Haskell, 69 bytes

x#a|x<3=1|a>x=a#2+(x-1)#2|mod x a<1,a<x=a#2*div x a#2|b<-a+1=x#b
(#2)

Ejemplo de uso: (#2) 1025->81

El parámetro ase cuenta hasta que se divide xo alcanza x( xes decir, es primo). Es un byte más corto para probar a > xy agregar una condición adicional ( a < x) a la prueba de módulo en lugar de probar a == x, porque el primero se une aa x+1, lo que ayuda en la llamada recursiva. Comparar:

|a==x=(x+1)#2+(x-1)#2|mod x a<1=
|a>x=a#2+(x-1)#2|mod x a<1,a<x=

Jalea , 18 bytes

‘;’Ñ€Sµ1n2$?
ÆfÇ€P

Pruébalo en línea!

Esto es básicamente una traducción directa de la especificación. (Después de pensarlo un poco, sospecho que si hay una fórmula cerrada para encontrar la secuencia, sería más bytes que el enfoque directo).

Explicación

Tenemos dos funciones recursivas mutuamente. Aquí está la función auxiliar (que calcula g (n) para primo n ):

‘;’Ñ€Sµ1n2$?
           ?  If
        n2$     the input is not equal to 2 (parsed as a group due to $)
      µ       then do all the following (parsed as a group due to µ):
‘;’             Find the list [n+1, n-1];
   р           Call the main program on each element (i.e. [g(n+1),g(n-1)]);
     S          and return the sum of the list (i.e. g(n+1)+g(n-1)).
              Otherwise:
       1        Return 1.

Y aquí está el programa principal, que calcula g (n) para cualquier n :

ÆfÇ€P
Æf            Factorize the input into its prime factors;
  ǀ          Call the helper function on each element of that list;
    P         Then take the product.

Claramente, si llamamos al programa principal en un número primo, todo es un no-op excepto el Ç, por lo que devuelve g (n) en este caso. El resto del programa maneja el comportamiento para el compuesto n .

JavaScript (ES6), 59 bytes

f=(n,d=2)=>n-2?d<n?n%d?f(n,d+1):f(n/d)*f(d):f(n-1)+f(n+1):1

Prueba

f=(n,d=2)=>n-2?d<n?n%d?f(n,d+1):f(n/d)*f(d):f(n-1)+f(n+1):1

// f(2) to f(50)
for(N = 2, list = []; N <= 50; N++) {
  list.push(N + ' -> ' + f(N));
}
console.log(list.join(', '));

// f(1025)
console.log(f(1025));

Python 2, 85 69 bytes

g=lambda n,k=3:(n&~-n<1)or n%k and g(n,k+2)or(g(k+1)+g(k-1))*g(n/k,k)

Jalea , 13 bytes

Æfḟ2µ‘,’߀€SP

Pruébalo en línea!

Cómo funciona

Æfḟ2µ‘,’߀€SP  Main link. Argument: n

Æf             Yield the array of prime factors of n.
  ḟ2           Remove all occurrences of 2.
    µ          Begin a new, monadic chain. Argument: A (array of odd prime factors)
     ‘         Increment all elements of A.
       ’       Decrement all elements of A.
      ,        Pair; yield [A+1, A-1].
        ߀€    Map the main link over all elements of A+1 and A-1.
           S   Column-wise reduce by addition.
            P  Reduce by multiplication.

Clojure, 126 bytes

(defn t[n](if(= n 2)1(let[a(+(.indexOf(for[b(range 2 n)](mod n b)2)0))](if(> a 1)(*(t(/ n a))(t a))(+(t(dec n))(t(inc n)))))))

¡Hurra! ¡Es casi el doble que la respuesta de Python!

Ungolfed y una explicación:

(defn trivial [n]
  ; Define the function.
  (if (= n 2) 1
  ; If the number is 2, return 1
    (let [a (+ 2 (.indexOf (for [b (range 2 n)] (mod n b)) 0))]
      ; Let a be the lowest prime factor of n
      (if (> a 1)
        ; The .indexOf function returns -1 if a is a prime, so -1 + 2 = 1.
        ; Checks if a is a prime.
        (* (trivial (/ n a)) (trivial a))
        ; If a is prime, return the trivial(a/n) * trivial(a).
        (+ (trivial (dec n)) (trivial (inc n)))))))
        ; Else, return trivial(n-1) + trivial(n + 1).

Mathematica, 83 bytes

Which[#<4,#-1,PrimeQ@#,Tr[#0/@({#-1,#+1}/2)],0<1,1##&@@#0/@Divisors@#~Part~{2,-2}]&

Función recursiva sin nombre de un argumento entero positivo, que devuelve un entero. No tan corto, al final. Tr[#0/@({#-1,#+1}/2)](en el caso donde la entrada es primo) llama a la función en ambos miembros del par ordenado {(#-1)/2,(#+1)/2}y agrega los resultados; Esto está bien ya que la función tiene el mismo valor en (#-1)/2y #-1, por ejemplo. Del mismo modo, 1##&@@#0/@Divisors@#~Part~{2,-2}llama a la función en el segundo divisor más pequeño #y su divisor complementario (el segundo divisor más grande) y multiplica las respuestas juntas.

Clojure, 120 bytes

(defn g[n](if(= n 2)1(if-let[F(first(for[i(range 2 n):when(=(mod n i)0)]i))](*(g F)(g(/ n F)))(+(g(dec n))(g(inc n))))))

Usos :whenpara obtener divisores de n, Fes nilsi no se encuentra dicho divisor ( nes primo).

Python 2 , 62 bytes

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

Pruébalo en línea!