Liczba obfita to dowolna liczba, w której suma jej właściwych dzielników jest większa niż liczba pierwotna. Na przykład właściwymi dzielnikami 12 są:

1, 2, 3, 4, 6

I sumując te wyniki w 16. Ponieważ 16 jest większe niż 12, 12 jest obfite. Zauważ, że nie obejmuje to „liczb doskonałych”, np. Liczb, które są równe sumie jego właściwych dzielników, takich jak 6 i 28.

Twoim zadaniem na dziś jest napisanie programu lub funkcji, która określa, czy liczba jest duża, czy nie. Twój program powinien przyjąć jedną liczbę całkowitą jako dane wejściowe i wygenerować wartość prawdy / fałszu w zależności od tego, czy jest ona obfita, czy nie. Możesz założyć, że dane wejściowe zawsze będą prawidłowe i większe od 0, więc w przypadku złych danych wejściowych niezdefiniowane zachowanie jest w porządku.

Możesz wziąć swoje dane wejściowe i wyjściowe w dowolnym rozsądnym formacie, na przykład dopuszczalne byłyby STDIN / STDOUT, pliki lub argumenty / zwracane wartości.

Dla porównania, oto obfite liczby do 100:

12,
18,
20,
24,
30,
36,
40,
42,
48,
54,
56,
60,
66,
70,
72,
78,
80,
84,
88,
90,
96,
100

Więcej można znaleźć na A005101

Ponieważ jest to gra w golfa kodowego , standardowe luki są odrzucane i spróbuj napisać możliwie najkrótszy kod w dowolnym języku, który wybierzesz!

ECMAScript Regex, 1085 855 597 536 511 508 504 bajtów

Dopasowywanie obfitych liczb w wyrażeniu regularnym ECMAScript jest zupełnie inną bestią niż w praktycznie każdym innym smaku wyrażenia regularnego. Brak odwołań do przodu / zagnieżdżonych wstecz lub rekurencji oznacza, że ​​nie można bezpośrednio policzyć ani zachować bieżącej sumy czegokolwiek. Brak wyglądu sprawia, że ​​często jest to wyzwanie, nawet mając wystarczająco dużo miejsca do pracy.

Do wielu problemów należy podchodzić z zupełnie innej perspektywy, a będziesz się zastanawiać, czy w ogóle można je rozwiązać. Zmusza cię to do rzucenia znacznie szerszej sieci w celu znalezienia, które matematyczne właściwości liczb, z którymi pracujesz, mogą być wykorzystane do rozwiązania konkretnego problemu.

Na przełomie marca i kwietnia 2014 roku opracowałem rozwiązanie tego problemu w wyrażeniu regularnym ECMAScript. Na początku miałem wszelkie powody, by podejrzewać, że problem jest całkowicie niemożliwy, ale potem matematyk teukon naszkicował pomysł, który zachęcał do tego, by mimo wszystko wyglądał na rozwiązalny - ale wyjaśnił, że nie ma zamiaru tworzyć wyrażenia regularnego ( rywalizował / współpracował ze mną przy konstruowaniu / grze w golfa wcześniejszych wyrażeń regularnych, ale do tego momentu osiągnął swój limit i był zadowolony z ograniczenia dalszego udziału w teoretyzowaniu).

Podobnie jak w przypadku mojego wyrażenia regularnego opublikowanego kilka dni temu, ostrzegam: Bardzo polecam nauczenie się rozwiązywania pojedynczych problemów matematycznych w wyrażeniu regularnym ECMAScript. To była dla mnie fascynująca podróż i nie chcę zepsuć jej nikomu, kto mógłby potencjalnie chcieć spróbować samemu, szczególnie tym, którzy interesują się teorią liczb. Zobacz ten post, aby uzyskać listę zalecanych problemów oznaczonych spoilerem do rozwiązania jeden po drugim.

Więc nie czytaj dalej, jeśli nie chcesz, aby zepsuła ci się jakaś głęboka, jednoargumentowa magia wyrażeń regularnych . Mój poprzedni post był tylko małym gustem. Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów z wyrażeniem regularnym ECMAScript, jak opisano w linku powyżej.

Przed wysłaniem mojego ECMAScript regex, myślałem, że dobrze byłoby, aby analizować Martina Endera .NET rozwiązanie czystego regex , ^(?!(1(?<=(?=(?(\3+$)((?>\2?)\3)))^(1+)))*1$). Okazuje się, że zrozumienie tego wyrażenia regularnego jest bardzo proste i jest elegancki w swojej prostocie. Aby zademonstrować kontrast między naszymi rozwiązaniami, oto skomentowana i ładnie wydrukowana (ale niezmodyfikowana) wersja jego wyrażenia regularnego:

# For the purpose of these comments, the input number will be referred to as N.

