Definiciones
Dejar m
y n
ser enteros positivos. Decimos que m
es un giro divisor de n
si existen enteros 1 < a ≤ b
tales que n = a*b
y m = (a - 1)*(b + 1) + 1
. Si m
se puede obtener n
aplicando cero o más giros divisores, entonces m
es un descendiente de n
. Tenga en cuenta que cada número es su propio descendiente.
Por ejemplo, considere n = 16
. Podemos elegir a = 2
y b = 8
, desde entonces 2*8 = 16
. Luego
(a - 1)*(b + 1) + 1 = 1*9 + 1 = 10
lo que muestra que 10
es un giro divisor de 16
. Con a = 2
y b = 5
, entonces vemos que 7
es un giro divisor de 10
. Así 7
es un descendiente de 16
.
La tarea
Dado un número entero positivo n
, calcule los descendientes de n
, listados en orden creciente, sin duplicados.
Reglas
No está permitido usar operaciones integradas que calculen los divisores de un número.
Se aceptan programas y funciones completos, y se permite devolver un tipo de datos de recopilación (como un conjunto de algún tipo), siempre que esté ordenado y sin duplicados. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.
Casos de prueba
1 -> [1]
2 -> [2] (any prime number returns just itself)
4 -> [4]
16 -> [7, 10, 16]
28 -> [7, 10, 16, 25, 28]
51 -> [37, 51]
60 -> [7, 10, 11, 13, 15, 16, 17, 18, 23, 25, 28, 29, 30, 32, 43, 46, 49, 53, 55, 56, 60]
fuente
<
para los números naturales, por cada n obtendrá cada número más pequeño que él, pero no por sí mismo. Creo que esto debería ser algo similar. De esta manera, creo que solo 4 sería su propio descendiente (aunque no estoy seguro de eso).Respuestas:
Python 2,
109988582 bytesComo
(a-1)*(b+1)+1 == a*b-(b-a)
yb >= a
, los descendientes son siempre menores o iguales que el número original. Entonces, podemos comenzar con el número inicial y seguir generando descendientes estrictamente más pequeños hasta que no quede ninguno.La condición
(n<x*x)>n%x
verifica dos cosas en una: eson<x*x
yn%x == 0
.(Gracias a @xnor por eliminar 3 bytes del caso base)
Pyth, 32 bytes
Traducción directa de lo anterior, excepto por el hecho de que Pyth parece ahogarse cuando intenta sumar (
s
) en una lista vacía.Esto define una función a la
y
que se puede llamar agregandoy<number>
al final, así ( intente en línea ):CJam,
4745 bytesTambién usando el mismo método, con algunas modificaciones. Quería probar CJam para comparar, pero desafortunadamente soy mucho peor en CJam que en Pyth / Python, por lo que probablemente haya mucho margen de mejora.
Lo anterior es un bloque (básicamente la versión de CJam de funciones sin nombre) que toma un int y devuelve una lista. Puedes probarlo así ( pruébalo en línea ):
fuente
set()
allí? ¿No puedes devolver la lista ordenada?set()
es eliminar duplicados :)[n]+sum(...,[])
tansum(...,[n])
?[]
que un caso base para sumar listas, ¡así que lo olvidé por completo!Java,
148146104 bytesVersión de golf:
Versión larga:
Así que estoy haciendo mi debut en PPCG con este programa, que usa una
TreeSet
(que afortunadamente clasifica los números, afortunadamente) y una recursión similar al programa de Geobits, pero de una manera diferente, verificando múltiplos de ny luego usándolos en el siguiente función Diría que este es un puntaje bastante justo para un novato (especialmente con Java, que no parece ser el lenguaje más ideal para este tipo de cosas, y la ayuda de Geobits).fuente
a*b
a lan
línea 9.c=n+a-b
adentroadd()
. Alternativamente, podría deshacerse de él porc
completo y simplemente usarlon+a-b
en ambos lugares para esos mismos dos bytes.add
dos veces. Espera un momento...a
que sabes que se dividen
limpiamente, entonces no deberías recorrerlo para encontrarlob
, es solon/a
. En ese punto comienza a acercarse más y más a la mía;)Java,
157121Aquí hay una función recursiva que obtiene descendientes de cada descendiente de
n
. Devuelve aTreeSet
, que se ordena por defecto.Con algunos saltos de línea:
fuente
Octava,
10796Bonito estampado:
fuente
end
lugar deendfor
yendfunction
. Eso te ahorraría 11 bytes.Haskell,
102100 bytesUso:
p 16
que salidas[7,10,16]
La función
d
calcula recursivamente todos los descendientes, pero no busca duplicados, por lo que muchos aparecen más de una vez, por ejemplo,d [4]
devuelve una lista infinita de4
s. Las funcionesp
toman los primerosn
elementos de esta lista, eliminan los duplicados y clasifican la lista. Voilà.fuente
CJam - 36
Pruébalo en línea
O, método diferente:
Los escribí hace casi 2 días, me quedé atrapado a los 36 años, me frustré y me dormí sin publicar.
fuente