Mnóstwo liczb całkowitych!

40

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 , standardowe luki są odrzucane i spróbuj napisać możliwie najkrótszy kod w dowolnym języku, który wybierzesz!

DJMcMayhem
źródło
11
„pierwsza nieparzysta liczna to 945 = 3 ^ 3 * 5 * 7, 232. liczna liczba!”
mbomb007
Asymptotyczna gęstość obfitych liczb mieści się gdzieś w przedziale [0.24761748, 0.24764422]. Obliczone przy użyciu kodu źródłowego zawartego w tym dokumencie .
Deadcode
1
Próbuję to zrobić w Geometry Dash. To koszmar
MilkyWay90

Odpowiedzi:

41

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 0 a 0 p 1 a 1 ... p k-1 a k-1 . Chcemy obsłużyć sumę czynników n, która wynosi (1 + p 0 + p 0 2 + ... + p 0 a 0 ) (1 + p 1 + p 1 2 + ... + p 1 a 1 ) ... (1 + p k-1 + p k-1 2 + ... + 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$)
  )
)+$
Deadcode
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
DJMcMayhem
1
-98 bajtów
Grimmy
27

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

Dennis
źródło
4
~k<0jest fantazyjne, ale myślę, że -1<krobi to samo;)
Martin Ender
12

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
Fatalizować
źródło
10

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.
Dennis
źródło
10

Python , 44 bajty

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

Wypróbuj online!

Jonathan Allan
źródło
Szkoda, że ​​nie możesz tego zrobić range(n). Ten nieznośny moduł zerowy
DJMcMayhem
10

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.
ngenisis
źródło
1
Dziwię się, że Mathematica nie ma wbudowanego do tego ..
MrPaulch
1
@MrPaulch Biorąc pod uwagę długość programu, wbudowane oprogramowanie może równie dobrze mieć dłuższą nazwę>.>
Conor O'Brien
1
@ ConorO'Brien Gdyby istniał, prawdopodobnie byłby AbundantNumberQ, więc zaoszczędziłby kilka bajtów :)
ngenisis
7

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

Martin Ender
źródło
6

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.

Martin Ender
źródło
1
Zawsze mnie zadziwiało, jak możesz robić matematykę w siatkówce. Chciałbym zobaczyć wyjaśnienie! :)
DJMcMayhem
1
@DJMcMayhem Przepraszamy, zapomniałem dodać to wcześniej. Gotowy.
Martin Ender
6

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!
640 KB
źródło
1
Sugerowałbym zastąpienie JLEprzez, JBEaby podwoić zakres liczb, które można przetestować, zanim zaczną się przepełnienia, powodując fałszywe negatywy. Następnie zamiast zaczynać niepowodzenie przy 12600 (suma podwielokrotności 35760), zacznie się nie udawać przy 25200 (podwielokrotna suma 74744). Jeszcze lepiej byłoby również wykryć flagę przenoszenia i traktować ją jako dużą liczbę bez konieczności obliczania rzeczywistej sumy> 16 bitów.
Deadcode
1
Dobry chwyt @Deadcode. Zaktualizowałem kod skoku poniżej zamiast skoku mniej. Rozumiem, co masz na myśli, robiąc JC po ADD BX, CX wyłapie tam nieoznaczony przepełnienie i poprawi go do N = 65535. Trochę komplikuje testowanie flagi i zwracanie stanu, ponieważ wcześniej CF sugerował fałsz. Zaktualizowano również z poprawką.
640 KB
1
Możesz zapisać 3 bajty, odwracając specyfikację wartości zwracanej, przy ustawieniu CF, jeśli jest ono obfite, i wyczyść, jeśli nie. Ale zalecam najpierw dokonanie edycji, aby najpierw poprawić dokumentację wyjściową, więc ładnie wygląda w historii edycji.
Deadcode
1
Ponadto, aby uprościć sprawę, specyfikacja powinna być taka, że ​​zwracana wartość znajduje się w chorągiewce przenoszenia, i żadna z tych kłopotów z innymi flagami. Dzwoniący powinien wykorzystać JClub JNCpodjąć decyzję, czy numer jest obfity, czy nie.
Deadcode
1
Dziękuję bardzo za całą waszą pomoc i komentarze. Zaktualizowałem dokumentację wbudowaną i usunąłem pojęcie nieprzyznane. Szczerze mówiąc, nigdy nie zastanawiałem się nad tym, ale rozumiem, o co ci chodzi, ponieważ nie jest inaczej, z wyjątkiem wewnętrznych komentarzy. Zgadzam się także, aby flagi powrotu były wyraźniejsze. Za chwilę nad tym popracuję. Dzięki za uwagę i pomoc!
640 KB
5

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.

