8
\$\begingroup\$

Let's define f(n) as the aximal number of regions obtained by joining n points around a circle by straight lines. For example, two points would split the circle into two pieces, three into four, like this: enter image description here

Make sure when you are drawing the lines, you don't have an intersection of more than two lines.

Your task

Given a number n, print f(n).

Test cases:

 n | f(n)   
---+-----
 1 |   1
 2 |   2
 3 |   4
 4 |   8
 5 |  16
 6 |  31
 7 |  57
 8 |  99
 9 | 163

You can see more here.

Using built-in sequence generators is not allowed.

Remember, this is , so the code with the smallest number of bytes wins.

If you guys want the formula, here it is:

\$\endgroup\$
0

15 Answers 15

6
\$\begingroup\$

Mathematica, 23 bytes

Tr@Binomial[#,{0,2,4}]&

Uses the formula in the question.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 29 bytes

n=>(((n-6)*n+23)*n/6-3)*n/4+1

Uses a formula given in OEIS.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 6 bytes

5Ḷc@’S

Try it online! | Verify test cases

Explanation

Uses the OEIS formula ((n-1)C4 + (n-1)C3 + ... + (n-1)C0).

5Ḷc@’S    Main link.  Args: n

5         Yield 5.
 Ḷ        Lowered range: yield [0,1,2,3,4].
    ’     Yield n-1.
   @      Swap operands of the preceding dyad, 'c'.
  c       Combinations: yield [(n-1)C0, (n-1)C1, (n-1)C2, (n-1)C3, (n-1)C4].
     S    Sum: return (n-1)C0 + (n-1)C1 + (n-1)C2 + (n-1)C3 + (n-1)C4.
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to PPCG and great first answer! \$\endgroup\$ – mbomb007 Oct 21 '16 at 15:29
3
\$\begingroup\$

MATL, 7 bytes

q5:qXns

Try it online! Or verify all test cases.

Explanation

Uses the formula (from OEIS): a(n) = C(n−1, 4) + C(n−1, 3) + ... + C(n−1, 0)

q      % Implicit input. Subtract 1
5:q    % Array [0 1 2 3 4]
Xn     % Binomial coefficient, vectorized
s      % Sum
\$\endgroup\$
3
\$\begingroup\$

Jelly, 6 bytes

c3ḶḤ¤S

Try it online! or verify all test cases.

How it works

c3ḶḤ¤S  Main link. Argument: n

    ¤   Combine the three links to the left into a niladic chain.
 3        Yield 3.
  Ḷ       Unlength; yield [0, 1, 2].
   Ḥ      Unhalve; yield [0, 2, 4].
c       Combinations; compute [nC0, nC2, nC4].
     S  Sum; return nC0 + nc2 + nC4.
\$\endgroup\$
3
\$\begingroup\$

Java 7,50 47 bytes

int c(int n){return(n*n*(n-6)+23*n-18)*n/24+1;}

Uses the formula (from OEIS)

\$\endgroup\$
3
\$\begingroup\$

><>, 27 26+3 = 29 bytes

3 bytes added for the -v flag

::::6-**$f8+*f3+-+*f9+,1+n

Try it online!

A byte saved thanks to Martin Ender.

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

R, 25 bytes

sum(choose(scan(),0:2*2))

scan() takes the input n from stdin, which is passed to choose along with 0:2*2. This latter term is 0 to 2 (i.e. [0, 1, 2]) multiplied by 2, which is [0, 2, 4]. Since choose is vectorized, this calculates n choose 0, n choose 2, n choose 4, and returns them in a list. Finally, sum returns the sum of these numbers, surprisingly enough.

I don't think that this can be golfed further but I would be very happy to be proven wrong!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I was 2 seconds from submitting the same solution, nice! \$\endgroup\$ – Billywob Oct 21 '16 at 11:43
2
\$\begingroup\$

dc, 21

?ddd6-*23+*6/3-*4/1+p

RPN-ised version of @Neil's answer.

Test output:

$ for i in {1..9}; do dc -e "?ddd6-*23+*6/3-*4/1+p" <<< $i; done
1
2
4
8
16
31
57
99
163
$ 
\$\endgroup\$
2
\$\begingroup\$

J, 9 bytes

+4&!+2!<:

Uses the formula C(n-1, 2) + C(n, 4) + n = C(n, 0) + C(n, 2) + C(n, 4).

Usage

   f =: +4&!+2!<:
   (,.f"0) >: i. 10
 1   1
 2   2
 3   4
 4   8
 5  16
 6  31
 7  57
 8  99
 9 163
10 256
   f 20
5036

Explanation

+4&!+2!<:  Input: integer n
       <:  Decrement n
     2     The constant 2
      !    Binomial coefficient C(n-1, 2)
 4&!       Binomial coefficient C(n, 4)
    +      Add them
+          Add that to n and return
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 6 bytes

2Ý·scO

Try it online!

Explanation

Straight implementation of the OEIS formula c(n,4) + c(n,2) + c(n,0)

2Ý       # range: [0,1,2]
  ·      # multiply by 2: [0,2,4]
   s     # swap list with input
    c    # combinations
     O   # sum
\$\endgroup\$
1
\$\begingroup\$

Actually, 6 bytes

D╣5@HΣ

Try it online!

Explanation:

D╣5@HΣ
D       decrement input
 ╣      push that row of Pascal's triangle
  5@H   first 5 values
     Σ  sum
\$\endgroup\$
0
0
\$\begingroup\$

Scala, 35 bytes

(n:Int)=>(n*n*(n-6)+23*n-18)*n/24+1

Uses the same formula as numberknot's java answer.

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

Octave, 27 bytes

@(m)binocdf(4,m-1,.5)*2^m/2

This is an anonymous function.

Try it at Ideone.

Explanation

This is based on the OEIS formula a(m) = C(m−1, 4) + C(m−1, 3) + ... + C(m−1, 0), where C are binomial coefficients. The binomial distribution function

enter image description here

for k = 4, n = m−1 and p = 1/2 gives 2m−1a(m).

\$\endgroup\$
1
  • \$\begingroup\$ @Oliver That would probably end up being longer, because then it's not the distribution function. I would need the probability (mass) function and sum; something like @(m)sum(binopdf(0:2:4,m,.5)*2^m) \$\endgroup\$ – Luis Mendo Oct 21 '16 at 23:37
0
\$\begingroup\$

TI-89 Basic, 57 Bytes

:Def a(a)=Func
:Return nCr(n,0)+nCr(n,2)+nCr(n,4)
:End Func

Throwback to old times.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm not sure, but can't you remove the ) on the last nCr? \$\endgroup\$ – Oliver Ni Oct 24 '16 at 20:29
  • \$\begingroup\$ @Oliver Hi "Not Sure", I am also Not Sure. (Idiocracy is a great movie). \$\endgroup\$ – Magic Octopus Urn Oct 24 '16 at 20:30

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.