Una abundancia de enteros!

40

Un número abundante es cualquier número donde la suma de sus divisores propios es mayor que el número original. Por ejemplo, los divisores propios de 12 son:

1, 2, 3, 4, 6

Y sumando estos resultados en 16. Como 16 es mayor que 12, 12 es abundante. Tenga en cuenta que esto no incluye "números perfectos", por ejemplo, números que son iguales a la suma de sus divisores propios, como 6 y 28.

Su tarea para hoy es escribir un programa o función que determine si un número es abundante o no. Su programa debe tomar un solo entero como entrada y generar un valor verdadero / falso dependiendo de si es abundante o no. Puede suponer que la entrada siempre será válida y mayor que 0, por lo que para entradas incorrectas, el comportamiento indefinido está bien.

Puede tomar su entrada y salida en cualquier formato razonable, por ejemplo, STDIN / STDOUT, archivos o argumentos / valores de retorno serían aceptables.

Como referencia, aquí están los números abundantes hasta 100:

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

Y más se puede encontrar en A005101

Como se trata de , se niegan las lagunas estándar, ¡y trata de escribir el código más corto posible en el idioma que elijas!

DJMcMayhem
fuente
11
"¡el primer número impar abundante es 945 = 3 ^ 3 * 5 * 7, el número número 232 abundante!"
mbomb007
La densidad asintótica de números abundantes está en algún lugar dentro del intervalo [0.24761748, 0.24764422]. Calculado usando el código fuente incluido en este documento .
Código muerto el
1
Estoy tratando de hacer esto en Geometry Dash. Es una pesadilla
MilkyWay90

Respuestas:

41

ECMAScript Regex, 1085 855 597 536 511 508 504 bytes

Emparejar números abundantes en ECMAScript regex es una bestia completamente diferente a hacerlo en prácticamente cualquier otro sabor de expresiones regulares. La falta de referencias hacia atrás / anidadas o recursividad significa que es imposible contar directamente o mantener un total acumulado de cualquier cosa. La falta de mirar atrás hace que a menudo sea un desafío incluso tener suficiente espacio para trabajar.

Muchos problemas deben abordarse desde una perspectiva completamente diferente, y se preguntará si tienen solución alguna. Te obliga a echar una red mucho más amplia para encontrar qué propiedades matemáticas de los números con los que estás trabajando podrían usarse para resolver un problema en particular.

En marzo y abril de 2014, construí una solución a este problema en ECMAScript regex. Al principio tenía todas las razones para sospechar que el problema era completamente imposible, pero luego el matemático teukon bosquejó una idea que hizo un argumento alentador para que pareciera solucionable después de todo, pero dejó en claro que no tenía intención de construir la expresión regular (él había competido / cooperado con mi en la construcción / golf de expresiones regulares anteriores, pero llegó a su límite en este punto y se contentó con restringir sus contribuciones adicionales a la teoría).

Al igual que con mi expresión regular publicada hace un par de días, daré una advertencia: recomiendo aprender a resolver problemas matemáticos unarios en expresiones regulares ECMAScript. Ha sido un viaje fascinante para mí, y no quiero estropearlo para cualquiera que quiera probarlo ellos mismos, especialmente aquellos interesados ​​en la teoría de números. Vea esa publicación para obtener una lista de problemas recomendados consecutivamente etiquetados con spoiler para resolver uno por uno.

Así que no sigas leyendo si no quieres que se te eche a perder una profunda magia regex unaria . Mi publicación anterior fue solo una pequeña muestra. Si desea intentar descubrir esta magia usted mismo, le recomiendo comenzar resolviendo algunos problemas en la expresión regular de ECMAScript como se describe en la publicación vinculada anteriormente.

Antes de la publicación de mi expresión regular ECMAScript, pensé que sería interesante analizar de Martin Ender solución pura de expresiones regulares de .NET , ^(?!(1(?<=(?=(?(\3+$)((?>\2?)\3)))^(1+)))*1$). Resulta muy sencillo entender esa expresión regular, y es elegante en su simplicidad. Para demostrar el contraste entre nuestras soluciones, aquí hay una versión comentada y bastante impresa (pero no modificada) de su expresión regular:

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

