# Taken from: OEIS-A071816

Your task, given an upper bound of n, is to find the number of solutions that satisfy the equation:

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


The sequence starts out as described on the OEIS page, and as below (1-indexed):

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


For n = 1, there's only one solution: (0,0,0,0,0,0)

For n = 2, there are 20 ordered solutions (a,b,c,x,y,z) to 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

• Input is a single integer denoting n.
• Output is a single integer/string denoting f(n), where f(...) is the function above.
• The indexing is exactly as described, no other indexing is acceptable.

This is , lowest byte-count wins.

• Ahhh crappp, I didn't notice the direct formula on OEIS, I thought this wouldn't be that easy. Oh well, I'm not +1'ing direct ports of that equation ;P. – Magic Octopus Urn Apr 28 '17 at 20:26
• At least the formula wasn't perfectly golfed :P – fəˈnɛtɪk Apr 28 '17 at 20:30
• Then again, it gives reg-langs a chance against the eso-langs. – Magic Octopus Urn Apr 28 '17 at 20:44
• Would it be better if the title is "equality comes in triplets"? – Leaky Nun Apr 29 '17 at 15:40

# Jelly, 9 6 bytes

ṗ6ḅ-ċ0


O(n6) solution.

Try it online!

### How it works

ṗ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.

• Ha! Gotta love the theoretical answers (my basis for a theoretical answer is now does it run on TIO for large values of n, this is probably bad). I was hoping to see a O(n^6) though :P. – Magic Octopus Urn Apr 28 '17 at 20:55

## Mathematica 17 or 76 Bytes

Using the formula:

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


(Saved 3 bytes per @GregMartin and @ngenisis)

Rather than using the formula, here I literally compute all the solutions and count them.

