Равенство приходит в тройках

11

Взято из: OEIS- A071816

Ваша задача, учитывая верхнюю границу n, состоит в том, чтобы найти число решений, которые удовлетворяют уравнению:

a+b+c = x+y+z, where 0 <= a,b,c,x,y,z < n

Последовательность начинается, как описано на странице OEIS, и как показано ниже (1-индексированный):

1, 20, 141, 580, 1751, 4332, 9331, 18152, 32661, 55252, 88913, 137292, 204763, 296492, 418503, 577744, 782153, 1040724, 1363573, 1762004, 2248575, 2837164, 3543035, 4382904, 5375005, 6539156, 7896825, 9471196, 11287235, 13371756

Ведь n = 1есть только одно решение:(0,0,0,0,0,0)

Для n = 2, есть 20 заказанных решений (a,b,c,x,y,z)для a+b+c = x+y+z:

(0,0,0,0,0,0), (0,0,1,0,0,1), (0,0,1,0,1,0), (0,0,1,1,0,0), (0,1,0,0,0,1), 
(0,1,0,0,1,0), (0,1,0,1,0,0), (0,1,1,0,1,1), (0,1,1,1,0,1), (0,1,1,1,1,0), 
(1,0,0,0,0,1), (1,0,0,0,1,0), (1,0,0,1,0,0), (1,0,1,0,1,1), (1,0,1,1,0,1), 
(1,0,1,1,1,0), (1,1,0,0,1,1), (1,1,0,1,0,1), (1,1,0,1,1,0), (1,1,1,1,1,1).

I & O

  • Ввод - одно целое число, обозначающее n.
  • Выход - одно целое число / строка, обозначающая f(n), где f(...)указанная выше функция.
  • Индексация в точности соответствует описанию, никакая другая индексация неприемлема.

Это код-гольф , побеждает наименьшее количество байтов.

code-golf number sequence Урна волшебного осьминога
источник
Ааа crappp, я не заметил прямую формулу на OEIS, я думал , что это не было бы , что легко. О, хорошо, я не + 1 'прямые порты этого уравнения; P.
Волшебная урна осьминога
1
По крайней мере, формула не была идеальной: P
f Pnɛtɪk
Опять же, это дает рег-шангу шанс против эсо-ланга.
Волшебная Урна Осьминога
Было бы лучше, если бы заголовок "равенство приходит в тройках"?
Утренняя монахиня

Ответы:

11

Желе , 9 6 байт

ṗ6ḅ-ċ0

O (n 6 ) решение.

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

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

ṗ6ḅ-ċ0  Main link. Argument: n

ṗ6      Cartesian power 6; build all 6-tuples (a, x, b, y, c, z) of integers in
        [1, ..., n]. The challenge spec mentions [0, ..., n-1], but since there
        are three summands on each side, this doesn't matter.
  ḅ-    Unbase -1; convert each tuple from base -1 to integer, mapping (a, ..., z)
        to a(-1)**5 + x(-1)**4 + b(-1)**3 + y(-1)**2 + c(-1)**1 + z(-1)**0, i.e.,
        to -a + x - b + y - c + z = (x + y + z) - (a + b + c). This yields 0 if and
        only if the 6-tuple is a match.
    ċ0  Count the number of zeroes.
Деннис
источник
Ха! Должен любить теоретические ответы (моя основа для теоретического ответа - теперь он работает на TIO для больших значений n , это, вероятно, плохо). Я надеялся увидеть O(n^6)хоть: P.
Волшебная урна осьминога
9

Mathematica 17 или 76 байт

Используя формулу:

.55#^5+#^3/4+#/5&

(Сохранено 3 байта на @GregMartin и @ngenisis)

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

