Erstellen Sie eine Funktion, einen Ausdruck oder ein Programm, das Folgendes ausführt:

1. Nehmen Sie die Primfaktoren einer beliebigen Zahl und addieren Sie sie. Zum Beispiel sind die Primfaktoren von 28 2 2 7, summiert zu 11.
2. Multiplizieren Sie das Ergebnis mit der Anzahl der Primfaktoren für die angegebene Anzahl. ZB hat 28 3 Primfaktoren, die sich zu 11 summieren. 11 * 3 ist 33.
3. Wiederholen Sie den Vorgang rekursiv und speichern Sie die resultierende Liste (die mit der ursprünglichen Nummer beginnt), bis Sie eine Nummer erreichen, die bereits in der Liste enthalten ist. Halten Sie an, ohne diese endgültige Nummer hinzuzufügen, damit die Liste keine Duplikate enthält. Die Progression für 28 ist 28 33, weil 33 wieder 28 ergibt.
4. Zählen Sie die Elemente in der resultierenden Liste. Im Fall von 28 lautet die Antwort 2.

Hier sind die Ergebnisse für 0<n<=10, damit Sie Ihren Algorithmus überprüfen können.

2 1 1 10 1 11 1 9 5 10

(Wie Balpha hervorhob, higley(1)lautet die Antwort für 2 aus der Liste 1 0. Ich hatte ursprünglich 1 aufgrund eines Fehlers in meinem ursprünglichen Algorithmus, der in J geschrieben wurde.)

Da ich ein eingebildeter SOB bin und dies bei OEIS nicht gefunden habe , nennen wir dies die "Higley-Sequenz", zumindest für die Dauer dieser Runde Code-Golf. Als zusätzlichen Bonus finden Sie die ersten beiden nmit dem niedrigsten, higley(n)wo nnicht prim und ist n>1. (Ich denke, es gibt nur zwei, aber ich kann es nicht beweisen.)

Dies ist Standard-Code-Golf, daher gewinnen wie üblich die wenigsten Tastenanschläge, aber ich bitte Sie, kluge Antworten in anderen Sprachen zu bewerten, auch wenn sie ausführlich sind.

J, 47 45

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

Es ist möglich, dass dies ohne Verwendung viel kürzer wäre ^:_, aber mein Gehirn ist bereits ausreichend gebraten.

Bearbeiten: (47-> 45) Doppelcoupon-Tag.

Verwendungszweck:

   higley =: #@((~.@,(+/@{:*+/@:*/)@(2&p:)@{:)^:_)`2:@.(=&1)
   higley 1
2
   higley"0 (1 + i. 10)
2 1 1 10 1 11 1 9 5 10

Golfscript, 68 67 62 61 Zeichen

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

Dies ist ein Ausdruck: Er nimmt nden Stapel an und belässt das Ergebnis auf dem Stapel. Um daraus ein Programm zu machen, das nvon stdin übernommen und das Ergebnis nach stdout gedruckt wird, ersetzen Sie das führende [durch~

Das Herzstück ist [.2@{1$1$%{)}{\1$/1$}if}*;;](28 Zeichen), das die oberste Zahl auf dem Stapel nimmt und (durch einen unglaublich ineffizienten Algorithmus) eine Liste seiner Primfaktoren generiert. Pseudocode-Äquivalent im C-Stil:

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

Die 0+kurz vor {+}*ist der Sonderfall zu behandeln n==1, weil Golfscript nicht wie eine binäre Operation über die leere Liste zu falten.

Einer der nicht primären Fixpunkte ist 27; Ich fand dies, ohne das Programm zu verwenden, indem ich das Mapping (p ^a -> a ² p), das ein Fixpunkt ist, wenn a == p ^{(a-1) / 2 ist} , und versuchte es klein a. ( a==1gibt die Fixpunktgenauigkeit von Primzahlen an).

Bei der Suche mit dem Programm wird ein zweiter Fixpunkt angezeigt: 30 = (2 + 3 + 5) * 3

Anhang: Beweis, dass es nur zwei Nicht-Prim-Fixpunkte gibt

Notation: sopfr(x)ist die Summe der Primfaktoren von xmit Wiederholung (A001414). Omega(x)ist die Anzahl der Primfaktoren von x(A001222). Die Higley-Nachfolgerfunktion ist alsoh(x) = sopfr(x) Omega(x)

Angenommen, wir haben einen Fixpunkt, N = h(N)der ein Produkt von n=Omega(N)Primzahlen ist.

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

Grundlegende Zahlentheorie: nteilt sich in p_0 ... p_{n-1}, so dass w=Omega(n)von diesen Primzahlen die Primfaktoren von sind n. Wlog wir nehmen sie als die letzten w. So können wir beide Seiten durch teilen nund bekommen

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

oder

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

Da alle der Primzahlen p_0bis p_{n-w-1}größer als 1 sind , die Erhöhung einer von ihnen erhöht sich die LHS mehr als die RHS. Für eine gegebene nkönnen wir also alle Kandidatenlösungen aufzählen.

Insbesondere kann es keine Lösungen geben, wenn die LHS größer als die RHS ist und alle "freien" Primzahlen auf 2 gesetzt werden. Dh es gibt keine Lösungen, wenn

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

Da sopfr(n) <= n(mit Gleichheit nur für n = 4 oder n Primzahl) können wir die schwächere Aussage treffen, dass es keine Fixpunkte gibt, wenn

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

Wenn wwir dies festhalten, können wir verschiedene Werte für die nBefriedigung auswählen w=Omega(n). Das kleinste davon nist 2^w. Beachten Sie, dass wenn 2^{n-w}mindestens 3 ist (dh wenn n-w>1, was wahr ist, wenn n>2), das Erhöhen nbei wkonstantem Halten die LHS mehr als die RHS erhöht. Beachten Sie auch, dass für w>2und unter Berücksichtigung der kleinstmöglichen ndie Ungleichung erfüllt ist und es keine Fixpunkte gibt.

Damit bleiben uns drei Fälle: w = 0und n = 1; w = 1und nist primitiv; oder w = 2und nist semi-prime.

Fall w = 0. n = 1, so Nist jede Primzahl.

Fall w = 1. Wenn n = 2dann N = 2pund wir benötigen p = p + 2, hat das keine Lösungen. Wenn n = 3dann haben wir pq = p + q + 3und zwei Lösungen, (p=2, q=5)und (p=3, q=3). Wenn n = 5dann 2^4 > 3 * 5 - 2 * 1, so gibt es keine weiteren Lösungen mit w = 1.

Fall w = 2. Wenn n = 4dann N = 4pqund wir benötigen pq = p + q + 4. Dies hat eine ganzzahlige Lösung p=2, q=6, aber keine primären Lösungen. Wenn n = 6dann 2^4 > 3 * 6 - 2 * 2, so gibt es keine weiteren Lösungen mit w = 2.

Alle Fälle sind erschöpft, daher sind die einzigen nicht primären Fixpunkte 27 und 30.

Ruby, 92 Zeichen

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}

Diese Lösung geht davon aus, dass Higley (1) tatsächlich 2 und nicht 1 ist (siehe Balphas Kommentar oben):

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

Oktave - 109 Zeichen

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

MATL , 19 Bytes

i`vt0)Yftnws*yy-]xn

Probieren Sie es online aus!