Суммы основных факторов

27

2013 год имеет первостепенную факторизацию 3*11*61. 2014 год имеет первостепенную факторизацию 2*19*53. Интересное свойство относительно этих факторизаций является то , что существует различные простые числа в факторизациях 2013 и 2014 , что сумма к тому же номеру: 11+61=19+53=72.

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


Разъяснения

  • Можно использовать более двух основных факторов. Не все основные факторы числа должны быть использованы в сумме. Нет необходимости, чтобы число простых чисел, используемых из двух чисел, было одинаковым.
  • Даже если простое число увеличивается до некоторой степени больше 1 при факторизации числа, его можно использовать только один раз в сумме простых чисел для числа.
  • 1 не простое число.
  • Оба входных номера будут меньше чем 2^32-1.

Контрольные примеры

5,6
    5=5
    6=2*3
    5=2+3
==>True

2013,2014
    2013=3*11*61
    2014=2*19*53
    11+61=19+53
==>True

8,15
    8=2^3
    15=3*5
    No possible sum
==>False

21,25
    21=3*7
    25=5^2
    No possible sum (can't do 3+7=5+5 because of exponent)
==>False

Это код гольф. Стандартные правила применяются. Самый короткий код в байтах побеждает.

Арктур
источник
6
Мне нравятся подобные вызовы, но для языков игры в гольф это будет цепочка встроенных элементов: фактор, уникальность, подмножества, суммы, перекрытия.
xnor
Можем ли мы принять входные данные как массив из двух элементов?
ETHproductions
@ETHproductions По умолчанию да.
lirtosiast
Как насчет 14 (2 * 7) и 21 (3 * 7) true, поскольку они имеют общий фактор 7?
Саймон Форсберг
@SimonForsbergMcFeely Да
Арктур

Ответы:

10

Юлия, 95 93 байта

g(x)=reduce(vcat,map(p->map(sum,p),partitions([keys(factor(x))...])))
f(a,b)=g(a)∩g(b)!=[]

Основная функция fи она вызывает вспомогательную функцию g.

Ungolfed:

function g(x::Integer)
    # Find the sum of each combination of prime factors of the input
    return reduce(vcat, map(p -> map(sum, p), partitions([keys(factor(x))...])))
end

function f(a::Integer, b::Integer)
    # Determine whether there's a nonzero intersection of the factor
    # sums of a and b
    return !isempty(g(a)  g(b))
end

Сохранено 2 байта благодаря Дарту Алефале

Алекс А.
источник
3
Я заметил, что это было понижено. Есть что-то, что я упустил? Если это не так, я был бы рад исправить это, но в нынешнем виде он отлично работает для меня и проходит все тестовые случаи.
Алекс А.
Я думаю, что map(p->mapкороче (m=map)(p->m.
алефальфа
@DarthAlephalpha Хороший звонок, спасибо.
Алекс А.
7

Pyth, 11 байт

t@FmsMy{PdQ

Ввод в форме 30,7.

t@FmsMy{PdQ     implicit: Q=input tuple
      y         powerset of
       {        unique elements of
        Pd      prime factorizations of d
    sM          Map sum over each element of the powerset
    sMy{Pd      lambda d: all sums of unique prime factors of d
   m      Q     Map over Q. Produces a two-element list.
 @F             Fold list intersection
t               Remove first element, which is a 0.
                If no other common sums, the remaining empty list is falsy.
lirtosiast
источник
1
Это теперь идентично другому ответу Pyth, за исключением одного перемещенного письма;)
ETHproductions
@ETHproductions Я ответил до того, как Малтисен исправил их; так что я сохраню это.
lirtosiast
7

Pyth - 17 12 11 байт

Спасибо @FryAmTheEggman за исправление моего ответа и сохранение байта.

@FmsMty{PdQ

Тестовый пакет .

Maltysen
источник
Я думаю, что использование tyработает и сохраняет пока?
FryAmTheEggman
@FryAmTheEggman спасибо!
Maltysen
17
@Maltysen ты упустил прекрасную возможность сказать "ты"
подземный
4

Хаскелл, 115 106 байт

import Data.Numbers.Primes
import Data.List
p=map sum.tail.subsequences.nub.primeFactors
a#b=p a/=p a\\p b

Пример использования: 2013 # 2014 -> True.

pсоздает список всех основных факторов своего аргумента, удаляет дубликаты, создает список всех подпоследовательностей, удаляет первую (которая всегда является пустым списком) и, наконец, суммирует подпоследовательности. #проверяет, p aне равна ли разница p a \\ p b. Если не равны, у них есть хотя бы один общий элемент.

Ними
источник
3

Japt, 25 байт

[UV]=N®k â à mx};Ud@J<VbX

Выходы trueили false. Попробуйте онлайн!

Неуправляемый и объяснение

[UV]=N®   k â à mx};Ud@ J<VbX
[UV]=NmZ{Zk â à mx};UdX{J<VbX

          // Implicit: N = list of inputs
[UV]=N    // Set variables U and V to the first to items in N,
mZ{    }  // with each item Z mapped to:
Zk        //  Generate list of Z's factors.
â         //  Keep only the unique items.
à         //  Generate all combinations.
mx        //  Sum each combination.
UdX{      // Check if any item X in U fulfills this condition:
J<VbX     //  -1 is less than V.indexOf(X).
          // Implicit: output last expression

Для дополнительного байта вы можете разделить код factorize-unique-Объединить-Сумма между обоими входами с дополнительным преимуществом временной сложности O(O(25-byte version)^2):

Uk â à mx d@J<Vk â à mx bX
ETHproductions
источник
3

CJam, 23 байта

q~{mf_&0a\{1$f++}/}/&0-

Проверьте это здесь.

Значение true будет объединять все общие суммы, значение false - пустая строка.

объяснение

q~     e# Read and evaluate input.
{      e# For each of the two numbers...
  mf   e# Get the prime factors.
  _&   e# Remove duplicates.
  0a\  e# Put an array containing a 0 below to initialise the list of possible sums.
  {    e# For each prime factor...
    1$ e#   Make a copy of the available sums so far.
    f+ e#   Add the current factor to each of them.
    +  e#   Combine with the list of sums without that factor.
  }/
}/
&      e# Set intersection between the two lists of sums.
0-     e# Remove the 0 which is always in the intersection.
Мартин Эндер
источник
3

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

{ḋd⊇+ℕ₁}ᵛ

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

Предикат успешно возвращается, [the sum, the sum]если он существует, и не выполняется, если сумма не существует.

{            Start of inline predicate.
 ḋ           The prime factors of the input,
  d          with duplicates removed.
   ⊇         Some subset of the unique prime factors
    +ℕ₁      has a sum greater than 0 which is output.
       }ᵛ    The predicate can have the same output for both elements of the input.

-1 байт благодаря Fatalize (создателю Brachylog), напомнившему мне, что существует мета-предикат проверки .

Несвязанная строка
источник
1
Вы можете использовать ᵛ - verifyвместо того, ˢ=чтобы сохранить один байт.
Роковая
2

MATL , 23 байта

2:"iYfutn2w^1-:B!Y*]!=z

Использует текущий выпуск 2.0.2 , который является более ранним, чем этот вызов.

Номера представлены как два отдельных входа. Вывод 0или 1.

пример

>> matl 2:"iYfutn2w^1-:B!Y*]!=z
> 2013
> 2014
1

объяснение

2:           % vector of two numbers, to generate two iterations
"            % for loop
  i          % input number                                                 
  Yfu        % get prime factors without repetitions
  tn         % duplicate and get number of elements in array N 
  2w^1-:     % numbers from 1 to 2^N                                        
  B!Y*       % convert to binary, transpose and matrix multiply to produce all sums
]            % end                                                      
!=z          % true if any value is equal to any other
Луис Мендо
источник
2

Mathematica, 58 байт

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&/@IntersectingQ@##&

Объяснение:

Это анонимная функция.

Сначала IntersectingQпроверяется, пересекаются ли два списка. Но входные данные являются числами, а не списками, поэтому он остается неоцененным. Например, если входными данными являются 2013и 2014, тогда IntersectingQ@##&возвращается IntersectingQ[2013, 2014].

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&это еще одна анонимная функция, которая принимает целое число, получает список ее простых факторов без повторений, получает набор мощности, удаляет пустой набор и затем получает сумму каждого набора. Так что Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]возвращается {3, 11, 61, 14, 64, 72, 75}.

Затем сопоставьте Tr/@Rest@Subsets[#&@@@FactorInteger@#]&выражение IntersectingQ[2013, 2014]. Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]и Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]являются списками, поэтому мы можем получить результат сбора на этот раз.

alephalpha
источник
Звонить IntersectingQпервым - это здорово! :)
Мартин Эндер
Не могли бы вы добавить объяснение?
Линн
2

PARI / GP , 98 байт

Factor, возьмите primes ( [,1]), зациклите непустые подмножества, sum и uniq, затем пересекайте результат этого для двух чисел. Возвращаемое значение - это количество пересечений, которое является достоверным, если только они не равны 0.

f(n,v=factor(n)[,1])=Set(vector(2^#v-1,i,vecsum(vecextract(v,i))))
g(m,n)=#setintersect(f(m),f(n))
Чарльз
источник
2

APL (Dyalog Extended) , 23 17 байт SBCS

-5 благодаря ngn

Анонимная негласная инфиксная функция.

1<≢⍤∩⍥(∊0+⍀.,∪⍤⍭)

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

⍥{} Применить следующую анонимную функцию к обоим аргументам:

 главные факторы

 тогда

 уникальные из тех,

0+⍀., добавление таблицы уменьшения нуля, сцепленного с каждым фактором

ε NLIST (Flatten)

 Перекресток

 тогда

 подсчет тех

1< там больше одного? (один, потому что суммы без факторов)

Адам
источник
используя только функции из самого dyalog: p+.×⊤1↓⍳2*≢p←->1↓∊(⊢,+)/0,⍨
ngn
еще короче 1↓∊∘.+/0,¨
нгн
который является 1↓∊0∘.+.,продуктом inouter - как часто вы видите это :)
ngn
если я правильно понимаю , это должно работать тоже:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
ngn
@ngn Спасибо. Выполнено.
адам
2

05AB1E , 10 8 байт

f€æO`å¦à

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

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

f         # Get all distinct prime factors of both values in the (implicit) input-list
          #  i.e. [2013,2014] → [[3,11,61],[2,19,53]]
 ۾       # Get the powerset for each
          #  → [[[],[3],[11],[3,11],[61],[3,61],[11,61],[3,11,61]],
          #     [[],[2],[19],[2,19],[53],[2,53],[19,53],[2,19,53]]]
   O      # Sum each inner-most list
          #  → [[0,3,11,14,61,64,72,75],[0,2,19,21,53,55,72,74]]
    `     # Push both lists to the stack
     å    # Check for each value in the second list if it's present in the first list
          #  → [1,0,0,0,0,0,1,0]
      ¦   # Remove the first item (since the powerset included empty leading lists)
          #  → [0,0,0,0,0,1,0]
       à  # Check if any are truthy by taking the maximum (which is output implicitly)
          #  → 1
Кевин Круйссен
источник
1
f€æO`å¦àдолжен работать на 8.
Emigna
1

Python 3 , 206 байт

Это лямбда-функция (m), которая принимает 2 числа и возвращает набор, содержащий любые суммы простых факторов, которые у них общие. В Python это истинное значение, если оно не пустое, и значение Falsey, если оно пустое.

Изменить: Оказывается, мой первоначальный ответ не работал для простых входов, как указано @JoKing. Это было исправлено (наряду с некоторыми другими ошибками) при трагической стоимости в 40 байт.

q=__import__('itertools').permutations
def p(n):
 i,s=2,set()
 while~-n:
  if n%i:i+=1
  else:n//=i;s|={i}
 return s
s=lambda f:{sum(i)for l in range(1,len(f)+1)for i in q(f,l)}
m=lambda a,b:s(p(a))&s(p(b))

Быстрое объяснение с использованием комментариев:

#Alias for permutations function
q=__import__('itertools').permutations
#Returns set of prime factors of n, including n, if prime
def p(n):
 i,s=2,set()
 while~-n:
  if n%i:i+=1
  else:n//=i;s|={i}
 return s
#Returns all possible sums of 2 or more elements in the given set
s=lambda f:{sum(i)for l in range(1,len(f)+1)for i in q(f,l)}
#Returns any shared possible sums of prime factors of a and b (the intersection of the sets)
m=lambda a,b:s(p(a))&s(p(b))

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

senox13
источник
Это не работает для первого контрольного примера 5,6, так как он не обрабатывает первичные входные данные
Джо Кинг
@JoKing Спасибо, что поймали это. Ответ был обновлен.
senox13
1

APL (NARS), 50 символов, 100 байтов

{⍬≢↑∩/+/¨¨{⍵∼⊂⍬}¨{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨∪¨π¨⍵}

здесь я нашел бы множество факторов на его аргумент;

{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵} 

была бы функция, которая находит все подмножества ... я должен сказать, что, кажется, {itsоператор itsArguments} ¨ (для каждого левого) и ¨ (для каждого правого) может имитировать цикл с фиксированным числом циклов, и ok в порядке в чтобы увидеть подмножества одного набора ... при таком взгляде кажется, что символы сокращаются в циклах описания ...; тест

  h←{⍬≢↑∩/+/¨¨{⍵∼⊂⍬}¨{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨∪¨π¨⍵}
  h 5 6
1
  h 2013 2014
1
  h 8 15
0
  h 21 25
0

Один маленький анализ:

π¨⍵  for each arg apply factor 
∪¨ for each arg apply unique
{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨ for each arg apply subsets
{⍵∼⊂⍬}¨ for each argument subtract Zilde enclosed (that would be the void set)
+/¨¨ for each arg (for each arg apply +/)
⍬≢↑∩/ apply intersection, get the first argument and see if it is Zilde (this it is right because enclosed Zilde it seems is the void set)
RosLuP
источник
1

Japt , 14 байт

®k â ã mx
rf Ê

Сохранено 3 байта благодаря @Shaggy

Попытайся

Воплощение невежества
источник
Вторая линия может быть ÎfUÌ lили, еще короче, rf l. было бы самым коротким способом сделать это, но Оливер победил вас в этом.
Лохматый
1

Желе , 18 9 байт

ÆfŒPḊ§)f/

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

Спасибо @Jonathan Allan за -9 и потрясающей помощи :).

Принимает ввод как массив из двух элементов. Объяснение кода:

      )    Call Chain 1 for each integer in the input array

ÆfŒPḊ§     Chain 1:
Æf           Compute a list of the prime factors of the integer
  ŒP         Powerset of P, with duplicates and an empty element
    Ḋ        Drop said empty element
     §       Vectorized sum: sum every combination

       f/  Chain 2:
        /    Reduce (the resulting list of two lists of possible sums) by...
       f     ...removing elements to the left that are not in the right

¹

Вен
источник
Возьмите ввод как список двух значений и избегайте ,. Это ẒƇизбыточно, нет простых простых факторов. Тогда ÆFḢ€ это справедливо Æf, за исключением того, что последний дает нам повторения, которые нам могут понадобиться, например, 26=2*13и в 125=5*5*5то время 2+13=5+5+5. Даже с этим, однако, это не достаточно хорошо, например, вместо 26использования, 182=2*7*13которое также должно найти это, 2+13=5+5+5но не делает - вместо этого мы хотим power-set ( ŒP) без ведущего, пустого элемента (мы можем использовать ). S€здесь можно заменить на §. - Вы, вероятно, можете сохранить байты с помощью $и Ɗ-.
Джонатан Аллан
Нет необходимости в тех приёмах, которые я упоминал в конце, которые мы можем использовать, )и с моими исправлениями, чтобы заставить его работать правильно (плюс замена œ&на f), код составляет 9 байтов: ÆfŒPḊ§)f/ try-it
Джонатан Аллан
Обновлено с объяснением. Еще раз спасибо :)!
Ven
1
Я немного обновил ваше объяснение.
Джонатан Аллан
0

Гея , 16 11 байт

ḍzΣ¦
↑@↑&ỵ!

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

Функция top (первая строка) вычисляет суммы набора степеней простых множителей, а вторая функция находит, если какой-либо из элементов пересечения ненулевой.

Giuseppe
источник