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 código de golf , se niegan las lagunas estándar, ¡y trata de escribir el código más corto posible en el idioma que elijas!
fuente
Respuestas:
ECMAScript Regex,
1085855597536511508504 bytesEmparejar 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: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
\14
a\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:
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\14
ambos 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:
fuente
Python 2 ,
4140 bytesLa 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%j
produce 0 y j >> n% j * n = j / 2 0 = j se resta de k . Sin embargo, si j no no dividir n ,n%j
es positivo, por lo quen%j*n
es 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%j
lanza un ZeroDivisionError y el programa sale con un error.fuente
~k<0
es elegante, pero creo que-1<k
también funciona;)Brachylog , 5 bytes
Pruébalo en línea!
Explicación
fuente
Jalea , 3 bytes
Pruébalo en línea!
Cómo funciona
fuente
Python , 44 bytes
Pruébalo en línea!
fuente
range(n)
. Ese módulo molesto por ceroMathematica, 17 bytes
Explicación
fuente
AbundantNumberQ
, por lo que ahorraría un par de bytes :)05AB1E ,
54 bytes-1 bytes gracias a scottinet
Pruébalo en línea! o prueba de 0 a 100
fuente
Retina ,
5045 bytesEntrada en unario , salida
1
para números abundantes, de lo0
contrario.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).
fuente
Retina , 34 bytes
El recuento de bytes asume la codificación ISO 8859-1.
Entrada en unario , salida
1
para números abundantes, de lo0
contrario.Pruébalo en línea!
Explicación
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).El escenario en sí simplemente coincide con los avances de línea (
¶
) y los elimina. Sin embargo, el1>
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.Finalmente, intentamos igualar al menos uno más
1
en 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á1
para números abundantes y de0
otra manera.fuente
8086 Asamblea,
23282524 bytesDesmontado:
Programa de prueba de ejemplo, prueba N = [12..1000]:
Salida [2..1000]
Salida [12500..12700]
Salida [25100..25300]
Actualizaciones:
fuente
JLE
con elJBE
doble 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.JC
oJNC
actuar sobre si el número es abundante o no.En realidad , 5 bytes
Pruébalo en línea!
fuente
05AB1E , 4 bytes
Pruébalo en línea!
Cómo funciona
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.
fuente
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í . :)PARI / GP , 15 bytes
La variante
n->sigma(n,-1)>2
es, desafortunadamente, más larga.fuente
Java 8, 53 bytes (mucho más si incluye el código ceremonial)
Pruébalo en línea
Explicacion:
fuente
return
si 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!n->java.util.stream.IntStream.range(1,n).filter(e->n%e<1).sum()>n
de 65 bytes (suponiendo que obtuve el paquete directamente de mi cabeza)Powershell,
5149 bytesDesearí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$i
Nput, 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-join
todos esos números, junto con+
yiex
la cadena resultante de calcular, y luego ver si el La suma de estas partes es mayor que la entrada.fuente
param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i
MATL, 6 bytes
Salidas 1 para números abundantes, 0 de lo contrario.
Cómo funciona
fuente
QBIC , 22 bytes
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 por1 to n
completo.Explicación:
fuente
JavaScript (ES6), 33 bytes
fuente
Japt ,
9 76 bytesAhorró 2 bytes gracias a ETHproductions. Guardado 1 byte gracias a obarakon.
Pruébalo en línea!
fuente
â
es 1 byte, al menos en Unicode (0xE2).â
hay un solo byte.â
se le da un argumento verdadero, eliminará el número real de la lista restante, por lo que puede hacerâ1 x >U
para guardar un par de bytes :-)<Uâ1 x
para guardar un byte. Japt agrega elU
frente del programa.Cubix , 38 bytes
Pruébalo aquí
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;rU
que 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, 0LOU@
gira a la izquierda, salidas y salidas, los negativos0O@
empujan a cero, salida y salidas. los positivos;O
eliminan la diferencia y las salidas n. Luego, el camino pasa a la izquierda que redirige a la@
salidafuente
Pure Bash, 37 bytes
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:
fuente
RProgN , 8 Bytes
Explicado
Pruébalo en línea!
fuente
Lote, 84 bytes
Salidas
-1
para un número abundante, de lo0
contrario. Funciona restando todos los factores2n
y luego desplazando el resultado 31 lugares para extraer el bit de signo. Formulación alternativa, también 84 bytes:Salidas
1
para un número abundante. Funciona restando todos los factores den
y luego comparando el resultado con-n
. (set/a
es la única forma de Batch de hacer aritmética, por lo que no puedo ajustar fácilmente el bucle).fuente
Perl 6,
7224 bytes1..a
.a
.a
.Gracias a @ b2gills.
fuente
$^a
posterior 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)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:
fuente
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.
(f g h) y' is the same as
(fy) g (hy). When
f` es un límite,([: g h) y
es aproximadamente lo mismo queg 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 a8 % 2
.#~
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 derechaPyth, 11 bytes
Antiguo:
No puedo usarlo
!%
como un pfn#
, porque son dos funciones. Me pone triste :(.fuente
>sPf!%QTS
k ,
19 1615 bytesDevuelve
1
para verdadero y0
para falso.Pruébalo en línea!
fuente
PowerShell , 43 bytes
Pruébalo en línea!
fuente
Lisp común, 63 bytes
Pruébalo en línea!
fuente
F #, 51 bytes
Pruébalo en línea!
Filtra todos los números que no se dividen en partes iguales
n
, luego los suma y los comparan
.fuente