Definicje

Pozwolić mi nbyć dodatnimi liczbami całkowitymi. Mówimy, że mjest skręt dzielnik od njeśli istnieje liczby całkowite 1 < a ≤ btakie, że n = a*bi m = (a - 1)*(b + 1) + 1. Jeśli mmoże być uzyskane z nstosując zero lub więcej skrętów dzielnik do niej, a następnie mjest potomkiem z n. Zauważ, że każda liczba jest własnym potomkiem.

Rozważmy na przykład n = 16. Możemy wybrać a = 2i b = 8, ponieważ 2*8 = 16. Następnie

(a - 1)*(b + 1) + 1 = 1*9 + 1 = 10

co pokazuje, że 10jest to skręt dzielnika 16. Za pomocą a = 2i b = 5widzimy, że 7jest to zwrot dzielnika 10. Zatem 7jest potomkiem 16.

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą n, oblicz potomków nwymienionych w kolejności rosnącej, bez duplikatów.

Zasady

Nie wolno używać wbudowanych operacji obliczających dzielniki liczby.

Akceptowane są zarówno pełne programy, jak i funkcje, a zwracanie typu danych kolekcji (jak pewnego rodzaju zestawu) jest dozwolone, o ile jest ono posortowane i wolne od duplikatów. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

1 ->  [1]
2 ->  [2] (any prime number returns just itself)
4 ->  [4]
16 -> [7, 10, 16]
28 -> [7, 10, 16, 25, 28]
51 -> [37, 51]
60 -> [7, 10, 11, 13, 15, 16, 17, 18, 23, 25, 28, 29, 30, 32, 43, 46, 49, 53, 55, 56, 60]

Python 2, 109 98 85 82 bajtów

f=lambda n:sorted(set(sum(map(f,{n-x+n/x for x in range(2,n)if(n<x*x)>n%x}),[n])))

Ponieważ (a-1)*(b+1)+1 == a*b-(b-a)i b >= apotomkowie są zawsze mniejsi lub równi oryginalnej liczbie. Możemy więc zacząć od początkowej liczby i generować ściśle mniejszych potomków, dopóki ich nie pozostanie.

Warunek (n<x*x)>n%xsprawdza dwie rzeczy w jednym - to n<x*xi n%x == 0.

(Dzięki @xnor za zdjęcie 3 bajtów ze skrzynki podstawowej)

Pyth, 32 bajty

LS{s+]]bmydm+-bk/bkf><b*TT%bTr2b

Bezpośrednie tłumaczenie powyższego, z wyjątkiem faktu, że Pyth wydaje się dusić podczas próby sumowania ( s) na pustej liście.

Definiuje funkcję, yktórą można wywołać dodając y<number>na końcu, tak jak to ( spróbuj online ):

LS{s+]]bmydm+-bk/bkf><b*TT%bTr2by60

CJam, 47 45 bajtów

{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}

Również przy użyciu tej samej metody, z kilkoma modyfikacjami. Chciałem wypróbować CJam do porównania, ale niestety jestem znacznie gorszy w CJam niż w Pyth / Python, więc prawdopodobnie jest dużo miejsca na ulepszenia.

Powyżej jest blok (w zasadzie wersja nienazwanych funkcji CJam), który przyjmuje int i zwraca listę. Możesz to przetestować w ten sposób ( wypróbuj online ):

{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}:G; 60 Gp

Java, 148 146 104 bajtów

Wersja golfowa:

import java.util.*;Set s=new TreeSet();void f(int n){s.add(n);for(int a=1;++a*a<n;)if(n%a<1)f(n+a-n/a);}

Długa wersja:

import java.util.*;
Set s = new TreeSet();
void f(int n) {
    s.add(n);
    for (int a = 1; ++a*a < n;)
        if (n%a < 1)
            f(n + a - n/a);
}

Debiutuję więc na PPCG za pomocą tego programu, który wykorzystuje TreeSet(na szczęście automatycznie sortuje liczby) i rekurencję podobną do programu Geobitów, ale w inny sposób, sprawdzając wielokrotności n, a następnie używając ich w następna funkcja. Powiedziałbym, że jest to całkiem niezły wynik jak na pierwszy raz (szczególnie w Javie, która nie wydaje się być najlepszym językiem dla tego rodzaju rzeczy i pomocy Geobitów).

Java, 157 121

Oto funkcja rekurencyjna, która pobiera potomków każdego potomka n. Zwraca a TreeSet, który jest domyślnie sortowany.

import java.util.*;Set t(int n){Set o=new TreeSet();for(int i=1;++i*i<n;)o.addAll(n%i<1?t(n+i-n/i):o);o.add(n);return o;}

Z pewnymi podziałami linii:

import java.util.*;
Set t(int n){
    Set o=new TreeSet();
    for(int i=1;++i*i<n;)
        o.addAll(n%i<1?t(n+i-n/i):o);
    o.add(n);
    return o;
}

Oktawa, 107 96

function r=d(n)r=[n];a=find(!mod(n,2:sqrt(n-1)))+1;for(m=(a+n-n./a))r=unique([d(m) r]);end;end

Ładny druk:

function r=d(n)
  r=[n];                          # include N in our list
  a=find(!mod(n,2:sqrt(n-1)))+1;  # gets a list of factors of a, up to (not including) sqrt(N)
  for(m=(a+n-n./a))               # each element of m is a twist
    r=unique([d(m) r]);           # recurse, sort, and find unique values
  end;
end

Haskell, 102 100 bajtów

import Data.List
d[]=[]
d(h:t)=h:d(t++[a*b-b+a|b<-[2..h],a<-[2..b],a*b==h])
p n=sort$nub$take n$d[n]

Zastosowanie: p 16które wyjścia[7,10,16]

Funkcja drekurencyjnie oblicza wszystkich potomków, ale nie sprawdza duplikatów, więc wielu pojawia się więcej niż jeden raz, np. d [4]Zwraca nieskończoną listę 4s. Funkcje ppobierają pierwsze nelementy z tej listy, usuwają duplikaty i sortują listę. Voilà.

CJam - 36

ri_a\{_{:N,2>{NNImd!\I-z*-}fI}%|}*$p

Wypróbuj online

Lub inna metoda:

ri_a\{_{_,2f#_2$4*f-&:mq:if-~}%|}*$p

Napisałem je prawie 2 dni temu, utknąłem w wieku 36 lat, byłem sfrustrowany i poszedłem spać bez wysyłania postów.