5
$\begingroup$

I want to find a formula to calculate the number of dispersion lines I can draw from any one corner of a square dot matrix of size $n \times n$.

By dispersion lines, I mean the lines that connect a particular point to all other points in a dot diagram. Here's a picture of what I mean :

Diagram

(That's an approximate diagram of what I mean; sorry for the crude diagram)
Here, the horizontal blue line on the top row (when considered a straight line) connects many dots to a single point (thus all those dots on the line are collinear), so when we count the number of dispersion lines, we have to count lines connecting many collinear points as one and we mustn't take the subunits into consideration.

So when we consider a square dot matrix, where the dots are arranged as a square, we can draw $3$ apparent dispersion lines, plus some more. What I would like to find is a formula to calculate the number of dispersion lines in square dot grids (or dot matrices).
What I have at hand is this one formula that I tried to formulate today:$$n^2 - (n + 2(n - 1)) + 3$$ The problem is that this formula isn't working for all values of $n$ (I mean, the number of dots in a column/row of the square dot matrix), and also I haven't been able to spend sufficient time to find the number of dispersion lines for $n > 5$. If asked for, I'll attach the numbers below.

Any help in formulating an accurate formula is appreciated. If such a formula exists, please do tell me.

Thanks in advance.

$\endgroup$
3
  • $\begingroup$ Euclid's orchard $\endgroup$ – Jean Marie Oct 30 '20 at 7:00
  • $\begingroup$ @JeanMarie , I'll try checking it out.. $\endgroup$ – Spectre Oct 30 '20 at 7:00
  • $\begingroup$ @JeanMarie , I am immature to understand all that.. maybe a simpler thing would suffice... $\endgroup$ – Spectre Oct 30 '20 at 7:09
4
$\begingroup$

For $n=5$, the slopes of lines are in ascending order

$${\color{red}{0},\color{blue}{\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},}\color{red}{1},\color{green}{\frac{4}{3},\frac{3}{2},2,3,4,}\color{red}{\infty}}$$

where blue and green are reciprocal of each other (symmetry about principal diagonal), hence equal in number.

Observe green slopes can be grouped as $$ \color{green}{\underbrace{\frac{4}{3},\frac{4}{1}},\underbrace{\frac{3}{2},\frac{3}{1}},\underbrace{\frac{2}{1}}}$$

where numerators run from $2$ to $4$ and denominators are respectively coprime to numerators.

In general, this series runs from $i=2$ to $i=n-1$ and counts for all integers less than $i$ and coprime to it. We have Euler's totient function to count this, it is simply $\varphi(i)$.

Hence desired number of dispersion lines is $$f(n) = \color{red}{3} + \color{green}{2\sum_{i=2}^{n-1}} \color{green}{\varphi(i)} $$

We get following values

  • $n=2$, $f(n) = 3$
  • $n=3$, $f(n) = 5$
  • $n=4$, $f(n) = 9$
  • $n=5$, $f(n) = 13$
  • $n=6$, $f(n) = 21$
  • $n=7$, $f(n) = 25$

$f(n)$ satisfies the recurrence relation $$f(n) = f(n-1) + 2\varphi(n-1)$$

$\endgroup$
17
  • $\begingroup$ is this what's in Euclid's Orchard ? I am a $10^{\text{th}}$ grader, so I have no idea of such stuff. $\endgroup$ – Spectre Oct 30 '20 at 8:32
  • 3
    $\begingroup$ You don't know about Euler's totient function, but you're asking about Brocard's problem? Look – the trouble with Number Theory is that it has a lot of problems that anyone can understand, but that no one can solve. It has other problems anyone can understand, but it takes a math degree to understand the solution. It's very easy to bite off more than you can chew. If you're interested in this sort of problem, there's no escaping it: you're going to have to sit yourself down and learn a lot of (fun) math. Get an intro Number Theory text, and start reading! $\endgroup$ – Gerry Myerson Oct 30 '20 at 8:40
  • 1
    $\begingroup$ As @GerryMyerson pointed out, please make yourself more thorough in Number theory, so you develop more tools and understanding necessary to attack the bigger problems. They're unsolved for a reason - for the depth they encompass, please understand that. $\endgroup$ – cosmo5 Oct 30 '20 at 8:43
  • 2
    $\begingroup$ @cosmo5 I asked in OEIS a sequence beginning by 3,5,9,13,21,25,.. : I obtained this answer mentionning "J. D. Laison and M. Schick, Seeing dots: visibility of lattice points, Mathematics Magazine, Vol. 80 (2007), pp. 274-282. See page 281 reference 13"... Please note the keywords "lattice points visibility" giving many Google interesting hits. $\endgroup$ – Jean Marie Oct 30 '20 at 16:49
  • 1
    $\begingroup$ Thank you, @JeanMarie! $\endgroup$ – cosmo5 Oct 30 '20 at 17:10

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.