Wrogie liczby dzielników


31

Niektóre dzielniki dodatnich liczb całkowitych naprawdę się nienawidzą i nie lubią dzielić jednej lub więcej wspólnych cyfr.

Te liczby całkowite nazywane są wrogimi numerami dzielników ( HDN )

Przykłady

Liczba 9566ma 4dzielniki: 1, 2, 4783 and 9566
(jak widać, żaden z nich nie ma tej samej cyfry ).
Tak więc, 9566 jest H ostile D ivisor N umbra

Liczba NIE9567 jest HDN, ponieważ jej dzielniki ( ) dzielą niektóre wspólne cyfry. 1, 3, 9, 1063, 3189, 9567

Oto kilka pierwszych 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...       


Zadanie

Powyższa lista jest długa, a Twoim zadaniem jest znalezienie n-tego HDN

Wkład

Dodatnia liczba całkowita nod 1do4000

Wydajność

nth HDN

Przypadki testowe

oto kilka przypadków testowych z 1 indeksowaniem .
Proszę podać, jakiego systemu indeksowania używasz w swojej odpowiedzi, aby uniknąć nieporozumień.

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

To jest , więc wygrywa najniższy wynik w bajtach.

EDYTOWAĆ

Dobre wieści! Przekazałem moją sekwencję do OEIS i ...
Numery wrogiego dzielnika to teraz OEIS A307636


1
Myślę, że liczby kwadratowe byłyby najmniej wrogie z liczb.
Frambot

3
@JoeFrambach Tego nie rozumiem. Istnieją idealnie kwadratowe HDN. Dla dość dużego przykładu 94699599289kwadrat kwadratu 307733ma dzielniki, [1, 307733, 94699599289]co pokazuje, że jest to HDN. Wydaje mi się wrogi.
Jeppe Stig Nielsen

@JeppeStigNielsen Na znacznie mniejszy przykład, dlaczego nie tylko 49? Czynniki [1, 7, 49]kwalifikuje się jako wrogie ... albo dobrze, 4: [1, 2, 4]...
Darrel Hoffman

@DarrelHoffman Nie wspominając, liczba kwadratowa 1z listą dzielników [1]. (Może duże HDN są bardziej interesujące?)
Jeppe Stig Nielsen

Zinterpretowałem, 49że mam dzielniki [7, 7] , które nie tylko dzielą cyfry, ale są tymi samymi cyframi. 49ma czynniki [1, 7, 49]
Frambot

Odpowiedzi:


9

05AB1E , 12 10 bajtów

µNNÑ€ÙSDÙQ

-2 bajty dzięki @Emigna .

1-indeksowany

Wypróbuj online lub sprawdź większość przypadków testowych (ostatnie dwa przypadki testowe są pomijane, ponieważ upłynęły limity czasu).

Wyjaśnienie:

µ           # 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)

2
Tym razem mnie pobiłeś. Miałem µNNÑ€ÙSDÙQza 10.
Emigna

2
@Emigna Ach, właśnie pracowałem nad alternatywą µ, więc oszczędzasz mi kłopotów. ;)
Kevin Cruijssen

jest to poetycko wymowne
don bright


6

JavaScript (ES6), 78 bajtów

1-indeksowany.

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

Wypróbuj online!

Szybsza wersja, 79 bajtów

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

Wypróbuj online!

W jaki sposób?

Biorąc pod uwagę liczbę całkowitą k>0 , budujemy ciąg s jako konkatenację wszystkich dzielników k .

Ponieważ k jest zawsze dzielnikiem samego siebie, s jest inicjalizowane na k (wymuszone na łańcuch), a pierwszym dzielnikiem, którego próbujemy, jest re=k-1 .

Dla każdego dzielnika re o k , testujemy, czy jakakolwiek cyfra re można znaleźć w s obracając re do zestawu znaków w wyrażeniu regularnym.

Przykłady

  • s=956647832 ,re=1"956647832".match(/[1]/)jest fałszem
  • s=9567 ,re=3189"9567".match(/[3189]/)jest prawdą

Skomentował

Jest to wersja bez eval(), dla czytelności

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
}                        //

6

Galaretka , 10 bajtów

ÆDQ€FQƑµ#Ṫ

Wypróbuj online!

-1 bajt dzięki ErikTheOutgolfer

Pobiera dane wejściowe ze STDIN, co jest niezwykłe w przypadku Galaretki, ale jest normalne tam, gdzie nfindjest używane.

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


