Números divisores hostiles

31

Algunos divisores de enteros positivos realmente se odian entre sí y no les gusta compartir uno o más dígitos comunes.

Esos números enteros se llaman Números Divisores Hostiles ( HDN )

Ejemplos

El número 9566tiene 4divisores: 1, 2, 4783 and 9566
(como puede ver, ninguno de ellos comparte el mismo dígito ).
Por lo tanto, 9566 es un H ostile D iVisor N umber

El número NO9567 es HDN porque sus divisores ( ) comparten algunos dígitos comunes. 1, 3, 9, 1063, 3189, 9567

Aquí están los primeros HDN

1,2,3,4,5,6,7,8,9,23,27,29,37,43,47,49,53,59,67,73,79,83,86,87,89,97,223,227,229,233,239,257,263,267,269,277,283,293,307,337...       


Tarea

La lista anterior continúa y su tarea es encontrar el enésimo HDN

Entrada

Un entero positivo nde 1a4000

Salida

El nth HDN

Casos de prueba

Aquí hay algunos casos de prueba indexados .
Indique qué sistema de indexación utiliza en su respuesta para evitar confusiones.

input -> output     
 1        1     
 10       23       
 101      853     
 1012     26053     
 3098     66686      
 4000     85009      

Este es el , por lo que gana la puntuación más baja en bytes.

EDITAR

¡Buenas noticias! Envié mi secuencia a OEIS y ...
Los números de divisor hostil ahora son OEIS A307636

J42161217
fuente
1
Creo que los números cuadrados serían los menos hostiles .
Frambot
3
@JoeFrambach Eso no lo entiendo. Hay HDN cuadrado perfecto. Para un ejemplo algo grande 94699599289, el cuadrado de 307733, tiene divisores [1, 307733, 94699599289]que muestran que es un HDN. Me parece hostil.
Jeppe Stig Nielsen
@JeppeStigNielsen Para un ejemplo mucho más pequeño, ¿por qué no solo 49? Factores [1, 7, 49]califica como hostil ... O bien, 4: [1, 2, 4]...
Darrel Hoffman
@DarrelHoffman Sin mencionar, el número cuadrado 1con la lista de divisores [1]. (¿Quizás las HDN grandes son más interesantes?)
Jeppe Stig Nielsen
Interpreté 49que tenía divisores [7, 7] , que no solo comparten dígitos, sino que son los mismos dígitos. 49tiene factores [1, 7, 49]
Frambot

Respuestas:

9

05AB1E , 12 10 bytes

µNNÑ€ÙSDÙQ

-2 bytes gracias a @Emigna .

1 indexado

Pruébelo en línea o verifique la mayoría de los casos de prueba (se omiten los dos últimos casos de prueba, ya que se agota el tiempo de espera).

Explicación:

µ           # Loop while the counter_variable is not equal to the (implicit) input yet:
 N          #  Push the 0-based index of the loop to the stack
  NÑ        #  Get the divisors of the 0-based index as well
            #   i.e. N=9566 → [1,2,4783,9566]
            #   i.e. N=9567 → [1,3,9,1063,3189,9567]
    €Ù      #  Uniquify the digits of each divisor
            #   → ["1","2","4783","956"]
            #   → ["1","3","9","1063","3189","9567"]
      S     #  Convert it to a flattened list of digits
            #   → ["1","2","4","7","8","3","9","5","6"]
            #   → ["1","3","9","1","0","6","3","3","1","8","9","9","5","6","7"]
       D    #  Duplicate this list
        Ù   #  Unique the digits
            #   → ["1","2","4","7","8","3","9","5","6"]
            #   → ["1","3","9","0","6","8","5","7"]
         Q  #  And check if it is still equal to the duplicated list
            #   → 1 (truthy)
            #   → 0 (falsey)
            #  And if it's truthy: implicitly increase the counter_variable by 1
            # (After the loop: implicitly output the top of the stack,
            #  which is the pushed index)
