Kelimpahan bilangan bulat!

40

Sebuah jumlah yang melimpah adalah nomor di mana jumlah dari pembagi tepat adalah lebih besar dari jumlah aslinya. Sebagai contoh, pembagi yang tepat dari 12 adalah:

1, 2, 3, 4, 6

Dan menjumlahkan hasil ini dalam 16. Karena 16 lebih besar dari 12, 12 berlimpah. Perhatikan bahwa ini tidak termasuk "Angka sempurna", mis. Angka yang sama dengan jumlah pembagi yang tepat, seperti 6 dan 28.

Tugas Anda hari ini adalah menulis program atau fungsi yang menentukan apakah jumlahnya banyak atau tidak. Program Anda harus mengambil bilangan bulat tunggal sebagai input, dan menampilkan nilai kebenaran / kepalsuan tergantung pada apakah jumlahnya berlimpah atau tidak. Anda dapat mengasumsikan bahwa input akan selalu valid dan lebih besar dari 0, jadi untuk input yang buruk, perilaku tidak terdefinisi baik-baik saja.

Anda dapat mengambil input dan output Anda dalam format yang masuk akal, misalnya STDIN / STDOUT, file, atau argumen / nilai pengembalian semua akan diterima.

Untuk referensi, berikut adalah angka melimpah hingga 100:

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

Dan banyak lagi dapat ditemukan di A005101

Karena ini adalah , celah standar ditolak, dan cobalah menulis kode sesingkat mungkin dalam bahasa apa pun yang Anda pilih!

DJMcMayhem
sumber
11
"Kelimpahan ganjil pertama adalah 945 = 3 ^ 3 * 5 * 7, jumlah kelimpahan 232!"
mbomb007
Densitas asimptotik dari jumlah yang melimpah ada di suatu tempat dalam interval [0,24761748, 0,24764422]. Dihitung menggunakan kode sumber yang termasuk dalam makalah ini .
Deadcode
1
Saya mencoba melakukan ini di Geometry Dash. Ini mimpi buruk
MilkyWay90

Jawaban:

41

ECMAScript Regex, 1085 855 597 536 511 508 504 byte

Mencocokkan jumlah yang melimpah di ECMAScript regex adalah binatang yang sama sekali berbeda dari melakukannya dalam hampir semua rasa regex lainnya. Kurangnya referensi atau rekursi maju / bersarang berarti bahwa tidak mungkin untuk secara langsung menghitung atau menjaga total apa pun yang berjalan. Kurangnya tampilan membuatnya sering menjadi tantangan bahkan untuk memiliki cukup ruang untuk bekerja.

Banyak masalah harus didekati dari perspektif yang sama sekali berbeda, dan Anda akan bertanya-tanya apakah mereka dapat dipecahkan sama sekali. Ini memaksa Anda untuk menggunakan jaring yang jauh lebih luas dalam menemukan properti matematika mana dari angka yang Anda kerjakan yang mungkin dapat digunakan untuk membuat masalah tertentu dapat dipecahkan.

Kembali pada bulan Maret-April 2014 saya membangun solusi untuk masalah ini di ECMAScript regex. Pada awalnya saya punya alasan untuk mencurigai masalah itu benar-benar mustahil, tetapi kemudian teukon ahli matematika membuat sketsa ide yang membuat kasus yang menggembirakan untuk membuatnya terlihat dapat dipecahkan - tetapi ia menjelaskan bahwa ia tidak berniat membangun regex (dia telah berkompetisi / bekerja sama dengan saya dalam membangun / golf regex sebelumnya, tetapi mencapai batasnya pada titik ini dan puas untuk membatasi kontribusinya lebih lanjut untuk berteori).

Seperti dengan regex saya diposting beberapa hari yang lalu, saya akan memberikan peringatan: Saya sangat merekomendasikan belajar bagaimana menyelesaikan masalah matematika unary di ECMAScript regex. Ini merupakan perjalanan yang menarik bagi saya, dan saya tidak ingin merusaknya bagi siapa pun yang mungkin ingin mencobanya sendiri, terutama mereka yang tertarik pada teori bilangan. Lihat posting itu untuk daftar masalah yang direkomendasikan untuk ditandai dengan spoiler bertanda satu per satu.