Length@Solve[a+b+c==x+y+z&&And@@Table[(0<=i<#),{i,{a,b,c,x,y,z}}],Integers]&

• Thanks for posting the non-brute-force way :). +1 for any mathematica answer that isn't an equation or a built-in. – Magic Octopus Urn Apr 28 '17 at 21:52
• As per this answer, you can replace 11/20 by .55 for a two-byte savings. – Greg Martin Apr 28 '17 at 23:23
• You also don't need the asterisk in the first term. – ngenisis Apr 28 '17 at 23:25

I didn't notice the formula before writing this, so it's definitely not the shortest (or fastest) general method, but I thought it was pretty.

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


Try it online!

f n generates all lists of 6 elements from [1..n], then counts the ones whose alternating sum is 0. Uses the fact that a+b+c==d+e+f is the same as a-(d-(b-(e-(c-f))))==0, and also that it doesn't matter if we add a 1 to all the numbers.

• I've noticed that, often, the shortest answer is the least impressive ;). This is a pretty cool use of fold that I wouldn't've considered before seeing this answer. – Magic Octopus Urn Apr 28 '17 at 21:00

# MATL, 12 bytes

l6:"G:gY+]X>


Try it online!

### Explanation

I couldn't miss the chance to use convolution again!

This makes use of the following characterization from OEIS:

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

and of course polynomial multiplication is convolution.

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


# Jelly, 9 bytes

ṗ3S€ĠL€²S


Not as short as @Dennis's, but it finishes in under 20 seconds for input 100.

Try it online!

### How it works

ṗ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.

• Can you explain this method? I'm currently in the process of learning Jelly, but I'm still not good enough to submit real answers yet; I always look to you, Dennis and a few others for good examples. – Magic Octopus Urn Apr 28 '17 at 20:57
• @carusocomputing Finished the explanation. Let me know if you still have any questions :-) – ETHproductions Apr 28 '17 at 21:04
• Awesome, I'm mostly confused on the optimization of answers from the most basic of brute-force implementation that I would do to the crazy short code I see you guys posting; but I feel like every explanation is a step closer thank you! – Magic Octopus Urn Apr 28 '17 at 21:08

# Pyth, 13 12 bytes

JsM^UQ3s/LJJ


Saved one byte thanks to Leaky Nun.

Explanation

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 for not using the direct formula :P. – Magic Octopus Urn Apr 28 '17 at 20:26
• You might like to post a link to the online interpreter. – Leaky Nun Apr 29 '17 at 1:29
• Also, you can use /LJJ instead of m/JdJ. – Leaky Nun Apr 29 '17 at 1:37

# Python 3, 28 bytes

lambda n:.55*n**5+n**3/4+n/5


Try it online!

# TI-BASIC, 19 bytes

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


Evaluates the OEIS formula.

• How are you counting the bytes here? Prompt x = 2 bytes? – Magic Octopus Urn Apr 28 '17 at 20:28
• @carusocomputing TI-BASIC is scored by tokens – dzaima Apr 28 '17 at 20:29
• Kinda sad that I've posted a TI-BASIC answer 5 times before and never scored it correctly now that I look through my history ._. – Magic Octopus Urn Apr 28 '17 at 20:58

# Oasis, 17 bytes

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


Try it online!

Oasis is a stack-based language optimized for recurring sequences. However, the recursion formula would be too long for this case.

# Brachylog, 17 bytes

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


Try it online!

### Explanation

{  |↰}ᶠ⁶           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

• I guess ᶜ should automatically come with ≜ – Leaky Nun Apr 29 '17 at 15:32
• @LeakyNun You can't run ᶜ by itself, it's a metapredicate. – Fatalize Apr 29 '17 at 15:34
• But still if it is used on a list, labeling that list could be made the default predicate, no? – mat May 1 '17 at 10:56
• @mat It could be made that way, but right now you cannot use a metapredicate on a variable. – Fatalize May 1 '17 at 13:55

# JavaScript, 24 bytes

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


Uses the formula from the OEIS page.

Try it online!

• I think you can save two bytes with x=>x**5*.55+x**3/4+x/5 – ETHproductions Apr 28 '17 at 21:24
• @ETHproductions there are floating point errors if I use *.55 instead of *11/20 – fəˈnɛtɪk Apr 28 '17 at 22:51

# Octave, 2523 21 bytes

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


Try it online!

Uses the formula from the OEIS-entry. Saved two four bytes by rearranging the formula and using .55 instead of 11/20, thanks to fəˈnɛtɪk.

# Python 2.7, 10910599 96 bytes

Thanks ETHproductions and Dennis for saving a few bytes:

from itertools import*
lambda s:sum(sum(x[:3])==sum(x[3:])for x in product(range(s),repeat=6))

• Interesting, doesn't Python 3 have shorter range functions than 2.7? – Magic Octopus Urn Apr 28 '17 at 21:51
• sum(sum(x[:3])==sum(x[3:])for x ...) would be even shorter. Also, from itertools import* saves a byte. – Dennis Apr 28 '17 at 21:59
• You don't need the space before for. Also, we don't require functions to be named by default, so you can remove h=. – Dennis Apr 28 '17 at 22:04

## Mathematica, 52 bytes

Kelly Lowder's implementation of the OEIS formula is way shorter, but this computes the numbers directly:

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


Well, it actually counts the number of solutions with 1 <= a,b,c,x,y,z <= n. This is the same number, since adding 1 to all the variables doesn't change the equality.

Explanation: Range@#~Tuples~6 makes all lists of six integers between 1 and n, #~Partition~3&/@ splits each list into two lists of length 3, Tr/@ sums these sublists, and Count[...,{n_,n_}] counts how many pairs have the same sum. I got very lucky with the order of precedence between f @, f /@ and ~f~!

# Octave, 41 bytes

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


Try it online!

Similar to my MATL answer, but computes the convolution via a discrete Fourier transform (fft) with a sufficient number of points (n^2). ~~(1:n) is used as a shorter version of ones(1,n). round is necessary because of floating point errors.

# CJam, 17 bytes

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


Input of 11 times out on TIO, and 12 and higher run out of memory.

Try it online!

Explanation

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.


## Clojure, 79 bytes

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


Tons of repetition in the code, on larger number of variables a macro might be shorter.