Kevin Cruijssen
fuente
2
Me ganaste esta vez. Tenía µNNÑ€ÙSDÙQpara 10.
Emigna
2
@Emigna Ah, solo estaba trabajando en una alternativa µ, así que me ahorraste el problema. ;)
Kevin Cruijssen
esto es poéticamente elocuente
don bright
7

Python 2 , 104 bytes

n=input()
x=1
while n: 
 x=i=x+1;d={0};c=1
 while i:m=set(`i`*(x%i<1));c*=d-m==d;d|=m;i-=1
 n-=c
print x

Pruébalo en línea!

0 indexado.

Erik el Outgolfer
fuente
6

JavaScript (ES6), 78 bytes

1 indexado.

n=>eval("for(k=0;n;n-=!d)for(s=d=++k+'';k%--d||d*!s.match(`[${s+=d,d}]`););k")

Pruébalo en línea!

Versión más rápida, 79 bytes.

n=>{for(k=0;n;n-=!d)for(s=d=++k+'';k%--d||d*!s.match(`[${s+=d,d}]`););return k}

Pruébalo en línea!

¿Cómo?

Dado un entero k>0 , construimos la cadena s como la concatenación de todos los divisores de k .

Debido a que k siempre es un divisor de sí mismo, s se inicializa en k (forzado a una cadena) y el primer divisor que intentamos es d=k1 .

Para cada divisor d de k , probamos si se puede encontrar cualquier dígito de d en s al convertir d en un conjunto de caracteres en una expresión regular.

Ejemplos

  • s="956647832" ,d=1"956647832".match(/[1]/)es falso
  • s="9567" ,d=3189"9567".match(/[3189]/)es verdadero

Comentado

Esta es la versión sin eval(), para facilitar la lectura

n => {                   // n = input
  for(                   // for() loop:
    k = 0;               //   start with k = 0
    n;                   //   go on until n = 0
    n -= !d              //   decrement n if the last iteration resulted in d = 0
  )                      //
    for(                 //   for() loop:
      s =                //     start by incrementing k and
      d = ++k + '';      //     setting both s and d to k, coerced to a string
      k % --d ||         //     decrement d; always go on if d is not a divisor of k
      d *                //     stop if d = 0
      !s.match(          //     stop if any digit of d can be found in s
        `[${s += d, d}]` //     append d to s
      );                 //
    );                   //   implicit end of inner for() loop
                         // implicit end of outer for() loop
  return k               // return k
}                        //
Arnauld
fuente
6

Jalea , 10 bytes

ÆDQ€FQƑµ#Ṫ

Pruébalo en línea!

-1 byte gracias a ErikTheOutgolfer

Toma información de STDIN, lo cual es inusual para Jelly pero normal donde nfindse usa.

ÆDQ€FQƑµ#Ṫ  Main link
         Ṫ  Get the last element of
        #   The first <input> elements that pass the filter:
ÆD          Get the divisors
  Q€        Uniquify each (implicitly converts a number to its digits)
    F       Flatten the list
     QƑ     Does that list equal itself when deduplicated?

2 indexados

Hiperneutrino
fuente
¿Es esto 2 indexado? Está bien conmigo, pero
dígalo
Sean cuales sean sus casos de prueba, así que 1
HyperNeutrino
3
No, no lo es. 101 devuelve 839. y 102 -> 853. Funciona bien pero está indexado en 2
J42161217
1
@ J42161217 espera qué? Supongo que cuando me mudé nfindcambió la indexación jajaja
HyperNeutrino
1
⁼Q$es el mismo que .
Erik the Outgolfer
4

Perl 6 , 53 bytes

{(grep {/(.).*$0/R!~~[~] grep $_%%*,1..$_},^∞)[$_]}

Pruébalo en línea!

1 indexado.

/(.).*$0/ coincide con cualquier número con un dígito repetido.

grep $_ %% *, 1 .. $_devuelve una lista de todos los divisores del número $_que se está comprobando actualmente para la pertenencia a la lista

[~]concatena todos esos dígitos y luego hace R!~~coincidir la cadena de la derecha con el patrón de la izquierda. ( ~~es el operador de coincidencia habitual, !~~es la negación de ese operador y Res un metaoperador que intercambia los argumentos de !~~).

