11
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 28, 2017 at 20:26
  • 1
    \$\begingroup\$ At least the formula wasn't perfectly golfed :P \$\endgroup\$ Apr 28, 2017 at 20:30
  • \$\begingroup\$ Then again, it gives reg-langs a chance against the eso-langs. \$\endgroup\$ Apr 28, 2017 at 20:44
  • \$\begingroup\$ Would it be better if the title is "equality comes in triplets"? \$\endgroup\$
    – Leaky Nun
    Apr 29, 2017 at 15:40

17 Answers 17

11
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 28, 2017 at 20:55
9
\$\begingroup\$

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]&
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Thanks for posting the non-brute-force way :). +1 for any mathematica answer that isn't an equation or a built-in. \$\endgroup\$ Apr 28, 2017 at 21:52
  • \$\begingroup\$ As per this answer, you can replace 11/20 by .55 for a two-byte savings. \$\endgroup\$ Apr 28, 2017 at 23:23
  • \$\begingroup\$ You also don't need the asterisk in the first term. \$\endgroup\$
    – user61980
    Apr 28, 2017 at 23:25
8
\$\begingroup\$

Haskell, 48 bytes

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 28, 2017 at 21:00
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 28, 2017 at 20:57
  • \$\begingroup\$ @carusocomputing Finished the explanation. Let me know if you still have any questions :-) \$\endgroup\$ Apr 28, 2017 at 21:04
  • \$\begingroup\$ 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! \$\endgroup\$ Apr 28, 2017 at 21:08
5
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ +1 for not using the direct formula :P. \$\endgroup\$ Apr 28, 2017 at 20:26
  • \$\begingroup\$ You might like to post a link to the online interpreter. \$\endgroup\$
    – Leaky Nun
    Apr 29, 2017 at 1:29
  • \$\begingroup\$ Also, you can use /LJJ instead of m/JdJ. \$\endgroup\$
    – Leaky Nun
    Apr 29, 2017 at 1:37
4
\$\begingroup\$

Python 3, 28 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

TI-BASIC, 19 bytes

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

Evaluates the OEIS formula.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ How are you counting the bytes here? Prompt x = 2 bytes? \$\endgroup\$ Apr 28, 2017 at 20:28
  • \$\begingroup\$ @carusocomputing TI-BASIC is scored by tokens \$\endgroup\$
    – dzaima
    Apr 28, 2017 at 20:29
  • 1
    \$\begingroup\$ 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 ._. \$\endgroup\$ Apr 28, 2017 at 20:58
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ I guess should automatically come with \$\endgroup\$
    – Leaky Nun
    Apr 29, 2017 at 15:32
  • \$\begingroup\$ @LeakyNun You can't run by itself, it's a metapredicate. \$\endgroup\$
    – Fatalize
    Apr 29, 2017 at 15:34
  • \$\begingroup\$ But still if it is used on a list, labeling that list could be made the default predicate, no? \$\endgroup\$
    – mat
    May 1, 2017 at 10:56
  • \$\begingroup\$ @mat It could be made that way, but right now you cannot use a metapredicate on a variable. \$\endgroup\$
    – Fatalize
    May 1, 2017 at 13:55
1
\$\begingroup\$

JavaScript, 24 bytes

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

Uses the formula from the OEIS page.

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I think you can save two bytes with x=>x**5*.55+x**3/4+x/5 \$\endgroup\$ Apr 28, 2017 at 21:24
  • \$\begingroup\$ @ETHproductions there are floating point errors if I use *.55 instead of *11/20 \$\endgroup\$ Apr 28, 2017 at 22:51
1
\$\begingroup\$

Octave, 25 23 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.

\$\endgroup\$
0
1
\$\begingroup\$

Python 2.7, 109 105 99 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))
\$\endgroup\$
3
  • \$\begingroup\$ Interesting, doesn't Python 3 have shorter range functions than 2.7? \$\endgroup\$ Apr 28, 2017 at 21:51
  • \$\begingroup\$ sum(sum(x[:3])==sum(x[3:])for x ...) would be even shorter. Also, from itertools import* saves a byte. \$\endgroup\$
    – Dennis
    Apr 28, 2017 at 21:59
  • \$\begingroup\$ You don't need the space before for. Also, we don't require functions to be named by default, so you can remove h=. \$\endgroup\$
    – Dennis
    Apr 28, 2017 at 22:04
1
\$\begingroup\$

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~!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.