Jadi jangan membaca lebih jauh jika Anda tidak ingin sihir regex unary yang dalam rusak bagi Anda . Posting saya sebelumnya hanya sedikit. Jika Anda ingin mencoba mencari tahu sendiri keajaiban ini, saya sangat menyarankan memulai dengan menyelesaikan beberapa masalah dalam ECMAScript regex sebagaimana diuraikan dalam pos yang ditautkan di atas.

Sebelum memposting regex ECMAScript saya, saya pikir akan menarik untuk menganalisis .NET murni solusi regex Martin Ender , ^(?!(1(?<=(?=(?(\3+$)((?>\2?)\3)))^(1+)))*1$). Ternyata sangat mudah untuk memahami regex itu, dan elegan dalam kesederhanaannya. Untuk menunjukkan perbedaan antara solusi kami, berikut adalah versi regex-nya yang dikomentari dan dicetak dengan bagus (tetapi tidak dimodifikasi):

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

Coba .NET regex online

Sekarang, kembali ke regex ECMAScript saya. Pertama, ini dalam format mentah, spasi-dan-komentar-bebas:

^(?=(((?=(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$)))+$

(ubah \14ke \14?untuk kompatibilitas dengan PCRE, .NET, dan hampir semua citarasa regex lainnya yang bukan ECMAScript)

Cobalah online!
Cobalah online! (lebih cepat, versi 537 byte regex)

Dan sekarang ringkasan singkat dari kisah di baliknya.

Pada awalnya itu sangat tidak jelas, setidaknya bagi saya, bahwa bahkan mungkin untuk mencocokkan bilangan prima dalam kasus umum. Dan setelah menyelesaikan itu, hal yang sama berlaku untuk kekuatan 2. Dan kemudian kekuatan angka gabungan. Dan kotak yang sempurna. Dan bahkan setelah menyelesaikannya, melakukan perkalian secara umum tampaknya tidak mungkin pada awalnya.

Dalam loop skrip ECMAS, Anda hanya dapat melacak satu nomor yang berubah; angka itu tidak dapat melebihi input, dan harus berkurang di setiap langkah. Regex kerja pertama saya untuk mencocokkan pernyataan perkalian yang benar A * B = C adalah 913 byte, dan bekerja dengan memfaktorkan A, B, dan C ke dalam kekuatan utama mereka - untuk setiap faktor utama, berulang kali membagi pasangan faktor daya utama A dan C dengan basis utama mereka sampai yang sesuai dengan A mencapai 1; yang berkorespondensi dengan C kemudian dibandingkan dengan faktor kekuatan utama B. Kedua kekuatan dari prime yang sama ini "multiplexed" menjadi satu angka dengan menambahkannya bersama-sama; ini akan selalu dipisahkan secara jelas pada setiap iterasi loop berikutnya, untuk alasan yang sama bahwa sistem angka posisi bekerja.

Kami mendapat perkalian hingga 50 byte menggunakan algoritma yang sama sekali berbeda (yang teukon dan saya dapat tiba secara mandiri, meskipun hanya butuh beberapa jam dan ia langsung ke sana, sedangkan saya butuh beberapa hari bahkan setelah itu menarik perhatian saya bahwa ada metode singkat): untuk A≥B, A * B = C jika ada hanya jika C adalah angka terkecil yang memenuhi C≡0 mod A dan C≡B mod A-1. (Mudahnya, perkecualian A = 1 tidak memerlukan penanganan khusus di regex, di mana 0% 0 = 0 menghasilkan kecocokan.) Saya hanya tidak bisa melupakan seberapa rapi itu bahwa cara elegan untuk melakukan penggandaan ada dalam suatu rasa regex minimal. (Dan persyaratan A≥B dapat diganti dengan persyaratan bahwa A dan B adalah kekuatan utama dari kekuatan yang sama. Untuk kasus A≥B, ini dapat dibuktikan menggunakan teorema sisa Cina.)

Jika ternyata tidak ada algoritma yang lebih sederhana untuk perkalian, jumlah regex yang melimpah mungkin akan berada di urutan sepuluh ribu byte atau lebih (bahkan dengan mempertimbangkan bahwa saya memasukkan algoritma 913 byte turun ke 651 byte). Ia melakukan banyak perkalian dan pembagian, dan regex ECMAScript tidak memiliki subrutin.

Saya mulai mengerjakan masalah angka melimpah secara tangensial pada tanggal 23 Maret 2014, dengan membangun solusi untuk apa yang pada saat itu tampaknya menjadi sub-masalah ini: Mengidentifikasi faktor utama dari multiplisitas tertinggi, sehingga dapat dibagi dari N di awal, meninggalkan ruang untuk melakukan beberapa perhitungan yang diperlukan. Pada saat itu, rute ini tampaknya merupakan rute yang menjanjikan untuk ditempuh. (Solusi awal saya akhirnya menjadi cukup besar pada 326 byte, kemudian golf turun menjadi 185 byte.) Tetapi metode teukon sketsa akan menjadi sangat rumit, sehingga ternyata, saya mengambil rute yang agak berbeda. Itu terbukti cukup untuk membagi faktor daya prima terbesar N yang sesuai dengan faktor prima terbesar pada N; melakukan ini untuk prime multiplicity tertinggi akan menambah kompleksitas dan panjang yang tidak perlu ke regex.

Yang tersisa adalah memperlakukan jumlah pembagi sebagai produk dari jumlah bukan jumlah yang lurus. Seperti yang dijelaskan oleh teukon pada 14 Maret 2014:

Kami diberi nomor n = p 0 a 0 p 1 a 1 ... p k-1 a k-1 . Kami ingin menangani jumlah faktor n, yaitu (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 ).

Saya terpesona melihat hal ini. Saya tidak pernah berpikir untuk menghitung jumlah alikuot dengan cara itu, dan formula inilah yang membuat solvabilitas pencocokan angka melimpah di ECMAScript regex terlihat masuk akal.

Pada akhirnya, alih-alih menguji untuk hasil penjumlahan atau perkalian yang melebihi N, atau menguji bahwa hasil seperti itu yang dipisah-pisahkan oleh M melebihi N / M, saya melakukan pengujian jika hasil pembagian kurang dari 1. Saya tiba di versi kerja pertama pada 7 April 2014.

Sejarah lengkap optimasi golf saya di regex ini ada di github. Pada titik tertentu satu optimasi akhirnya membuat regex jauh lebih lambat, jadi sejak saat itu saya mempertahankan dua versi. Mereka:

regex untuk pencocokan angka berlimpah.txt
regex untuk pencocokan angka berlimpah - shortest.txt

Regex ini sepenuhnya kompatibel dengan ECMAScript dan PCRE, tetapi optimasi baru-baru ini melibatkan penggunaan grup tangkap yang berpotensi tidak berpartisipasi \14, jadi dengan menjatuhkan kompatibilitas PCRE dan mengubahnya \14?menjadi \14keduanya dapat dikurangi dengan 1 byte.

Ini adalah versi terkecil, dengan optimasi yang diterapkan (membuatnya hanya ECMAScript), diformat ulang agar sesuai dengan blok kode StackExchange dengan (kebanyakan) tidak diperlukan pengguliran horizontal:

# 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$)
  )
)+$
Kode mati
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
DJMcMayhem
1
-98 byte
Grimmy
27

