Oblicz sekwencję całkowitą uzyskaną z czynników pierwszych

10

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.

Gregory Higley
źródło
4
Dlaczego highley(1) == 1? Nie ma żadnych czynników pierwszych, więc wynikowa lista w 4) jest [1, 0]taka, highley(1) == 2jak ją widzę.
balpha
Czy możemy założyć, że liczba wejściowa i wartości pośrednie nie będą większe niż 2 ^ 31-1 (tzn. Mieszczą się w 32-bitowej liczbie całkowitej ze znakiem)?
Peter Taylor,
@Peter Taylor Sure.
Gregory Higley,
Jeśli ktoś uzna to za pomocne, sekwencje OEIS, które są niejasno powiązane i mogą dostarczyć inspiracji, to A001414, A001222 i A002217.
Peter Taylor,
1
skoro nie skomentowałeś, zakładam, że nie zauważyłeś: Udowodniłem, że są tylko dwa niepoprawne punkty stałe i dodałem go jako załącznik do mojego postu.
Peter Taylor

Odpowiedzi:

6

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
Jesse Millikan
źródło
Łał! Rozwiązanie AJ, które jest krótsze niż rozwiązanie GolfScript. Pierwszy, który widziałem. (Jestem wielkim fanem J.)
Gregory Higley
3
Możesz to znacznie skrócić, stosując nieco inny algorytm: o długości #@((~.@,((+/*#)@:q:)@{:)^:_)`2:@.(=&1)38 znaków.
Gregory Higley
Wow, próbowałem wymyślić, jak to zrobić za pomocą q: ale próbowałem manipulować nim w moim rozwiązaniu 2 p: więc nie dostałem. Oczywiste z perspektywy czasu.
Jesse Millikan
Fakt, że możesz spojrzeć na eksplozję postaci i powiedzieć, że „ oczywiste z perspektywy czasu ” po prostu budzi mój umysł. Któregoś dnia powinienem sprawdzić Golfscript lub J.
Casey
@Casey Czułem się w ten sam sposób w tym samym czasie, ale im więcej J uczysz się i używasz, tym bardziej to jakby „rzuca się na ciebie”, chociaż wciąż widzę rzeczy, które muszę rozwiązać. Jedną przydatną rzeczą, którą należy wiedzieć o J, jest to, że jeśli dodasz. czyli po symbolu, tworzy nowy symbol, na przykład {, {., i {:wszystko oznacza różne rzeczy, ale {-(na przykład) jest zdecydowanie sekwencja dwóch rzeczy, {a -.
Gregory Higley
5

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

Peter Taylor
źródło
1
Znalazłem dwa takie same punkty za pomocą ołówka i papieru: 27 i 30. Zgadzam się z OP, wydaje się, że są to jedyne dwa.
mellamokb
1
Kolejne interesujące pytanie może być. Czy istnieje nieskończenie wiele higley (x) = 2? Co powiesz na to, że istnieje sposób na wygenerowanie dowolnej wartości Higley (x), takiej jak Higley (x) = 100?
mellamokb
Bardzo dobrze! Jestem facetem od J, ale może będę musiał nauczyć się golfa.
Gregory Higley
@mellamokb Myślę, że istnieje wiele interesujących pytań dotyczących tej sekwencji. Na przykład, jeśli weźmiemy pod uwagę sekwencję liczb wygenerowanych dla każdej nprzed jej policzeniem, czy istnieją jakieś niepierwotne npo 49, dla których wspomniana sekwencja nie kończy się na 28?
Gregory Higley
2
Innym interesującym pytaniem jest to, czy istnieje prosta funkcja, nktórej granice podano higley(n)powyżej. (Pozwoliłoby to znacznie uprościć pętlę - wystarczy f(n)powtórzyć czasy, a następnie odrzucić duplikaty).
Peter Taylor,
4

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]
Ventero
źródło
2

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);
Juan
źródło