^(?!                  # Attempt to add up all the divisors. Since this is a regex and we
                      # can only work within the available space of the input, that means
                      # if the sum of the divisors is greater than N, the attempt to add
                      # all the divisors will fail at some point, causing this negative
                      # lookahead to succeed, showing that N is an abundant number.

  (1                  # Cycle through all values of tail that are less than N, testing
                      # each one to see if it is a divisor of N.

    (?<=              # Temporarily go back to the start so we can directly operate both
                      # on N and the potential divisor. This requires variable-length
                      # lookbehind, a .NET feature – even though this special case of
                      # going back to the start, if done left-to-right, would actually be
                      # very easy to implement even in a regex flavour that has no
                      # lookbehind to begin with. But .NET evaluates lookbehinds right
                      # to left, so please read these comments in the order indicated,
                      # from [Step 1] to [Step 7]. The comment applying to entering the
                      # lookahead group, [Step 2], is shown on its closing parenthesis.
      (?=             # [Step 3] Since we're now in a lookahead, evaluation is left to
                      #          right.
        (?(\3+$)      # [Step 4] If \3 is a divisor of N, then...
          (           # [Step 5] Add it to \2, the running total sum of divisors:
                      #          \2 = \2 + \3         
            (?>\2?)   # [Step 6] Since \2 is a nested backref, it will fail to match on
                      #          the first iteration. The "?" accounts for this, making
                      #          it add zero to itself on the first iteration. This must
                      #          be done before adding \3, to ensure there is enough room
                      #          for the "?" not to cause the match to become zero-length
                      #          even if \2 has a value.
            \3        # [Step 7] Iff we run out of space here, i.e. iff the sum would
                      #          exceed N at this point, the match will fail, making the
                      #          negative lookahead succeed, showing that we have an
                      #          abundant number.
          )

        )
      )               # [Step 2] Enter a lookahead that is anchored to the start due to
                      #          having a "^" immediately to its right. The regex would
                      #          still work if the "^" were moved to the left of the
                      #          lookahead, but would be slightly slower, because the
                      #          engine would do some spurious matching before hitting
                      #          the "^" and backtracking.
      ^(1+)           # [Step 1] \3 = number to test for being a potential divisor – its
                      #               right-side-end is at the point where the lookbehind
                      #               started, and thus \3 cycles through all values from
                      #               1 to N-1.
    )
  )*1$                # Exclude N itself from being considered as a potential divisor,
                      # because if we included it, the test for proper abundance would be
                      # the sum of divisors exceeding 2*N. We don't have enough space for
                      # that, so instead what would happen if we did not exclude N as a
                      # divisor would be testing for "half-abundance", i.e. the sum of
                      # all divisors other than N exceeding N/2. By excluding N as a
                      # divisor we can let our threshold for abundance be the sum of
                      # divisors exceeding N.
)

Wypróbuj .ge regex online

Teraz wróć do mojego wyrażenia regularnego ECMAScript. Po pierwsze, tutaj jest w surowym formacie, bez białych znaków i bez komentarzy:

^(?=(((?=(xx+?)\3+$)(x+)\4*(?=\4$))+(?!\3+$)(?=(xx(x*?))\5*$)x)(x+))(?=\1(x(x*))(?=\8*$)\6\9+$)(?=(.*)((?=\8*$)\5\9+$))(?=(x*?)(?=(x\11)+$)(?=\12\10|(x))(x(x*))(?=\15*$)(?=\11+$)\11\16+$)(?=(x(x*))(?=\17*$)\7\18+$)((?=(x*?(?=\17+$)(?=\17+?(?=((xx(x*))(?=\18+$)\22*$))(x+).*(?=\17$)\24*(?=\24$)(?!(xx+)\25*(?!\22+$)\25$)\22+$)((?=(x\7)+$)\15{2}\14|)))(?=.*(?=\24)x(x(x*))(?=\28*$)\23\29*$)(?=.*(x((?=\28*$)\22\29+$)))(.*(?!\30)\20|(?=.*?(?!x\20)(?=\30*$)(x(x*))(?=\33*$)(?=\31+$)\31\34+$).*(?=\33\21$)))+$

^{(zmień \14na \14?na kompatybilność z PCRE, .NET i praktycznie każdym innym wyrażeniem regularnym, który nie jest ECMAScript)}

Wypróbuj online!
Wypróbuj online! (szybsza, 537 bajtowa wersja wyrażenia regularnego)

A teraz krótkie streszczenie tej historii.

Na początku było dla mnie bardzo nieoczywiste, że w ogóle możliwe było dopasowanie liczb pierwszych. I po rozwiązaniu tego, to samo dotyczyło potęg 2., a następnie potęg liczb zespolonych. A potem idealne kwadraty. I nawet po rozwiązaniu tego, generalizacja mnożenia wydawała się początkowo niemożliwa.

W pętli ECMAScript można śledzić tylko jedną zmieniającą się liczbę; liczba ta nie może przekraczać wartości wejściowej i musi maleć z każdym krokiem. Moje pierwsze wyrażenie regularne dla dopasowania poprawnych instrukcji mnożenia A * B = C wynosiło 913 bajtów i pracowałem przez faktoryzację A, B i C w ich liczbach pierwszych - dla każdego czynnika pierwszego, wielokrotnie dzielę parę głównych współczynników mocy A i C przez swoją podstawową podstawę, aż ta odpowiadająca A osiągnie 1; ta odpowiadająca C jest następnie porównywana z pierwszym współczynnikiem mocy B. Te dwie moce tej samej liczby pierwszej zostały „zmultipleksowane” w jedną liczbę poprzez dodanie ich razem; byłoby to zawsze jednoznacznie rozdzielne przy każdej kolejnej iteracji pętli, z tego samego powodu, dla którego działają systemy liczbowe pozycyjne.