Length@Solve[a+b+c==x+y+z&&And@@Table[(0<=i<#),{i,{a,b,c,x,y,z}}],Integers]&
Келли Лоудер
источник
2
Спасибо за публикацию не грубой силы :). +1 для любого ответа математики, который не является уравнением или встроенным.
Волшебная урна осьминога
Согласно этому ответу , вы можете заменить 11/20на .55двухбайтовую экономию.
Грег Мартин
Вам также не нужна звездочка в первом семестре.
ngenisis
8

Haskell , 48 байтов

Я не заметил формулу до того, как написал это, так что это определенно не самый короткий (или самый быстрый) общий метод, но я подумал, что он хорош.

f n=sum[1|0<-foldr1(-)<$>pure[1..n]`mapM`[1..6]]

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

f nгенерирует все списки 6 элементов из [1..n], а затем подсчитывает те , у которых чередующиеся сумма 0. использует тот факт , что a+b+c==d+e+fтак же , как a-(d-(b-(e-(c-f))))==0, и что это не имеет значения , если мы добавим 1 ко всем номерам.

Орджан Йохансен
источник
Я заметил, что часто самый короткий ответ наименее впечатляющий;). Это довольно крутое использование сгиба, которое я бы не рассмотрел, прежде чем увидеть этот ответ.
Волшебная урна с осьминогом
6

MATL , 12 байт

l6:"G:gY+]X>

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

объяснение

Я не мог упустить шанс снова использовать свертку!

Это использует следующую характеристику от OEIS:

a(n) = largest coefficient of (1+...+x^(n-1))^6

и, конечно, полиномиальное умножение является сверткой.

l        % Push 1
6:"      % Do the following 6 times
  G:g    %   Push a vector of n ones, where n is the input
  Y+     %   Convolution
]        % End
X>       % Maximum
Луис Мендо
источник
5

Желе , 9 байт

ṗ3S€ĠL€²S

Не такой короткий, как у @ Dennis's, но он заканчивается менее чем за 20 секунд для ввода 100.

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

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

ṗ3S€ĠL€²S  Main link. Argument: n

ṗ3         Cartesian power; yield all subsets of [1, ..., n] of length 3.
  S€       Sum each. 
    Ġ      Group indices by their values; for each unique sum S, list all indices whose
           values are equal to S.
     L€    Length each; for each unique sum S, yield the number of items in the original
           array that sum to S.
       ²   Square each; for each unique sum S, yield the number of pairs that both sum to S.
        S  Sum; yield the total number of equal pairs.
ETHproductions
источник
Можете ли вы объяснить этот метод? В настоящее время я нахожусь в процессе изучения Jelly, но я все еще недостаточно хорош, чтобы представить реальные ответы; Я всегда обращаюсь к вам, Деннису и нескольким другим за хорошими примерами.
Волшебная урна осьминога
@carusocomputing Закончил объяснение. Дайте мне знать, если у вас остались какие-либо вопросы :-)
ETHproductions
Круто, я в основном запутался в оптимизации ответов от самой простой реализации грубой силы, которую я бы сделал для сумасшедшего короткого кода, который вы, ребята, публикуете; но я чувствую, что каждое объяснение на шаг ближе, спасибо!
Волшебная урна осьминога
5

Pyth, 13 12 байт

JsM^UQ3s/LJJ

Сохраненный один байт благодаря Leaky Nun.

объяснение

JsM^UQ3s/LJJ
   ^UQ3         Get all triples in the range.
JsM             Save the sums as J.
        /LJJ    Count occurrences of each element of J in J.
       s        Take the sum.

источник
+1 за неиспользование прямой формулы: P.
Волшебная урна осьминога
Вы можете разместить ссылку на онлайн-переводчика .
Утренняя монахиня
Также вы можете использовать /LJJвместо m/JdJ.
Утренняя монахиня
2

TI-BASIC, 19 байтов

