10
\$\begingroup\$

Let's define f(n) as the maximal 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:

Improve this question
\$\endgroup\$
0

19 Answers 19

Reset to default
6
\$\begingroup\$

Mathematica, 23 bytes

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

Uses the formula in the question.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 29 bytes

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

Uses a formula given in OEIS.

Improve this answer
\$\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.
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to PPCG and great first answer! \$\endgroup\$
    – mbomb007
    Commented Oct 21, 2016 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
Improve this answer
\$\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.
Improve this answer
\$\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)

Improve this answer
\$\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.

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I was 2 seconds from submitting the same solution, nice! \$\endgroup\$
    – Billywob
    Commented Oct 21, 2016 at 11:43
3
\$\begingroup\$

tinylisp, 73 bytes

(load library)
(d D(q((N)(+(/(*(s N 1)N(s N 2)(s N 3))24)(/(*(s N 1)N)2)1

Try it online!

From Giuseppe.

tinylisp, 90 bytes

(d C(q((N K)(i K(i N(a(C(s N 1)(s K 1))(C(s N 1)K))0)1
(d D(q((N)(a(a(C N 0)(C N 2))(C N 4

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ You're only using library for + which is rather wasteful so just use a twice: Try it online! I think neil's answer is using floordiv which is why it doesn't port quite right. \$\endgroup\$
    – Giuseppe
    Commented Feb 4, 2022 at 15:32
  • \$\begingroup\$ Could port the R answer as well... \$\endgroup\$
    – Giuseppe
    Commented Feb 4, 2022 at 15:41
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
$
Improve this answer
\$\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
Improve this answer
\$\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
Improve this answer
\$\endgroup\$
2
\$\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.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'm not sure, but can't you remove the ) on the last nCr? \$\endgroup\$
    – Oliver Ni
    Commented Oct 24, 2016 at 20:29
  • \$\begingroup\$ @Oliver Hi "Not Sure", I am also Not Sure. (Idiocracy is a great movie). \$\endgroup\$
    – Magic Octopus Urn
    Commented Oct 24, 2016 at 20:30
  • \$\begingroup\$ Isn't nCr(n,0) always equal to 1? \$\endgroup\$
    – Giuseppe
    Commented Feb 4, 2022 at 15:38
2
\$\begingroup\$

Excel, 31 bytes

=(A1^2*(A1-6)+A1*23-18)*A1/24+1

Link to Spreadsheet

Using one of OEIS formulas

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Factor + math.combinatorics math.unicode, 29 bytes

[ "\0"[ nCk ] with map Σ ]

Try it online!

You might not be able to see them here, but there are literal 2 and literal 4 control codes embedded in the string. It's a shorter version of { 2 4 0 }. You can see them for sure on TIO.

Improve this answer
\$\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
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Vyxal d, 4 bytes

3ʁdƈ

Try it Online!

Simply an implementation of the formula.

Improve this answer
\$\endgroup\$
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.

Improve this 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).

Improve this answer
\$\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
    Commented Oct 21, 2016 at 23:37

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.