8
\$\begingroup\$

Let's say we have a n × n lattice; we can then divide the lattice into two sections by drawing a line through the lattice. Everything to one side of the line is in one set and everything else in another.

How many ways can we divide the lattice in the manner?

For example lets take a 2 × 2 lattice:

. .
. .

We can make 2 partitions dividing the lattice in half like so:

× ×    × o
o o    × o

We can also partition off each of the corners:

× o    o ×    o o    o o
o o    o o    × o    o ×

Lastly we can put all of the points in one partition by missing the lattice entirely:

× ×
× ×

This makes for a total of 7 partitions. Note that the following partition is not valid because it cannot be made with a single straight line.

× o
o ×

Here is a 3 × 3 lattice

. . .
. . .
. . .

There are 4 purely horizontal or vertical partitions

× × ×    × × ×    × o o    × × o
× × ×    o o o    × o o    × × o
o o o    o o o    × o o    × × o

There are 4 corner partitions

× o o    o o ×    o o o    o o o    
o o o    o o o    o o o    o o o
o o o    o o o    o o ×    × o o

There are 4 larger corner partitions

× × o    o × ×    o o o    o o o
× o o    o o ×    o o ×    × o o
o o o    o o o    o × ×    × × o

There are 8 partitions of partial corners

× × o    o × ×    o o ×    o o o    o o o    o o o    o o o    × o o
o o o    o o o    o o ×    o o ×    o o o    o o o    × o o    × o o
o o o    o o o    o o o    o o ×    o × ×    × × o    × o o    o o o

There are 8 knights move partitions

× × o    o × ×    × × ×    o o o    o o ×    × o o    o o o    × × ×
× o o    o o ×    o o ×    o o ×    o o ×    × o o    × o o    × o o
× o o    o o ×    o o o    × × ×    o × ×    × × o    × × ×    o o o

And there is one whole partition

× × ×
× × ×
× × ×

That makes for 29 partitions in total.

Task

Given a number n as input, output the number of partitions that can be made in this fashion of an n × n lattice.

This is a question so answers will be scored in bytes, with less bytes being better.

Test Cases

Here are the first 34 courtesy of the OEIS:

1, 7, 29, 87, 201, 419, 749, 1283, 2041, 3107, 4493, 6395, 8745, 11823, 15557, 20075, 25457, 32087, 39725, 48935, 59457, 71555, 85253, 101251, 119041, 139351, 161933, 187255, 215137, 246691, 280917, 319347, 361329, 407303

OEIS A114043

\$\endgroup\$
2
  • \$\begingroup\$ Can you please add an example with a lattice larger than 2×2? \$\endgroup\$ Jul 20, 2017 at 18:06
  • \$\begingroup\$ @EriktheOutgolfer Added. \$\endgroup\$
    – Wheat Wizard
    Jul 20, 2017 at 18:16

5 Answers 5

2
\$\begingroup\$

JavaScript (ES6), 113 111 bytes

Saved 2 bytes thanks to guest44851

0-indexed.

n=>[...Array(n)].map((_,i,a)=>a.map((_,j)=>x+=(g=(a,b)=>b?g(b,a%b):a<2&&(n-i-1)*(n-j))(i+1,++j)),x=n*++n)|x+x+1

Based on the formula mentioned on OEIS:

Let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)(n+1-j)
a(n+1) = 2(n2 + n + V(n,n)) + 1

Demo

let f =

n=>[...Array(n)].map((_,i,a)=>a.map((_,j)=>x+=(g=(a,b)=>b?g(b,a%b):a<2&&(n-i-1)*(n-j))(i+1,++j)),x=n*++n)|x+x+1

for(n = 0; n < 50; n++) {
  console.log('f(' + n + ') = ' + f(n));
}

\$\endgroup\$
3
  • \$\begingroup\$ You can replace a==1&& with a<2&&. \$\endgroup\$
    – user72349
    Jul 20, 2017 at 18:01
  • \$\begingroup\$ @guest44851 Yes, this one works. :-) Thanks! \$\endgroup\$
    – Arnauld
    Jul 20, 2017 at 18:05
  • \$\begingroup\$ You can also replace &&x+x+1 with |x+x+1. \$\endgroup\$
    – user72349
    Jul 20, 2017 at 18:06
1
\$\begingroup\$

Python 2, 116 bytes

lambda n:2*(~-n*n+sum((n-i)*(n-j)*g(i,j)for i in range(1,n)for j in range(1,n)))+1
g=lambda x,y:y and g(y,x%y)or x<2

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ R=range? Would that save some bytes? \$\endgroup\$
    – Adalynn
    Jul 20, 2017 at 22:51
  • \$\begingroup\$ @Zacharý not with two ranges \$\endgroup\$
    – ovs
    Jul 21, 2017 at 4:47
1
\$\begingroup\$

Jelly, 14 bytes

ạþ`Fgþ`FỊS_²H‘

Try it online!

Explanation

ạþ`Fgþ`FỊS_²H‘  Input: integer n
ạþ`             Form the table of absolute differences on [1, 2, ..., n]
   F            Flatten
    gþ`         Form a GCD table on that
       F        Flatten
        Ị       Test if the absolute value of each is <= 1
         S      Sum (Count the number of true's)
          _     Subtract
           ²    Square of n
            H   Halve
             ‘  Increment
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 59 bytes

2Sum[(#-i)(#-j)Boole[i~GCD~j<2],{i,#-1},{j,#-1}]+2#^2-2#+1&

courtesy of the OEIS (just like the question)

-1 byte from @ovs

Try it online!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ This is almost verbatim copied from the OEIS page \$\endgroup\$
    – nmjcman101
    Jul 20, 2017 at 17:31
  • 3
    \$\begingroup\$ The question is courtesy of the OEIS and so is this answer. An original question would have an original answer \$\endgroup\$
    – ZaMoC
    Jul 20, 2017 at 17:35
  • 3
    \$\begingroup\$ I don't disagree with you, which is why I didn't downvote, I just prefer transparency. \$\endgroup\$
    – nmjcman101
    Jul 20, 2017 at 17:39
  • 4
    \$\begingroup\$ Me too! But I think that OEIS-questions is an easy trick to get easy reputation points. That's why I answer in the same way, to state this situation \$\endgroup\$
    – ZaMoC
    Jul 20, 2017 at 17:43
  • \$\begingroup\$ You can replace ==1 with <2 TIO. \$\endgroup\$
    – ovs
    Jul 20, 2017 at 18:41
0
\$\begingroup\$

Python 2, 90 bytes

lambda n:4*n*n-6*n+3+4*sum((n-i)*(n-k/i)for i in range(n)for k in range(i*i)if k/i*k%i==1)
\$\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.