Números hostis do divisor

31

Alguns divisores de números inteiros positivos realmente se odeiam e não gostam de compartilhar um ou mais dígitos comuns.

Esses números inteiros são chamados de números de divisor hostis ( HDN )

Exemplos

O número 9566tem 4divisores: 1, 2, 4783 and 9566
(como você pode ver, nenhum deles compartilha o mesmo dígito ).
Assim, 9566 é um H ostile D iVisor N úmero

O número NÃO9567 é HDN porque seus divisores ( ) compartilham alguns dígitos comuns. 1, 3, 9, 1063, 3189, 9567

Aqui estão os primeiros 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...       


Tarefa

A lista acima continua e sua tarefa é encontrar o enésimo HDN

Entrada

Um número inteiro positivo nde 1a4000

Saída

O nth HDN

Casos de teste

Aqui estão alguns casos de teste indexados em 1 .
Indique qual sistema de indexação você usa em sua resposta para evitar confusão.

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

Isso é , então a pontuação mais baixa em bytes vence.

EDITAR

Boas notícias! Enviei minha sequência para o OEIS e ...
Os números dos divisores hostis agora são OEIS A307636

J42161217
fonte
1
Eu acho que os números quadrados seriam os menos hostis .
Frambot
3
@ JoeFrambach Isso eu não entendo. Há um HDN quadrado perfeito. Para um exemplo um tanto grande 94699599289, o quadrado de 307733, possui divisores [1, 307733, 94699599289]que mostram que é um HDN. Parece hostil para mim.
Jeppe Stig Nielsen
@JeppeStigNielsen Para um exemplo muito menor, por que não apenas 49? Fatores [1, 7, 49]qualifica como hostil ... ou, bem, 4: [1, 2, 4]...
Darrel Hoffman
@ DarrelHoffman Sem mencionar o número do quadrado 1com a lista do divisor [1]. (Talvez o HDN grande seja mais interessante?)
Jeppe Stig Nielsen
Eu interpretei 49como tendo divisores [7, 7] , que não apenas compartilham dígitos, mas são os mesmos dígitos. 49tem fatores [1, 7, 49]
Frambot

Respostas:

9

05AB1E , 12 10 bytes

µNNÑ€ÙSDÙQ

-2 bytes graças a @Emigna .

Indexado 1

Experimente online ou verifique a maioria dos casos de teste (os dois últimos casos são omitidos, pois atingem o tempo limite).

Explicação:

µ           # 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
fonte
2
Você me venceu desta vez. Eu tinha µNNÑ€ÙSDÙQpor 10.
Emigna
2
@ Emigna Ah, eu estava apenas trabalhando em uma alternativa µ, para que você me salve o problema. ;)
Kevin Cruijssen
isso é poeticamente eloquente
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

Experimente online!

Indexado a 0.

Erik, o Outgolfer
fonte
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")

Experimente online!

Versão mais 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}

Experimente online!

Quão?

Dado um número inteiro k>0 , construímos a string s como a concatenação de todos os divisores de k .

Como k é sempre um divisor de si mesmo, s é inicializado como k (coagido a uma string) e o primeiro divisor que tentamos é d=k1 .

dkdsd

Exemplos

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

Comentado

Esta é a versão sem eval(), para facilitar a leitura

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
fonte
6

Gelatina , 10 bytes

ÆDQ€FQƑµ#Ṫ

Experimente online!

-1 byte graças a ErikTheOutgolfer

Recebe informações do STDIN, o que é incomum para o Jelly, mas normal onde nfindé usado.

Æ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?

Indexado em 2

HyperNeutrino
fonte
isso é 2 indexado? Está tudo bem comigo, mas por favor indique para os outros
J42161217 03/05
Quaisquer que
3
Não, não é. 101 retorna 839. e 102 -> 853. Funciona bem, mas é indexado em 2
J42161217
1
@ J42161217 espera o que? Eu acho que quando mudei o nfindmudou a indexação lol
HyperNeutrino
1
⁼Q$é o mesmo que .
Erik the Outgolfer
4

