Utwórz funkcję, wyrażenie lub program, który wykonuje następujące czynności:

1. Weź czynniki pierwsze dowolnej liczby i zsumuj je. Na przykład czynniki pierwsze 28 wynoszą 2 2 7, zsumowane do 11.
2. Pomnóż wynik przez liczbę czynników pierwszych dla podanej liczby. Np. 28 ma 3 czynniki pierwsze, które sumują się do 11. 11 * 3 to 33.
3. Powtórz proces rekurencyjnie, przechowując wynikową listę (która zaczyna się od oryginalnego numeru), aż dojdziesz do liczby, która jest już na liście. Zatrzymaj się bez dodawania tego ostatniego numeru, aby lista nie zawierała duplikatów. Progresja dla 28 wynosi 28 33, ponieważ 33 daje ponownie 28.
4. Policz elementy na wynikowej liście. W przypadku 28 odpowiedź brzmi 2.

Oto wyniki dla 0<n<=10, dzięki czemu możesz sprawdzić swój algorytm.

2 1 1 10 1 11 1 9 5 10

(Jak zauważył Balpha, odpowiedź na higley(1)to 2, z listy 1 0. Pierwotnie miałem 1, z powodu błędu w moim oryginalnym algorytmie napisanym w J.)

Ponieważ jestem zarozumiałym SOBem i nie znalazłem tego w OEIS , nazwijmy to „Sekwencją Higleya”, przynajmniej na czas tej rundy golfa kodu. Jako dodatkowy bonus, znajdź pierwsze dwa nz najniższą, higley(n)gdzie nnie jest pierwsza i n>1. (Myślę, że są tylko dwa, ale nie mogę tego udowodnić.)

Jest to standardowy kod golfowy, więc jak zwykle wygrywa najmniejsza liczba naciśnięć klawiszy, ale proszę o głosowanie sprytnych odpowiedzi w innych językach, nawet jeśli są pełne.

J, 47 45

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

Możliwe, że byłoby to znacznie krótsze bez użycia ^:_, ale mój mózg jest już wystarczająco usmażony.

Edycja: (47-> 45) Dzień podwójnego kuponu.

Stosowanie:

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

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

To wyrażenie: przyjmuje nstos i pozostawia wynik na stosie. Aby włączyć go do programu, który zabierze nze standardowego wejścia i wypisuje wynik na standardowe wyjście, wymień wiodącym [z~

Jego sednem jest [.2@{1$1$%{)}{\1$/1$}if}*;;](28 znaków), który zajmuje najwyższą liczbę na stosie i (dzięki nieefektywnemu algorytmowi) generuje listę jego głównych czynników. Odpowiednik pseudokodu w stylu C:

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

0+Tuż przed {+}*jest obsłużyć szczególny przypadek n==1, bo nie lubi Golfscript składane operacji binarnej nad pustą listę.

Jednym z nietrwałych punktów stałych jest 27; Znalazłem to bez użycia programu, biorąc pod uwagę mapowanie (p ^a -> a ² p), co jest punktem stałym, jeśli a == p ^{(a-1) / 2} , i próbowanie małych a. ( a==1podaje punkt stałości liczb pierwszych).

Wyszukiwanie za pomocą programu ujawnia drugi punkt stały: 30 = (2 + 3 + 5) * 3

Dodatek: dowód, że istnieją tylko dwa punkty stałe inne niż główne

Notacja: sopfr(x)jest sumą czynników pierwszych xz powtórzeniem (A001414). Omega(x)to liczba czynników pierwszych x(A001222). Tak więc funkcja następcy Higleya jesth(x) = sopfr(x) Omega(x)

Załóżmy, że mamy punkt stały, N = h(N)który jest iloczynem n=Omega(N)liczb pierwszych.

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

Podstawowa teoria liczb: ndzieli się na p_0 ... p_{n-1}, więc w=Omega(n)z tych liczb pierwszych należą czynniki pierwszen . Wlog, weźmiemy je jako ostatnie w. Więc możemy podzielić obie strony ni uzyskać

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

lub

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

Biorąc pod uwagę, że wszystkie liczby pierwsze p_0 do p_{n-w-1}są większe niż 1, zwiększając każdy z nich zwiększa LHS ponad RHS. Tak więc dla danego nmożemy wyliczyć wszystkie rozwiązania kandydujące.

W szczególności nie może być rozwiązań, jeśli LHS jest większy niż RHS, ustawiając wszystkie „wolne” liczby pierwsze na 2. Tzn. Nie ma rozwiązań, jeśli

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

Ponieważ sopfr(n) <= n(z równością tylko dla n = 4 lub n liczby pierwszej) możemy uczynić słabszym stwierdzeniem, że nie ma punktów stałych, jeśli

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

Trzymając wstały możemy wybrać różne wartości nsatysfakcji w=Omega(n). Najmniejszy taki njest 2^w. Należy zauważyć, że jeśli 2^{n-w}wynosi co najmniej 3 (tj. Jeśli n-w>1, co jest prawdą, jeśli n>2), to zwiększenie nprzy utrzymaniu wstałej zwiększy LHS bardziej niż RHS. Zauważ też, że dlaw>2 najmniejszych możliwych nnierówności są spełnione i nie ma punktów stałych.

Pozostają nam trzy przypadki: w = 0i n = 1; w = 1i njest liczbą pierwszą; lubw = 2 i njest półpierwotny.

Case w = 0. n = 1, więcN każda liczba pierwsza.

Case w = 1. Jeśli n = 2to N = 2pi wymagamy p = p + 2, co nie ma rozwiązań. Jeśli n = 3to mamy pq = p + q + 3i dwa rozwiązania, (p=2, q=5)i (p=3, q=3). Jeśli n = 5następnie 2^4 > 3 * 5 - 2 * 1, więc nie ma dalszych roztwory w = 1.

Case w = 2. Jeśli n = 4to N = 4pqi będziemy wymagać pq = p + q + 4. Ma to rozwiązanie liczb całkowitych p=2, q=6, ale nie ma najlepszych rozwiązań. Jeśli n = 6następnie 2^4 > 3 * 6 - 2 * 2, więc nie ma dalszych roztwory w = 2.

Wszystkie przypadki są wyczerpane, więc jedynymi nie-głównymi punktami stałymi są 27 i 30.

Ruby, 92 znaki

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}

To rozwiązanie zakłada, że ​​higley (1) to tak naprawdę 2, a nie 1 (patrz komentarz balpha powyżej):

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

Oktawa - 109 znaków

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

i`vt0)Yftnws*yy-]xn

Wypróbuj online!