czy to jest 2-indeksowane? Jest ze mną w porządku, ale proszę podać to innym
J42161217

Niezależnie od tego, jakie były twoje przypadki testowe, więc 1
HyperNeutrino

3
Nie, nie jest. 101 zwraca 839. i 102 -> 853. Działa dobrze, ale ma 2 indeksy
J42161217

1
@ J42161217 co czekać? myślę, że kiedy przeniosłem nfindto zmieniło indeksowanie lol
HyperNeutrino

1
⁼Q$jest taki sam jak .
Erik the Outgolfer

4

Perl 6 , 53 bajtów

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

Wypróbuj online!

1-indeksowany.

/(.).*$0/ dopasowuje dowolną liczbę z powtarzającą się cyfrą.

grep $_ %% *, 1 .. $_zwraca listę wszystkich dzielników liczby $_aktualnie sprawdzanej pod kątem członkostwa na liście.

[~]łączy wszystkie te cyfry razem, a następnie R!~~dopasowuje ciąg po prawej stronie do wzoru po lewej stronie. ( ~~jest zwykłym operatorem dopasowania, !~~jest zaprzeczeniem tego operatora i Rjest metaoperatorem, który zamienia argumenty !~~.)




3

Język Wolfram 103 bajty

Wykorzystuje indeksowanie 1. Dziwię się, że wymagało tak dużo kodu.

(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)&

Czy możesz dodać link TIO, aby każdy mógł sprawdzić twoją odpowiedź?
J42161217