Perl 6 , 53 bytes

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

Experimente online!

1 indexado.

/(.).*$0/ corresponde a qualquer número com um dígito repetido.

grep $_ %% *, 1 .. $_retorna uma lista de todos os divisores do número que $_está sendo verificado no momento para associação à lista.

[~]concatena todos esses dígitos juntos e, em seguida, R!~~combina a string à direita com o padrão à esquerda. ( ~~é o operador de correspondência usual, !~~é a negação desse operador e Ré um metaoperador que troca os argumentos de !~~.)

Sean
fonte
50 bytes
Jo King
4

Python 2 (PyPy) , 117 114 bytes

Usa indexação 1

k=input();n=0;r=range
while k:n+=1;k-=1-any(set(`a`)&set(`b`)for a in r(1,n+1)for b in r(1,a)if n%a<1>n%b)
print n

Experimente online!

ovs
fonte
3

Wolfram Language 103 bytes

Usa indexação 1. Estou surpreso por ter exigido muito 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
fonte
Você pode adicionar um link TIO para que todos possam verificar sua resposta?
J42161217
95 bytes: (n=t=1;While[t<=#,If[!Or@@IntersectingQ@@@Subsets[IntegerDigits@Divisors@n,{2}],t++];n++];n-1)&não estou planejando postar uma resposta, portanto deixarei isso aqui
J42161217
@ J42161217, estou tentando fazer com que o código funcione no TIO sem sucesso. Deve haver algum truque que estou perdendo.
DavidC
@ J42161217, seu código parece funcionar, mas leva três vezes o tempo de execução. Você pode enviá-lo como seu. (Talvez eu aprenda a implementar o TIO a partir do seu exemplo.)
DavidC
Muito rápido mesmo! aqui está o seu link Experimente online!
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

Experimente online!

Recebe entrada indexada em 1 $args[0], armazena isso em $a, faz um loop até que seja atingido 0. A cada iteração, zeramos uma matriz de dez elementos $z(usada para armazenar nossas contagens de dígitos). Então construímos nossa lista de divisores com 1..++$n|?{!($n%$_)}. Para cada divisor, convertemos para uma string "$_", toCharArra ye sortesses dígitos com o -usinalizador nique (porque não nos importamos se o próprio divisor possui dígitos duplicados). Em seguida, incrementamos a contagem de dígitos apropriada $z. Então, decrementamos $aapenas se $zcontiver 0s e 1s (ou seja, encontramos um HDN). Se terminamos nosso forloop, significa que encontramos o número apropriado de HDNs, então deixamos $no pipeline e a saída está implícita.

AdmBorkBork
fonte
você pode salvar alguns bytes: em $a-=!($z-ge2)vez disso$a-=!($z|?{$_-ge2})
mazzy
3

Python 3 , 115 bytes

Indexado 1

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

Experimente online!

Isso usa muita recursão; mesmo com o aumento do limite de recursão, não é possível f(30). Eu acho que pode ser ainda mais jogável, e tentei encontrar algo para substituir o (1-x%d), mas não consegui encontrar nada ( -~-x%dtem a precedência errada). Quaisquer bytes que possam ser raspados são muito apreciados.

Como 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
fonte
2

Braquilog (v2), 14 bytes

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

Experimente online!

Envio de função; entrada da esquerda, saída para a direita. (O link TIO contém um argumento de linha de comando para executar uma função como se fosse um programa completo.)

Explicação

"Esse é um número divisor hostil?" código do :

ℕ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

Isso acabou basicamente o mesmo que o do @ UnrelatedString, embora eu tenha escrito de forma independente.

Wrapper "nésima solução para um ":

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

Esse é um daqueles casos em que o wrapper necessário para produzir a enésima saída é significativamente maior que o código necessário para testar cada saída por vez :-)

Eu vim com esse invólucro independentemente do @ UnrelatedString. É do mesmo tamanho e funciona com o mesmo princípio, mas de alguma forma acaba sendo escrito de maneira bastante diferente. Ele tem mais possibilidades de aprimoramento, pois poderíamos adicionar restrições sobre quais valores estávamos procurando gratuitamente, substituindo-os Apor alguma variável de restrição, mas nenhuma das possíveis variáveis ​​de restrição salva bytes. (Se houvesse uma variável de restrição "número inteiro não negativo", você poderia substituí A-lo por ela e salvar um byte, tornando desnecessário.)

ais523
fonte
É 2 indexado?
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 em .matchesvez de .containspor dígito, inspirado na resposta JavaScript de @Arnauld .
-5 bytes graças a @ValueInk
-1 byte graças a @ceilingcat

Indexado 1

Experimente online.

Explicação:

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
fonte
1

Braquilog , 16 bytes

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

Experimente online!

Muito lento e o dobro do tempo, se isso fosse um . 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).
String não relacionada
fonte
1
Se você acabou de ler essa explicação como uma frase ...
FireCubez
Eu tento escrever minhas explicações como o inglês comum, que normalmente acaba dificultando a leitura
String não relacionada
1

