Feindliche Divisorenzahlen

31

Einige Teiler positiver Ganzzahlen hassen sich wirklich und teilen nicht gerne eine oder mehrere gemeinsame Ziffern.

Diese ganzen Zahlen heißen Hostile Divisor Numbers ( HDN )

Beispiele

Die Zahl 9566hat 4Teiler: 1, 2, 4783 and 9566
(Wie Sie sehen, haben keine zwei die gleiche Ziffer ).
Somit ist 9566 ein H- Ostil D ivisor N umber

Nummer 9567ist NICHT HDN da die Teiler ( 1, 3, 9, 1063, 3189, 9567) einige gemeinsame Ziffern haben.

Hier sind die ersten paar 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...       


Aufgabe

Die obige Liste geht weiter und Ihre Aufgabe ist es, den n-ten HDN zu finden

Eingang

Eine positive ganze Zahl nvon 1bis4000

Ausgabe

Der nth HDN

Testfälle

Hier sind einige 1-indizierte Testfälle.
Bitte geben Sie an, welches Indexsystem Sie in Ihrer Antwort verwenden, um Verwirrung zu vermeiden.

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

Das ist , also gewinnt die niedrigste Punktzahl in Bytes.

BEARBEITEN

Gute Nachrichten! Ich habe meine Sequenz bei OEIS eingereicht und ... Die
feindlichen Divisorennummern lauten jetzt OEIS A307636

J42161217
quelle
1
Ich denke, quadratische Zahlen wären die am wenigsten feindlichen Zahlen.
Frambot
3
@ JoeFrambach Das verstehe ich nicht. Es gibt perfekt quadratische HDN. Für ein etwas größeres Beispiel hat 94699599289das Quadrat von 307733Teiler, [1, 307733, 94699599289]was zeigt, dass es sich um ein HDN handelt. Scheint mir feindlich zu sein.
Jeppe Stig Nielsen
@JeppeStigNielsen Für ein viel kleineres Beispiel, warum nicht einfach 49? Faktoren [1, 7, 49]qualifizieren sich als feindselig ... Oder 4: [1, 2, 4]...
Darrel Hoffman
@ DarrelHoffman Ganz zu schweigen von der Quadratzahl 1mit Teilerliste [1]. (Vielleicht sind große HDN interessanter?)
Jeppe Stig Nielsen
Ich interpretierte dies 49als Divisoren [7, 7] , die nicht nur Ziffern teilen, sondern die gleichen Ziffern sind. 49hat Faktoren [1, 7, 49]
Frambot

Antworten:

9

05AB1E , 12 10 Bytes

µNNÑ€ÙSDÙQ

-2 Bytes dank @Emigna .

1-indiziert

Probieren Sie es online aus oder überprüfen Sie die meisten Testfälle (die letzten beiden Testfälle werden ausgelassen, da sie eine Zeitüberschreitung aufweisen).

Erläuterung:

µ           # 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
quelle
2
Du hast mich diesmal geschlagen. Ich hatte µNNÑ€ÙSDÙQfür 10.
Emigna
2
@Emigna Ah, ich habe gerade an einer Alternative mitgearbeitet µ, damit du mir die Mühe ersparst . ;)
Kevin Cruijssen
das ist poetisch eloquent
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

Probieren Sie es online!

0-indiziert.

Erik der Outgolfer
quelle
6

JavaScript (ES6), 78 Byte

1-indiziert.

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

Probieren Sie es online!

Schnellere Version, 79 Bytes

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

Probieren Sie es online!

Wie?

Bei einer Ganzzahl k>0 bilden wir den String s als Verkettung aller Teiler von k .

Da k immer ein Teiler von sich selbst ist, wird s mit k initialisiert (zu einem String gezwungen) und der erste Teiler, den wir versuchen, ist d=k1 .

Für jeden Teiler d von k , prüfen wir , ob eine beliebige Ziffer von d finden Sie in s durch Drehen d in einen Zeichensatz in einem regulären Ausdruck umwandeln.

Beispiele

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

Kommentiert

Dies ist die Version ohne eval(), für die Lesbarkeit

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

Gelee , 10 Bytes

ÆDQ€FQƑµ#Ṫ

Probieren Sie es online!

-1 Byte dank ErikTheOutgolfer

Nimmt Eingaben von STDIN auf, was für Jelly ungewöhnlich ist, aber bei nfindVerwendung normal ist.

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

HyperNeutrino
quelle
ist das 2-indiziert? Es ist in
Ordnung
Es ist wie auch immer Ihre Testfälle waren, also 1
HyperNeutrino
3
Nein, ist es nicht. 101 gibt 839 zurück und 102 -> 853. Es funktioniert gut, aber es ist 2-indiziert
J42161217
1
@ J42161217 was warten? ich schätze, als ich das bewegte nfind, änderte es die Indexierung lol
HyperNeutrino
1
⁼Q$ist das gleiche wie .
Erik der Outgolfer
4

Perl 6 , 53 Bytes

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

Probieren Sie es online!

1-indiziert.

/(.).*$0/ Entspricht einer beliebigen Zahl mit einer wiederholten Ziffer.

grep $_ %% *, 1 .. $_Gibt eine Liste aller Teiler der Nummer zurück, die $_derzeit auf Mitgliedschaft in der Liste überprüft werden.

[~]Verkettet alle diese Ziffern miteinander und vergleicht dann R!~~die Zeichenfolge rechts mit dem Muster links. ( Ist ~~der übliche Übereinstimmungsoperator, !~~ist die Negation dieses Operators und Rist ein Metaoperator, der die Argumente von vertauscht !~~.)

Sean
quelle
50 Bytes
Jo King
4

Python 2 (PyPy) , 117 114 Byte

Verwendet 1-Indizierung

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

Probieren Sie es online!

ovs
quelle
3

Wolfram Language 103 Bytes

Verwendet 1-Indizierung. Ich bin überrascht, dass so viel Code erforderlich ist.

(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
quelle
Können Sie bitte einen TIO-Link hinzufügen, damit jeder Ihre Antwort überprüfen kann?
J42161217
95 Bytes: (n=t=1;While[t<=#,If[!Or@@IntersectingQ@@@Subsets[IntegerDigits@Divisors@n,{2}],t++];n++];n-1)&Ich habe nicht vor, eine Antwort zu posten, daher lasse ich diese hier
J42161217
@ J42161217, Ich habe versucht, den Code in TIO zum Laufen zu bringen, ohne Erfolg. Es muss einen Trick geben, den ich vermisse.
DavidC
@ J42161217, Ihr Code scheint zu funktionieren, benötigt jedoch die dreifache Laufzeit. Sie können es als Ihr eigenes einreichen. (Vielleicht lerne ich
anhand
Sehr schnell! hier ist dein link Online ausprobieren!
J42161217
3

PowerShell , 112 Byte

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

Probieren Sie es online!

Nimmt 1-indizierte Eingaben auf $args[0], speichert diese in $aSchleifen, bis diese treffen 0. Bei jeder Iteration wird ein Array mit zehn Elementen auf Null gesetzt $z(verwendet, um unsere Stellenzahlen zu speichern). Dann konstruieren wir unsere Liste der Teiler mit 1..++$n|?{!($n%$_)}. Für jeden Teiler setzen wir ihn in einen String um "$_", setzen ihn in toCharArra um yund sortdiese Ziffern mit dem -uNique-Flag (da es uns egal ist, ob ein Teiler selbst doppelte Ziffern hat). Wir erhöhen dann die entsprechende Ziffernanzahl $z. Dann verringern wir $anur , wenn $zenthält 0s und 1s (dh haben wir ein HDN gefunden). Wenn wir unsere forSchleife beendet haben, bedeutet dies, dass wir die entsprechende Anzahl von HDNs gefunden haben, sodass wir $nin der Pipeline verbleiben und die Ausgabe implizit erfolgt.

AdmBorkBork
quelle
Sie könnten ein paar Bytes sparen: $a-=!($z-ge2)Stattdessen$a-=!($z|?{$_-ge2})
mazzy
3

Python 3 , 115 Bytes

1-indiziert

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

Probieren Sie es online!

Dies erfordert viel Rekursion. Selbst mit einem erhöhten Rekursionslimit ist dies nicht möglich f(30). Ich denke, es könnte weiter Golf spielen und ich habe versucht, etwas zu finden, das das ersetzt (1-x%d), aber ich konnte mir nichts einfallen lassen ( -~-x%dhat den falschen Vorrang). Alle Bytes, die entfernt werden können, werden sehr geschätzt.

Wie es funktioniert

# 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
quelle
2

Brachylog (v2), 14 Bytes

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

Probieren Sie es online!

Funktionsübermittlung; Eingabe von links, Ausgabe nach rechts. (Die TIO-Verknüpfung enthält ein Befehlszeilenargument zum Ausführen einer Funktion, als wäre sie ein vollständiges Programm.)

Erläuterung

"Ist das eine feindliche Teilernummer?" :

ℕ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

Dies stellte sich im Grunde als das gleiche heraus wie bei @ UnrelatedString, obwohl ich es unabhängig geschrieben habe.

Wrapper "n-te Lösung für ein ":

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

Dies ist einer der Fälle, in denen der Wrapper, der zum Erzeugen der n-ten Ausgabe erforderlich ist, erheblich länger ist als der Code, der zum Testen der einzelnen Ausgaben erforderlich ist :-)

Ich habe mir diesen Wrapper unabhängig von @ UnrelatedStrings ausgedacht. Es ist gleich lang und funktioniert nach dem gleichen Prinzip, wird aber irgendwie etwas anders geschrieben. Es hat mehr Verbesserungspotential, da wir durch Ersetzen der Adurch eine Einschränkungsvariable gesuchte Werte Einschränkungen hinzufügen könnten , aber keine der möglichen Einschränkungsvariablen spart Byte. (Wenn es eine "nichtnegative Ganzzahl" -Einschränkungsvariable gäbe, könnten Sie die Adurch diese ersetzen und dann ein Byte speichern, indem Sie das Unnötige machen.)

ais523
quelle
Es ist 2-indiziert?
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 durch Verwenden von .matchesanstelle von .containspro Ziffer, inspiriert von der JavaScript-Antwort von @Arnauld .
-5 Byte dank @ValueInk
-1 Byte dank @ceilingcat

1-indiziert

Probieren Sie es online aus.

Erläuterung:

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

Brachylog , 16 Bytes

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

Probieren Sie es online!

Sehr langsam und doppelt so lang wie es wäre, wenn dies ein . 1-indiziert.

                    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).
Nicht verwandte Zeichenfolge
quelle
1
Wenn Sie diese Erklärung nur als Satz lesen ...
FireCubez
Ich versuche, meine Erklärungen wie normales Englisch zu schreiben, was in der Regel dazu führt, dass sie nur noch schwerer zu lesen sind
verwandte Zeichenfolge
1

Japt v2.0a0, 17 Bytes

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

Versuch es

Port dieser Brachylog-Antwort .

Gutschrift: 4 Bytes Ersparnis insgesamt dank Shaggy, der auch vorgeschlagen hat, dass es eine bessere Lösung gibt, die zu viel mehr Bytes führt :)


Originalantwort 28-Byte-Ansatz:

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

Versuch es

Port dieser JavaScript-Antwort .

Dana
quelle
28 Bytes
Shaggy
Nizza - ich hatte die «Abkürzung vorher nicht benutzt :) Ich denke, wenn Shaggy sich nur um eine Handvoll Bytes in meiner Punktzahl verbessert, muss ich dabei (etwas) anständig werden?
dana
Es kann in 20 (vielleicht weniger) b7 mit einer etwas anderen Methode durchgeführt werden.
Shaggy
Hah - ich denke, ich habe zu früh gesprochen :) Ja, einige der anderen Golfplätze haben viel kürzere Lösungen.
Dana
1
17 Bytes
Shaggy
0

