Eine Wendung einer trivialen Sequenz

15

Einführung

Betrachten Sie eine Folge von Ganzzahlen f, die wie folgt definiert sind:

  1. f (2) = 2
  2. Wenn n eine ungerade Primzahl ist, dann ist f (n) = (f (n-1) + f (n + 1)) / 2
  3. Wenn n = p · q zusammengesetzt ist, dann ist f (n) = f (p) · f (q)

Es ist nicht sehr schwer zu erkennen, dass f (n) = n für jedes n ≥ 2 ist , und daher wäre die Berechnung von f keine sehr interessante Herausforderung. Nehmen wir eine Änderung der Definition vor: Halbieren Sie den ersten Fall und verdoppeln Sie den zweiten Fall. Wir bekommen eine neue Sequenz g definiert wie folgt:

  1. g (2) = 1
  2. Wenn n eine ungerade Primzahl ist, dann ist g (n) = g (n-1) + g (n + 1)
  3. Wenn n = p · q zusammengesetzt ist, dann ist g (n) = g (p) · g (q)

Die Aufgabe

Ihre Aufgabe ist es, eine ganze Zahl n ≥ 2 als Eingabe zu nehmen und g (n) als Ausgabe zu erzeugen . Sie müssen sich keine Gedanken über einen Ganzzahlüberlauf machen, sollten jedoch in der Lage sein, g (1025) = 81 korrekt zu berechnen , und Ihr Algorithmus sollte theoretisch für beliebig große Eingaben funktionieren.

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt.

Beispiel

Ich habe oben behauptet, dass g (1025) = 81 , also lassen Sie es uns von Hand berechnen. Die Primfaktorisierung von 1025 ergibt

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

Da 41 Prime ist, bekommen wir

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

Als nächstes berechnen wir die Primfaktoren von 40 und 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)

Für diese kleinen Primzahlen bekommen wir

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

Das bedeutet, dass

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

und

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

Testfälle

Hier sind die Werte von g bis zu 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
Zgarb
quelle
Unheimlich ähnlich wie A002487 , und doch nicht (anders bei 15, 21, 25, 29, 33, 41und ein paar mehr, aber ich kann kein wirkliches Muster zu warum finden.)
Gabriel Benamy
@ GabrielBenamy Nun, meine Sequenz erfüllt auch a(2*n) = a(n), und a(2*n+1) = a(n) + a(n+1)hält, wenn 2*n+1ist prime. Für viele andere ungerade Zahlen stimmen die Folgen wahrscheinlich zufällig überein.
Zgarb
Ist es akzeptabel, True anstelle von 1 zurückzugeben ?
Dennis
@ Tennis Die Herausforderung besteht darin, eine numerische Funktion zu bewerten, kein Entscheidungsproblem, also würde ich nicht annehmen.
Pavel
1
@Pavel Es gibt starke Unterstützung dafür, und zumindest in Python verhält sich True in jeder Hinsicht wie 1 .
Dennis

Antworten:

7

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)

Anwendungsbeispiel: (#2) 1025->81

Der Parameter awird hochgezählt, bis er dividiert xoder erreicht ist x(dh xPrimzahl). Es es ein Byte kürzer Test für a > xund eine weitere Bedingung (add a < x) mit dem Modul Test statt Testen auf a == x, weil die früherer Bindungen azu x+1, die in dem rekursiven Aufruf helfen. Vergleichen Sie:

|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=
nimi
quelle
4

Jelly , 18 Bytes

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

Probieren Sie es online!

Dies ist im Grunde nur eine direkte Übersetzung der Spezifikation. (Nachdem ich ein bisschen darüber nachgedacht habe, vermute ich, dass es mehr Bytes als den direkten Ansatz gibt, wenn es eine geschlossene Formel zum Finden der Sequenz gibt.)

Erläuterung

Wir haben zwei gegenseitig rekursive Funktionen. Hier ist die Hilfsfunktion (die g (n) für Primzahl n berechnet ):

‘;’Ñ€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.

Und hier ist das Hauptprogramm, das g (n) für jedes n berechnet :

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

Wenn wir das Hauptprogramm für eine Primzahl aufrufen, ist alles ein No-Op mit Ausnahme von Ç, sodass in diesem Fall g (n) zurückgegeben wird. Der Rest des Programms behandelt das Verhalten für Composite n .


quelle
4

JavaScript (ES6), 59 Byte

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

Prüfung

Arnauld
quelle
3

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)
orlp
quelle
3

Gelee , 13 Bytes

Æfḟ2µ‘,’߀€SP

Probieren Sie es online!

Wie es funktioniert

Æ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.
Dennis
quelle
3

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

Yay! Es ist fast doppelt so lang wie die Python-Antwort!

Ungolfed und eine Erklärung:

(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).
Clismique
quelle
Cool, ich wusste nicht, dass du das kannst (.indexOf (for [...] ...) x)!
NikoNyrh
Die aktuelle 118-Byte-Version gibt 11 für zurück (t 1025), vielleicht ifsollte das so sein :when? Aber dann nthleere Liste wirft IndexOutOfBoundsException.
NikoNyrh
@NikoNyrh Ja, das sollte nicht passieren - ich habe es auch getestet und der Code ist ungültig. Stellt die ursprüngliche Version wieder her.
Clismique
2

Mathematica, 83 Bytes

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

Unbenannte rekursive Funktion eines positiven Integer-Arguments, die eine Ganzzahl zurückgibt. Letztendlich nicht ganz so kurz. Tr[#0/@({#-1,#+1}/2)](in dem Fall, in dem die Eingabe prim ist) ruft die Funktion für beide Mitglieder des geordneten Paares auf {(#-1)/2,(#+1)/2}und addiert die Ergebnisse; Dies ist in Ordnung, da die Funktion zum Beispiel bei (#-1)/2und den gleichen Wert hat #-1. Ruft 1##&@@#0/@Divisors@#~Part~{2,-2}auf ähnliche Weise die Funktion für den zweitkleinsten Divisor #und seinen komplementären Divisor (den zweitgrößten Divisor) auf und multipliziert die Antworten miteinander.

Greg Martin
quelle
Wie funktionieren unbenannte rekursive Funktionen?
Pavel
1
Lesen Sie den Abschnitt #0in dieser Antwort .
Greg Martin
2

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

Verwendet :when, um Teiler von zu erhalten n, Fist, nilwenn kein solcher Teiler gefunden wird ( nist Primzahl).

NikoNyrh
quelle
Wollen Sie streiten, Sir? Ist Zustand. (Freundschaftswettbewerb?)
Clismique