Mnożymy do 50 bajtów przy użyciu zupełnie innego algorytmu (do którego Teukon i ja mogliśmy dojść niezależnie, chociaż zajęło mu to tylko kilka godzin i poszedł od razu, podczas gdy zajęło mi to kilka dni, nawet po tym, jak było zwróciłem uwagę, że istnieje krótka metoda): dla A ≥B, A * B = C, jeśli występuje, tylko jeśli C jest najmniejszą liczbą, która spełnia C0 mod A i C≡B mod A-1. (Dogodnie, wyjątek A = 1 nie wymaga specjalnej obsługi w wyrażeniach regularnych, gdzie 0% 0 = 0 daje dopasowanie.) Po prostu nie mogę się pogodzić z tym, jak fajnie jest, że taki elegancki sposób mnożenia istnieje w takim minimalny smak wyrażenia regularnego. (A wymaganie A≥B można zastąpić wymogiem, że A i B są podstawowymi mocami o tej samej mocy. W przypadku A≥B można to udowodnić za pomocą twierdzenia o reszcie chińskiej.)

Gdyby okazało się, że nie ma prostszego algorytmu do mnożenia, znaczna liczba wyrażeń regularnych prawdopodobnie byłaby rzędu dziesięciu tysięcy bajtów (nawet biorąc pod uwagę, że wykorzystałem algorytm 913 bajtów do 651 bajtów). Robi wiele mnożenia i dzielenia, a regex ECMAScript nie ma podprogramów.

Rozpocząłem pracę nad problemem licznej liczby stycznie w 23 marca 2014 r., Konstruując rozwiązanie tego, co w tamtym czasie wydawało się być podproblemem tego problemu: Identyfikowanie czynnika pierwszego o największej krotności, aby można go było podzielić na N na początku pozostawiając miejsce na wykonanie niezbędnych obliczeń. W tym czasie wydawało się, że jest to obiecująca droga. (Moje początkowe rozwiązanie okazało się dość duże przy 326 bajtach, później golfa do 185 bajtów.) Ale reszta metody naszkicowanej przez Teukona byłaby niezwykle skomplikowana, więc jak się okazało, wybrałem inną drogę. Okazało się, że wystarczające jest podzielenie największego głównego współczynnika mocy N odpowiadającego największemu pierwszemu współczynnikowi mocy na N; robienie tego dla liczby największej krotności zwiększyłoby niepotrzebną złożoność i długość wyrażenia regularnego.

Pozostało traktowanie sumy dzielników jako iloczynu sum zamiast sumy prostej. Jak wyjaśnił teukon 14 marca 2014 r .:

Otrzymujemy numer n = p ₀ ^{a ₀} p ₁ ^{a ₁} ... p _k-1 ^{a _k-1} . Chcemy obsłużyć sumę czynników n, która wynosi (1 + p ₀ + p ₀ ² + ... + p ₀ ^{a ₀} ) (1 + p ₁ + p ₁ ² + ... + p ₁ ^{a ₁} ) ... (1 + p _k-1 + p _k-1 ² + ... + p _k-1 ^{a _k-1} ).

Zrozumiałem, że to widzę. Nigdy nie myślałem o tak liczeniu sumy podwielokrotności i to właśnie ta formuła sprawiła, że ​​rozwiązalność obfitego dopasowywania liczb w wyrażeniu regularnym ECMAScript wydaje się wiarygodna.

W końcu zamiast testowania pod kątem dodania lub pomnożenia przekraczającego N lub testowania, że ​​taki wynik podzielony przez M przekracza N / M, przystąpiłem do testowania, jeśli wynik podziału jest mniejszy niż 1. Dotarłem do pierwsza działająca wersja 7 kwietnia 2014 r.

Pełna historia moich optymalizacji golfa tego wyrażenia regularnego znajduje się na github. W pewnym momencie jedna optymalizacja zakończyła się znacznie wolniejszym wyrażeniem regularnym, więc od tego momentu zachowałem dwie wersje. Oni są:

Wyrażenie regularne dla dopasowania licznej liczby.txt
Wyrażenie regularne dla dopasowania licznej liczby - shortest.txt

Te wyrażenia regularne są w pełni kompatybilne zarówno z ECMAScript, jak i PCRE, ale ostatnia optymalizacja wymagała użycia potencjalnie nieuczestniczącej grupy przechwytywania \14, więc porzucenie kompatybilności PCRE i przejście \14?na \14obie można zmniejszyć o 1 bajt.

Oto najmniejsza wersja z zastosowaną optymalizacją (czyniącą ją tylko ECMAScript), sformatowaną tak, aby pasowała do bloku kodu StackExchange bez (głównie) przewijania w poziomie:

# Match abundant numbers in the domain ^x*$ using only the ECMAScript subset of regex
# functionality. For the purposes of these comments, the input number = N.
^
# Capture the largest prime factor of N, and the largest power of that factor that is
# also a factor of N. Note that the algorithm used will fail if N itself is a prime
# power, but that's fine, because prime powers are never abundant.
(?=
  (                      # \1 = tool to make tail = Z-1
    (                    # Repeatedly divide current number by its smallest factor
      (?=(xx+?)\3+$)
      (x+)\4*(?=\4$)
    )+                   # A "+" is intentionally used instead of a "*", to fail if N
                         #  is prime. This saves the rest of the regex from having to
                         #  do needless work, because prime numbers are never abundant.
    (?!\3+$)             # Require that the last factor divided out is a different prime.
    (?=(xx(x*?))\5*$)    # \5 = the largest prime factor of N; \6 = \5-2
    x                    # An extra 1 so that the tool \1 can make tail = Z-1 instead of just Z
  )
  (x+)                   # Z = the largest power of \5 that is a factor of N; \7 = Z-1
)
# We want to capture Z + Z/\5 + Z/\5^2 + ... + \5^2 + \5 + 1 = (Z * \5 - 1) / (\5 - 1),
# but in case Z * \5 > N we need to calculate it as (Z - 1) / (\5 - 1) * \5 + 1.
# The following division will fail if Z == N, but that's fine, because no prime power is
# abundant.
(?=
  \1                     # tail = (Z - 1)
  (x(x*))                # \8   = (Z - 1) / (\5 - 1); \9 = \8-1
  # It is guaranteed that either \8 > \5-1 or \8 == 1, which allows the following
  # division-by-multiplication to work.
  (?=\8*$)
  \6\9+$
)
(?=
  (.*)                   # \10 = tool to compare against \11
  (                      # \11 = \8 * \5  =  (Z - 1) / (\5 - 1) * \5; later, \13 = \11+1
    (?=\8*$)
    \5\9+$
  )
)
# Calculate Q = \15{2} + Q_R = floor(2 * N / \13). Since we don't have space for 2*N, we
# need to calculate N / \13 first, including the fractional part (i.e. the remainder),
# and then multiply the result, including the fractional part, by 2.
(?=
  (x*?)(?=(x\11)+$)      # \12 = N % \13; \13 = \11 + 1
  (?=\12\10|(x))         # \14 = Q_R = floor(\12 * 2 / \13)
                         #     = +1 carry if \12 * 2 > \11, or NPCG otherwise
  (x(x*))                # \15 = N / \13; \16 = \15-1
  (?=\15*$)
  (?=\11+$)              # must match if \15 <  \13; otherwise doesn't matter
  \11\16+$               # must match if \15 >= \13; otherwise doesn't matter
)
# Calculate \17 = N / Z. The division by Z can be done quite simply, because the divisor
# is a prime power.
(?=
  (x(x*))                # \17 = N / Z; \18 = \17-1
  (?=\17*$)
  \7\18+$
)
# Seed a loop which will start with Q and divide it by (P^(K+1)-1)/(P-1) for every P^K
# that is a factor of \17. The state is encoded as \17 * P + R, where the initial value
# of R is Q, and P is the last prime factor of N to have been already processed.
#
# However, since the initial R would be larger than \17 (and for that matter there would
# be no room for any nonzero R since with the initial value of P, it is possible for
# \17 * P to equal N), treat it as a special case, and let the initial value of R be 0,
# signalling the first iteration to pretend R=Q. This way we can avoid having to divide Q
# and \17 again outside the loop.
#
# While we're at it, there's really no reason to do anything to seed this loop. To seed
# it with an initial value of P=\5, we'd have to do some multiplication. If we don't do
# anything to seed it, it will decode P=Z. That is wrong, but harmless, since the next
# lower prime that \17 is divisible by will still be the same, as \5 cannot be a factor
# of \17.

