Числа враждебных делителей

31

Некоторые делители натуральных чисел действительно ненавидят друг друга, и им не нравится использовать одну или несколько общих цифр.

Эти целые числа называются номерами враждебных делителей ( HDN )

Примеры

У числа 9566есть 4делители: 1, 2, 4783 and 9566
(как видите, нет двух одинаковых цифр ).
Таким образом, 9566 представляет собой Н ostile D ivisor N умбры

Номер НЕ9567 является HDN, потому что его делители ( ) имеют некоторые общие цифры. 1, 3, 9, 1063, 3189, 9567

Вот первые несколько 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...       


задача

Приведенный выше список можно продолжить, и ваша задача найти n-й HDN

вход

Целое положительное число nот 1до4000

Выход

nth ГБН

Тестовые случаи

Вот несколько 1-индексированных тестов.
Пожалуйста, укажите, какую систему индексации вы используете в своем ответе, чтобы избежать путаницы.

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

Это , поэтому выигрывает самая низкая оценка в байтах.

РЕДАКТИРОВАТЬ

Хорошие новости! Я представил свою последовательность в OEIS и ...
Номера враждебных делителей теперь OEIS A307636

J42161217
источник
1
Я думаю, что квадратные числа были бы наименее враждебными из чисел.
Фрамбот
3
@JoeFrambach Это я не понимаю. Есть идеально-квадратный HDN. Для довольно большого примера, 94699599289квадрат 307733, имеет делители, [1, 307733, 94699599289]которые показывают, что это HDN. Мне кажется враждебным.
Джепп Стиг Нильсен
@JeppeStigNielsen Для гораздо меньшего примера, почему бы не просто 49? Факторы [1, 7, 49]квалифицируются как враждебные ... Или, ну, 4[1, 2, 4]
Даррел Хоффман
@DarrelHoffman Не говоря уже о квадратном числе 1со списком делителей [1]. (Может быть, большие HDN более интересны?)
Джепп Стиг Нильсен
Я интерпретировал 49как наличие делителей [7, 7] , которые не только разделяют цифры, но и являются одинаковыми цифрами. 49есть факторы [1, 7, 49]
Frambot

Ответы:

9

05AB1E , 12 10 байт

µNNÑ€ÙSDÙQ

-2 байта благодаря @Emigna .

1-индексированных

Попробуйте онлайн или проверьте большинство тестовых случаев (последние два тестовых примера опущены, так как они истекли).

Объяснение:

µ           # 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
Вы победили меня в этот раз. У меня было µNNÑ€ÙSDÙQна 10.
Эминья
2
@ Emigna Ах, я просто работал над альтернативой µ, так что вы избавили меня от проблем. ;)
Кевин Круйссен
это поэтично красноречиво
не дари светлый
6

JavaScript (ES6), 78 байт

1-индексироваться.

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

Попробуйте онлайн!

Быстрая версия, 79 байт

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

Попробуйте онлайн!

Как?

Учитывая целое число К>0 , мы строим строку s как объединение всех делителей К .

Поскольку К всегда является самим делителем, s инициализируется в К (приводится к строке), и первый делитель, который мы пробуем, это dзнак равноК-1 .

Для каждого делителя d из К мы проверяем, можно ли найти любую цифру d в s , превратив d в набор символов в регулярном выражении.

Примеры

  • sзнак равно"956647832" ,dзнак равно1"956647832".match(/[1]/)ложно
  • sзнак равно"9567" ,dзнак равно3189"9567".match(/[3189]/)верно

комментарии

Это версия без eval(), для удобства чтения

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
источник
6

Желе , 10 байт

ÆDQ€FQƑµ#Ṫ

Попробуйте онлайн!

-1 байт благодаря ErikTheOutgolfer

Принимает данные из STDIN, что необычно для желе, но обычно там, где nfindиспользуется.

Æ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-индексированные

HyperNeutrino
источник
это 2-х индексированный? Со мной все в порядке, но, пожалуйста, укажите это для других
J42161217
Это какими бы ни были ваши тесты, поэтому 1
HyperNeutrino
3
Нет, это не так. 101 возвращает 839. и 102 -> 853. Работает нормально, но с 2 индексами
J42161217
1
@ J42161217 подожди что? я думаю, когда я переместил nfindэто изменило индексирование LOL
HyperNeutrino
1
⁼Q$так же, как .
Эрик Outgolfer
4