kosmiczne śmieci
źródło
4
Sorry to post in old questionNie martw się o to! Zawsze cieszę się, widząc odpowiedzi na moje stare wyzwania, i tutaj jest to zachęcane . :)
DJMcMayhem
4

PARI / GP , 15 bajtów

n->sigma(n)>2*n

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

Charles
źródło
4

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
Gautam D.
źródło
4
Świetna odpowiedź, ale w Javie 8 musisz uwzględnić tę funkcję w swojej liczbie bajtów. Z drugiej strony możesz upuścić, returnjeśli się nie mylę, więc będzie jeszcze krótsza: n->IntStream.range(1,n).filter(e->n%e<1).sum()>n(nie 100%, jeśli jest to poprawne, prawie nigdy nie programuję w Javie 8). Witamy w PPCG!
Kevin Cruijssen
1
Prawidłowe zliczanie za pomocą standardowego liczenia będzie dotyczyło n->java.util.stream.IntStream.range(1,n).filter(e->n%e<1).sum()>n65 bajtów (zakładając, że dostałem paczkę prosto z głowy)
97 CAD
4

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
colsw
źródło
Możesz zapisać dwa bajty, licząc najwyższą wartość i sprawdzając, czy jest ona większa niż 2x wejście -param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i
AdmBorkBork
3

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
B. Mehta
źródło
3

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.
Steenbergh
źródło
3

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>

ETHprodukcje
źródło
Byłem pewien, że odpowiedź rekurencyjna byłaby najlepsza, ale nie sądziłem, że będzie tak dobra.
Neil
3

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!

Tomek
źródło
9 znaków, 10 bajtów.
Metoniem
@Metoniem Jestem pewien, że âma 1 bajt, przynajmniej w Unicode (0xE2).
Tom
1
@Metoniem Japt używa kodowania ISO-8859-1 , w którym âjest to jeden bajt.
ETHprodukcje
Jeśli âpodany zostanie prawdziwy argument, usunie on rzeczywistą liczbę z pozostałej listy, dzięki czemu można zrobić, â1 x >Uaby zapisać kilka bajtów :-)
ETHprodukcje
@TomDevs Nice! Możesz zrobić, <Uâ1 xaby zapisać bajt. Japt dodaje Uprzed programem.
Oliver
3

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

MickyT
źródło
3

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
Mitchell Spector
źródło
Możesz zapisać 6 bajtów, unikając zbłąkanego wyjścia do STDERR. tio.run/nexus/bash#S04sUbBTSEwqzUtJzCtRsLFRUHf1d1P/…
Dennis
2

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!

ATaco
źródło
2

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

Neil
źródło
1
„(% 1 %%%% j)” o, partia :)
Bryan Boettcher
2

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.

Ven
źródło
Każde wystąpienie $^apo pierwszym można skrócić do sprawiedliwego $a. ale jest jeszcze krótszy, jeśli napiszesz go jako {$_ <sum grep $_%%*,^$_}Patrząc również na wcześniejszą wersję, [+](LIST)działa (bez spacji)
Brad Gilbert b2gills
@ BradGilbertb2gills Thanks! :)
Ven
2

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
Bloki
źródło
Witamy w PPCG! Zezwalamy na anonimowe funkcje, dzięki czemu możesz usunąć wiodące f=:jako część liczby bajtów. Ponadto możesz przejść do 19, przechodząc na cichy czasownik:<[:+/i.#~i.e.]%2+i.
Conor O'Brien
Dzięki za radę! Czy mógłbyś jednak wyjaśnić czasownik cap ([:) i czasownik przełączający (~). Naprawdę nie rozumiem, co powinni robić w tym milczącym czasowniku.
Blokuje
~ przełącza, więc to jest # i. ale jaki jest cel [:?
Blokuje
więc wiesz o widelcach, prawda? (f g h) y' is the same as (fy) g (hy) . When f` to czapka, ([: g h) yjest mniej więcej taka sama jak g h y. W przypadku ~przełącza argumenty lewy i prawy. Ważne jest, aby wiedzieć, że ~nie jest to czasownik, ale w rzeczywistości jest przysłówkiem. Zmienia czasownik. Na przykład moglibyśmy mieć coś takiego 2 %~ 8. Tutaj ~modyfikuje się, %aby zmienić argumenty, więc wyrażenie jest równoważne z 8 % 2.
Conor O'Brien
W łańcuchu rozwidlenia #~jest oceniany po wykonaniu czasowników po jego prawej stronie, więc jego lewy argument staje się wynikiem po prawej
Conor O'Brien
2

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
Ven
źródło
Nieokreślenie funkcji wydaje się krótsze:>sPf!%QTS
FryAmTheEggman
2

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

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.

Ciaran_McCarthy
źródło