# Start the loop.
(
  (?=
    (                    # \20 = actual value of R
      x*?(?=\17+$)       # move forward by directly decoded value of R, which can be zero
      # The division by \17 can be done quite simply, because it is known that
      # the quotient is prime.
      (?=
        \17+?            # tail = \17 * (a prime which divides into \17)
        (?=
          (              # \21 = encoded value for next loop iteration
            (xx(x*))     # \22 = decoded value of next smaller P; \23 = (\22-1)-1
            (?=\18+$)    # iff \22 > \17, this can have a false positive, but never a false negative
            \22*$        # iff \22 < \17, this can have a false positive, but never a false negative
          )
        )
        # Find the largest power of \22 that is a factor of \17, while also asserting
        # that \22 is prime.
        (x+)             # \24 = the largest power of \22 that is a factor of \17
        .*(?=\17$)
        \24*(?=\24$)
        (?!
          (xx+)\25*
          (?!\22+$)
          \25$
        )
        \22+$
      )
      (
        (?=(x\7)+$)      # True iff this is the first iteration of the loop.
        \15{2}\14        # Potentially unset capture, and thus dependent on ECMAScript
                         # behavior. Change "\14" to "\14?" for compatibility with non-
                         # ECMAScript engines, so that it will act as an empty capture
                         # with engines in which unset backrefs always fail to match.
      |
      )
    )
  )
  # Calculate \30 = (\24 - 1) / (\22 - 1) * \22 + 1
  (?=
    .*(?=\24)x           # tail = \24 - 1
    (x(x*))              # \28 = (\24 - 1) / (\22 - 1); \29 = \28-1
    (?=\28*$)
    \23\29*$
  )
  (?=
    .*(x(                # \30 = 1 + \28 * \22 = (\28 - 1) / (\22 - 1) * \22 + 1; \31 = \30-1
      (?=\28*$)
      \22\29+$
    ))
  )
  # Calculate \33 = floor(\20 / \30)
  (
    .*(?!\30)\20         # if dividing \20 / \30 would result in a number less than 1,
                         # then N is abundant and we can exit the loop successfully
  |
    (?=
      .*?(?!x\20)(?=\30*$)
      (x(x*))            # \33 = \20 / \30; \34 = \33-1
      (?=\33*$)
      (?=\31+$)          # must match if \33 <  \30; otherwise doesn't matter
      \31\34+$           # must match if \33 >= \30; otherwise doesn't matter
    )
    # Encode the state for the next iteration of the loop, as \17 * \22 + \33
    .*(?=\33\21$)
  )
)+$

Python 2 , 41 40 bajtów

n=k=j=input()
while~k<0:j-=1;k-=j>>n%j*n

Wyjście odbywa się za pomocą kodu wyjścia , więc 0 to prawda, a 1 to fałsz.

Wypróbuj online!

Jak to działa

Po ustawieniu wszystkich n , k oraz j do wejścia ze standardowego wejścia, wchodzimy do while pętli. Wspomniana pętla zostanie przerwana, gdy tylko -k - 1 = ~ k ≥ 0 , tj. K ≤ -1 / k <0 .

W każdej iteracji najpierw zmniejszamy j, aby uwzględnić tylko właściwe dzielniki n . Jeśli j jest dzielnikiem n , n%jdaje 0, a j >> n% j * n = j / 2 ⁰ = j jest odejmowane od k . Jednakże, jeśli j czy nie podzielić n , n%jjest dodatni, więc n%j*njest co najmniej n> log ₂ j i j >> n% n * j = j / 2 ^{n% j * n} = 0 jest odejmowany od k .

Dla liczb obfitych, k osiągnie wartość ujemną przed lub po j staje się 1 , ponieważ suma n „s odpowiednie dzielniki jest większe niż n . W tym przypadku możemy wyrwać się z while pętli i program zakończy się normalnie.

Jeśli jednak n nie jest obfite, j ostatecznie osiąga 0 . W takim przypadku n%jzgłasza ZeroDivisionError i program kończy działanie z błędem.

Brachylog , 5 bajtów

fk+>?

Wypróbuj online!

Wyjaśnienie

f           Factors
 k          Knife: remove the last one (the input itself)
  +         Sum
   >?       Stricly greater than the Input

Galaretka , 3 bajty

Æṣ>

Wypróbuj online!

Jak to działa

Æṣ>  Main link. Argument: n

Æs   Get the proper divisor sum of n.
  >  Test if the result is greater than n.

Python , 44 bajty

lambda n:sum(i*(n%i<1)for i in range(1,n))>n

Wypróbuj online!

Mathematica, 17 bajtów

Tr@Divisors@#>2#&

Wyjaśnienie

Tr@                 The sum of the main diagonal of
   Divisors@         the list of divisors of
            #         the first argument
             >      is greater than
              2#      twice the first argument.
                &   End of function.

05AB1E , 5 4 bajtów

-1 bajtów dzięki scottinet

ѨO‹

Wypróbuj online! lub Spróbuj od 0 do 100

Siatkówka , 50 45 bajtów

^(?!(1(?<=(?=(?(\3+$)((?>\2?)\3)))^(1+)))*1$)

Wpisuj w unary , w 1przypadku obfitych liczb, w 0przeciwnym razie.

W tym rozwiązaniu nie ma nic specyficznego dla siatkówki. Powyżej jest czystym wyrażeniem regularnym .NET, które pasuje tylko do obfitych liczb.

Wypróbuj online! (Pakiet testowy, który filtruje dane dziesiętne z powyższym wyrażeniem regularnym).

Retina , 34 bajty

Liczba bajtów zakłada kodowanie ISO 8859-1.

M!&`(1+)$(?<=^\1+)
1>`¶

^(1+)¶1\1

Wpisuj w unary , w 1przypadku obfitych liczb, w 0przeciwnym razie.

Wypróbuj online!

Wyjaśnienie

M!&`(1+)$(?<=^\1+)

Zaczynamy od uzyskania wszystkich dzielników danych wejściowych. Aby to zrobić, zwracamy ( !) wszystkie pokrywające się ( &) dopasowania ( M) wyrażenia regularnego (1+)$(?<=^\1+). Wyrażenie regularne pasuje do jakiegoś sufiksu wejścia, pod warunkiem, że całe wejście jest wielokrotnością tego sufiksu (co zapewniamy, próbując dotrzeć do początku ciągu przy użyciu tylko kopii sufiksu). Z powodu sposobu, w jaki silnik wyrażeń regularnych szuka dopasowań, spowoduje to wyświetlenie listy dzielników w malejącej kolejności (oddzielonych liniami).

1>`¶