Sean
fuente
50 bytes
Jo King
3

Wolfram Language 103 bytes

Utiliza 1-indexación. Me sorprende que requiriera tanto código.

(k=1;u=Union;n=2;l=Length;While[k<#,If[l[a=Join@@u/@IntegerDigits@Divisors@#]==l@u@a&@n,k++];n++];n-1)&
DavidC
fuente
¿Puede agregar un enlace TIO para que todos puedan verificar su respuesta?
J42161217
95 bytes: (n=t=1;While[t<=#,If[!Or@@IntersectingQ@@@Subsets[IntegerDigits@Divisors@n,{2}],t++];n++];n-1)&no estoy planeando publicar una respuesta, así que dejaré esto aquí
J42161217
@ J42161217, he estado intentando que el código funcione en TIO sin éxito. Debe haber algún truco que me estoy perdiendo.
DavidC
@ J42161217, su código parece funcionar pero tarda 3 veces el tiempo de ejecución. Puedes enviarlo como tuyo. (Tal vez aprenderé cómo implementar TIO a partir de su ejemplo.)
DavidC
Muy rápido de hecho! aquí está tu enlace Pruébalo en línea!
J42161217
3

PowerShell , 112 bytes

for($a=$args[0];$a-gt0){$z=,0*10;1..++$n|?{!($n%$_)}|%{"$_"|% t*y|sort -u|%{$z[+"$_"]++}};$a-=!($z|?{$_-ge2})}$n

Pruébalo en línea!

Toma una entrada indexada $args[0], la almacena en$a bucle hasta que llega 0. Cada iteración, ponemos a cero una matriz de diez elementos $z(utilizada para mantener nuestros recuentos de dígitos). Luego construimos nuestra lista de divisores con 1..++$n|?{!($n%$_)}. Para cada divisor, lo convertimos en una cadena "$_", lo tconvertimos en oCharArra yy sortesos dígitos con la -ubandera de nique (porque no nos importa si un divisor en sí tiene dígitos duplicados). Luego incrementamos el recuento de dígitos apropiado en $z. Luego, disminuimos $asolo si $zcontiene 0sys 1(es decir, hemos encontrado un HDN). Si hemos terminado nuestro forciclo, eso significa que hemos encontrado el número apropiado de HDN, por lo que lo dejamos $nen la tubería y la salida es implícita.

AdmBorkBork
fuente
podría guardar algunos bytes: en su $a-=!($z-ge2)lugar$a-=!($z|?{$_-ge2})
mazzy
3

Python 3 , 115 bytes

1 indexado

f=lambda n,x=1,s="",l="",d=1:n and(d>x+1and f(n-1,x+1)or{*s}&{*l}and f(n,x+1)or f(n,x,s+l,(1-x%d)*str(d),d+1))or~-x

Pruébalo en línea!

Esto usa mucha recursividad; incluso con un mayor límite de recursión, no puede hacerlo f(30). Creo que podría ser más fácil de jugar, e intenté encontrar algo para reemplazarlo (1-x%d), pero no pude encontrar nada ( -~-x%dtiene la precedencia incorrecta). Cualquier byte que pueda eliminarse es muy apreciado.

Cómo funciona

# n: HDNs to go
# x: Currently tested number
# s: String of currently seen divisor digits
# l: String of digits of last tried divisor if it was a divisor, empty string otherwise
# d: Currently tested divisor

f=lambda n,x=1,s="",l="",d=1:n and(                    # If there are still numbers to go
                             d>x+1and f(n-1,x+1)or     # If the divisors have been
                                                       #  exhausted, a HDN has been found
                             {*s}&{*l}and f(n,x+1)or   # If there were illegal digits in
                                                       #  the last divisor, x isn't a HDN
                             f(n,x,s+l,(1-x%d)*str(d),d+1)
                                                       # Else, try the next divisor, and
                                                       #  check this divisor's digits (if
                                                       #  if is one) in the next call
                             )or~-x                    # Else, return the answer
ArBo
fuente
2

Brachylog (v2), 14 bytes

;A{ℕfdᵐc≠&}ᶠ⁽t

Pruébalo en línea!

Presentación de funciones; entrada desde la izquierda, salida hacia la derecha. (El enlace TIO contiene un argumento de línea de comandos para ejecutar una función como si fuera un programa completo).

Explicación

"¿Es este un número divisor hostil?" código de :

ℕfdᵐc≠
ℕ       number is ≥0 (required to match the question's definition of "nth solution")
 f      list of all factors of the number
   ᵐ    for each factor
  d       deduplicate its digits
    c   concatenate all the deduplications with each other
     ≠  the resulting number has no repeated digits

Esto resultó básicamente lo mismo que @ UnrelatedString, aunque lo escribí de forma independiente.

Contenedor "enésima solución a un ":

;A{…&}ᶠ⁽t
    &      output the successful input to
  {  }ᶠ    the first n solutions of the problem
       ⁽   taking <n, input> as a pair
;A         form a pair of user input and a "no constraints" value
        t  take the last solution (of those first n)

Este es uno de esos casos donde el contenedor requerido para producir la enésima salida es significativamente más largo que el código requerido para probar cada salida a su vez :-)

Se me ocurrió este envoltorio independientemente de @ UnrelatedString's. Tiene la misma longitud y funciona con el mismo principio, pero de alguna manera termina siendo escrito de manera bastante diferente. Tiene más posibilidades potenciales de mejora, ya que podríamos agregar restricciones a los valores que estábamos buscando de forma gratuita mediante el reemplazo de Aalguna variable de restricción, pero ninguna de las posibles variables de restricción guarda bytes. (Si hubiera una variable de restricción de "entero no negativo", podría reemplazarla Apor ella y luego guardar un byte haciendo innecesario el valor).

ais523
fuente
¿Está indexado en 2?
FrownyFrog
2

Java 10, 149 139 138 126 125 120 119 bytes

n->{int r=0,i,d;for(;n>0;n-=d){var s="1";for(r+=d=i=1;i++<r;)if(r%i<1){d=s.matches(".*["+i+"].*")?0:d;s+=i;}}return r;}

-10 bytes usando en .matcheslugar de .containspor dígito, inspirado en la respuesta JavaScript de @Arnauld .
-5 bytes gracias a @ValueInk
-1 byte gracias a @ceilingcat

1 indexado

Pruébalo en línea.

Explicación:

n->{                 // Method with integer as both parameter and return-type
  int r=0,           //  Result-integer, starting at 0
      i,             //  Index integer
      d;             //  Decrement integer
  for(;n>0;          //  Loop until the input `n` is 0:
      n-=d){         //    After every iteration: decrease `n` by the decrement integer `d`
    var s="1";       //   Create a String `s`, starting at "1"
    for(r+=d=i=1;    //   (Re)set the decrement and index integers to 1,
                     //   and increase the result by 1 as well
        i++<r;)      //   Inner loop `i` in the range [2, r]:
      if(r%i<1){     //    If `r` is divisible by `i`:
        d=s.matches(".*["+i+"].*")?
                     //     If string `s` contains any digits also found in integer `i`:
           0         //      Set the decrement integer `d` to 0
          :d;        //     Else: leave `d` unchanged
        s+=i;}}      //     And then append `i` to the String `s`
  return r;}         //  After the loops, return the result `r`
Kevin Cruijssen
fuente
1

Brachylog , 16 bytes

g{∧0<.fdᵐc≠∧}ᵘ⁾t

Pruébalo en línea!

Muy lento, y el doble de lo que sería si esto fuera un . 1 indexado.

                    The output
               t    is the last
             ᵘ⁾     of a number of unique outputs,
g                   where that number is the input,
 {          }       from the predicate declaring that:
     .              the output
    <               which is greater than
   0                zero
  ∧                 (which is not the empty list)
      f             factorized
        ᵐ           with each factor individually
       d            having duplicate digits removed
          ≠         has no duplicate digits in
         c          the concatenation of the factors
           ∧        (which is not the output).
Cadena no relacionada
fuente
1
Si acabas de leer esa explicación como una oración ...
FireCubez
Trato de escribir mis explicaciones como un inglés simple, que generalmente termina haciendo que sean más difíciles de leer
Cadena no relacionada
1

Japt v2.0a0, 17 bytes

_=â ®sâìUµZ¶â}f1

Intentalo

Puerto de esta respuesta Brachylog .

Crédito: 4 bytes de ahorro total gracias a Shaggy, quien también sugirió que había una mejor solución que conducía a muchos más bytes :)


Respuesta original Enfoque de 28 bytes:

Èâ¬rÈ«è"[{Y}]" ©X+Y}Xs)«U´Ãa