:Prompt X
:.05X(11X^4+5X²+4

Оценивает формулу OEIS.

Скотт Милнер
источник
1
Как ты считаешь байты здесь? Prompt x= 2 байта?
Волшебная урна осьминога
@carusocomputing TI-BASIC оценивается токенами
dzaima
1
Как-то грустно, что я опубликовал ответ TI-BASIC 5 раз и никогда не набирал его правильно, когда просматриваю свою историю ._.
Волшебная урна осьминога
2

Оазис , 17 байт

5m11*n3m5*nz++20÷

5                   n 5             implicit n for illustration
 m                  n**5
  11                n**5 11
    *               11*n**5
     n              11*n**5 n
      3             11*n**5 n 3
       m            11*n**5 n**3
        5           11*n**5 n**3 5
         *          11*n**5 5*n**3
          n         11*n**5 5*n**3 n
           z        11*n**5 5*n**3 4*n
            +       11*n**5 5*n**3+4*n
             +      11*n**5+5*n**3+4*n
              20    11*n**5+5*n**3+4*n 20
                ÷  (11*n**5+5*n**3+4*n)÷20

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

Oasis - это стековый язык, оптимизированный для повторяющихся последовательностей. Однако формула рекурсии была бы слишком длинной для этого случая.

Дрянная Монахиня
источник
2

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

{>ℕ|↰}ᶠ⁶ḍD+ᵐ=∧D≜ᶜ

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

объяснение

{  |↰}ᶠ⁶           Generate a list of 6 variables [A,B,C,D,E,F]...
 >ℕ                  ...which are all in the interval [0, Input)
        ḍD         Dichotomize; D = [[A,B,C],[D,E,F]]
          +ᵐ=      A + B + C must be equal to D + E + F
             ∧
              D≜ᶜ  Count the number of possible ways you can label the elements of D while
                     satisfying the constraints they have
Fatalize
источник
Я предполагаю, что ᶜдолжен автоматически прийти с≜
Leaky Nun
@LeakyNun Вы не можете работать ᶜсамостоятельно, это метапредикат.
Fatalize
Но, тем не менее, если он используется в списке, маркировка этого списка может стать предикатом по умолчанию, нет?
мат
@mat Это можно сделать таким образом, но сейчас вы не можете использовать метапредикат для переменной.
Роковая
1

JavaScript, 24 байта

x=>11*x**5/20+x**3/4+x/5

Использует формулу со страницы OEIS.

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

fənɛtɪk
источник
Я думаю, что вы можете сохранить два байта сx=>x**5*.55+x**3/4+x/5
ETHproductions
@ETHproductions есть ошибки с плавающей запятой, если я использую * .55 вместо *
11/20
1

Октава , 25 23 21 байт

@(n).55*n^5+n^3/4+n/5

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

Использует формулу из OEIS-записи. Сохраненные два четыре байта, перестраивая формулу и используя .55вместо 11/20, благодаря fənɛtɪk.

Стьюи Гриффин
источник
1

Python 2.7, 109 105 99 96 байт

Спасибо ETHproductions и Деннису за сохранение нескольких байтов:

from itertools import*
lambda s:sum(sum(x[:3])==sum(x[3:])for x in product(range(s),repeat=6))
acidtobi
источник
Интересно, разве в Python 3 функции диапазона короче, чем в 2.7?
Волшебная Урна Осьминога
sum(sum(x[:3])==sum(x[3:])for x ...)будет еще короче. Также from itertools import*сохраняет байт.
Деннис
Вам не нужно пространство раньше for. Кроме того, мы не требуем, чтобы функции назывались по умолчанию, поэтому вы можете удалить их h=.
Деннис
1

Mathematica, 52 байта

Реализация формулы OEIS Келли Лоудером намного короче, но это вычисляет числа напрямую:

Count[Tr/@#~Partition~3&/@Range@#~Tuples~6,{n_,n_}]&

Ну, это фактически подсчитывает количество решений с 1 <= a,b,c,x,y,z <= n. Это то же самое число, так как добавление 1 ко всем переменным не меняет равенства.

Объяснение: Range@#~Tuples~6делает все списки из шести целых чисел от 1 до n, #~Partition~3&/@разбивает каждый список на два списка длиной 3, Tr/@суммирует эти подсписки и Count[...,{n_,n_}]подсчитывает, сколько пар имеют одинаковую сумму. Мне очень повезло с порядком старшинства между f @, f /@и ~f~!

Не дерево
источник
1

Октава , 41 байт

@(n)round(max(ifft(fft(~~(1:n),n^2).^6)))

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

Аналогично моему ответу на MATL , но вычисляет свертку с помощью дискретного преобразования Фурье ( fft) с достаточным количеством точек ( n^2). ~~(1:n)используется в качестве более короткой версии ones(1,n). roundнеобходимо из-за ошибок с плавающей точкой.

Луис Мендо
источник
0

CJam , 17 байт

ri,6m*{3/::+:=},,

Ввод 11тайм-аутов на TIO, 12и выше нехватка памяти.

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

объяснение

ri                e# Read an int from input.
  ,               e# Generate the range 0 ... input-1.
   6m*            e# Take the 6th Cartesian power of the range.
      {           e# Keep only the sets of 6 values where:
       3/         e#  The set split into (two) chunks of 3
         ::+:=    e#  Have the sums of both chunks equal.
              },  e# (end of filter)
                , e# Get the length of the resulting list.
Бизнес Кот
источник
0

Clojure, 79 байт

#(count(for[r[(range %)]a r b r c r x r y r z r :when(=(+ a b c)(+ x y z))]1))

Тонны повторения в коде, при большем числе переменных макрос может быть короче.

NikoNyrh
источник