Sam etap dopasowuje po prostu linefeeds ( ¶) i usuwa je. Jednak 1>jest granica, która pomija pierwszy mecz. To skutecznie sumuje wszystkie dzielniki z wyjątkiem samego wkładu. Kończymy z danymi wejściowymi w pierwszym wierszu i sumą wszystkich właściwych dzielników w drugim wierszu.

^(1+)¶1\1

Wreszcie, staramy się dopasować co najmniej jeden więcej 1w drugiej linii niż w pierwszej linii. W takim przypadku suma właściwych dzielników przekracza dane wejściowe. Siatkówka liczy liczbę dopasowań tego wyrażenia regularnego, które będzie 1dla obfitych liczb i 0nie tylko.

8086 Zgromadzenie, 23 28 25 24 bajty

8bc8 d1e9 33db 33d2 50f7 f158 85d2 7502 03d9 7204 e2f0 3bc3

Niezmontowane:

; calculate if N (1 < N <= 65535) is abundant
; input: N (mem16/r16)
; output: CF=1 -> abundant, CF=0 -> not abundant
ABUND   MACRO   N 
        LOCAL DIV_LOOP, CONT_LOOP, END_ABUND
        IFDIFI <N>,<AX> ; skip if N is already AX
    MOV  AX, N          ; AX is dividend
        ENDIF
    MOV  CX, AX         ; counter starts at N / 2
    SHR  CX, 1          ; divide by 2
    XOR  BX, BX         ; clear BX (running sum of factors)
DIV_LOOP:
    XOR  DX, DX         ; clear DX (high word for dividend)
    PUSH AX             ; save original dividend
    DIV  CX             ; DX = DX:AX MOD CX, AX = DX:AX / CX
    POP  AX             ; restore dividend (AX was changed by DIV)
    TEST DX, DX         ; if remainder (DX) = 0, it divides evenly so CX is a divisor
    JNZ  CONT_LOOP      ; if not, continue loop to next
    ADD  BX, CX         ; add number to sum
    JC   END_ABUND      ; if CF=1, BX has unsigned overflow it is abundant (when CX < 65536)
CONT_LOOP:
    LOOP DIV_LOOP
    CMP  AX, BX         ; BX<=AX -> CF=0 (non-abund), BX>AX -> CF=1 (abund)
END_ABUND:
        ENDM

Przykładowy program testowy, testujący N = [12..1000]:

    MOV  AX, 12         ; start tests at 12
LOOP_START:
    ABUND AX            ; call ABUND MACRO for N (in AX)
    JNC  LOOP_END       ; if not abundant, display nothing
    CALL OUTDECCSV      ; display AX as decimal (generic decimal output routine)
LOOP_END:
    INC  AX             ; increment loop counter
    CMP  AX, 1000       ; if less than 1000...
    JBE  LOOP_START     ; continue loop
    RET                 ; return to DOS

Wyjście [2..1000]

12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 192, 196, 198, 200, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 288, 294, 300, 304, 306, 308, 312, 318, 320, 324, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364, 366, 368, 372, 378, 380, 384, 390, 392, 396, 400, 402, 408, 414, 416, 420, 426, 432, 438, 440, 444, 448, 450, 456, 460, 462, 464, 468, 474, 476, 480, 486, 490, 492, 498, 500, 504, 510, 516, 520, 522, 528, 532, 534, 540, 544, 546, 550, 552, 558, 560, 564, 570, 572, 576, 580, 582, 588, 594, 600, 606, 608, 612, 616, 618, 620, 624, 630, 636, 640, 642, 644, 648, 650, 654, 660, 666, 672, 678, 680, 684, 690, 696, 700, 702, 704, 708, 714, 720, 726, 728, 732, 736, 738, 740, 744, 748, 750, 756, 760, 762, 768, 770, 774, 780, 784, 786, 792, 798, 800, 804, 810, 812, 816, 820, 822, 828, 832, 834, 836, 840, 846, 852, 858, 860, 864, 868, 870, 876, 880, 882, 888, 894, 896, 900, 906, 910, 912, 918, 920, 924, 928, 930, 936, 940, 942, 945, 948, 952, 954, 960, 966, 968, 972, 978, 980, 984, 990, 992, 996, 1000

Wyjście [12500..12700]

12500, 12504, 12510, 12512, 12516, 12520, 12522, 12528, 12530, 12534, 12540, 12544, 12546, 12552, 12558, 12560, 12564, 12570, 12572, 12576, 12580, 12582, 12584, 12588, 12594, 12600, 12606, 12612, 12618, 12620, 12624, 12628, 12630, 12636, 12640, 12642, 12648, 12650, 12654, 12656, 12660, 12666, 12670, 12672, 12678, 12680, 12684, 12688, 12690, 12696, 12700

