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\$
  • \$\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\$ – Magic Octopus Urn Apr 28 '17 at 20:26
  • 1
    \$\begingroup\$ At least the formula wasn't perfectly golfed :P \$\endgroup\$ – fəˈnɛtɪk Apr 28 '17 at 20:30
  • \$\begingroup\$ Then again, it gives reg-langs a chance against the eso-langs. \$\endgroup\$ – Magic Octopus Urn Apr 28 '17 at 20:44
  • \$\begingroup\$ Would it be better if the title is "equality comes in triplets"? \$\endgroup\$ – Leaky Nun Apr 29 '17 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\$
  • \$\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\$ – Magic Octopus Urn Apr 28 '17 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\$
  • 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\$ – Magic Octopus Urn Apr 28 '17 at 21:52
  • \$\begingroup\$ As per this answer, you can replace 11/20 by .55 for a two-byte savings. \$\endgroup\$ – Greg Martin Apr 28 '17 at 23:23
  • \$\begingroup\$ You also don't need the asterisk in the first term. \$\endgroup\$ – ngenisis Apr 28 '17 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\$
  • \$\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\$ – Magic Octopus Urn Apr 28 '17 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\$
  • \$\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\$ – Magic Octopus Urn Apr 28 '17 at 20:57
  • \$\begingroup\$ @carusocomputing Finished the explanation. Let me know if you still have any questions :-) \$\endgroup\$ – ETHproductions Apr 28 '17 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\$ – Magic Octopus Urn Apr 28 '17 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\$
  • \$\begingroup\$ +1 for not using the direct formula :P. \$\endgroup\$ – Magic Octopus Urn Apr 28 '17 at 20:26
  • \$\begingroup\$ You might like to post a link to the online interpreter. \$\endgroup\$ – Leaky Nun Apr 29 '17 at 1:29
  • \$\begingroup\$ Also, you can use /LJJ instead of m/JdJ. \$\endgroup\$ – Leaky Nun Apr 29 '17 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\$
  • 1
    \$\begingroup\$ How are you counting the bytes here? Prompt x = 2 bytes? \$\endgroup\$ – Magic Octopus Urn Apr 28 '17 at 20:28
  • \$\begingroup\$ @carusocomputing TI-BASIC is scored by tokens \$\endgroup\$ – dzaima Apr 28 '17 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\$ – Magic Octopus Urn Apr 28 '17 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\$
  • \$\begingroup\$ I guess should automatically come with \$\endgroup\$ – Leaky Nun Apr 29 '17 at 15:32
  • \$\begingroup\$ @LeakyNun You can't run by itself, it's a metapredicate. \$\endgroup\$ – Fatalize Apr 29 '17 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 '17 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 '17 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\$
  • \$\begingroup\$ I think you can save two bytes with x=>x**5*.55+x**3/4+x/5 \$\endgroup\$ – ETHproductions Apr 28 '17 at 21:24
  • \$\begingroup\$ @ETHproductions there are floating point errors if I use *.55 instead of *11/20 \$\endgroup\$ – fəˈnɛtɪk Apr 28 '17 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\$
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\$
  • \$\begingroup\$ Interesting, doesn't Python 3 have shorter range functions than 2.7? \$\endgroup\$ – Magic Octopus Urn Apr 28 '17 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 '17 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 '17 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, privacy policy and cookie policy

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