Perl 6 , 53 байта

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

Попробуйте онлайн!

1-индексироваться.

/(.).*$0/ сопоставляет любое число с повторяющейся цифрой.

grep $_ %% *, 1 .. $_возвращает список всех делителей числа $_, проверяемого в данный момент на членство в списке.

[~]объединяет все эти цифры вместе, а затем R!~~сопоставляет строку справа с шаблоном слева. ( ~~это обычный оператор сопоставления, !~~отрицание этого оператора и Rметаоператор, который меняет аргументы !~~.)

Шон
источник
50 байтов
Джо Кинг
3

Wolfram Language 103 байта

Использует 1-индексацию. Я удивлен, что это потребовало так много кода.

(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
источник
Можете ли вы добавить ссылку TIO, чтобы каждый мог проверить ваш ответ?
J42161217
95 байтов: (n=t=1;While[t<=#,If[!Or@@IntersectingQ@@@Subsets[IntegerDigits@Divisors@n,{2}],t++];n++];n-1)&я не планирую публиковать ответ, поэтому я оставлю это здесь
J42161217
@ J42161217, я пытался заставить код работать в TIO безуспешно. Должен быть какой-то трюк, который я пропустил.
DavidC
@ J42161217, твой код вроде работает, но занимает в 3 раза больше времени выполнения. Вы можете отправить его как свой собственный. (Может быть, я узнаю, как реализовать TIO из вашего примера.)
DavidC
Очень быстро! вот ваша ссылка Попробуйте онлайн!
J42161217
3

PowerShell , 112 байт

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

Попробуйте онлайн!

Принимает 1-индексированный ввод $args[0], сохраняет его в $aцикле, пока не попадет 0. На каждой итерации мы обнуляем массив из десяти элементов $z(используется для хранения нашего количества цифр). Затем мы строим наш список делителей с помощью 1..++$n|?{!($n%$_)}. Для каждого делителя мы приводим его к строке "$_", tприводим oCharArra yи sortэти цифры с помощью -uфлага nique (потому что нам все равно, если сам делитель имеет повторяющиеся цифры). Затем мы увеличиваем число соответствующих цифр в $z. Затем мы уменьшаем значение, $aтолько если $zсодержит 0s и 1s (т. Е. Мы нашли HDN). Если мы закончили наш forцикл, это означает, что мы нашли соответствующее количество HDN, поэтому мы оставляем $nв конвейере и вывод неявный.

AdmBorkBork
источник
Вы можете сэкономить несколько байтов: $a-=!($z-ge2)вместо этого$a-=!($z|?{$_-ge2})
mazzy
3

Python 3 , 115 байт

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

Попробуйте онлайн!

Это использует много рекурсии; даже с увеличенным лимитом рекурсии это невозможно f(30). Я думаю, что это может быть в будущем, и я попытался найти что-то, чтобы заменить(1-x%d) , но не смог придумать что-либо ( -~-x%dимеет неправильный приоритет). Любые байты, которые можно сбрить, очень ценятся.

Как это работает

# 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
источник
2

Brachylog (v2), 14 байт

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

Попробуйте онлайн!

Подчинение функции; ввод слева, вывод справа. (Ссылка TIO содержит аргумент командной строки для запуска функции, как если бы она была полной программой.)

объяснение

"Это число враждебных делителей?" код :

ℕ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

Это оказалось в основном таким же, как у @ UnrelatedString, хотя я написал это независимо.

«энное решение для » обертка:

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

Это один из тех случаев, когда оболочка, необходимая для создания n-го вывода, значительно длиннее, чем код, необходимый для проверки каждого вывода по очереди :-)

Я придумал эту обертку независимо от @ UnrelatedString. Это та же самая длина и работает по тому же принципу, но так или иначе заканчивает тем, что было написано довольно по-другому. У него действительно больше возможностей для улучшения, поскольку мы можем добавить ограничения на то, какие значения мы ищем бесплатно, заменив их Aнекоторой переменной ограничения, но ни одна из возможных переменных ограничения не сохраняет байты. (Если бы существовала переменная ограничения «неотрицательное целое число», вы можете заменить ее на Aнее, а затем сохранить байт, сделав ненужным.)

ais523
источник
Это 2-х индексируется?
FrownyFrog
2

Ява 10, 149 139 138 126 125 120 119 байт

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 байт, используя .matchesвместо .containsцифры, вдохновленный ответом @Arnauld на JavaScript .
-5 байт благодаря @ValueInk
-1 байт благодаря @ceilingcat

1-индексированных

Попробуйте онлайн.

Объяснение:

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`
Кевин Круйссен
источник
1

Брахилог , 16 байт

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

Попробуйте онлайн!

Очень медленно и вдвое дольше, чем если бы это была с . 1-индексироваться.

                    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
Если вы просто прочитаете это объяснение как предложение, хотя ...
FireCubez
Я пытаюсь написать свои объяснения, как обычный английский, который обычно заканчивается их составлением становится труднее читать
Unrelated String
1

Japt v2.0a0, 17 байт

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

Попытайся

Порт этого брахилога ответ .

Кредит: 4-байтовая экономия благодаря Шегги, который также предложил, что есть лучшее решение, приводящее к большему количеству байтов :)


Оригинальный ответ 28 байтовый подход:

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

Попытайся

Порт этого JavaScript ответа .

Dana
источник
28 байтов
лохматый
Хорошо - я раньше не использовал этот «ярлык :) Я полагаю, если Шэгги только улучшил свой счет на несколько байтов, я должен быть (несколько) приличным в этом?
Дана
Это можно сделать за 20 (может быть меньше) b7, используя немного другой метод.
лохматый
Ха-ха, наверное, я говорил слишком рано :) Да, у некоторых других игроков в гольф есть более короткие решения.
Дана
1
17 байтов
лохматый
0

Значок , 123 байта

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

Попробуйте онлайн!

1-индексироваться. Действительно медленно для больших входов.

Гален Иванов
источник
0

Perl 6 , 74 байта

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

0 индексированные. Только первые три случая перечислены на TIO, так как остальные слишком медленны для тестирования.

Попробуйте онлайн!

bb94
источник
1
57 байтов
Джо Кинг
0

Рубин , 110 97 92 84 байта

-13 байт, используя проверку регулярных выражений JavaScript @ Арнаулда .

-5 байт для замены timesцикла для уменьшителя и a while.

-8 байт, отказавшись combinationот чего-то более похожего на другие ответы.

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

Попробуйте онлайн!

Значение чернил
источник
0

J , 87 59 байт

-28 байт благодаря FrownFrog

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

Попробуйте онлайн!

оригинал

J , 87 байт

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

Попробуйте онлайн!

Хлоп.

Это ужасно долго для J, но я не вижу хороших способов его обуздать.

объяснение

Это помогает ввести пару вспомогательных глаголов, чтобы увидеть, что происходит:

d=.(]#~0=|~)1+i.
h=. [: (-:~.) [: -.&' '@,/ ~.@":"0
  • d возвращает список всех делителей своего аргумента
  • hговорит, что такой список враждебен. Он структурирует и дедуплицирует каждое число ~.@":"0, которое возвращает квадратную матрицу, где более короткие числа дополняются пробелами. -.&' '@,/выравнивает матрицу, удаляет пробелы и, наконец, (-:~.)сообщает вам , повторяется ли это число или нет.

С этими двумя помощниками наш общий, негольфированный глагол становится:

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

Здесь мы поддерживаем список, глава которого является нашим «текущим кандидатом» (который начинается с 1), а хвост которого - все найденные на данный момент враждебные числа.

Мы увеличиваем заголовок списка >:@[на каждой итерации и добавляем «текущего кандидата», только если он враждебен h@d@[ # [. Мы продолжаем делать это, пока длина нашего списка не достигнет 1 + n:^:(#@] < 1 + [)^:_ .

Наконец, когда мы закончим, мы возвращаем последний номер этого списка, [: {:который является n-м враждебным номером.

Ион
источник
66
FrownyFrog
62
FrownyFrog
Это здорово, большое спасибо. Пойду через это и обновлю сегодня вечером
Иона
59
FrownyFrog