Prueba el .NET regex en línea

Ahora, de vuelta a mi expresión regular ECMAScript. Primero, aquí está en formato sin formato, sin espacios en blanco y sin comentarios:

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

(cambio \14a \14?la compatibilidad con PCRE, .NET, y prácticamente todos los otros sabores de expresiones regulares que no es ECMAScript)

Pruébalo en línea!
Pruébalo en línea! (más rápido, versión de 537 bytes de la expresión regular)

Y ahora un breve resumen de la historia detrás de esto.

Al principio era muy poco obvio, al menos para mí, que incluso era posible igualar los números primos en el caso general. Y después de resolver eso, lo mismo se aplica a las potencias de 2. Y luego a las potencias de los números compuestos. Y luego cuadrados perfectos. E incluso después de resolver eso, hacer una multiplicación generalizada parecía imposible al principio.

En un bucle ECMAScript, solo puede realizar un seguimiento de un número cambiante; ese número no puede exceder la entrada y tiene que disminuir en cada paso. Mi primera expresión regular de trabajo para hacer coincidir las declaraciones de multiplicación correctas A * B = C fue de 913 bytes, y trabajé factorizando A, B y C en sus potencias primarias: para cada factor primo, divida repetidamente el par de factores de potencia primos de A y C por su base principal hasta que la correspondiente a A llegue a 1; el correspondiente a C se compara con el factor de potencia primo de B. Estas dos potencias del mismo primo se "multiplexaron" en un solo número al sumarlas; esto siempre sería inequívocamente separable en cada iteración posterior del bucle, por la misma razón que funcionan los sistemas de numeración posicional.

La multiplicación se redujo a 50 bytes usando un algoritmo completamente diferente (al cual teukon y yo pudimos llegar de forma independiente, aunque le tomó solo unas pocas horas y fue directo a ello, mientras que me tomó un par de días incluso después de que fue me llamó la atención que existía un método corto): para A≥B, A * B = C, si lo hay, solo si C es el número más pequeño que satisface C≡0 mod A y C≡B mod A-1. (Convenientemente, la excepción de A = 1 no necesita un manejo especial en expresiones regulares, donde 0% 0 = 0 produce una coincidencia). Simplemente no puedo superar cuán ordenado es que exista una forma tan elegante de multiplicar en Sabor mínimo de expresiones regulares. (Y el requisito de A≥B se puede reemplazar con el requisito de que A y B son potencias primarias de la misma potencia. Para el caso de A≥B, esto se puede probar utilizando el teorema del resto chino).

Si hubiera resultado que no había un algoritmo más simple para la multiplicación, la expresión regular de números abundantes probablemente sería del orden de diez mil bytes más o menos (incluso teniendo en cuenta que utilicé el algoritmo de 913 bytes hasta 651 bytes). Hace mucha multiplicación y división, y la expresión regular ECMAScript no tiene subrutinas.

Comencé a trabajar en el problema de los números abundantes tangencialmente el 23 de marzo de 2014, construyendo una solución para lo que en ese momento parecía ser un subproblema de esto: identificar el factor primo de mayor multiplicidad, para que pudiera dividirse de N al principio, dejando espacio para hacer algunos cálculos necesarios. En ese momento, parecía ser una ruta prometedora. (Mi solución inicial terminó siendo bastante grande en 326 bytes, luego bajó a 185 bytes.) Pero el resto del método que bosquejó el teukon habría sido extremadamente complicado, así que resultó que tomé una ruta bastante diferente. Resultó ser suficiente para dividir el factor de potencia primo más grande de N correspondiente al factor primo más grande en N; hacer esto para obtener la máxima multiplicidad habría agregado complejidad y longitud innecesarias a la expresión regular.

Lo que quedaba era tratar la suma de divisores como un producto de sumas en lugar de una suma directa. Según lo explicado por teukon el 14 de marzo de 2014:

Se nos da un número n = p 0 a 0 p 1 a 1 ... p k-1 a k-1 . Queremos manejar la suma de los factores de n, que es (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 ).