95 bajtów: (n=t=1;While[t<=#,If[!Or@@IntersectingQ@@@Subsets[IntegerDigits@Divisors@n,{2}],t++];n++];n-1)&Nie planuję opublikować odpowiedzi, więc zostawiam ją tutaj
J42161217

@ J42161217, próbowałem zmusić kod do działania w TIO bez powodzenia. Musi być jakiś trik, za którym tęsknię.
DavidC

@ J42161217, Twój kod wydaje się działać, ale zajmuje 3 razy więcej czasu działania. Możesz przesłać go jako swój własny. (Może nauczę się implementować TIO z twojego przykładu.)
DavidC

Rzeczywiście bardzo szybko! oto twój link Wypróbuj online!
J42161217

3

PowerShell , 112 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe o indeksie 1 $args[0], przechowuje je w $apętlach, aż do uzyskania trafienia 0. W każdej iteracji zerujemy dziesięcioelementową tablicę $z(używaną do przechowywania naszych cyfr). Następnie tworzymy naszą listę dzielników 1..++$n|?{!($n%$_)}. Dla każdego dzielnika rzucamy go na ciąg "$_", trzucamy oCharArra y, a sortte cyfry -uflagą nique (ponieważ nie obchodzi nas, czy sam dzielnik ma zduplikowane cyfry). Następnie zwiększamy odpowiednią liczbę cyfr $z. Następnie zmniejszamy $atylko, jeśli $zzawiera 0si 1s (tzn. Znaleźliśmy HDN). Jeśli zakończyliśmy naszą forpętlę, oznacza to, że znaleźliśmy odpowiednią liczbę HDN, więc wychodzimy $nz potoku i dane wyjściowe są niejawne.


możesz zapisać kilka bajtów: $a-=!($z-ge2)zamiast tego$a-=!($z|?{$_-ge2})
mazzy


3

Python 3 , 115 bajtów

1-indeksowany

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

Wypróbuj online!

To wymaga dużo rekurencji; nawet przy zwiększonym limicie rekurencji nie da się tego zrobić f(30). Wydaje mi się, że może być bardziej do gry w golfa i próbowałem znaleźć coś do zastąpienia (1-x%d), ale nie mogłem niczego wymyślić ( -~-x%dma zły priorytet). Wszelkie bajty, które można ogolić, są bardzo mile widziane.

Jak to działa

# 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

2

Brachylog (v2), 14 bajtów

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

Wypróbuj online!

Podanie funkcji; wejście z lewej strony, wyjście z prawej. (Łącze TIO zawiera argument wiersza polecenia służący do uruchamiania funkcji tak, jakby był to pełny program.)

Wyjaśnienie

„Czy to wrogi numer dzielnika?” kod :

ℕ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

Okazało się to w zasadzie takie samo jak @ UnrelatedString, chociaż napisałem to niezależnie.

Opakowanie „n-tego rozwiązania ”:

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

Jest to jeden z tych przypadków, w których opakowanie wymagane do wygenerowania n-tego wyjścia jest znacznie dłuższe niż kod wymagany do testowania każdego wyjścia kolejno :-)

Wymyśliłem to opakowanie niezależnie od @ UnrelatedString's. Ma tę samą długość i działa na tej samej zasadzie, ale w jakiś sposób zostaje napisany inaczej. Ma większy potencjalny zakres do ulepszenia, ponieważ moglibyśmy dodawać ograniczenia do tego, jakie wartości szukaliśmy za darmo, zastępując Azmienną ograniczającą, ale żadna z możliwych zmiennych ograniczających nie oszczędza bajtów. (Jeśli istnieje zmienna ograniczenia „nieujemna liczba całkowita”, możesz ją zastąpić A, a następnie zapisać bajt, czyniąc niepotrzebnym.)


Jest 2-indeksowane?
FrownyFrog

2

Java 10, 149 139 138 126 126 120 120 119 bajtów

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 bajtów przy użyciu .matcheszamiast .containsna cyfrę, zainspirowanych odpowiedzią JavaScript @Arnauld .
-5 bajtów dzięki @ValueInk
-1 bajtów dzięki @ceilingcat

1-indeksowany

Wypróbuj online.

Wyjaśnienie:

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`


@ValueInk Thanks! :)
Kevin Cruijssen

1

Brachylog , 16 bajtów

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

Wypróbuj online!

Bardzo wolno i dwa razy dłużej, niż gdyby to był . 1-indeksowany.

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

1
Jeśli po prostu przeczytasz to wyjaśnienie jako zdanie ...
FireCubez

Staram się pisać moje wyjaśnienia jak zwykły angielski, co zwykle sprawia, że ​​stają się trudniejsze do odczytania
Niepowiązany ciąg


1

Japt v2.0a0, 17 bajtów

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

Spróbuj

Port tej odpowiedzi Brachylog .

Credit: 4 bajty oszczędności ogółem dzięki Shaggy'emu, który również zasugerował, że istnieje lepsze rozwiązanie prowadzące do większej liczby bajtów :)


Oryginalna odpowiedź 28-bajtowe podejście:

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

Spróbuj

Port tej odpowiedzi JavaScript .



Fajnie - wcześniej nie korzystałem ze «skrótu :) Sądzę, że jeśli Kudłaty poprawia mój wynik tylko o kilka bajtów, to muszę być w tym (trochę) przyzwoity?
dana

To może być wykonane w 20 (może być mniej) B7 stosując nieco inny sposób.
Kudłaty

Hah - chyba mówiłem za wcześnie :) tak, niektórzy inni golfiści mają znacznie krótsze rozwiązania.
dana


0

Ikona , 123 bajty

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

Wypróbuj online!

1-indeksowany. Naprawdę wolny dla dużych nakładów.





0

J , 87 59 bajtów

-28 bajtów dzięki FrownFrog

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

Wypróbuj online!

oryginalny

J , 87 bajtów

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

Wypróbuj online!

Yikes.

To okropnie długo trwa dla J, ale nie widzę świetnych sposobów na obniżenie go.

wyjaśnienie

Pomaga wprowadzić kilka czasowników pomocniczych, aby zobaczyć, co się dzieje:

d=.(]#~0=|~)1+i.
h=. [: (-:~.) [: -.&' '@,/ ~.@":"0
  • d zwraca listę wszystkich dzielników jego argumentu
  • hmówi ci, że taka lista jest wroga. Strąca i deduplikuje każdą liczbę ~.@":"0, co zwraca macierz kwadratową, w której krótsze liczby są wypełniane spacjami. -.&' '@,/spłaszcza macierz i usuwa spacje, a na koniec (-:~.)informuje, czy ta liczba się powtarza, czy nie.

Dzięki tym dwóm pomocnikom nasz ogólny czasownik niepoliczony staje się:

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

Prowadzimy tutaj listę, której głowa jest naszym „obecnym kandydatem” (która zaczyna się od 1) i której ogonem są wszystkie wrogie liczby znalezione do tej pory.

Przy >:@[każdej iteracji zwiększamy nagłówek listy i dołączamy „bieżącego kandydata” tylko wtedy, gdy jest wrogi h@d@[ # [. Robimy to, dopóki nasza lista nie osiągnie 1 + n:^:(#@] < 1 + [)^:_ .

Wreszcie, kiedy skończymy, zwracamy ostatnią liczbę z tej listy, [: {:która jest n-tym numerem wrogim.




To wspaniale, wielkie dzięki. Omówię to i zaktualizuję dziś wieczorem
Jonasz

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.