Giro divisor iterado

13

Definiciones

Dejar my nser enteros positivos. Decimos que mes un giro divisor de nsi existen enteros 1 < a ≤ btales que n = a*by m = (a - 1)*(b + 1) + 1. Si mse puede obtener naplicando cero o más giros divisores, entonces mes un descendiente de n. Tenga en cuenta que cada número es su propio descendiente.

Por ejemplo, considere n = 16. Podemos elegir a = 2y b = 8, desde entonces 2*8 = 16. Luego

(a - 1)*(b + 1) + 1 = 1*9 + 1 = 10

lo que muestra que 10es un giro divisor de 16. Con a = 2y b = 5, entonces vemos que 7es un giro divisor de 10. Así 7es 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]
Zgarb
fuente
@Zgarb si permite una cadena de giros de divisor 0, entonces, ¿cómo no todos los números son descendientes de ningún otro número?
rorlork
3
@rcrmn Para mí, una cadena de operaciones cero significa la operación de identidad. Entonces, permitir giros de divisor cero solo implica que cada número es un descendiente de sí mismo.
Zgarb
@Zgarb está bien, por lo que la definición debe cambiarse para expresar eso, porque si no, por lo que puedo decir, cualquier número se considera un descendiente de cualquier otro número. No sé por qué se necesita la reflexividad. ¿Te gustaría explicarlo?
rorlork
@rcrmn Cambié un poco la redacción, ¿está más claro ahora?
Zgarb
@Zgarb lo siento pero no, no es una operación, estás definiendo una relación entre números. Si define la relación <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).
rorlork

Respuestas:

9

Python 2, 109 98 85 82 bytes

f=lambda n:sorted(set(sum(map(f,{n-x+n/x for x in range(2,n)if(n<x*x)>n%x}),[n])))

Como (a-1)*(b+1)+1 == a*b-(b-a)y b >= 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%xverifica dos cosas en una: eso n<x*xy n%x == 0.

(Gracias a @xnor por eliminar 3 bytes del caso base)

Pyth, 32 bytes

LS{s+]]bmydm+-bk/bkf><b*TT%bTr2b

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 yque se puede llamar agregando y<number>al final, así ( intente en línea ):

LS{s+]]bmydm+-bk/bkf><b*TT%bTr2by60

CJam, 47 45 bytes

{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}

Tambié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 ):

{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}:G; 60 Gp
Sp3000
fuente
No soy un experto en Python, pero ¿hay alguna razón por la que necesites set()allí? ¿No puedes devolver la lista ordenada?
Alex A.
@Alex set()es eliminar duplicados :)
Sp3000
Ah, vale. Ordenado. ¡Buen trabajo!
Alex A.
Puede que quizá no [n]+sum(...,[])tan sum(...,[n])?
xnor
@xnor Ah sí, puedo. Nunca he usado nada más []que un caso base para sumar listas, ¡así que lo olvidé por completo!
Sp3000
6

Java, 148 146 104 bytes

Versión de golf:

import java.util.*;Set s=new TreeSet();void f(int n){s.add(n);for(int a=1;++a*a<n;)if(n%a<1)f(n+a-n/a);}

Versión larga:

import java.util.*;
Set s = new TreeSet();
void f(int n) {
    s.add(n);
    for (int a = 1; ++a*a < n;)
        if (n%a < 1)
            f(n + a - n/a);
}

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

TNT
fuente
Bienvenido a PPCG! Puede guardar un par cambiando a*ba la nlínea 9.
Geobits
Gracias por la bienvenida y la sugerencia! Sí, me llevará un tiempo detectar estas pequeñas cosas. ¡Cada byte cuenta! ¡Gracias de nuevo!
TNT
También puedes guardar dos más poniéndolos c=n+a-badentro add(). Alternativamente, podría deshacerse de él por ccompleto y simplemente usarlo n+a-ben ambos lugares para esos mismos dos bytes.
Geobits
Hablando de eso, no creo que necesite usar adddos veces. Espera un momento...
TNT
Pero el segundo ciclo no es necesario en general. Si tienes un aque sabes que se divide nlimpiamente, entonces no deberías recorrerlo para encontrarlo b, es solon/a . En ese punto comienza a acercarse más y más a la mía;)
Geobits
4

Java, 157 121

Aquí hay una función recursiva que obtiene descendientes de cada descendiente de n. Devuelve a TreeSet, que se ordena por defecto.

import java.util.*;Set t(int n){Set o=new TreeSet();for(int i=1;++i*i<n;)o.addAll(n%i<1?t(n+i-n/i):o);o.add(n);return o;}

Con algunos saltos de línea:

import java.util.*;
Set t(int n){
    Set o=new TreeSet();
    for(int i=1;++i*i<n;)
        o.addAll(n%i<1?t(n+i-n/i):o);
    o.add(n);
    return o;
}
Geobits
fuente
2

Octava, 107 96

function r=d(n)r=[n];a=find(!mod(n,2:sqrt(n-1)))+1;for(m=(a+n-n./a))r=unique([d(m) r]);end;end

Bonito estampado:

function r=d(n)
  r=[n];                          # include N in our list
  a=find(!mod(n,2:sqrt(n-1)))+1;  # gets a list of factors of a, up to (not including) sqrt(N)
  for(m=(a+n-n./a))               # each element of m is a twist
    r=unique([d(m) r]);           # recurse, sort, and find unique values
  end;
end
dcsohl
fuente
1
Tengo entendido que Octave puede terminar los bloques con solo en endlugar de endfory endfunction. Eso te ahorraría 11 bytes.
Alex A.
Oye, tienes razon! No cómo aprendí el idioma y nunca me di cuenta de que se podía hacer. ¿Por qué eres el primero en señalar esto después de haber hecho varios golf con él?
dcsohl
Solo lo sabía porque recientemente lo busqué después de verlo en el golf de otra persona con otra pregunta. Nunca he usado Octave y han pasado años desde que usé Matlab. Supongo que no hay tantos usuarios activos de Octave en PPCG, pero podría estar equivocado.
Alex A.
Bueno, gracias por señalarlo.
dcsohl
Un placer, me alegro de poder ayudar. Buena solución
Alex A.
1

Haskell, 102 100 bytes

import Data.List
d[]=[]
d(h:t)=h:d(t++[a*b-b+a|b<-[2..h],a<-[2..b],a*b==h])
p n=sort$nub$take n$d[n]

Uso: p 16 que salidas[7,10,16]

La función dcalcula 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 de 4s. Las funciones ptoman los primeros nelementos de esta lista, eliminan los duplicados y clasifican la lista. Voilà.

nimi
fuente
1

CJam - 36

ri_a\{_{:N,2>{NNImd!\I-z*-}fI}%|}*$p

Pruébalo en línea

O, método diferente:

ri_a\{_{_,2f#_2$4*f-&:mq:if-~}%|}*$p

Los escribí hace casi 2 días, me quedé atrapado a los 36 años, me frustré y me dormí sin publicar.

aditsu renunció porque SE es MALO
fuente