Wyjście [25100..25300]

25100, 25104, 25110, 25116, 25120, 25122, 25128, 25130, 25134, 25140, 25144, 25146, 25152, 25158, 25160, 25164, 25168, 25170, 25172, 25176, 25180, 25182, 25188, 25194, 25200, 25206, 25212, 25216, 25218, 25220, 25224, 25228, 25230, 25232, 25236, 25240, 25242, 25245, 25248, 25254, 25256, 25260, 25266, 25270, 25272, 25278, 25280, 25284, 25290, 25296, 25300

Aktualizacje:

• Naprawiono 16-bitowe przepełnienie (+5 bajtów). Dzięki @deadcode za sugestie!
• Uproszczona logika powrotu (-3 bajty). Dziękujemy za pomoc w @deadcode jeszcze raz.
• Użyj TEST zamiast CMP (-1 bajt). Dzięki za @ l4m2!

Właściwie 5 bajtów

;÷Σ½>

Wypróbuj online!

;     # Duplicate input
 ÷    # Get divisors
  Σ   # Sum
   ½  # Divide by 2 (float)
    > # Test is greater than input

05AB1E , 4 bajty

ѨO‹

Wypróbuj online!

Jak to działa

Ñ        #list of divisors
 ¨       #remove last element (i.e the input from the list of factors)
  O      #sum the list 
   ‹     #is this sum less than the input? 

Przepraszam za stare pytanie, właśnie przeglądałem stare posty i zauważyłem, że moje rozwiązanie jest krótsze niż następne najlepsze rozwiązanie 05AB1E.

PARI / GP , 15 bajtów

n->sigma(n)>2*n

Wariant n->sigma(n,-1)>2jest niestety dłuższy.

Java 8, 53 bajty (znacznie więcej, jeśli podasz kod ceremonialny)

return IntStream.range(1,n).filter(e->n%e<1).sum()>n;

Wypróbuj online

Objaśnienie:

IntStream.range(1,n) \\ numbers from 1 to n-1
filter(e->n%e<1)     \\ filter in numbers that perfectly divide the number n
sum()>n              \\ sum and compare to original number

PowerShell, 51 49 bajtów

param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i

Chciałbym móc usunąć kilka nawiasów.

-2 dzięki AdmBorkBork, zamiast nie zliczać danych wejściowych w początkowym zakresie, po prostu bierzemy to pod uwagę w końcowej kontroli.

Zapętl się przez zakres 1..do $input, minus 1, znajdź gdzie ( ?) odwrotnym modułem wejściowym według bieżącej liczby jest $true(aka tylko 0) - wtedy -joinwszystkie te liczby razem +i iexwynikowy ciąg do obliczenia, a następnie sprawdź, czy suma tych części jest większa niż wkład.

PS C:\++> 1..100 | ? {.\abundance.ps1 $_}
12
18
20
24
30
36
40
42
48
54
56
60
66
70
72
78
80
84
88
90
96
100

MATL, 6 bajtów

Z\sGE>

Wyjścia 1 dla obfitych liczb, w przeciwnym razie 0.

Jak to działa

Z\      % list the divisors of the implicit input
s       % add them
G       % push the input again
E       % double it
>       % compare
        % implicitly display result

QBIC , 22 bajty

:[a/2|~a%b|\p=p+b}?p>a

Jest to dostosowanie do testu pierwotności QBIC . Zamiast zliczać dzielniki i sprawdzać, czy jest mniejsza niż trzy, sumuje to właściwe dzielniki. Działa to tylko w połowie 1 to n, gdzie test pierwotności przebiega 1 to ncałkowicie.

Wyjaśnienie:

