Делительные делители

17

Учитывая положительное целое число n всегда можно найти кортеж (k1,k2,...,km) целых чисел ki2 таким образом, что k1k2...km=n и

k1|k2 , k2|k3 ,  , km1|km.
Здесь |a|b означает, чтоb кратноa , скажем "a делит b". Еслиn>1 все записиki должны быть не менее2 . Дляn=1 у нас нет такого фактора, и поэтому мы получаем пустой кортеж.

Если вам интересно, откуда это взялось: Это разложение известно как разложение по инвариантным факторам в теории чисел и используется в классификации конечно порожденных абелевых групп.

Вызов

Учитывая n выходной все такие кортежи (k1,k2,...,km) для данного n ровно один раз, в любом порядке , как. Стандартные форматы вывода разрешены.

Примеры

  1: () (empty tuple)
  2: (2)
  3: (3)
  4: (2,2), (4)
  5: (5)
  6: (6)
  7: (7)
  8: (2,2,2), (2,4), (8)
  9: (3,3), (9)
 10: (10)
 11: (11)
 12: (2,6), (12)
108: (2,54), (3,3,12), (3,6,6), (3,36), (6,18), (108)

Связанный: http://oeis.org/A000688 , перечислите все мультипликативные разбиения n

flawr
источник
Можем ли мы вывести каждый кортеж в обратном порядке? (например 12,3,3)
Арно
1
@Arnauld Да, я думаю, пока это отсортировано в порядке возрастания или убывания, все должно быть в порядке!
Flawr
Можем ли мы ограничить ввод целыми числами> = 2? Если нет, то это лишит законной силы некоторые из существующих ответов?
Ник Кеннеди
1
Нет, в спецификациях четко сказано, что любое положительное целое число может быть задано в качестве входных данных, включая . Если я изменю это сейчас, каждый, кто действительно придерживается спецификаций, должен будет изменить свой ответ. Nзнак равно1
flawr

Ответы:

3

05AB1E , 13 байтов

Òœ€.œP€`êʒüÖP

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

Ò                      # prime factorization of the input
 œ€.œ                  # all partitions
     P                 # product of each sublist
      €`               # flatten
        ê              # sorted uniquified
         ʒ             # filter by:
          üÖ           #  pairwise divisible-by (yields list of 0s or 1s)
            P          #  product (will be 1 iff the list is all 1s)
Grimmy
источник
Хороший способ использовать, Òœ€.œPчтобы получить списки. У меня действительно были проблемы с нахождением чего-то более короткого. Если бы был встроенный аналог, Åœно для продукта вместо суммы. ;)
Кевин Круйссен
Сбой для n = 1 (см. Комментарии к вопросу)
Ник Кеннеди
2

JavaScript (V8) ,  73  70 байт

Печатает кортежи в порядке убывания (Км,Км-1,,,,,К1),

f=(n,d=2,a=[])=>n>1?d>n||f(n,d+1,a,d%a[0]||f(n/d,d,[d,...a])):print(a)

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

комментарии

f = (             // f is a recursive function taking:
  n,              //   n   = input
  d = 2,          //   d   = current divisor
  a = []          //   a[] = list of divisors
) =>              //
  n > 1 ?         // if n is greater than 1:
    d > n ||      //   unless d is greater than n,
    f(            //   do a recursive call with:
      n,          //     -> n unchanged
      d + 1,      //     -> d + 1
      a,          //     -> a[] unchanged
      d % a[0] || //     unless the previous divisor does not divide the current one,
      f(          //     do another recursive call with:
        n / d,    //       -> n / d
        d,        //       -> d unchanged
        [d, ...a] //       -> d preprended to a[]
      )           //     end of inner recursive call
    )             //   end of outer recursive call
  :               // else:
    print(a)      //   this is a valid list of divisors: print it
Arnauld
источник
1

05AB1E , 17 15 14 байтов

ѦIиæʒPQ}êʒüÖP

Очень медленно для больших тестовых случаев.

-1 байт благодаря @Grimy .

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

Объяснение:

Ñ               # Get all divisors of the (implicit) input-integer
 ¦              # Remove the first value (the 1)
  Iи            # Repeat this list (flattened) the input amount of times
                #  i.e. with input 4 we now have [2,4,2,4,2,4,2,4]
    æ           # Take the powerset of this list
     ʒ  }       # Filter it by:
      PQ        #  Where the product is equal to the (implicit) input
         ê      # Then sort and uniquify the filtered lists
          ʒ     # And filter it further by:
           ü    #  Loop over each overlapping pair of values
            Ö   #   And check if the first value is divisible by the second value
             P  #  Check if this is truthy for all pairs

                # (after which the result is output implicitly)
Кевин Круйссен
источник
@ Грими Спасибо. И хороший вызов на делители. Это все еще очень медленно дляNзнак равно8, но все биты помогают, и если это не требует дополнительных байтов для повышения производительности, то почему бы не использовать его. :)
Кевин Круйссен
1
13 и быстрее . Чувствуется, что это может быть еще короче.
Grimmy
1

JavaScript, 115 байт

f=(n,a=[],i=1)=>{for(;i++<n;)n%i||(a=a.concat(f(n/i).filter(e=>!(e[0]%i)).map(e=>[i].concat(e))));return n>1?a:[a]}

Позже напишу объяснение

Naruyoko
источник
1

Wolfram Language (Mathematica) , 78 76 72 71 67 байт

If[#>(p=1##2),Join@@If[i∣##,##~#0~i,{}]~Table~{i,2,#/p},{{##2}}]&

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

Рекурсивное дерево поиска.


Решение по грубой силе, 64 байта :

Union@Cases[Range@#~Tuples~#,{a__,__}/;1a==#&&a>=2&&1∣a:>{a}]&

Тривиальная модификация моего решения Mathematica для перечисления всех мультипликативных разбиений n .

Так как это нужно проверить NNкортежи, попробуйте более эффективную версию, используя ту же логику .

attinat
источник
0

Japt , 22 байта

â Åï c à f@¥XשXäv eÃâ

Попытайся

â Åï c à f@¥XשXäv eÃâ     :Implicit input of integer U
â                          :Divisors
  Å                        :Slice off the first element, removing the 1
   ï                       :Cartesian product
     c                     :Flatten
       à                   :Combinations
         f                 :Filter by
          @                :Passing each sub-array X through the following function
           ¥               :  Test U for equality with
            X×             :  X reduced by multiplication
              ©            :  Logical AND with
               Xä          :  Consecutive pairs of X
                 v         :  Reduced by divisibility
                   e       :  All truthy?
                    Ã      :End filter
                     â     :Deduplicate
мохнатый
источник