Python 2 , 41 40 byte

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

Output adalah melalui kode keluar , jadi 0 benar dan 1 palsu.

Cobalah online!

Bagaimana itu bekerja

Setelah mengatur semua n , k , dan j ke input dari STDIN, kita masukkan loop while . Kata loop akan pecah segera setelah -k - 1 = ~ k ≥ 0 , yaitu, k ≤ -1 / k <0 .

Dalam setiap iterasi, pertama-tama kita mengurangi j untuk mempertimbangkan hanya pembagi n yang tepat . Jika j adalah pembagi dari n , n%jhasilkan 0 dan j >> n% j * n = j / 2 0 = j akan dikurangi dari k . Namun, jika j tidak tidak membagi n , n%jpositif, jadi n%j*nsetidaknya n> log 2 j dan j >> n% j * n = j / 2 n% j * n = 0 dikurangi dari k .

Untuk angka yang melimpah, k akan mencapai nilai negatif sebelum atau ketika j menjadi 1 , karena jumlah pembagi n yang tepat benar-benar lebih besar dari n . Dalam hal ini, kami keluar dari loop sementara dan program selesai secara normal.

Namun, jika n adalah tidak berlimpah, j akhirnya mencapai 0 . Dalam hal ini, n%jmelempar ZeroDivisionError dan program keluar dengan kesalahan.

