Counting intersections of lines in a triangle

[haruspex]

As a result of working on https://www.physicsforums.com/threads/area-of-hexagon-geometry-challenge.914759, this question occurred to me:
Divide each side of a triangle into n equal lengths. Connect the ends of each length to the opposite vertex with straight lines, thereby forming 3n overlapping triangles of equal area.
(The problem at the link is an example with n=3.)
At how many points will three lines intersect?

I can show this is equivalent to finding the number of integer solutions to
abc = (n-a)(n-b)(n-c)
This is easy for n even. For n odd I have not found any, but don't yet see how to prove there are none.

[Edit: I mean it is easy to find some solutions for n even. If there are solutions for n odd then these lead to additional solutions for 2n.]

A follow-on question: how many regions are formed? How many triangles, quadrilaterals, ..., hexagons?

 

[mfb]

A follow-on question: how many regions are formed?

If there are no points where three lines intersect: If we have N_A lines to vertex A and N_B lines to vertex B, a new line to vertex C will add N_A+N_B+1 regions.

We start with 1 region.
Draw all lines from A, then we have n regions.
Draw all lines from B, adding n regions n-1 times, for a total of n² regions.
Draw all lines from C, adding 2n-1 regions n-1 times, for a total of n²+(2n-1)(n-1) = 3n² - 3n + 1 regions.

A point where three lines intersect is like a triangle with zero area, therefore we can always subtract this number from the previous result to get the total number of regions in the general case, once the original problem has been answered.

abc = (n-a)(n-b)(n-c)

If n is odd, then a,b,c cannot be all odd, otherwise the left side is odd and the right side is even. That means abc is even. At least one of a,b,c has to be odd to make the right side even, and at least one has to be even to make the left side even.

 

[haruspex]

If there are no points where three lines intersect: If we have N_A lines to vertex A and N_B lines to vertex B, a new line to vertex C will add N_A+N_B+1 regions.

We start with 1 region.
Draw all lines from A, then we have n regions.
Draw all lines from B, adding n regions n-1 times, for a total of n² regions.
Draw all lines from C, adding 2n-1 regions n-1 times, for a total of n²+(2n-1)(n-1) = 3n² - 3n + 1 regions.

A point where three lines intersect is like a triangle with zero area, therefore we can always subtract this number from the previous result to get the total number of regions in the general case, once the original problem has been answered.

Neat. Any thoughts on numbers of triangles etc?

If n is odd, then a,b,c cannot be all odd, otherwise the left side is odd and the right side is even. That means abc is even. At least one of a,b,c has to be odd to make the right side even, and at least one has to be even to make the left side even

Not sure how that helps. E.g. a could be 4 mod 8 while n-b and n-c are each 2 mod 4.

 

[mfb]

Neat. Any thoughts on numbers of triangles etc?

First assume no three lines intersect. A line crossing x other lines creates 4x+3 new interior corners. Same approach as before:
Start with an empty triangle. 3 interior angles.
Add n-1 lines from A to get (n-1)*3=3n-3 more corners.
Add n-1 lines from B for additional (n-1)*(4(n-1)+3) = 4n^2 - 5n + 1 corners.
Add n-1 lines from C for additional (n-1)*(4(2n-2)+3) = 8n^2 - 13n + 5 corners.
Sum: 12n² - 15n + 6

A point where three lines intersect has just 6 angles instead of 12. Therefore, subtract 6 times the number of these points for the general case.

We have T triangles, Q quadrilaterals, P pentagons and H hexagons. We have X points where three lines cross.

We now have two equations:
T+Q+P+H+X = 3n² - 3n + 1
3T + 4Q + 5P + 6H + 6X = 12n² - 15n + 6

Just needs three more equations.

I would expect that H=1 for n odd, H=0 for n even.
P=3H? Edit: Turns out to be wrong.

 

[chiro]

Hey haruspex.

Since this is linear, have you tried setting up a matrix equation for all lines and making sure that it meets the constraint for the parameters of those lines?

A triangle has a finite length for each edge so in addition to solving a system Ax = b, you need to make sure that certain parameters are within proper intervals.

This is an example of a constrained optimization problem.

 

[mfb]

I would expect that abc = (n-a)(n-b)(n-c) is the result of that approach.

A triangle has a finite length for each edge so in addition to solving a system Ax = b, you need to make sure that certain parameters are within proper intervals.

There are no intersections outside.

Not sure how that helps. E.g. a could be 4 mod 8 while n-b and n-c are each 2 mod 4.

Not sure how that helps either, but I thought it could be interesting.

 

[haruspex]

I would expect that abc = (n-a)(n-b)(n-c) is the result of that approach.

I drew a triangle with sides 1, 1, √2 as model and, working in a clockwise direction, marked points on the edges at (fraction) a, b, c from each starting vertex. I wrote down the equations for the three lines connecting them to their opposite vertices and took them all to pass through some point (x,y).

 

[mfb]

There are odd solutions. Here are the first few, excluding permutations:

n= 15 , a= 3 , b= 10 c= 10
n= 15 , a= 5 , b= 5 c= 12
n= 35 , a= 7 , b= 14 c= 30
n= 35 , a= 5 , b= 21 c= 28

There are also solutions for n=45, n=55, n=63, n=65, n=77, n=85, n=91, n=99.

You can clearly scale solutions by multiplying them with an odd number, but we also get completely new solutions, such as (45,36,30,5) for (n,a,b,c).

Spoiler: number of solutions up to n=99

