Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Featured B Counting intersections of lines in a triangle

  1. Jun 20, 2017 #1

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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. jcsd
  3. Jun 20, 2017 #2

    mfb

    User Avatar
    2016 Award

    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
  4. Jun 20, 2017 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  5. Jun 20, 2017 #4

    mfb

    User Avatar
    2016 Award

    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.
     
  6. Jun 20, 2017 #5

    chiro

    User Avatar
    Science Advisor

    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.
     
  7. Jun 21, 2017 #6

    mfb

    User Avatar
    2016 Award

    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.
     
  8. Jun 21, 2017 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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).
     
  9. Jun 21, 2017 #8

    mfb

    User Avatar
    2016 Award

    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
     
  10. Jun 22, 2017 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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
     
     
  11. Jun 23, 2017 #10

    mfb

    User Avatar
    2016 Award

    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.
     
  12. Jun 23, 2017 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  13. Jun 24, 2017 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  14. Jun 24, 2017 #13

    mfb

    User Avatar
    2016 Award

    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
  15. Jun 24, 2017 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Thanks.
    It looks like the max p for an n=pq solution is always a bit less than q2.
     
  16. Jun 24, 2017 #15

    mfb

    User Avatar
    2016 Award

    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?
     
  17. Jun 25, 2017 #16

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  18. Jun 25, 2017 #17
    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
  19. Jun 28, 2017 #18

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    |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.
     
  20. Jun 28, 2017 #19

    mfb

    User Avatar
    2016 Award

    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...
     
  21. Jun 28, 2017 #20

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Counting intersections of lines in a triangle
  1. Line intersections. (Replies: 2)

Loading...