Dennis
sumber
4
~k<0mewah, tapi saya pikir -1<kjuga melakukan trik;)
Martin Ender
12

Brachylog , 5 byte

fk+>?

Cobalah online!

Penjelasan

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

Jelly , 3 byte

Æṣ>

Cobalah online!

Bagaimana itu bekerja

Æṣ>  Main link. Argument: n

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

Python , 44 byte

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

Cobalah online!

Jonathan Allan
sumber
Sayang sekali Anda tidak bisa melakukannya range(n). Modulus sial itu nol
DJMcMayhem
10

Mathematica, 17 byte

Tr@Divisors@#>2#&

Penjelasan

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
sumber
1
Saya terkejut Mathematica tidak memiliki
bawaan
1
@MrPaulch Dengan mempertimbangkan panjangnya program, builtin mungkin lebih panjang dalam nama>.>
Conor O'Brien
1
@ ConorO'Brien Jika ada, itu mungkin akan AbundantNumberQ, jadi itu akan menghemat beberapa byte :)
ngenisis
7

Retina , 50 45 byte

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

Input dalam unary , output 1untuk angka melimpah, 0jika tidak

Tidak ada yang khusus-Retina tentang solusi ini. Di atas adalah .NET regex murni yang hanya cocok dengan angka berlimpah.

Cobalah online! (Test suite yang menyaring input desimal dengan regex di atas.)

Martin Ender
sumber
6

Retina , 34 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.

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

^(1+)¶1\1

Input dalam unary , output 1untuk angka melimpah, 0jika tidak

Cobalah online!

Penjelasan

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

Kami mulai dengan mendapatkan semua pembagi input. Untuk melakukan ini, kami mengembalikan ( !) semua kecocokan tumpang tindih ( &) ( M) dari regex (1+)$(?<=^\1+). Regex cocok dengan beberapa akhiran input, asalkan seluruh input adalah kelipatan dari akhiran itu (yang kami pastikan dengan mencoba mencapai awal untuk string menggunakan hanya salinan akhiran itu). Karena cara mesin regex mencari kecocokan, ini akan menghasilkan daftar pembagi dalam urutan menurun (dipisahkan oleh baris baris).

