Numéros de diviseurs hostiles

31

Certains diviseurs d'entiers positifs se détestent vraiment et ils n'aiment pas partager un ou plusieurs chiffres communs.

Ces nombres entiers sont appelés nombres de diviseurs hostiles ( HDN )

Exemples

Le nombre 9566a des 4diviseurs: 1, 2, 4783 and 9566
(comme vous pouvez le voir, deux d'entre eux ne partagent pas le même chiffre ).
Ainsi, 9566 est un H ostile D iVisor N mbre

Le nombre 9567n'est PAS HDN car ses diviseurs ( 1, 3, 9, 1063, 3189, 9567) partagent des chiffres communs.

Voici les premiers 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...       


Tâche

La liste ci-dessus continue et votre tâche est de trouver le nième HDN

Contribution

Un entier positif nde 1à4000

Sortie

Le nth HDN

Cas de test

voici quelques cas de test indexés 1 .
Veuillez indiquer le système d'indexation que vous utilisez dans votre réponse pour éviter toute confusion.

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

C'est le , donc le score le plus bas en octets l'emporte.

MODIFIER

Bonnes nouvelles! J'ai soumis ma séquence à OEIS et ...
Les numéros de diviseurs hostiles sont maintenant OEIS A307636

J42161217
la source
1
Je pense que les nombres carrés seraient les moins hostiles .
Frambot
3
@JoeFrambach Que je ne comprends pas. Il existe un HDN carré parfait. Pour un exemple assez grand 94699599289, le carré de 307733, a des diviseurs [1, 307733, 94699599289]qui montrent que c'est un HDN. Cela me semble hostile.
Jeppe Stig Nielsen
@JeppeStigNielsen Pour un exemple beaucoup plus petit, pourquoi pas juste 49? Les facteurs [1, 7, 49]sont considérés comme hostiles ... Ou bien, ... 4:[1, 2, 4]
Darrel Hoffman
@DarrelHoffman Sans oublier le nombre carré 1avec la liste des diviseurs [1]. (Peut-être que les grands HDN sont plus intéressants?)
Jeppe Stig Nielsen
J'ai interprété 49comme ayant des diviseurs [7, 7] , qui non seulement partagent des chiffres mais sont les mêmes chiffres. 49a des facteurs [1, 7, 49]
Frambot

Réponses:

9

05AB1E , 12 10 octets

µNNÑ€ÙSDÙQ

-2 octets grâce à @Emigna .

1 indexé

Essayez-le en ligne ou vérifiez la plupart des cas de test (les deux derniers cas de test sont omis, car ils expirent).

Explication:

µ           # 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
la source
2
Tu m'as battu cette fois. J'en avais µNNÑ€ÙSDÙQpour 10.
Emigna
2
@Emigna Ah, je travaillais juste sur une alternative avec µ, alors tu me sauves la peine. ;)
Kevin Cruijssen
c'est poétiquement éloquent
Don Bright
7

Python 2 , 104 octets

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

Essayez-le en ligne!

0 indexé.

Erik le golfeur
la source
6

JavaScript (ES6), 78 octets

1 indexé.

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

Essayez-le en ligne!

Version plus rapide, 79 octets

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

Essayez-le en ligne!

Comment?

Étant donné un entier k>0 , nous construisons la chaîne s comme la concaténation de tous les diviseurs de k .

Parce que k est toujours un diviseur de lui-même, s est initialisé à k (contraint à une chaîne) et le premier diviseur que nous essayons est d=k1 .

Pour chaque diviseur d de k , nous testons si un chiffre de d peut être trouvé dans s en transformant d en un jeu de caractères dans une expression régulière.

Exemples

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

Commenté

Ceci est la version sans eval(), pour plus de lisibilité

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
la source
6

Gelée , 10 octets

ÆDQ€FQƑµ#Ṫ

Essayez-le en ligne!

-1 octet grâce à ErikTheOutgolfer

Prend l'entrée de STDIN, ce qui est inhabituel pour Jelly mais normal où nfindest utilisé.

Æ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 indexés

HyperNeutrino
la source
est-ce 2 indexé? C'est ok avec moi mais veuillez le dire pour les autres
J42161217
C'est quoi que vos cas de test étaient, donc 1
HyperNeutrino
3
Non ça ne l'est pas. 101 renvoie 839. et 102 -> 853. Cela fonctionne bien mais il est indexé 2
J42161217
1
@ J42161217 attendez quoi? je suppose que quand j'ai déplacé le nfindil a changé l'indexation lol
HyperNeutrino
1
⁼Q$est le même que .
Erik the Outgolfer
4