Me sorprendió ver esto. Nunca había pensado en factorizar la suma de alícuotas de esa manera, y fue esta fórmula más que ninguna otra cosa la que hizo que la solvencia de la coincidencia de números abundantes en ECMAScript regex pareciera plausible.

Al final, en lugar de probar un resultado de suma o multiplicación que excede N, o probar que dicho resultado dividido previamente por M excede N / M, fui a probar si el resultado de la división es menor que 1. Llegué a La primera versión de trabajo el 7 de abril de 2014.

La historia completa de mis optimizaciones de golf de esta expresión regular está en github. En cierto punto, una optimización terminó haciendo que la expresión regular fuera mucho más lenta, por lo que desde ese momento mantuve dos versiones. Son:

regex para hacer coincidir números abundantes.txt
regex para hacer coincidir números abundantes - shortest.txt

Estas expresiones regulares son totalmente compatibles con ECMAScript y PCRE, pero una optimización reciente implicó el uso de un grupo de captura potencialmente no participante \14, por lo que al eliminar la compatibilidad con PCRE y cambiar \14?a \14ambos se puede reducir en 1 byte.

Aquí está la versión más pequeña, con esa optimización aplicada (haciéndola solo ECMAScript), reformateada para caber en un bloque de código StackExchange sin (en su mayoría) desplazamiento horizontal necesario:

# 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$)
  )
)+$
Código muerto
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DJMcMayhem
1
-98 bytes
Grimmy
27

Python 2 , 41 40 bytes

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

La salida es a través del código de salida , por lo que 0 es verdadero y 1 es falso.

Pruébalo en línea!

Cómo funciona

Después de ajustar todos de n , k , y j a la entrada de STDIN, entramos en el tiempo de bucle. Dicho ciclo se romperá tan pronto como -k - 1 = ~ k ≥ 0 , es decir, k ≤ -1 / k <0 .

En cada iteración, primero disminuimos j para considerar solo divisores propios de n . Si j es un divisor de n , n%jproduce 0 y j >> n% j * n = j / 2 0 = j se resta de k . Sin embargo, si j no no dividir n , n%jes positivo, por lo que n%j*nes al menos n> log 2 j y j >> n * n = j / 2% j n% j * n = 0 se resta de k .

Para números abundantes, k alcanzará un valor negativo antes o cuando j se convierta en 1 , ya que la suma de los divisores propios de n es estrictamente mayor que n . En este caso, partimos del tiempo de bucle y el programa termina de manera normal.

Sin embargo, si n no es abundante, j eventualmente llega a 0 . En este caso, n%jlanza un ZeroDivisionError y el programa sale con un error.

Dennis
fuente
44
~k<0es elegante, pero creo que -1<ktambién funciona;)
Martin Ender
12

Brachylog , 5 bytes

fk+>?

Pruébalo en línea!

Explicación

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

Jalea , 3 bytes

Æṣ>

Pruébalo en línea!

Cómo funciona

Æṣ>  Main link. Argument: n

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

Python , 44 bytes

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

Pruébalo en línea!

Jonathan Allan
fuente
Es una pena que no puedas hacer range(n). Ese módulo molesto por cero
DJMcMayhem
10

Mathematica, 17 bytes

Tr@Divisors@#>2#&

Explicación

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
fuente
1
Me sorprende que Mathematica no haya construido para esto ...
MrPaulch
1
@MrPaulch Sin embargo, teniendo en cuenta la duración del programa, es muy posible que el nombre incorporado sea más largo en nombre>.>
Conor O'Brien
1
@ ConorO'Brien Si existiera, probablemente lo sería AbundantNumberQ, por lo que ahorraría un par de bytes :)
ngenisis
7

Retina , 50 45 bytes

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

Entrada en unario , salida 1para números abundantes, de lo 0contrario.

No hay nada específico de Retina sobre esta solución. Lo anterior es una expresión regular pura de .NET que solo coincide con números abundantes.

Pruébalo en línea! (Conjunto de pruebas que filtra la entrada decimal con la expresión regular anterior).

Martin Ender
fuente
6

Retina , 34 bytes

El recuento de bytes asume la codificación ISO 8859-1.

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

^(1+)¶1\1

Entrada en unario , salida 1para números abundantes, de lo 0contrario.

