Wprowadzenie

Rozważ ciąg liczb całkowitych f zdefiniowany w następujący sposób:

1. f (2) = 2
2. Jeśli n jest nieparzystą liczbą pierwszą, to f (n) = (f (n-1) + f (n + 1)) / 2
3. Jeśli n = p · q jest złożony, to f (n) = f (p) · f (q)

Nietrudno dostrzec, że f (n) = n dla każdego n ≥ 2 , a zatem obliczenie f nie byłoby bardzo interesującym wyzwaniem. Przekręćmy definicję: połowę pierwszego przypadku i dwukrotność drugiego przypadku. Otrzymujemy nową sekwencję g zdefiniowaną następująco:

1. g (2) = 1
2. Jeśli n jest nieparzystą liczbą pierwszą, to g (n) = g (n-1) + g (n + 1)
3. Jeśli n = p · q jest złożony, to g (n) = g (p) · g (q)

Zadanie

Twoim zadaniem jest przyjęcie liczby całkowitej n ≥ 2 jako wartości wejściowej i uzyskanie g (n) jako wartości wyjściowej. Nie musisz się martwić przepełnieniem liczb całkowitych, ale powinieneś być w stanie poprawnie obliczyć g (1025) = 81 , a twój algorytm powinien teoretycznie działać dla dowolnie dużych danych wejściowych.

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów.

Przykład

Twierdziłem powyżej, że g (1025) = 81 , więc obliczmy to ręcznie. Pierwotna faktoryzacja 1025 daje

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

Ponieważ 41 jest liczbą pierwszą, otrzymujemy

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

Następnie obliczamy czynniki pierwsze 40 i 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)

Za te małe liczby pierwsze otrzymujemy

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

To znaczy że

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

i

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

Przypadki testowe

Oto wartości od g do 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 bajtów

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)

Przykład użycia: (#2) 1025->81

Parametr ajest zliczany, dopóki się nie podzieli xlub nie osiągnie x(tzn. xJest liczbą pierwszą). Jest o jeden bajt krótszy do testowania a > xi dodawania kolejnego warunku ( a < x) do testu modułu zamiast testowania a == x, ponieważ ten pierwszy wiąże się az x+1, co pomaga w wywołaniu rekurencyjnym. Porównać:

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

Galaretka , 18 bajtów

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

Wypróbuj online!

Jest to w zasadzie tylko bezpośrednie tłumaczenie specyfikacji. (Po zastanowieniu się trochę, podejrzewam, że jeśli istnieje zamknięta formuła znalezienia sekwencji, byłoby to więcej bajtów niż bezpośrednie podejście).

Wyjaśnienie

Mamy dwie wzajemnie rekurencyjne funkcje. Oto funkcja pomocnika (która oblicza g (n) dla liczby pierwszej 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.

A oto główny program, który oblicza g (n) dla dowolnego 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.

Oczywiście, jeśli wywołujemy program główny na liczbach pierwszych, wszystko nie działa Ç, oprócz , więc w tym przypadku zwraca g (n) . Reszta programu obsługuje zachowanie dla złożonego n .

JavaScript (ES6), 59 bajtów

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

Test

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 bajtów

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)

Galaretka , 13 bajtów

Æfḟ2µ‘,’߀€SP

Wypróbuj online!

Jak to działa

Æ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 bajtów

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

Tak! Jest prawie dwa razy dłuższy niż odpowiedź w Pythonie!

Niegolfowany i wyjaśnienie:

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

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

Nienazwana funkcja rekurencyjna jednego dodatniego argumentu liczby całkowitej, zwracająca liczbę całkowitą. Ostatecznie wcale nie tak krótko. Tr[#0/@({#-1,#+1}/2)](w przypadku, gdy wejście jest liczbą pierwszą) wywołuje funkcję na obu członach uporządkowanej pary {(#-1)/2,(#+1)/2}i dodaje wyniki; to jest w porządku, ponieważ funkcja ma taką samą wartość co (#-1)/2i #-1, na przykład. Podobnie, 1##&@@#0/@Divisors@#~Part~{2,-2}wywołuje funkcję na drugim najmniejszym dzielniku #i jego uzupełniającym dzielniku (dzielnik drugiej dużej) i mnoży odpowiedzi razem.

Clojure, 120 bajtów

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

Zastosowania :whendostać dzielniki n, Fto niljeśli nie zostanie znaleziony taki dzielnik ( nto pierwsze).

Python 2 , 62 bajty

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)

Wypróbuj online!