Intentalo

Puerto de esta respuesta de JavaScript .

dana
fuente
28 bytes
Shaggy
Agradable: no había usado el «atajo antes :) Me imagino que si Shaggy solo mejora mi puntaje en un puñado de bytes, ¿debo estar (algo) decente en esto?
dana
Se puede hacer en 20 (quizás menos) b7 empleando un método ligeramente diferente.
Shaggy
Ja, supongo que hablé demasiado pronto :) sí, algunos de los otros jugadores de golf tienen soluciones mucho más cortas.
dana
1
17 bytes
Shaggy
0

Icono , 123 bytes

procedure f(n)
k:=m:=0
while m<n do{
k+:=1
r:=0
s:=""
every k%(i:=1 to k)=0&(upto(i,s)&r:=1)|s++:=i
r=0&m+:=1}
return k
end

Pruébalo en línea!

1 indexado. Muy lento para grandes entradas.

Galen Ivanov
fuente
0

Perl 6 , 74 bytes

{(grep {!grep *>1,values [(+)] map *.comb.Set,grep $_%%*,1..$_},1..*)[$_]}

0 indexado. Solo los primeros tres casos se enumeran en TIO ya que es demasiado lento para probar el resto.

Pruébalo en línea!

bb94
fuente
1
57 bytes
Jo King
0