Japt v2.0a0, 17 bytes

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

Tente

Porta desta resposta Brachylog .

Crédito: economia total de 4 bytes graças a Shaggy, que também sugeriu que havia uma solução melhor, levando a muito mais bytes :)


Resposta original abordagem de 28 bytes:

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

Tente

Porta desta resposta JavaScript .

dana
fonte
28 bytes
Shaggy
Bom - eu não tinha usado o «atalho antes :) Eu acho que se o Shaggy só estiver melhorando minha pontuação com um punhado de bytes, devo estar ficando (um pouco) decente nisso?
dana
Isso pode ser feito em 20 (talvez menos) b7, empregando um método ligeiramente diferente.
Shaggy
Hah - acho que falei cedo demais :) sim, alguns dos outros langs do golfe têm soluções muito mais curtas.
dana
1
17 bytes
Shaggy
0

Ícone , 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

Experimente online!

1 indexado. Muito lento para grandes entradas.

Galen Ivanov
fonte
0

Perl 6 , 74 bytes

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

Indexado a 0. Apenas os três primeiros casos estão listados no TIO, pois é muito lento para testar o restante.

Experimente online!

bb94
fonte
1
57 bytes
Jo King
0

Perl 5 -p , 66 bytes

map{1while(join$",map{$\%$_==0&&$_}1..++$\)=~/(\d).* .*\1/}1..$_}{

Experimente online!

1 indexado

Xcali
fonte
0

J , 87 59 bytes

-28 bytes graças ao FrownFrog

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

Experimente online!

original

J , 87 bytes

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

Experimente online!

Caramba.

Isso é atrozmente longo para J, mas não estou vendo ótimas maneiras de derrubá-lo.

explicação

Ajuda a introduzir alguns verbos auxiliares para ver o que está acontecendo:

d=.(]#~0=|~)1+i.
h=. [: (-:~.) [: -.&' '@,/ ~.@":"0
  • d retorna uma lista de todos os divisores de seu argumento
  • hdiz que essa lista é hostil. Ele especifica e deduplica cada número ~.@":"0, que retorna uma matriz quadrada na qual números mais curtos são preenchidos com espaços. -.&' '@,/nivela a matriz e remove espaços e, finalmente, (-:~.)informa se esse número se repete ou não.

Com esses dois ajudantes, nosso verbo não-gobrado se torna:

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

Aqui mantemos uma lista cuja cabeça é o nosso "candidato atual" (que começa em 1) e cuja cauda são todos os números hostis encontrados até agora.

Nós incrementamos o cabeçalho da lista >:@[em cada iteração e apenas anexamos o "candidato atual" se for hostil h@d@[ # [. Nós continuamos fazendo isso até que o nosso comprimento lista atinge 1 + n: ^:(#@] < 1 + [)^:_.

Finalmente, quando terminamos, retornamos o último número desta lista, [: {:que é o enésimo número hostil.

Jonah
fonte
66
FrownyFrog
62
FrownyFrog
Isso é ótimo, muito obrigado. Vai passar por isso e atualizar hoje à noite
Jonah
59
FrownyFrog