a<=b<=c
n= 4 , solutions= 2
n= 6 , solutions= 3
n= 8 , solutions= 4
n= 10 , solutions= 5
n= 12 , solutions= 6
n= 14 , solutions= 7
n= 15 , solutions= 2
n= 16 , solutions= 8
n= 18 , solutions= 9
n= 20 , solutions= 12
n= 22 , solutions= 11
n= 24 , solutions= 16
n= 26 , solutions= 13
n= 28 , solutions= 14
n= 30 , solutions= 17
n= 32 , solutions= 16
n= 34 , solutions= 17
n= 35 , solutions= 2
n= 36 , solutions= 18
n= 38 , solutions= 19
n= 40 , solutions= 24
n= 42 , solutions= 23
n= 44 , solutions= 22
n= 45 , solutions= 8
n= 46 , solutions= 23
n= 48 , solutions= 32
n= 50 , solutions= 25
n= 52 , solutions= 26
n= 54 , solutions= 27
n= 55 , solutions= 2
n= 56 , solutions= 30
n= 58 , solutions= 29
n= 60 , solutions= 42
n= 62 , solutions= 31
n= 63 , solutions= 8
n= 64 , solutions= 32
n= 65 , solutions= 2
n= 66 , solutions= 35
n= 68 , solutions= 34
n= 70 , solutions= 39
n= 72 , solutions= 48
n= 74 , solutions= 37
n= 75 , solutions= 2
n= 76 , solutions= 38
n= 77 , solutions= 2
n= 78 , solutions= 41
n= 80 , solutions= 56
n= 82 , solutions= 41
n= 84 , solutions= 48
n= 85 , solutions= 2
n= 86 , solutions= 43
n= 88 , solutions= 46
n= 90 , solutions= 57
n= 91 , solutions= 2
n= 92 , solutions= 46
n= 94 , solutions= 47
n= 96 , solutions= 58
n= 98 , solutions= 49
n= 99 , solutions= 4

In most cases we have n/2 solutions for even n. Exceptions: n=20, 24, 30, 40, 42, 48, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90

Note that I counted n= 15 , a= 3 , b= 10 c= 10 and n= 15 , a= 5 , b= 5 c= 12 both as one solution, but the first corresponds to three points, where the second corresponds to 6 points.
I still have the code, I can make lists for different ways to count quickly.

Odd solutions stay rare. A quick view on larger n:

Spoiler

n= 380 , solutions= 200
n= 382 , solutions= 191
n= 384 , solutions= 202
n= 385 , solutions= 34
n= 386 , solutions= 193
n= 387 , solutions= 2
n= 388 , solutions= 194
n= 390 , solutions= 243
n= 391 , solutions= 6
n= 392 , solutions= 198
n= 394 , solutions= 197
n= 396 , solutions= 226
n= 398 , solutions= 199
n= 399 , solutions= 30

n= 980 , solutions= 528
n= 982 , solutions= 491
n= 984 , solutions= 502
n= 986 , solutions= 495
n= 987 , solutions= 2
n= 988 , solutions= 532
n= 989 , solutions= 4
n= 990 , solutions= 613
n= 992 , solutions= 508
n= 994 , solutions= 497
n= 996 , solutions= 498
n= 998 , solutions= 499
n= 999 , solutions= 8

n= 2000 , solutions= 1036
n= 2001 , solutions= 30
n= 2002 , solutions= 1081
n= 2004 , solutions= 1002
n= 2006 , solutions= 1011
n= 2008 , solutions= 1004
n= 2009 , solutions= 24
n= 2010 , solutions= 1017
n= 2012 , solutions= 1006
n= 2013 , solutions= 10
n= 2014 , solutions= 1015
n= 2015 , solutions= 36
n= 2016 , solutions= 1382
n= 2018 , solutions= 1009

 

[haruspex]