J , 87 59 bytes

-28 bytes gracias a FrownFrog

0{(+1,1(-:~.)@;@(~.@":&.>@,i.#~0=i.|])@+{.)@]^:(>{:)^:_&0 0

Pruébalo en línea!

original

J , 87 bytes

[:{:({.@](>:@[,],([:(-:~.)[:-.&' '@,/~.@":"0)@((]#~0=|~)1+i.)@[#[)}.@])^:(#@]<1+[)^:_&1

Pruébalo en línea!

Yikes

Esto es atrozmente largo para J, pero no veo grandes maneras de derribarlo.

explicación

Ayuda a introducir un par de verbos auxiliares para ver qué sucede:

d=.(]#~0=|~)1+i.
h=. [: (-:~.) [: -.&' '@,/ ~.@":"0
  • d devuelve una lista de todos los divisores de su argumento
  • hte dice que tal lista es hostil. Encadena y deduplica cada número ~.@":"0, lo que devuelve una matriz cuadrada donde los números más cortos se rellenan con espacios. -.&' '@,/aplana la matriz y elimina espacios, y finalmente (-:~.)te dice si ese número se repite o no.

Con esos dos ayudantes, nuestro verbo general sin golf se convierte:

[: {: ({.@] (>:@[ , ] , h@d@[ # [) }.@])^:(#@] < 1 + [)^:_&1

Aquí mantenemos una lista cuya cabeza es nuestro "candidato actual" (que comienza en 1), y cuya cola son todos los números hostiles encontrados hasta ahora.

Incrementamos el encabezado de la lista >:@[en cada iteración y solo agregamos el "candidato actual" si es hostil h@d@[ # [. Seguimos haciendo esto hasta que la longitud de nuestra lista alcance 1 + n:^:(#@] < 1 + [)^:_ .

Finalmente, cuando terminamos, devolvemos el último número de esta lista, [: {:que es el enésimo número hostil.

Jonás
fuente
66
FrownyFrog
62
FrownyFrog
Esto es genial, muchas gracias. Lo revisaremos y actualizaremos esta noche
Jonás
59
FrownyFrog