introduction

Considérons une séquence d'entiers f définie comme suit:

1. f (2) = 2
2. Si n est un nombre impair impair, alors f (n) = (f (n-1) + f (n + 1)) / 2
3. Si n = p · q est composite, alors f (n) = f (p) · f (q)

Il n'est pas très difficile de voir que f (n) = n pour chaque n ≥ 2 , et donc calculer f ne serait pas un défi très intéressant. Faisons un tour à la définition: divisez par deux le premier cas et doublez le deuxième. On obtient une nouvelle séquence g définie comme suit:

1. g (2) = 1
2. Si n est un nombre impair impair, alors g (n) = g (n-1) + g (n + 1)
3. Si n = p · q est composite, alors g (n) = g (p) · g (q)

La tâche

Votre tâche consiste à prendre un entier n ≥ 2 en entrée et à produire g (n) en sortie. Vous n'avez pas à vous soucier du débordement d'entier, mais vous devriez pouvoir calculer correctement g (1025) = 81 , et votre algorithme devrait théoriquement fonctionner pour des entrées arbitrairement grandes.

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas gagne.

Exemple

J'ai affirmé ci-dessus que g (1025) = 81 , alors calculons-le à la main. La factorisation de 1025 donne

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

Puisque 41 est premier, nous obtenons

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

Ensuite, nous calculons les factorisations premières de 40 et 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)

Pour ces petits nombres premiers, nous obtenons

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

Cela signifie que

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

et

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

Cas de test

Voici les valeurs de g jusqu'à 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 octets

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)

Exemple d'utilisation: (#2) 1025->81

Le paramètre aest compté jusqu'à ce qu'il se divise xou qu'il atteigne x(c'est x-à- dire qu'il est premier). Il est un octet plus court pour tester a > xet ajouter une autre condition ( a < x) au test de module au lieu de tester a == x, car le premier se lie aà x+1, ce qui aide à l'appel récursif. Comparer:

|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=

Gelée , 18 octets

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

Essayez-le en ligne!

Il s'agit essentiellement d'une traduction directe de la spécification. (Après y avoir réfléchi un peu, je soupçonne que s'il existe une formule fermée pour trouver la séquence, ce serait plus d'octets que l'approche directe.)

Explication

Nous avons deux fonctions mutuellement récursives. Voici la fonction d'assistance (qui calcule g (n) pour le premier 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.

Et voici le programme principal, qui calcule g (n) pour tout 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.

De toute évidence, si nous appelons le programme principal sur un nombre premier, tout est un no-op sauf le Ç, donc il renvoie g (n) dans ce cas. Le reste du programme gère le comportement du composite n .

JavaScript (ES6), 59 octets

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

Tester

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 octets

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)

Gelée , 13 octets

Æfḟ2µ‘,’߀€SP

Essayez-le en ligne!

Comment ça fonctionne

Æ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 octets

(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)))))))

Yay! C'est presque deux fois plus longtemps que la réponse Python!

Non golfé et une explication:

(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 octets

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

Fonction récursive sans nom d'un argument entier positif, renvoyant un entier. Pas si court, finalement. Tr[#0/@({#-1,#+1}/2)](dans le cas où l'entrée est principale) appelle la fonction sur les deux membres de la paire ordonnée {(#-1)/2,(#+1)/2}et ajoute les résultats; c'est bien puisque la fonction a la même valeur à (#-1)/2et #-1, par exemple. De même, 1##&@@#0/@Divisors@#~Part~{2,-2}appelle la fonction sur le deuxième plus petit diviseur #et son diviseur complémentaire (le deuxième diviseur) et multiplie les réponses ensemble.

Clojure, 120 octets

(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))))))

Utilisations :whenpour obtenir diviseurs n, Fest nilsi aucun diviseur est trouvé ( nest premier).

Python 2 , 62 octets

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)

Essayez-le en ligne!