Pruébalo en línea!

Explicación

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

Comenzamos obteniendo todos los divisores de la entrada. Para hacer esto, devolvemos ( !) todas las coincidencias superpuestas ( &) ( M) de la expresión regular (1+)$(?<=^\1+). La expresión regular coincide con algún sufijo de la entrada, siempre que la entrada completa sea un múltiplo de ese sufijo (que aseguramos al tratar de llegar al principio de la cadena usando solo copias del sufijo). Debido a la forma en que el motor de expresiones regulares busca coincidencias, esto dará como resultado una lista de divisores en orden descendente (separados por avances de línea).

1>`¶

El escenario en sí simplemente coincide con los avances de línea ( ) y los elimina. Sin embargo, el 1>es un límite, que omite el primer partido. Entonces esto efectivamente suma todos los divisores, excepto la entrada en sí. Terminamos con la entrada en la primera línea y la suma de todos los divisores propios en la segunda línea.

^(1+)¶1\1

Finalmente, intentamos igualar al menos uno más 1en la segunda línea que el que tenemos en la primera línea. Si ese es el caso, la suma de los divisores propios excede la entrada. La retina cuenta el número de coincidencias de esta expresión regular, que será 1para números abundantes y de 0otra manera.

Martin Ender
fuente
1
Siempre me ha sorprendido cómo puedes hacer matemáticas en la retina. ¡Me encantaría ver una explicación! :)
DJMcMayhem
1
@DJMcMayhem Lo siento, olvidé agregar eso antes. Hecho.
Martin Ender
6

8086 Asamblea, 23 28 25 24 bytes

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

Desmontado:

; 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

Programa de prueba de ejemplo, prueba 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

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

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

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

Actualizaciones:

  • Corregido por desbordamiento de 16 bits (+5 bytes). Gracias @deadcode por las sugerencias!
  • Lógica de retorno simplificada (-3 bytes). Gracias por ayudar a @deadcode una vez más.
  • Use TEST en lugar de CMP (-1 byte). Gracias a @ l4m2!
640 KB
fuente
1
Sugeriría reemplazar JLEcon el JBEdoble del rango de números que esto puede probar antes de que los desbordamientos comiencen a causar falsos negativos. Luego, en lugar de comenzar a fallar a 12600 (suma alícuota 35760), comenzará a fallar a 25200 (suma alícuota 74744). Aún mejor sería detectar también el indicador de acarreo y tratarlo como un número abundante sin necesidad de calcular la suma real> 16 bits.
Código muerto el
1
Buena captura @Deadcode. He actualizado el código para saltar a continuación en lugar de saltar menos. Veo lo que quieres decir, haciendo un JC después de ADD BX, CX detectará el desbordamiento sin firmar allí y lo corregirá hasta N = 65535. Complica las pruebas de indicador y el estado de retorno un poco, ya que anteriormente CF implicaba falso. Actualizado con arreglo también.
640 KB
1
Puede ahorrar 3 bytes invirtiendo la especificación de su valor de retorno, con CF establecido si es abundante y claro si no. Pero recomiendo hacer la edición para corregir la documentación de salida primero, para que se vea bien en el historial de edición.
Deadcode
1
Además, para simplificar las cosas, la especificación debería ser que el valor de retorno esté en el indicador de acarreo, y que nada de eso se preocupe con los otros indicadores. La persona que llama debe usar JCoJNC actuar sobre si el número es abundante o no.
Código muerto el
1
Muchas gracias por toda su ayuda y sus comentarios. Actualicé la documentación en línea y eliminé el término sin golf. Sinceramente, nunca lo pensé mucho, pero veo su punto al respecto, ya que no es diferente con la excepción de los comentarios en línea. También acuerde sobre makint las banderas de retorno más claras también. Trabajaré en eso en un momento. Gracias por la atención y la asistencia!
640 KB
5

05AB1E , 4 bytes

ѨO‹

Pruébalo en línea!

Cómo funciona

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

Lamento publicar en una pregunta anterior, solo estaba revisando publicaciones antiguas para practicar y noté que mi solución era más corta que la siguiente mejor solución 05AB1E.

basura espacial
fuente
44
Sorry to post in old question¡No te preocupes por eso! Siempre estoy feliz de ver respuestas a mis viejos desafíos, y en realidad es alentado por aquí . :)
DJMcMayhem
4

PARI / GP , 15 bytes

n->sigma(n)>2*n

La variante n->sigma(n,-1)>2es, desafortunadamente, más larga.

Charles
fuente
4

Java 8, 53 bytes (mucho más si incluye el código ceremonial)

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

Pruébalo en línea

Explicacion:

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
fuente
44
Gran respuesta, pero con Java 8 debe incluir la función en su conteo de bytes. Por otra parte, puede descartar returnsi no me equivoco, por lo que será aún más corto: n->IntStream.range(1,n).filter(e->n%e<1).sum()>n(no 100% si esto es correcto, casi nunca programo en Java 8). Bienvenido a PPCG!
Kevin Cruijssen
1
El recuento correcto a través del recuento estándar sería n->java.util.stream.IntStream.range(1,n).filter(e->n%e<1).sum()>nde 65 bytes (suponiendo que obtuve el paquete directamente de mi cabeza)
CAD97
4

Powershell, 51 49 bytes

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

Desearía poder quitar algunos corchetes.

-2 gracias a AdmBorkBork, en lugar de no contar la entrada en el rango inicial, solo lo tenemos en cuenta en la verificación final.

Bucle a través de gama de 1..la $iNput, menos 1, encuentra que ( ?) del módulo inverso de la entrada por el número actual es $true(también conocido como sólo 0) - entonces -jointodos esos números, junto con +y iexla cadena resultante de calcular, y luego ver si el La suma de estas partes es mayor que la entrada.

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
fuente
Puede guardar dos bytes contando el valor superior y la comprobación de que es más grande que la entrada de 2x -param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i
AdmBorkBork
3

MATL, 6 bytes

Z\sGE>

Salidas 1 para números abundantes, 0 de lo contrario.

Cómo funciona

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

QBIC , 22 bytes

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

Esta es una adaptación a la prueba de primalidad QBIC . En lugar de contar los divisores y verificar si son menos de tres, esto suma los divisores adecuados. Esto se ejecuta solo en la mitad de 1 to n, donde la prueba de primalidad se ejecuta por 1 to ncompleto.

Explicación:

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

JavaScript (ES6), 33 bytes

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>

ETHproducciones
fuente
Estaba seguro de que una respuesta recursiva sería la mejor, pero no pensé que sería tan buena.
Neil
3

Japt , 9 7 6 bytes

<Uâ1 x

Ahorró 2 bytes gracias a ETHproductions. Guardado 1 byte gracias a obarakon.

Pruébalo en línea!

Tom
fuente
9 caracteres, 10 bytes.
Metoniem
@Metoniem Estoy seguro de que âes 1 byte, al menos en Unicode (0xE2).
Tom
1
@Metoniem Japt usa la codificación ISO-8859-1 , en la cual âhay un solo byte.
ETHproductions
Si âse le da un argumento verdadero, eliminará el número real de la lista restante, por lo que puede hacer â1 x >Upara guardar un par de bytes :-)
ETHproductions
@TomDevs Nice! Puede hacer <Uâ1 xpara guardar un byte. Japt agrega el Ufrente del programa.
Oliver
3

Cubix , 38 bytes

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

Pruébalo aquí

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

0I:- configura la pila con 0, n, n (s, n, d)
^- inicio del bucle )?- decremento d y prueba para 0. 0 sale del bucle
%?- mod contra ny prueba. 0 causas ;rrw+s;rUque rota s hacia arriba y agrega d, rota s hacia abajo y vuelve a unirse al bucle
;<: limpie y vuelva a unir el bucle.
Al salir del bucle
;<: eliminar d de la pila y redirigir
-?: eliminar n de sy probar, 0 LOU@gira a la izquierda, salidas y salidas, los negativos 0O@empujan a cero, salida y salidas. los positivos ;Oeliminan la diferencia y las salidas n. Luego, el camino pasa a la izquierda que redirige a la @salida

MickyT
fuente
3

Pure Bash, 37 bytes

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

Gracias a @Dennis por reorganizar el código, ahorrando 6 bytes y eliminando la salida incidental a stderr.

La entrada se pasa como argumento.

La salida se devuelve en el código de salida: 0 para abundante, 1 para no abundante.

La salida a stderr debe ignorarse.

Pruebas de funcionamiento:

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
fuente
Puede guardar 6 bytes mientras evita la salida perdida a STDERR. tio.run/nexus/bash#S04sUbBTSEwqzUtJzCtRsLFRUHf1d1P/…
Dennis
2

RProgN , 8 Bytes

~_]k+2/<

Explicado

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

Pruébalo en línea!

Un taco
fuente
2

Lote, 84 bytes

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

Salidas -1para un número abundante, de lo 0contrario. Funciona restando todos los factores 2ny luego desplazando el resultado 31 lugares para extraer el bit de signo. Formulación alternativa, también 84 bytes:

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

Salidas 1para un número abundante. Funciona restando todos los factores de ny luego comparando el resultado con -n. ( set/aes la única forma de Batch de hacer aritmética, por lo que no puedo ajustar fácilmente el bucle).

Neil
fuente
1
"(% 1 %%%% j)" oh, lote :)
Bryan Boettcher
2

Perl 6, 72 24 bytes

{$_ <sum grep $_%%*,^$_}
  • Argumento del programa: a.
  • Generar una lista de 1..a.
  • Tome todos los números que son divisores de a.
  • Suma de ellos.
  • Comprueba si esa suma es mayor que a.

Gracias a @ b2gills.

Ven
fuente
Cada ocurrencia $^aposterior a la primera se puede acortar a justa $a. pero es aún más corto si lo escribe como {$_ <sum grep $_%%*,^$_}También mirando una versión anterior, [+](LIST)funciona (sin espacios)
Brad Gilbert b2gills
@ BradGilbertb2gills Gracias! :)
Ven
2

J, 19 bytes

¡Gracias a Conor O'Brien por reducirlo a 19 bytes!

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

Anterior: (34 bytes)

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

Devuelve 1 si es abundante y 0 si no lo es.

Salida:

   f 3
0
   f 12
1
   f 11
0
   f 20
1
Bloques
fuente
Bienvenido a PPCG! Permitimos funciones anónimas, por lo que puede eliminar el inicio f=:como parte de su recuento de bytes. Además, puede bajar a 19 convirtiéndose a un verbo tácito:<[:+/i.#~i.e.]%2+i.
Conor O'Brien
¡Gracias por el consejo! Sin embargo, ¿podría explicar el verbo cap ([:) y el verbo switch (~). Realmente no entiendo lo que se supone que deben hacer en este verbo tácito.
Bloques del
~ cambia así que es decir, # i. pero ¿para qué sirve [:?
Bloques del
así que sabes sobre tenedores, ¿verdad? (f g h) y' is the same as (fy) g (hy) . When f` es un límite, ([: g h) yes aproximadamente lo mismo que g h y. En cuanto a ~, esto cambia los argumentos izquierdo y derecho. Es importante saber que ~no es un verbo sino un adverbio. Modifica un verbo. Por ejemplo, podríamos tener algo así 2 %~ 8. Aquí, ~modifica %para cambiar sus argumentos, por lo que la expresión es equivalente a 8 % 2.
Conor O'Brien
En la cadena de la bifurcación, #~se evalúa después de que se ejecutan los verbos a su derecha, por lo que su argumento izquierdo se convierte en el resultado a la derecha
Conor O'Brien
2

Pyth, 11 bytes

>sPf!%QTS

Antiguo:

L!%Qb>sPy#S

No puedo usarlo !%como un pfn #, porque son dos funciones. Me pone triste :(.


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
fuente
No definir una función parece ser más corto:>sPf!%QTS
FryAmTheEggman
2

k , 19 16 15 bytes

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

Devuelve 1para verdadero y 0para falso.

Pruébalo en línea!

{             } /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
fuente
2

F #, 51 bytes

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

Pruébalo en línea!

Filtra todos los números que no se dividen en partes iguales n, luego los suma y los compara n.

Ciaran_McCarthy
fuente