1>`¶

Panggung itu sendiri hanya cocok dengan umpan baris ( ) dan menghapusnya. Namun, 1>batasnya adalah, yang melewatkan pertandingan pertama. Jadi ini secara efektif menambahkan semua pembagi kecuali input itu sendiri. Kita berakhir dengan input pada baris pertama dan jumlah semua pembagi yang tepat pada baris kedua.

^(1+)¶1\1

Akhirnya, kami mencoba untuk mencocokkan setidaknya satu lagi 1di baris kedua daripada yang ada di baris pertama. Jika itu masalahnya, jumlah pembagi yang tepat melebihi input. Retina menghitung jumlah kecocokan dari regex ini, yang akan 1berjumlah banyak dan 0sebaliknya.

Martin Ender
sumber
1
Itu selalu membuatku heran bagaimana kamu bisa melakukan matematika di retina. Saya ingin sekali melihat penjelasan! :)
DJMcMayhem
1
@DJMcMayhem Maaf lupa menambahkan itu sebelumnya. Selesai
Martin Ender
6

Majelis 8086, 23 28 25 24 byte

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

Belum dirakit:

; 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

Contoh program pengujian, pengujian 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

Output [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

Output [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

Output [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

Pembaruan:

  • Diperbaiki untuk overflow 16-bit (+5 byte). Terima kasih @ kode kode untuk sarannya!
  • Logika pengembalian yang disederhanakan (-3 byte). Terima kasih untuk membantu dari @deadcode sekali lagi.
  • Gunakan TEST, bukan CMP (-1 byte). Thx ke @ l4m2!
640KB
sumber
1
Saya akan menyarankan untuk mengganti JLEdengan JBEmenggandakan rentang angka yang dapat diuji ini sebelum overflows mulai menyebabkannya memberikan negatif palsu. Kemudian alih-alih mulai gagal pada 12600 (aliquot jumlah 35760), itu akan mulai gagal pada 25200 (jumlah aliquot 74744). Yang lebih baik adalah mendeteksi flag carry dan memperlakukannya sebagai angka yang melimpah tanpa perlu menghitung jumlah sebenarnya> 16 bit.
Deadcode
1
Good catch @Deadcode. Saya telah memperbarui kode untuk lompat di bawah dan bukannya lompat kurang Saya mengerti maksud Anda, melakukan JC setelah ADD BX, CX akan menangkap limpahan unsigned di sana dan membuatnya benar hingga N = 65535. Rumit pengujian bendera dan status pengembalian sedikit, karena CF sebelumnya tersirat salah. Diperbarui dengan perbaikan juga.
640KB
1
Anda dapat menyimpan 3 byte dengan membalikkan spesifikasi nilai pengembalian Anda, dengan CF yang ditetapkan jika berlimpah dan jelas jika tidak. Tetapi saya akan merekomendasikan untuk melakukan edit untuk memperbaiki dokumentasi keluaran terlebih dahulu, sehingga terlihat bagus dalam riwayat edit.
Deadcode
1
Juga, untuk menjaga hal-hal sederhana, spesifikasinya adalah bahwa nilai pengembalian ada di carry flag, dan tidak ada yang repot dengan flag lainnya. Penelepon harus menggunakan JCatau JNCuntuk bertindak apakah jumlahnya banyak atau tidak.
Deadcode
1
Terima kasih banyak atas semua bantuan dan komentar Anda. Saya telah memperbarui dokumentasi sebaris dan menghapus istilah yang tidak diubah. Jujur tidak pernah banyak memikirkannya tapi saya mengerti maksud Anda, karena tidak ada bedanya dengan pengecualian komentar inline. Juga setuju tentang membuat bendera kembali lebih jelas juga. Akan mengerjakannya sedikit. Terima kasih atas perhatian dan bantuannya!
640KB
5

Sebenarnya , 5 byte

;÷Σ½>

Cobalah online!

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

05AB1E , 4 byte

ѨO‹

Cobalah online!

Bagaimana itu bekerja

Ñ        #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? 

Maaf memposting di pertanyaan lama, saya baru saja melalui posting lama untuk latihan dan melihat solusi saya lebih pendek dari solusi 05AB1E terbaik berikutnya.

sampah luar angkasa
sumber
4
Sorry to post in old questionJangan khawatir tentang itu! Saya selalu senang melihat jawaban tentang tantangan lama saya, dan sebenarnya dianjurkan di sini . :)
DJMcMayhem
4

PARI / GP , 15 byte

n->sigma(n)>2*n

Variannya n->sigma(n,-1)>2, sayangnya, lebih lama.

Charles
sumber
4

Java 8, 53 byte (lebih banyak jika Anda memasukkan kode upacara)

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

Cobalah online

Penjelasan:

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
sumber
4
Jawaban yang bagus, tetapi dengan Java 8 Anda harus memasukkan fungsi dalam byte-count Anda. Kemudian lagi, Anda dapat menghapus returnjika saya tidak salah, sehingga akan lebih pendek: n->IntStream.range(1,n).filter(e->n%e<1).sum()>n(tidak 100% jika ini benar, saya hampir tidak pernah memprogram di Java 8). Selamat datang di PPCG!
Kevin Cruijssen
1
Penghitungan yang benar melalui penghitungan standar adalah n->java.util.stream.IntStream.range(1,n).filter(e->n%e<1).sum()>n65 byte (dengan asumsi saya mendapatkan paket langsung dari atas kepala saya)
CAD97
4

Powershell, 51 49 Bytes

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

Saya berharap saya bisa menghapus beberapa tanda kurung.

-2 Terima kasih kepada AdmBorkBork, alih-alih tidak menghitung input pada rentang awal, kami hanya memperhitungkannya pada pemeriksaan akhir.

Loop melalui rentang 1..ke $input, minus 1, temukan di mana ( ?) modulo input terbalik oleh angka saat ini adalah $true(alias hanya 0) - maka -joinsemua angka tersebut bersama-sama dengan +dan iexstring yang dihasilkan untuk menghitungnya, kemudian lihat apakah jumlah bagian ini lebih besar dari input.

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
sumber
Anda dapat menyimpan dua byte dengan menghitung nilai teratas dan memeriksa bahwa itu lebih besar dari 2x input -param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i
AdmBorkBork
3

MATL, 6 byte

Z\sGE>

Output 1 untuk angka melimpah, 0 sebaliknya.

Bagaimana itu bekerja

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
sumber
3

QBIC , 22 byte

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

Ini adalah adaptasi dari tes primitif QBIC . Alih-alih menghitung pembagi dan memeriksa apakah itu kurang dari tiga, ini menjumlahkan pembagi yang tepat. Ini hanya berjalan di sepanjang setengah dari 1 to n, di mana tes primality berjalan 1 to nsepenuhnya.

Penjelasan:

:       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
sumber
3

JavaScript (ES6), 33 byte

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>

Produksi ETH
sumber
Saya yakin jawaban rekursif akan lebih baik tetapi saya tidak berpikir itu akan sebaik ini.
Neil
3

Japt , 9 7 6 byte

<Uâ1 x

Disimpan 2 byte berkat produk ETH. Disimpan 1 byte berkat obarakon.

Cobalah online!

Tom
sumber
9 karakter, 10 byte.
Metoniem
@Metoniem Saya yakin â1 byte, setidaknya dalam unicode (0xE2).
Tom
1
@Metoniem Japt menggunakan pengkodean ISO-8859-1 , di mana âsatu byte.
ETHproduk
Jika âdiberi argumen yang benar, itu akan menghapus angka aktual dari daftar yang tersisa, sehingga Anda dapat melakukan â1 x >Uuntuk menyimpan beberapa byte :-)
ETHproduksi
@ TomDevs Bagus! Anda dapat melakukannya <Uâ1 xuntuk menghemat satu byte. Japt menambahkan Udi depan program.
Oliver
3

Cubix , 38 byte

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

Coba di sini

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

0I:- mengatur stack dengan 0, n, n (s, n, d)
^- mulai dari loop )?- decrement d dan uji untuk 0. 0 keluar loop
%?-mod terhadap n dan uji. 0 sebab ;rrw+s;rUyang berputar s ke atas dan menambahkan d, memutar s ke bawah dan bergabung kembali loop
;<- Bersihkan dan bergabung kembali loop.
Pada loop keluar
;<- Hapus d dari tumpukan dan redirect
-?- Hapus n dari s dan uji, 0 LOU@belok kiri, output dan keluar, negatif 0O@mendorong nol, output dan keluar. positif ;Omenghapus perbedaan dan keluaran n. Jalur kemudian melewati belok kiri yang mengarahkan ke @pintu keluar

MickyT
sumber
3

Bash Murni, 37 byte

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

Terima kasih kepada @ Dennis untuk mengatur ulang kode - menghemat 6 byte dan menghilangkan output insidental ke stderr.

Input dilewatkan sebagai argumen.

Output dikembalikan dalam kode keluar: 0 untuk berlimpah, 1 untuk tidak berlimpah.

Output ke stderr harus diabaikan.

Tes berjalan:

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
sumber
Anda dapat menghemat 6 byte sambil menghindari keluaran yang menyimpang ke STDERR. tio.run/nexus/bash#S04sUbBTSEwqzUtJzCtRsLFRUHf1d1P/…
Dennis
2

RProgN , 8 Bytes

~_]k+2/<

Dijelaskan

~_]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.

Cobalah online!

ATaco
sumber
2

Batch, 84 byte

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

Output -1untuk jumlah yang banyak, 0jika tidak. Bekerja dengan mengurangi semua faktor dari 2ndan kemudian menggeser 31 hasil tempat untuk mengekstrak bit tanda. Formulasi alternatif, juga 84 byte:

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

Output 1untuk jumlah yang melimpah. Bekerja dengan mengurangi semua faktor dari ndan kemudian membandingkan hasilnya dengan -n. ( set/aadalah satu-satunya cara Batch melakukan aritmatika jadi saya tidak dapat dengan mudah mengatur loop.)

Neil
sumber
1
"(% 1 %%%% j)" oh, batch :)
Bryan Boettcher
2

Perl 6, 72 24 byte

{$_ <sum grep $_%%*,^$_}
  • Argumen program: a.
  • Buat daftar dari 1..a.
  • Ambil semua angka yang merupakan pembagi a.
  • Jumlahkan mereka.
  • Periksa apakah jumlah itu lebih besar dari a.

Berkat @ b2gills.

Yang Mulia
sumber
Setiap kejadian $^asetelah yang pertama dapat disingkat menjadi adil $a. tetapi bahkan lebih singkat jika Anda menuliskannya {$_ <sum grep $_%%*,^$_}juga Melihat versi sebelumnya, [+](LIST)berfungsi (tanpa spasi)
Brad Gilbert b2gills
@ BradGilbertb2gills Terima kasih! :)
Ven
2

J, 19 byte

Terima kasih kepada Conor O'Brien karena memotongnya menjadi 19 byte!

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

Sebelumnya: (34 byte)

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

Mengembalikan 1 jika berlimpah dan 0 jika tidak.

Keluaran:

   f 3
0
   f 12
1
   f 11
0
   f 20
1
Blok
sumber
Selamat datang di PPCG! Kami mengizinkan fungsi anonim, sehingga Anda dapat menghapus yang pertama f=:sebagai bagian dari jumlah byte Anda. Juga, Anda bisa turun ke 19 dengan mengonversi ke kata kerja diam-diam:<[:+/i.#~i.e.]%2+i.
Conor O'Brien
Terima kasih atas sarannya! Namun, bisakah Anda menjelaskan cap kata kerja ([:) dan kata kerja switch (~). Saya tidak benar-benar mendapatkan apa yang seharusnya mereka lakukan dalam kata kerja diam-diam ini.
Blok
~ Berganti jadi itu adalah # i. tapi apa tujuan dari [:?
Blok
jadi kamu tahu tentang garpu, kan? (f g h) y' is the same as (fy) g (hy) . When f` adalah penutup, ([: g h) ykira-kira sama dengan g h y. Adapun ~, ini beralih argumen kiri dan kanan. Penting untuk diketahui bahwa ~itu bukan kata kerja tetapi sebenarnya kata keterangan. Itu memodifikasi kata kerja. Misalnya, kita dapat memiliki sesuatu seperti 2 %~ 8. Di sini, ~memodifikasi %untuk mengalihkan argumennya, sehingga ekspresi setara dengan 8 % 2.
Conor O'Brien
Dalam rantai garpu, #~dievaluasi setelah kata kerja di sebelah kanannya dieksekusi, jadi argumen kiri menjadi hasil di sebelah kanan
Conor O'Brien
2

Pyth, 11 byte

>sPf!%QTS

Tua:

L!%Qb>sPy#S

Saya tidak dapat menggunakan !%sebagai pfn untuk #, karena ini dua fungsi. Membuat saya sedih :(.


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
Yang Mulia
sumber
Tidak mendefinisikan fungsi tampaknya lebih pendek:>sPf!%QTS
FryAmTheEggman
2

k , 19 16 15 byte

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

Pengembalian 1untuk yang benar, dan 0untuk yang salah.

Cobalah 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
sumber
2

Common Lisp, 63 byte

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

Cobalah online!

Renzo
sumber
2

F #, 51 byte

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

Cobalah online!

Saring semua angka yang tidak terbagi rata n, lalu jumlahkan dan bandingkan n.

Ciaran_McCarthy
sumber