Perl 6 , 53 octets

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

Essayez-le en ligne!

1 indexé.

/(.).*$0/ correspond à n'importe quel nombre avec un chiffre répété.

grep $_ %% *, 1 .. $_renvoie une liste de tous les diviseurs du nombre $_en cours de vérification d'appartenance à la liste.

[~]concatène tous ces chiffres ensemble, puis fait R!~~correspondre la chaîne de droite avec le modèle de gauche. ( ~~est l'opérateur de correspondance habituel, !~~est la négation de cet opérateur et Rest un méta-opérateur qui permute les arguments de !~~.)

Sean
la source
50 octets
Jo King
4

Python 2 (PyPy) , 117 114 octets

Utilise l'indexation 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

Essayez-le en ligne!

ovs
la source
3

Langue Wolfram 103 octets

Utilise l'indexation 1. Je suis surpris qu'il ait fallu autant de code.

(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
la source
Pouvez-vous s'il vous plaît ajouter un lien TIO afin que tout le monde puisse vérifier votre réponse?
J42161217
95 octets: (n=t=1;While[t<=#,If[!Or@@IntersectingQ@@@Subsets[IntegerDigits@Divisors@n,{2}],t++];n++];n-1)&je n'ai pas l'intention de poster une réponse, je vais donc laisser ceci ici
J42161217
@ J42161217, j'ai essayé de faire fonctionner le code dans TIO sans succès. Il doit y avoir un truc qui me manque.
DavidC
@ J42161217, votre code semble fonctionner mais prend 3 fois le temps d'exécution. Vous pouvez le soumettre comme le vôtre. (Peut-être que j'apprendrai comment implémenter TIO à partir de votre exemple.)
DavidC
Très rapide en effet! voici votre lien Essayez-le en ligne!
J42161217
3

PowerShell , 112 octets

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

Essayez-le en ligne!

Prend une entrée indexée 1 $args[0], la stocke dans $a, boucle jusqu'à ce qu'elle frappe 0. À chaque itération, nous remettons à zéro un tableau à dix éléments $z(utilisé pour contenir nos chiffres). Ensuite, nous construisons notre liste de diviseurs avec 1..++$n|?{!($n%$_)}. Pour chaque diviseur, nous le convertissons en une chaîne "$_", le ttranscrivons en oCharArra yet sortces chiffres avec le -udrapeau nique (parce que nous ne nous soucions pas si un diviseur lui-même a des chiffres en double). Nous incrémentons ensuite le nombre de chiffres approprié dans $z. Ensuite, nous décrémentons $auniquement si $zcontient 0s et 1s (c'est-à-dire que nous avons trouvé un HDN). Si nous avons terminé notre forboucle, cela signifie que nous avons trouvé le nombre approprié de HDN, donc nous laissons $nle pipeline et la sortie est implicite.

AdmBorkBork
la source
vous pourriez économiser quelques octets: à la $a-=!($z-ge2)place$a-=!($z|?{$_-ge2})
mazzy
3

Python 3 , 115 octets

1 indexé

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

Essayez-le en ligne!

Cela utilise beaucoup de récursivité; même avec une limite de récursivité accrue, cela ne peut pas f(30). Je pense que cela pourrait être golfable plus loin, et j'ai essayé de trouver quelque chose pour remplacer le (1-x%d), mais je n'ai rien trouvé (-~-x%d a la mauvaise priorité). Tous les octets qui peuvent être rasés sont grandement appréciés.

Comment ça marche

# 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
la source
2

Brachylog (v2), 14 octets

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

Essayez-le en ligne!

Soumission de fonction; entrée par la gauche, sortie par la droite. (Le lien TIO contient un argument de ligne de commande pour exécuter une fonction comme s'il s'agissait d'un programme complet.)

Explication

"Est-ce un nombre diviseur hostile?" code 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

Cela s'est avéré fondamentalement le même que celui de @ UnrelatedString, bien que je l'ai écrit indépendamment.

wrapper "nième solution à 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)

C'est l'un de ces cas où l'encapsuleur requis pour produire la nième sortie est beaucoup plus long que le code requis pour tester chaque sortie à son tour :-)

J'ai trouvé ce wrapper indépendamment de @ UnrelatedString. C'est la même longueur et fonctionne sur le même principe, mais finit en quelque sorte par être écrit assez différemment. Il a plus de possibilités d'amélioration, car nous pourrions ajouter des contraintes sur les valeurs que nous regardions gratuitement en remplaçant la Apar une variable de contrainte, mais aucune des variables de contrainte possibles n'économise d'octets. (S'il y avait une variable de contrainte "entier non négatif", vous pouvez remplacer le Apar, puis enregistrer un octet en rendant le inutile.)

ais523
la source
C'est indexé 2?
FrownyFrog
2

Java 10, 149 139 138 138 125 125 120 119 octets

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 octets en utilisant .matchesau lieu de .containspar chiffre, inspiré par la réponse JavaScript de @Arnauld .
-5 octets grâce à @ValueInk
-1 octet grâce à @ceilingcat

1 indexé

Essayez-le en ligne.

Explication:

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
la source
1

Brachylog , 16 octets

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

Essayez-le en ligne!

Très lent, et deux fois plus long que s'il s'agissait d'un . 1 indexé.

                    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).
Chaîne non liée
la source
1
Si vous lisez juste cette explication comme une phrase ...
FireCubez
J'essaie d'écrire mes explications comme un anglais simple, ce qui finit généralement par les rendre plus difficiles à lire
Chaîne non liée
1

Japt v2.0a0, 17 octets

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

L'essayer

Port de cette réponse Brachylog .

Crédit: 4 octets d'économies au total grâce à Shaggy qui a également suggéré qu'il y avait une meilleure solution conduisant à beaucoup plus d'octets :)


Réponse originale approche de 28 octets:

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

L'essayer

Port de cette réponse JavaScript .

Dana
la source
28 octets
Shaggy
Bien - je n'avais pas utilisé le «raccourci auparavant :) Je pense que si Shaggy ne fait qu'améliorer mon score de quelques octets, je dois être (un peu) décent à ce sujet?
dana
Cela peut être fait en 20 (peut-être moins) b7 en utilisant une méthode légèrement différente.
Shaggy
Hah - je suppose que j'ai parlé trop tôt :) ouais, certains des autres lang de golf ont des solutions beaucoup plus courtes.
dana
1
17 octets
Shaggy
0

Icône , 123 octets

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

Essayez-le en ligne!

1 indexé. Vraiment lent pour les grosses entrées.

Galen Ivanov
la source
0

Perl 6 , 74 octets

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

0 indexé. Seuls les trois premiers cas sont répertoriés sur TIO car il est trop lent pour tester le reste.

Essayez-le en ligne!

bb94
la source
1
57 octets
Jo King
0

Perl 5 -p , 66 octets

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

Essayez-le en ligne!

1 indexé

Xcali
la source
0

J , 87 59 octets

-28 octets grâce à FrownFrog

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

Essayez-le en ligne!

original

J , 87 octets

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

Essayez-le en ligne!

Beurk.

C'est atrocement long pour J, mais je ne vois pas de bons moyens de le faire baisser.

explication

Cela aide à introduire quelques verbes auxiliaires pour voir ce qui se passe:

d=.(]#~0=|~)1+i.
h=. [: (-:~.) [: -.&' '@,/ ~.@":"0
  • d renvoie une liste de tous les diviseurs de son argument
  • hvous dit qu'une telle liste est hostile. Il stringifie et dédoublonne chaque nombre ~.@":"0, ce qui renvoie une matrice carrée où les nombres plus courts sont remplis d'espaces. -.&' '@,/aplatit la matrice et supprime les espaces, et (-:~.)vous indique enfin si ce nombre s'est répété ou non.

Avec ces deux aides, notre verbe global et non-golfé devient:

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

Ici, nous maintenons une liste dont la tête est notre "candidat actuel" (qui commence à 1), et dont la queue est tous les nombres hostiles trouvés jusqu'à présent.

Nous incrémentons la tête de liste >:@[à chaque itération, et nous ajoutons le "candidat actuel" uniquement s'il est hostile h@d@[ # [. Nous continuons ainsi jusqu'à ce que la longueur de notre liste atteigne 1 + n:^:(#@] < 1 + [)^:_ .

Enfin, lorsque nous avons terminé, nous renvoyons le dernier numéro de cette liste [: {:qui est le nième numéro hostile.

Jonas
la source
66
FrownyFrog
62
FrownyFrog
C'est super, merci beaucoup. J'y reviendrai et je mettrai à jour ce soir
Jonah
59
FrownyFrog