Progress...
abc = (n-a)(n-b)(n-c)
Modulo n: abc ≡ -abc ... [n]
(I'll use square brackets instead of the usual parentheses for clarity.)
Suppose the solution (n, a, b, c) is irreducible (no common factor to all four numbers).

1. Consider n as power of an odd prime, p^k.
abc ≡ 0... [n]
Wlog (without loss of generality) p|a. Let a = pa'.
(I'll write "does not divide" as ~|.)
Since a < n, p^k~|a, so k>1, and wlog p|b. Since irreducible, p~|c.
a'b'c=(p^k-1-a')(p^k-1-b')(p^k-c)
2a'b'c ≡ p^k-1(a'+b')c ... [p^2k-1]
2a'b' ≡ p^k-1(a'+b') ... [p^2k-1]
Let the powers of p in a', b' be r, s respectively. Wlog r≥s.
Write a'=p^ra", etc.
2a"b"p^r+s≡p^k+s-1(p^r-sa"+b") ... [p^2k-1]
2a"b"p^r≡p^k-1(p^r-sa"+b") ... [p^2k-1-s]
Now r < k-1, so the above implies r ≥ 2k-1-s. Hence s > k, a contradiction.

2. Consider n as a product of two odd primes, pq.
Wlog, p|a, q|b.
pqa'b'c = pq(q-a')(p-b')(pq-c)
2a'b'c ≡ (qb'+pa')c ... [pq]

If c coprime to p and q:
2a'b' ≡ (qb'+pa') ... [pq]
(2a'-q)(2b'-p)≡0 ... [pq]
Since a < pq, q~|a', so
p|(2a'-q) and q|(2b'-p)
Wlog p>q.
2a'=p+q, so a'>q and a > n, a contradiction.
So p or q divides c. Wlog p|c.

2a'b'c'p ≡ (qb'+pa')c'p ... [pq]
2a'b'c' ≡ (qb'+pa')c' ... [q]
2a'b'c' ≡ pa'c' ... [q]
Since a<n and c<n, q cannot divide either:
2b' ≡ p ... [q]
In particular, p>q.
Let 2b' = p+kq (so k odd, but may be positive or negative, as long as |kq|<p).
We get
(2ka'+(p-kq))(2kb'+(p-kq))=(p-kq)(p+kq)
E.g. for n=21, p=7, q=3, |k|=1.
k=-1: (10-2a')(10-2b')=40 - no solutions
k=+1: (4+2a')(4+2b')=40 - no solutions

For n = 15 or 35, k must be ±1.

 n    a    b    c   a'   b'   c'   k
15   10    3   10   2    2    2   -1
15    5   12    5   1    4    1    1
35    7   30   14   1    6    2    1
35   21    5   28   3    1    4   -1

 

[mfb]

n=45 = 3²*5 is a case not covered yet. It has both reducible and irreducible solutions.
n=99 = 3²*11 is similar. All its solutions are irreducible (as there are no solutions for 33 or 9).

I can check 105=3*5*7 and other products of three distinct primes later.

 

[haruspex]

n=45 = 3²*5 is a case not covered yet.

Yes, I realize I have only scratched the surface. I would like to find a generic subclass of n=pq that has no solutions, like 21. And maybe construct some infinite class of solutions for odd n.

 

[haruspex]

Yes, I realize I have only scratched the surface. I would like to find a generic subclass of n=pq that has no solutions, like 21. And maybe construct some infinite class of solutions for odd n.

Update: can show there are no n=3p solutions greater than 15.
Conjecture that for any q there is a max p for n=pq solutions.

 

[mfb]

Here all distinct solutions for odd n up to n=200.

Spoiler

n= 15   [3, 5]
  a= 3 , b= 10  c= 10
  a= 5 , b= 5  c= 12
n= 35   [5, 7]
  a= 5 , b= 21  c= 28
  a= 7 , b= 14  c= 30
n= 45   [3, 3, 5]
  a= 3 , b= 35  c= 36
  a= 5 , b= 30  c= 36
  a= 9 , b= 10  c= 42
  a= 9 , b= 15  c= 40
  a= 9 , b= 24  c= 35
  a= 9 , b= 30  c= 30
  a= 10 , b= 21  c= 36
  a= 15 , b= 15  c= 36
n= 55   [5, 11]
  a= 11 , b= 33  c= 40
  a= 15 , b= 22  c= 44
n= 63   [3, 3, 7]
  a= 3 , b= 45  c= 56
  a= 7 , b= 18  c= 60
  a= 7 , b= 36  c= 54
  a= 7 , b= 45  c= 48
  a= 9 , b= 27  c= 56
  a= 15 , b= 18  c= 56
  a= 18 , b= 35  c= 42
  a= 21 , b= 28  c= 45
n= 65   [5, 13]
  a= 20 , b= 39  c= 39
  a= 26 , b= 26  c= 45
n= 75   [3, 5, 5]
  a= 15 , b= 50  c= 50
  a= 25 , b= 25  c= 60
n= 77   [7, 11]
  a= 11 , b= 44  c= 63
  a= 14 , b= 33  c= 66
n= 85   [5, 17]
  a= 5 , b= 68  c= 68
  a= 17 , b= 17  c= 80
n= 91   [7, 13]
  a= 21 , b= 52  c= 65
  a= 26 , b= 39  c= 70
n= 99   [3, 3, 11]
  a= 9 , b= 55  c= 88
  a= 11 , b= 44  c= 90
  a= 22 , b= 63  c= 66
  a= 33 , b= 36  c= 77

n= 105   [3, 5, 7]
  a= 6 , b= 77  c= 90
  a= 14 , b= 65  c= 84
  a= 15 , b= 28  c= 99
  a= 15 , b= 63  c= 84
  a= 15 , b= 72  c= 77
  a= 21 , b= 40  c= 91
  a= 21 , b= 42  c= 90
  a= 21 , b= 70  c= 70
  a= 28 , b= 33  c= 90
  a= 28 , b= 55  c= 75
  a= 28 , b= 65  c= 66
  a= 30 , b= 50  c= 77
  a= 35 , b= 35  c= 84
  a= 35 , b= 60  c= 63
  a= 39 , b= 40  c= 77
  a= 42 , b= 45  c= 70
n= 117   [3, 3, 13]
  a= 39 , b= 65  c= 72
  a= 45 , b= 52  c= 78
n= 119   [7, 17]
  a= 17 , b= 84  c= 85
  a= 34 , b= 35  c= 102
n= 135   [3, 3, 3, 5]
  a= 5 , b= 108  c= 117
  a= 9 , b= 105  c= 108
  a= 15 , b= 90  c= 108
  a= 18 , b= 27  c= 130
  a= 27 , b= 30  c= 126
  a= 27 , b= 45  c= 120
  a= 27 , b= 72  c= 105
  a= 27 , b= 80  c= 99
  a= 27 , b= 90  c= 90
  a= 30 , b= 63  c= 108
  a= 36 , b= 55  c= 108
  a= 45 , b= 45  c= 108
n= 143   [11, 13]
  a= 11 , b= 78  c= 130
  a= 11 , b= 104  c= 117
  a= 13 , b= 65  c= 132
  a= 26 , b= 39  c= 132
n= 153   [3, 3, 17]
  a= 9 , b= 102  c= 136
  a= 17 , b= 51  c= 144
n= 161   [7, 23]
  a= 46 , b= 92  c= 105
  a= 56 , b= 69  c= 115
n= 165   [3, 5, 11]
  a= 9 , b= 120  c= 143
  a= 15 , b= 100  c= 143
  a= 20 , b= 87  c= 143
  a= 22 , b= 45  c= 156
  a= 22 , b= 65  c= 150
  a= 22 , b= 78  c= 145
  a= 22 , b= 105  c= 130
  a= 22 , b= 117  c= 120
  a= 33 , b= 99  c= 120
  a= 33 , b= 110  c= 110
  a= 35 , b= 60  c= 143
  a= 45 , b= 48  c= 143
  a= 45 , b= 66  c= 132
  a= 55 , b= 55  c= 132
  a= 55 , b= 88  c= 105
  a= 60 , b= 77  c= 110
n= 171   [3, 3, 19]
  a= 38 , b= 95  c= 126
  a= 45 , b= 76  c= 133
n= 175   [5, 5, 7]
  a= 7 , b= 140  c= 150
  a= 14 , b= 115  c= 150
  a= 15 , b= 112  c= 150
  a= 25 , b= 35  c= 168
  a= 25 , b= 60  c= 161
  a= 25 , b= 63  c= 160
  a= 25 , b= 105  c= 140
  a= 25 , b= 112  c= 135
  a= 35 , b= 70  c= 150
  a= 40 , b= 63  c= 150
  a= 63 , b= 100  c= 100
  a= 75 , b= 75  c= 112
n= 187   [11, 17]
  a= 33 , b= 119  c= 136
  a= 51 , b= 68  c= 154
n= 189   [3, 3, 3, 7]
  a= 9 , b= 135  c= 168
  a= 21 , b= 54  c= 180
  a= 21 , b= 108  c= 162
  a= 21 , b= 135  c= 144
  a= 27 , b= 81  c= 168
  a= 36 , b= 119  c= 135
  a= 45 , b= 54  c= 168
  a= 54 , b= 70  c= 153
  a= 54 , b= 105  c= 126
  a= 63 , b= 84  c= 135
n= 195   [3, 5, 13]
  a= 3 , b= 160  c= 182
  a= 6 , b= 135  c= 182
  a= 10 , b= 111  c= 182
  a= 13 , b= 35  c= 192
  a= 13 , b= 60  c= 189
  a= 13 , b= 84  c= 185
  a= 13 , b= 105  c= 180
  a= 13 , b= 120  c= 175
  a= 13 , b= 135  c= 168
  a= 13 , b= 140  c= 165
  a= 13 , b= 147  c= 160
  a= 15 , b= 90  c= 182
  a= 20 , b= 75  c= 182
  a= 27 , b= 60  c= 182
  a= 30 , b= 55  c= 182
  a= 30 , b= 130  c= 143
  a= 35 , b= 48  c= 182
  a= 35 , b= 104  c= 156
  a= 39 , b= 91  c= 160
  a= 39 , b= 130  c= 130
  a= 52 , b= 65  c= 165
  a= 60 , b= 117  c= 117
  a= 65 , b= 65  c= 156
  a= 78 , b= 78  c= 135

And the prime factorization of numbers from 200 to 1000 which have at least one solution:

Spoiler

n= 203   [7, 29]
n= 207   [3, 3, 23]
n= 209   [11, 19]
n= 221   [13, 17]
n= 225   [3, 3, 5, 5]
n= 231   [3, 7, 11]
n= 245   [5, 7, 7]
n= 247   [13, 19]
n= 255   [3, 5, 17]
n= 259   [7, 37]
n= 261   [3, 3, 29]
n= 273   [3, 7, 13]
n= 275   [5, 5, 11]
n= 285   [3, 5, 19]
n= 297   [3, 3, 3, 11]
n= 299   [13, 23]
n= 315   [3, 3, 5, 7]
n= 319   [11, 29]
n= 323   [17, 19]
n= 325   [5, 5, 13]
n= 333   [3, 3, 37]
n= 341   [11, 31]
n= 345   [3, 5, 23]
n= 351   [3, 3, 3, 13]
n= 357   [3, 7, 17]
n= 369   [3, 3, 41]
n= 375   [3, 5, 5, 5]
n= 377   [13, 29]
n= 385   [5, 7, 11]
n= 387   [3, 3, 43]
n= 391   [17, 23]
n= 399   [3, 7, 19]
n= 403   [13, 31]
n= 405   [3, 3, 3, 3, 5]
n= 407   [11, 37]
n= 425   [5, 5, 17]
n= 429   [3, 11, 13]
n= 435   [3, 5, 29]
n= 437   [19, 23]
n= 441   [3, 3, 7, 7]
n= 455   [5, 7, 13]
n= 459   [3, 3, 3, 17]
n= 465   [3, 5, 31]
n= 473   [11, 43]
n= 475   [5, 5, 19]
n= 477   [3, 3, 53]
n= 481   [13, 37]
n= 483   [3, 7, 23]
n= 495   [3, 3, 5, 11]

n= 513   [3, 3, 3, 19]
n= 517   [11, 47]
n= 525   [3, 5, 5, 7]
n= 527   [17, 31]
n= 533   [13, 41]
n= 539   [7, 7, 11]
n= 551   [19, 29]
n= 555   [3, 5, 37]
n= 559   [13, 43]
n= 561   [3, 11, 17]
n= 567   [3, 3, 3, 3, 7]
n= 575   [5, 5, 23]
n= 583   [11, 53]
n= 585   [3, 3, 5, 13]
n= 589   [19, 31]
n= 595   [5, 7, 17]
n= 605   [5, 11, 11]
n= 609   [3, 7, 29]
n= 615   [3, 5, 41]
n= 621   [3, 3, 3, 23]
n= 627   [3, 11, 19]
n= 629   [17, 37]
n= 637   [7, 7, 13]
n= 645   [3, 5, 43]
n= 649   [11, 59]
n= 651   [3, 7, 31]
n= 663   [3, 13, 17]
n= 665   [5, 7, 19]
n= 667   [23, 29]
n= 671   [11, 61]
n= 675   [3, 3, 3, 5, 5]
n= 689   [13, 53]
n= 693   [3, 3, 7, 11]
n= 703   [19, 37]
n= 705   [3, 5, 47]
n= 713   [23, 31]
n= 715   [5, 11, 13]
n= 725   [5, 5, 29]
n= 731   [17, 43]
n= 735   [3, 5, 7, 7]
n= 741   [3, 13, 19]
n= 759   [3, 11, 23]
n= 765   [3, 3, 5, 17]
n= 775   [5, 5, 31]
n= 777   [3, 7, 37]
n= 779   [19, 41]
n= 781   [11, 71]
n= 783   [3, 3, 3, 29]
n= 795   [3, 5, 53]
n= 799   [17, 47]
n= 803   [11, 73]
n= 805   [5, 7, 23]
n= 819   [3, 3, 7, 13]
n= 825   [3, 5, 5, 11]
n= 833   [7, 7, 17]
n= 837   [3, 3, 3, 31]
n= 845   [5, 13, 13]
n= 847   [7, 11, 11]
n= 851   [23, 37]
n= 855   [3, 3, 5, 19]
n= 861   [3, 7, 41]
n= 871   [13, 67]
n= 875   [5, 5, 5, 7]
n= 885   [3, 5, 59]
n= 891   [3, 3, 3, 3, 11]
n= 893   [19, 47]
n= 897   [3, 13, 23]
n= 899   [29, 31]
n= 901   [17, 53]
n= 903   [3, 7, 43]
n= 913   [11, 83]
n= 915   [3, 5, 61]
n= 923   [13, 71]
n= 925   [5, 5, 37]
n= 931   [7, 7, 19]
n= 935   [5, 11, 17]
n= 943   [23, 41]
n= 945   [3, 3, 3, 5, 7]
n= 957   [3, 11, 29]
n= 969   [3, 17, 19]
n= 975   [3, 5, 5, 13]
n= 987   [3, 7, 47]
n= 989   [23, 43]
n= 999   [3, 3, 3, 37]

5*17 seems to be the largest n=5*q.
7*23 seems to be the largest n=7*q.

I looked specifically for prime multiples of 5, 7 and 11 up to n=2500.
Nothing more for 5 and 7.
For 11, the product 11*101=1111 is the largest one I found.I found the origin of the pattern for the even numbers; for n=2m, we have the solution (a,m,n-a) for a=1 to m. They correspond to the lines that go through the center of mass of the triangle.
If we exclude these trivial solutions, we just get very few even solutions as well. Some of them are irreducible, e.g. (56,14,35,36).

Edit: All irreducible non-trivial solutions for even n up to 100:

Spoiler

n= 20   [2, 2, 5]
  a= 2 , b= 15  c= 15
  a= 5 , b= 5  c= 18
n= 24   [2, 2, 2, 3]
  a= 3 , b= 14  c= 20
  a= 4 , b= 10  c= 21
  a= 4 , b= 15  c= 18
  a= 6 , b= 9  c= 20
n= 40   [2, 2, 2, 5]
  a= 5 , b= 28  c= 30
  a= 10 , b= 12  c= 35
n= 42   [2, 3, 7]
  a= 7 , b= 28  c= 30
  a= 12 , b= 14  c= 35
n= 48   [2, 2, 2, 2, 3]
  a= 3 , b= 36  c= 40
  a= 4 , b= 33  c= 40
  a= 8 , b= 12  c= 45
  a= 8 , b= 15  c= 44
n= 56   [2, 2, 2, 7]
  a= 14 , b= 35  c= 36
  a= 20 , b= 21  c= 42
n= 60   [2, 2, 3, 5]
  a= 3 , b= 38  c= 55
  a= 5 , b= 22  c= 57
  a= 5 , b= 33  c= 54
  a= 5 , b= 44  c= 48
  a= 6 , b= 27  c= 55
  a= 12 , b= 16  c= 55
  a= 15 , b= 36  c= 40
  a= 20 , b= 24  c= 45
n= 66   [2, 3, 11]
  a= 6 , b= 44  c= 55
  a= 11 , b= 22  c= 60
n= 70   [2, 5, 7]
  a= 7 , b= 42  c= 60
  a= 10 , b= 28  c= 63
n= 72   [2, 2, 2, 3, 3]
  a= 2 , b= 60  c= 63
  a= 4 , b= 51  c= 63
  a= 6 , b= 44  c= 63
  a= 9 , b= 12  c= 70
  a= 9 , b= 21  c= 68
  a= 9 , b= 28  c= 66
  a= 9 , b= 48  c= 56
  a= 16 , b= 24  c= 63
n= 78   [2, 3, 13]
  a= 3 , b= 65  c= 65
  a= 13 , b= 13  c= 75
n= 80   [2, 2, 2, 2, 5]
  a= 2 , b= 65  c= 72
  a= 5 , b= 50  c= 72
  a= 8 , b= 15  c= 78
  a= 8 , b= 30  c= 75
  a= 8 , b= 45  c= 70
  a= 8 , b= 54  c= 65
  a= 10 , b= 35  c= 72
  a= 15 , b= 26  c= 72
  a= 15 , b= 52  c= 56
  a= 20 , b= 45  c= 56
  a= 24 , b= 28  c= 65
  a= 24 , b= 35  c= 60
n= 84   [2, 2, 3, 7]
  a= 7 , b= 63  c= 66
  a= 12 , b= 56  c= 63
  a= 18 , b= 21  c= 77
  a= 21 , b= 28  c= 72
n= 88   [2, 2, 2, 11]
  a= 4 , b= 66  c= 77
  a= 11 , b= 22  c= 84
n= 90   [2, 3, 3, 5]
  a= 15 , b= 50  c= 72
  a= 18 , b= 40  c= 75
  a= 20 , b= 54  c= 63
  a= 27 , b= 36  c= 70
n= 96   [2, 2, 2, 2, 2, 3]
  a= 16 , b= 56  c= 75
  a= 21 , b= 40  c= 80

It looks like a,b,c always share a factor with n, just not all three with the same factor.
a is most of the time, but not always a divisor of n (see 96 a for counterexample)

 

[haruspex]

Thanks.
It looks like the max p for an n=pq solution is always a bit less than q².

 

[mfb]

23 is quite a bit below 49.

15,35,45,55,63,65 (the first odd n with non-trivial solutions) is not in oeis.
15,20,24,35,40,42,45 (some n with non-trivial solutions) is not there either.

1417=13*109 is the largest 13*prime solution up to n=5000.

477=3*3*53 is the largest 3*3*prime solution up to n=2500. Before that there are many solutions.

That seems to be some general pattern, probably not limited to primes as initial factor.

How did your proof for 3 work?

 

[haruspex]

How did your proof for 3 work?

My equation in post #9
(2ka'+(p-kq))(2kb'+(p-kq))=(p-kq)(p+kq)
Leads to
k(2a'b'-(a'+b')q+q²)=p(q-a'-b') ... 1
Since |kq|<p, |k|<p, so
p | 2a'b'-(a'+b')q+q²
Since a'<q, for q=3 we only have a'=1 or 2.
a'=1: p | 6-b', implying p <= 5.
a'=2: p | 3+b'
Since b'<p this implies b'=p-3:
Substituting in 1: k(4p-12 - (p-1)3 +9) = p(2-p)
k=2-p.
But |3k|<p, so p<3.

The same approach to q=5 has the cases of a' from 1 to 4. The second gives p <= 17, while the first is less. The same method for a'=3 yields no upper bound, but a different approach gives p<=17. This makes me hopeful that the pincer movement of the two methods may lead to a general upper bound for p as a function of q.

 

[SlowThinker]

You act as if the answer is obvious, but why prime $n$ has no solutions?

Edit: Oops, answer to second question is obvious.
Edit2: I guess the answer to this one is obvious as well. Since abc=-abc (mod n), then abc=0 (mod n), thus n is composite (even if abc=kn for $k\neq 1$).

 

[haruspex]

My equation in post #9
(2ka'+(p-kq))(2kb'+(p-kq))=(p-kq)(p+kq)
Leads to
k(2a'b'-(a'+b')q+q²)=p(q-a'-b') ... 1
Since |kq|<p, |k|<p, so
p | 2a'b'-(a'+b')q+q²

|k|<|p/q|, so from 1
|q(q-a'-b')| < |2a'b'+q(q-a'-b')|
So q>a'+b'.
Since p prime and |k|<p, 1 implies p ≤ | 2a'b'-(a'+b')q+q² |
with a'+b'<q, the RHS is maximised at q²-2q+2.
So p ≤ q²-2q+2.
This bound is achieved for q=3, 5 and 11, but not 7.

 

[mfb]

I made a mistake with 7.
259=7*37 does have solutions.

3*p has solutions for p=5 only.

5*p has solutions for p=3, 7, 11, 13, 17

7*p has solutions for p=5, 11, 13, 17, 23, 29, 37
Missing: 19, 31

11*p has solutions for p=5,7,13,17,19,29,31,37,43,47,53,59,61,71,73,83,101
16 out of 22 possible primes below 100 (2,3,11 excluded), only 23, 41, 67, 79, 89, 97 are missing.

13*p has 109 as largest solution up to your upper bound of 145.

17*p has 257 as largest solution up to your upper bound of 257.

19*p has 293 as largest solution up to your upper bound of 325.

The code needs O(n²) to test a specific n, testing a prime p for second factors up to p² runs with O(p⁸). Testing 19 took 2:30. Testing 23 would need 12 minutes, and testing 29 would need about an hour. This assumes all integers are in 64 bit already and all operations take constant time. Maybe tomorrow...

 

[haruspex]

I made a mistake with 7.
259=7*37 does have solutions.

3*p has solutions for p=5 only.

5*p has solutions for p=3, 7, 11, 13, 17

7*p has solutions for p=5, 11, 13, 17, 23, 29, 37
Missing: 19, 31

11*p has solutions for p=5,7,13,17,19,29,31,37,43,47,53,59,61,71,73,83,101
16 out of 22 possible primes below 100 (2,3,11 excluded), only 23, 41, 67, 79, 89, 97 are missing.

13*p has 109 as largest solution up to your upper bound of 145.

17*p has 257 as largest solution up to your upper bound of 257.

19*p has 293 as largest solution up to your upper bound of 325.

The code needs O(n²) to test a specific n, testing a prime p for second factors up to p² runs with O(p⁸). Testing 19 took 2:30. Testing 23 would need 12 minutes, and testing 29 would need about an hour. This assumes all integers are in 64 bit already and all operations take constant time. Maybe tomorrow...

Would it be faster to work with my eqn 1? There are fewer than q²/2 solutions to a'+b'<q. For each, look for the largest prime factor of 2a'b'-(a'+b')q+q².

 

[mfb]

I don't really understand the calculations you do.
q² would be smaller than n², that helps. What exactly do I have to check?

These are the current inner loops:

    for a in range(1,int(n/2)+1):
        for b in range(a,n):

 

[haruspex]

I don't really understand the calculations you do.
q² would be smaller than n², that helps. What exactly do I have to check?

These are the current inner loops:

    for a in range(1,int(n/2)+1):
        for b in range(a,n):

For the case n=pq, odd, an irreducible solution is equivalent to a solution of
k(2a'b'-(a'+b')q+q²)=p(q-a'-b') ... 1
where 0<b'≤a'<q and kq<p
(I previously allowed k negative here, but now see that is not possible.)
So it suffices to find solutions of this system.

 

[mfb]

That is faster by a huge factor.
In general the largest possible p doesn't léad to a solution. In cases where it does I marked it with a small arrow:

for q= 3 , max p found is 5 , max possible is 5 <--
for q= 5 , max p found is 17 , max possible is 17 <--
for q= 7 , max p found is 37 , max possible is 37 <--
for q= 11 , max p found is 101 , max possible is 101 <--
for q= 13 , max p found is 109 , max possible is 145
for q= 17 , max p found is 257 , max possible is 257 <--
for q= 19 , max p found is 293 , max possible is 325
for q= 23 , max p found is 443 , max possible is 485
for q= 29 , max p found is 733 , max possible is 785
for q= 31 , max p found is 743 , max possible is 901
for q= 37 , max p found is 1297 , max possible is 1297 <--
for q= 41 , max p found is 1601 , max possible is 1601 <--
for q= 43 , max p found is 1609 , max possible is 1765
for q= 47 , max p found is 2029 , max possible is 2117
for q= 53 , max p found is 2417 , max possible is 2705
for q= 59 , max p found is 3253 , max possible is 3365
for q= 61 , max p found is 3373 , max possible is 3601
for q= 67 , max p found is 4357 , max possible is 4357 <--
for q= 71 , max p found is 4373 , max possible is 4901
for q= 73 , max p found is 4909 , max possible is 5185
for q= 79 , max p found is 5783 , max possible is 6085
for q= 83 , max p found is 6563 , max possible is 6725
for q= 89 , max p found is 7573 , max possible is 7745
for q= 97 , max p found is 9029 , max possible is 9217
for q= 101 , max p found is 9803 , max possible is 10001

I don't really see patterns so far.

 

[haruspex]

That is faster by a huge factor.
In general the largest possible p doesn't léad to a solution. In cases where it does I marked it with a small arrow:

for q= 3 , max p found is 5 , max possible is 5 <--
for q= 5 , max p found is 17 , max possible is 17 <--
for q= 7 , max p found is 37 , max possible is 37 <--
for q= 11 , max p found is 101 , max possible is 101 <--
for q= 13 , max p found is 109 , max possible is 145
for q= 17 , max p found is 257 , max possible is 257 <--
for q= 19 , max p found is 293 , max possible is 325
for q= 23 , max p found is 443 , max possible is 485
for q= 29 , max p found is 733 , max possible is 785
for q= 31 , max p found is 743 , max possible is 901
for q= 37 , max p found is 1297 , max possible is 1297 <--
for q= 41 , max p found is 1601 , max possible is 1601 <--
for q= 43 , max p found is 1609 , max possible is 1765
for q= 47 , max p found is 2029 , max possible is 2117
for q= 53 , max p found is 2417 , max possible is 2705
for q= 59 , max p found is 3253 , max possible is 3365
for q= 61 , max p found is 3373 , max possible is 3601
for q= 67 , max p found is 4357 , max possible is 4357 <--
for q= 71 , max p found is 4373 , max possible is 4901
for q= 73 , max p found is 4909 , max possible is 5185
for q= 79 , max p found is 5783 , max possible is 6085
for q= 83 , max p found is 6563 , max possible is 6725
for q= 89 , max p found is 7573 , max possible is 7745
for q= 97 , max p found is 9029 , max possible is 9217
for q= 101 , max p found is 9803 , max possible is 10001

I don't really see patterns so far.

Clearly the algebraic bound will sometimes not be prime. Half the time it will be divisible by 5. More generally, if prime r is such that x²+1 mod r has a root then some bounds will be divisible by r. 2² and 3² are both -1 mod 5. The next such primes are 13, 17, 29. In your list above, all failing bounds are divisible by one of those four.

It might be interesting to look for cases where the actual max p is "less than it needs to be", i.e. less then a prime which is within the bound.
In particular, is it true that the bound is achieved whenever it happens to be prime? If so, can we construct an infinite family of solutions for those cases?

 

[mfb]

I figured out how to overheat the CPU. Switched to a different computer.

It might be interesting to look for cases where the actual max p is "less than it needs to be", i.e. less then a prime which is within the bound.

That happens in all the cases where the bound is not achieved in the list above, often there are many primes between the largest solution and the upper bound.

In particular, is it true that the bound is achieved whenever it happens to be prime?

Yes.

If so, can we construct an infinite family of solutions for those cases?

In all cases I checked, a'=b'=1 and k=q-2. There might be more solutions but I just looked for the first one. Plug that into equation 1:

(q-2)(2-2q+q²)=p(q-2)

Written like that is is trivial. It works exactly if the upper bound is a prime.
And now we do have an OEIS hit. It doesn't tell us if the set is infinite, but it is plausible.

I pushed around some more electrons:

Spoiler: 100 to 300

('for q=', 101, ', max p found is', 9803, ', max possible is', 10001, '')
('for q=', 103, ', max p found is', 10009, ', max possible is', 10405, '')
('for q=', 107, ', max p found is', 11027, ', max possible is', 11237, '')
('for q=', 109, ', max p found is', 11243, ', max possible is', 11665, '')
('for q=', 113, ', max p found is', 12323, ', max possible is', 12545, '')
('for q=', 127, ', max p found is', 15877, ', max possible is', 15877, ' (prime)')
('for q=', 131, ', max p found is', 16901, ', max possible is', 16901, ' (prime)')
('for q=', 137, ', max p found is', 18229, ', max possible is', 18497, '')
('for q=', 139, ', max p found is', 18773, ', max possible is', 19045, '')
('for q=', 149, ', max p found is', 21613, ', max possible is', 21905, '')
('for q=', 151, ', max p found is', 22501, ', max possible is', 22501, ' (prime)')
('for q=', 157, ', max p found is', 24337, ', max possible is', 24337, ' (prime)')
('for q=', 163, ', max p found is', 25609, ', max possible is', 26245, '')
('for q=', 167, ', max p found is', 26903, ', max possible is', 27557, '')
('for q=', 173, ', max p found is', 29243, ', max possible is', 29585, '')
('for q=', 179, ', max p found is', 31333, ', max possible is', 31685, '')
('for q=', 181, ', max p found is', 32401, ', max possible is', 32401, ' (prime)')
('for q=', 191, ', max p found is', 35353, ', max possible is', 36101, '')
('for q=', 193, ', max p found is', 36109, ', max possible is', 36865, '')
('for q=', 197, ', max p found is', 37643, ', max possible is', 38417, '')
('for q=', 199, ', max p found is', 38039, ', max possible is', 39205, '')
('for q=', 211, ', max p found is', 44101, ', max possible is', 44101, ' (prime)')
('for q=', 223, ', max p found is', 48409, ', max possible is', 49285, '')
('for q=', 227, ', max p found is', 50627, ', max possible is', 51077, '')
('for q=', 229, ', max p found is', 49757, ', max possible is', 51985, '')
('for q=', 233, ', max p found is', 52901, ', max possible is', 53825, '')
('for q=', 239, ', max p found is', 56171, ', max possible is', 56645, '')
('for q=', 241, ', max p found is', 57601, ', max possible is', 57601, ' (prime)')
('for q=', 251, ', max p found is', 62501, ', max possible is', 62501, ' (prime)')
('for q=', 257, ', max p found is', 65537, ', max possible is', 65537, ' (prime)')
('for q=', 263, ', max p found is', 67607, ', max possible is', 68645, '')
('for q=', 269, ', max p found is', 71293, ', max possible is', 71825, '')
('for q=', 271, ', max p found is', 72901, ', max possible is', 72901, ' (prime)')
('for q=', 277, ', max p found is', 75629, ', max possible is', 76177, '')
('for q=', 281, ', max p found is', 78401, ', max possible is', 78401, ' (prime)')
('for q=', 283, ', max p found is', 78401, ', max possible is', 79525, '')
('for q=', 293, ', max p found is', 83537, ', max possible is', 85265, '')

The last one corresponds to a solution for n=24,476,341, where the general approach (iterate over a,b) would need up to hundreds of trillions of checks. Checking everything from 83537 to 85265 (~250 primes) would need quadrillions of checks just for this part. With equation 1 the whole script for q=100 to 300 was done in minutes.

 

[mfb]

http://mfb.bplaced.net/PF/triangle.html to visualize the triangles. Just put in n.
Careful at n=7: There are extremely small triangles.

Large n (60-200) lead to interesting patterns due to the finite resolution.

It accepts non-integer values but don't expect meaningful results then :p.

 

[haruspex]

a'=b'=1 and k=q-2.

Did you mean b'=p-1?
Anyway, what you have found there is that, for any m, n=m³-2m²+2m has the solution a=c=m²-2m+2, b=m³-2m²+m. Our first infinite family of non-trivial solutions.
Note that it is irreducible whenever m is odd. If m is even we can cancel a factor of 2 throughout to get, again, an irreducible solution.

 

[haruspex]

http://mfb.bplaced.net/PF/triangle.html to visualize the triangles. Just put in n.
Careful at n=7: There are extremely small triangles.

Large n (60-200) lead to interesting patterns due to the finite resolution.

It accepts non-integer values but don't expect meaningful results then :p.

Lovely!
Would it be possible to have it highlight the triple intersections?

 

[mfb]

Did you mean b'=p-1?

No, but that could be a solution as well (didn't check).

Our first infinite family of non-trivial solutions.

We were looking for primes only, but it works for every m. Nice. It leads to non-trivial solutions for n=15, n=40, n=85, n=156.
For n=4 it leads to a trivial solution.

Would it be possible to have it highlight the triple intersections?

Done via additional checkbox.

 

[haruspex]

Here's a way to generate plenty of non-trivial (but maybe reducible) solutions.
Choose any k and 0<a≤b<k such that none of 2a, 2b, a+b equals k.
Set c=(k-a)(k-b), m=c+ab. Then the system (mk; am, bm, ck) is a non-trivial solution for n=mk.
E.g. k=3, a=1, b=1 gives (15; 5, 5, 12). k=10, a=1, b=8 gives (260; 26, 208, 180), reducing to (130, 13, 104, 90).

 

[mfb]

It generates a large number of solutions, but not all:
n= 35, a= 5 , b= 21 c= 28
As three numbers need a common divisor, we have m=7 as only option (m=1 doesn't fit with the generating equations). This leads to k=5 and c=1:
(7*5 ; 3*7 , 4*7 , 1*5)
We also need 7=1+2*3 (correct) and 1=(5-4)(5-3) (wrong).

k=a+b, k=a+a and k=b+b lead to the trivial solutions.

Spoiler: various generated solutions

15	5	5	12
15	10	10	3
20	5	5	18
20	15	15	2
35	7	14	30
42	7	28	30
55	11	33	40
63	9	27	56
63	21	28	45
65	26	26	45
65	39	39	20
66	11	22	60
72	16	24	63
77	11	44	63
78	13	13	75
85	17	17	80
90	27	36	70
99	11	44	90
112	16	32	105
136	51	51	100
152	19	57	140
175	75	75	112
203	58	58	175
259	37	37	252
290	29	116	270
310	62	93	280