:       Get the input number, 'a'
[a/2|   FOR(b=1, b<=(a/2), b++)
~a%b    IF a MOD b != 0  --> QBasic registers a clean division  (0) as false. 
        The IF-branch ('|') therefor is empty, the code is in the ELSE branch ('\')
|\p=p+b THEN add b to runnning total p
}       Close all language constructs: IF/END IF, FOR/NEXT
?p>a    Print '-1' for abundant numbers, 0 otherwise.

JavaScript (ES6), 33 bajty

let g =
x=>(f=n=>--n&&n*!(x%n)+f(n))(x)>x

<input type=number min=1 value=1 step=1 oninput="O.innerHTML=g(+value)"><br>
<pre id=O>false</pre>

Japt , 9 7 6 bajtów

<Uâ1 x

Zaoszczędzono 2 bajty dzięki produktom ETH. Zaoszczędzono 1 bajt dzięki obarakon.

Wypróbuj online!

Cubix , 38 bajtów

/..?%?(O;0I:^.<.>;rrw+s;rUO?-<...O0L.@

Wypróbuj tutaj

      / . .
      ? % ?
      ( O ;
0 I : ^ . < . > ; r r w
+ s ; r U O ? - < . . .
O 0 L . @ . . . . . . .
      . . .
      . . .
      . . .

0I:- ustawia stos na 0, n, n (s, n, d)
^- początek pętli )?- zmniejsza d i testuje na 0. 0 kończy pętlę
%?- mod na n i testuje. 0 przyczyn, ;rrw+s;rUktóre obraca s do góry i dodaje d, obraca s do dołu i dołącza ponownie do pętli
;<- Oczyść i ponownie dołącz do pętli.
Przy wyjściu z pętli
;<- Usuń d ze stosu i przekieruj
-?- Usuń n ze s i przetestuj, 0 LOU@skręca w lewo, wyjścia i wyjścia, negatywy 0O@wypychają zero, wyjścia i wyjścia. pozytywy ;Ousuwają różnicę i wyniki n. Ścieżka prowadzi następnie do skrętu w lewo, który przekierowuje do @wyjścia

Pure Bash, 37 bajtów

for((;k++<$1;s+=$1%k?0:k)){((s>$1));}

Dzięki @Dennis za zmianę układu kodu - oszczędność 6 bajtów i wyeliminowanie przypadkowych danych wyjściowych dla stderr.

Dane wejściowe są przekazywane jako argument.

Dane wyjściowe są zwracane w kodzie wyjścia: 0 dla dużej, 1 dla małej.

Dane wyjściowe do stderr należy zignorować.

Przebiegi testowe:

for n in {1..100}; do if ./abundant "$n"; then echo $n; fi; done 2>/dev/null
12
18
20
24
30
36
40
42
48
54
56
60
66
70
72
78
80
84
88
90
96
100

RProgN , 8 bajtów

~_]k+2/<

Wyjaśniono

~_]k+2/<
~           # Zero Space Segment
 _          # Convert the input to an integer
  ]         # Duplicate the input on the stack
   k+       # Get the sum of the divisors of the top of the stack
     2/     # Divded by 2
       <    # Is the Input less than the sum of its divisors/2.

Wypróbuj online!

Partia, 84 bajtów

@set/ak=%1*2
@for /l %%j in (1,1,%1)do @set/ak-=%%j*!(%1%%%%j)
@cmd/cset/a"%k%>>31

Wyjścia -1dla dużej liczby, w 0przeciwnym razie. Działa poprzez odjęcie wszystkich czynników, 2na następnie przesunięcie wyniku o 31 miejsc w celu wyodrębnienia bitu znaku. Alternatywne sformułowanie, również 84 bajty:

@set k=%1
@for /l %%j in (1,1,%1)do @set/ak-=%%j*!(%1%%%%j)
@if %k% lss -%1 echo 1

Wyjścia 1dla obfitej liczby. Działa odejmując wszystkie czynniki, na następnie porównując wynik z -n. ( set/ajest to jedyny sposób wykonywania arytmetyki przez Batch, więc nie mogę łatwo dopasować pętli).

Perl 6, 72 24 bajtów

{$_ <sum grep $_%%*,^$_}

• Argument programowy: a.
• Wygeneruj listę z 1..a.
• Weź wszystkie liczby, które są dzielnikami a.
• Zsumuj je.
• Sprawdź, czy suma ta jest większa niż a.

Dzięki @ b2gills.

J, 19 bajtów

Dzięki Conorowi O'Brienowi za zmniejszenie go do 19 bajtów!

<[:+/i.#~i.e.]%2+i.

Poprzedni: (34 bajty)

f=:3 :'(+/((i.y)e.y%2+i.y)#i.y)>y'

Zwraca 1, jeśli jest obfity, a 0, jeśli nie.

Wynik:

   f 3
0
   f 12
1
   f 11
0
   f 20
1

Pyth, 11 bajtów

>sPf!%QTS

Stary:

L!%Qb>sPy#S

Nie mogę użyć !%jako pfn #, ponieważ są to dwie funkcje. Zasmuca mnie :(.

L!%Qb>sPy#SQ    Program's argument: Q
L!%Qb           Define a lambda y, that takes b as an argument
 !%Qb           Return true if Q is divisible by b
          S     Make a range 1..Q
        y#      Filter that range with the lambda (y)
       P        Remove the last element (Q itself)
      s         Sum them
     >     Q    Check if that sum is greater than the program's argument

k , 19 16 15 bajtów

{x<+/&~(!x)!'x}

Zwraca 1za prawda i 0za fałsz.

Wypróbuj online!

{             } /function(x)
       (!x)     /{0, 1, ..., x-1}
            '   /for each n in {0, 1, ..., x-1}:
           ! x  /    do (x mod n)
      ~         /for each, turn 0 -> 1, * -> 0 (map not)
     &          /get indices of 1's
   +/           /sum (fold add)
 x<             /check if x < the sum

PowerShell , 43 bajty

param($n)1..$n|%{$s+=$_*!($n%$_)}
$s-gt2*$n

Wypróbuj online!

Common Lisp, 63 bajty

(lambda(n)(>(loop for i from 1 below n if(=(mod n i)0)sum i)n))

Wypróbuj online!

F #, 51 bajtów

let f n=Seq.filter(fun x->n%x=0){1..n-1}|>Seq.sum>n

Wypróbuj online!

Filtruje wszystkie liczby, które nie dzielą się równomiernie n, a następnie sumuje je i porównuje z nimi n.