# FeaturedB Counting intersections of lines in a triangle

1. Jun 20, 2017

### 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?

Last edited: Jun 20, 2017
2. Jun 20, 2017

### Staff: Mentor

If there are no points where three lines intersect: If we have NA lines to vertex A and NB lines to vertex B, a new line to vertex C will add NA+NB+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 n2 regions.
Draw all lines from C, adding 2n-1 regions n-1 times, for a total of n2+(2n-1)(n-1) = 3n2 - 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.

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.

Last edited: Jun 20, 2017
3. Jun 20, 2017

### haruspex

Neat. Any thoughts on numbers of triangles etc?
Not sure how that helps. E.g. a could be 4 mod 8 while n-b and n-c are each 2 mod 4.

4. Jun 20, 2017

### Staff: Mentor

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: 12n2 - 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 = 3n2 - 3n + 1
3T + 4Q + 5P + 6H + 6X = 12n2 - 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.

5. Jun 20, 2017

### 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.

6. Jun 21, 2017

### Staff: Mentor

I would expect that abc = (n-a)(n-b)(n-c) is the result of that approach.
There are no intersections outside.

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

7. Jun 21, 2017

### haruspex

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

8. Jun 21, 2017

### Staff: Mentor

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).
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:
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

9. Jun 22, 2017

### 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, pk.
abc ≡ 0... [n]
Wlog (without loss of generality) p|a. Let a = pa'.
(I'll write "does not divide" as ~|.)
Since a < n, pk~|a, so k>1, and wlog p|b. Since irreducible, p~|c.
a'b'c=(pk-1-a')(pk-1-b')(pk-c)
2a'b'c ≡ pk-1(a'+b')c ... [p2k-1]
2a'b' ≡ pk-1(a'+b') ... [p2k-1]
Let the powers of p in a', b' be r, s respectively. Wlog r≥s.
Write a'=pra", etc.
2a"b"pr+s≡pk+s-1(pr-sa"+b") ... [p2k-1]
2a"b"pr≡pk-1(pr-sa"+b") ... [p2k-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.
Code (Text):

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

10. Jun 23, 2017

### Staff: Mentor

n=45 = 32*5 is a case not covered yet. It has both reducible and irreducible solutions.
n=99 = 32*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.

11. Jun 23, 2017

### haruspex

Yes, I realise 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.

12. Jun 24, 2017

### haruspex

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.

13. Jun 24, 2017

### Staff: Mentor

Here all distinct solutions for odd n up to n=200.
Code (Text):
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:
Code (Text):
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:
Code (Text):
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)

Last edited: Jun 24, 2017
14. Jun 24, 2017

### haruspex

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

15. Jun 24, 2017

### Staff: Mentor

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?

16. Jun 25, 2017

### haruspex

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

17. Jun 25, 2017

### 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$).

Last edited: Jun 25, 2017
18. Jun 28, 2017

### haruspex

|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+q2 |
with a'+b'<q, the RHS is maximised at q2-2q+2.
So p ≤ q2-2q+2.
This bound is achieved for q=3, 5 and 11, but not 7.

19. Jun 28, 2017

### Staff: Mentor

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(n2) to test a specific n, testing a prime p for second factors up to p2 runs with O(p8). 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...

20. Jun 28, 2017

### haruspex

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

21. Jun 29, 2017

### Staff: Mentor

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

These are the current inner loops:
Code (Text):
for a in range(1,int(n/2)+1):
for b in range(a,n):

22. Jun 29, 2017

### haruspex

For the case n=pq, odd, an irreducible solution is equivalent to a solution of
k(2a'b'-(a'+b')q+q2)=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.

23. Jun 29, 2017

### Staff: Mentor

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.

24. Jun 29, 2017

### haruspex

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 x2+1 mod r has a root then some bounds will be divisible by r. 22 and 32 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?

25. Jun 30, 2017

### Staff: Mentor

I figured out how to overheat the CPU. Switched to a different computer.
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.
Yes.

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+q2)=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:
('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.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted