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 9566
ma 4
dzielniki: 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 n
od 1
do4000
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 golf golfowy , 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
źródło
94699599289
kwadrat kwadratu307733
ma dzielniki,[1, 307733, 94699599289]
co pokazuje, że jest to HDN. Wydaje mi się wrogi.49
? Czynniki[1, 7, 49]
kwalifikuje się jako wrogie ... albo dobrze,4
:[1, 2, 4]
...1
z listą dzielników[1]
. (Może duże HDN są bardziej interesujące?)49
że mam dzielniki[7, 7]
, które nie tylko dzielą cyfry, ale są tymi samymi cyframi.49
ma czynniki[1, 7, 49]
Odpowiedzi:
05AB1E ,
1210 bajtów-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:
źródło
µNNÑ€ÙSDÙQ
za 10.µ
, więc oszczędzasz mi kłopotów. ;)Python 2 , 104 bajty
Wypróbuj online!
0-indeksowane.
źródło
JavaScript (ES6), 78 bajtów
1-indeksowany.
Wypróbuj online!
Szybsza wersja, 79 bajtów
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 dzielnikare 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
"956647832".match(/[1]/)
jest fałszem"9567".match(/[3189]/)
jest prawdąSkomentował
Jest to wersja bez
eval()
, dla czytelnościźródło
Galaretka , 10 bajtów
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
nfind
jest używane.2-indeksowane
źródło
nfind
to zmieniło indeksowanie lol⁼Q$
jest taki sam jakQƑ
.Perl 6 , 53 bajtów
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ępnieR!~~
dopasowuje ciąg po prawej stronie do wzoru po lewej stronie. (~~
jest zwykłym operatorem dopasowania,!~~
jest zaprzeczeniem tego operatora iR
jest metaoperatorem, który zamienia argumenty!~~
.)źródło
Python 2 (PyPy) ,
117114 bajtówWykorzystuje indeksowanie 1
Wypróbuj online!
źródło
Język Wolfram 103 bajty
Wykorzystuje indeksowanie 1. Dziwię się, że wymagało tak dużo kodu.
źródło
(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ą tutajPowerShell , 112 bajtów
Wypróbuj online!
Pobiera dane wejściowe o indeksie 1
$args[0]
, przechowuje je w$a
pętlach, aż do uzyskania trafienia0
. W każdej iteracji zerujemy dziesięcioelementową tablicę$z
(używaną do przechowywania naszych cyfr). Następnie tworzymy naszą listę dzielników1..++$n|?{!($n%$_)}
. Dla każdego dzielnika rzucamy go na ciąg"$_"
,t
rzucamy oCharArray
, asort
te cyfry-u
flagą nique (ponieważ nie obchodzi nas, czy sam dzielnik ma zduplikowane cyfry). Następnie zwiększamy odpowiednią liczbę cyfr$z
. Następnie zmniejszamy$a
tylko, jeśli$z
zawiera0
si1
s (tzn. Znaleźliśmy HDN). Jeśli zakończyliśmy nasząfor
pętlę, oznacza to, że znaleźliśmy odpowiednią liczbę HDN, więc wychodzimy$n
z potoku i dane wyjściowe są niejawne.źródło
$a-=!($z-ge2)
zamiast tego$a-=!($z|?{$_-ge2})
Python 3 , 115 bajtów
1-indeksowany
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%d
ma zły priorytet). Wszelkie bajty, które można ogolić, są bardzo mile widziane.Jak to działa
źródło
Brachylog (v2), 14 bajtów
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 problemu decyzyjnego :
Okazało się to w zasadzie takie samo jak @ UnrelatedString, chociaż napisałem to niezależnie.
Opakowanie „n-tego rozwiązania problemu decyzyjnego ”:
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
A
zmienną 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.)źródło
Java 10,
149139138126126120 120119 bajtów-10 bajtów przy użyciu
.matches
zamiast.contains
na cyfrę, zainspirowanych odpowiedzią JavaScript @Arnauld .-5 bajtów dzięki @ValueInk
-1 bajtów dzięki @ceilingcat
1-indeksowany
Wypróbuj online.
Wyjaśnienie:
źródło
i
is
wyrażenie regularne, nie potrzebujesz dodatkowej konwersji ciągów, a wynik jest taki sam.Brachylog , 16 bajtów
Wypróbuj online!
Bardzo wolno i dwa razy dłużej, niż gdyby to był problem decyzyjny . 1-indeksowany.
źródło
Wolfram Language (Mathematica) , 74 bajty
Wypróbuj online!
źródło
Japt v2.0a0, 17 bajtów
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:
Spróbuj
Port tej odpowiedzi JavaScript .
źródło
«
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?Ikona , 123 bajty
Wypróbuj online!
1-indeksowany. Naprawdę wolny dla dużych nakładów.
źródło
Perl 6 , 74 bajtów
0-indeksowane. Tylko trzy pierwsze przypadki są wymienione w TIO, ponieważ jest zbyt wolny, aby przetestować resztę.
Wypróbuj online!
źródło
Rubin ,
110979284 bajtów-13 bajtów poprzez wykorzystanie sprawdzania wyrażenia regularnego @ Arnauld's JavaScript .
-5 bajtów na zamianę
times
pętli dekrementatora i awhile
.-8 bajtów, porzucając
combination
coś bardziej podobnego do innych odpowiedzi.Wypróbuj online!
źródło
Perl 5
-p
, 66 bajtówWypróbuj online!
1 indeksowany
źródło
J ,
8759 bajtów-28 bajtów dzięki FrownFrog
Wypróbuj online!
oryginalny
J , 87 bajtów
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
zwraca listę wszystkich dzielników jego argumentuh
mó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ę:
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 wrogih@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.źródło