Symbol , 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

Probieren Sie es online!

1-indiziert. Wirklich langsam für große Eingaben.

Galen Ivanov
quelle
0

Perl 6 , 74 Bytes

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

0-indiziert. Bei TIO werden nur die ersten drei Fälle aufgelistet, da es zu langsam ist, den Rest zu testen.

Probieren Sie es online!

bb94
quelle
1
57 Bytes
Jo King
0

Ruby , 110 97 92 84 Bytes

-13 Bytes durch Nutzung von @ Arnauld's JavaScript-Regex-Check .

-5 Bytes zum Auswechseln der timesSchleife für einen Dekrementierer und a while.

-8 Bytes, indem Sie combinationnach etwas suchen, das den anderen Antworten ähnelt.

->n{x=0;n-=1if(s='';1..x+=1).all?{|a|x%a>0||(e=/[#{a}]/!~s;s+=a.to_s;e)}while n>0;x}

Probieren Sie es online!

Wert Tinte
quelle
0

Perl 5 -p , 66 Bytes

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

Probieren Sie es online!

1 indiziert

Xcali
quelle
0

J , 87-59 Bytes

-28 Bytes dank FrownFrog

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

Probieren Sie es online!

Original

J 87 Bytes

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

Probieren Sie es online!

Huch.

Das ist für J furchtbar lang, aber ich sehe keine großartigen Möglichkeiten, es zu beenden.

Erläuterung

Es hilft, ein paar Hilfsverben einzuführen, um zu sehen, was passiert:

d=.(]#~0=|~)1+i.
h=. [: (-:~.) [: -.&' '@,/ ~.@":"0
  • d Gibt eine Liste aller Teiler des Arguments zurück
  • hsagt dir, eine solche Liste ist feindlich. Jede Zahl ~.@":"0wird stringifiziert und dedupliziert , wodurch eine quadratische Matrix zurückgegeben wird, in der kürzere Zahlen mit Leerzeichen aufgefüllt werden. -.&' '@,/Die Matrix wird geglättet und Leerzeichen werden entfernt. Abschließend (-:~.)erfahren Sie, ob diese Zahl Wiederholungen aufweist oder nicht.

Mit diesen beiden Helfern wird unser gesamtes, ungolfed Verb:

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

Hier führen wir eine Liste, deren Kopf unser "aktueller Kandidat" ist (der bei 1 beginnt) und deren Schwanz alle bisher gefundenen feindlichen Zahlen enthält.

Wir erhöhen den Kopf der Liste >:@[bei jeder Iteration und hängen den "aktuellen Kandidaten" nur an, wenn er feindlich ist h@d@[ # [. Wir machen das so lange, bis unsere Listenlänge 1 + n erreicht:^:(#@] < 1 + [)^:_ .

Wenn wir fertig sind, geben wir die letzte Nummer dieser Liste zurück, [: {:die die n-te feindliche Nummer ist.

Jona
quelle
66
FrownyFrog
62
FrownyFrog
Das ist toll, vielen Dank. Werde es durchgehen und heute Abend aktualisieren
Jonah
59
FrownyFrog