Loading ...
Sorry, an error occurred while loading the content.

Re: Pythagoras and factoring

Expand Messages
  • Dick
    Hello, To put it yet another way. Factoring n is as easy as finding d such that d/(n-2*d) is a natural number. -Dick Boland ... doesn t win ... methods). ...
    Message 1 of 9 , Nov 30, 2001
    • 0 Attachment
      Hello,

      To put it yet another way.
      Factoring n is as easy as finding d such that
      d/(n-2*d) is a natural number.

      -Dick Boland


      --- In primenumbers@y..., "David Litchfield" <Mnemonix@g...> wrote:
      > Hi All,
      > Curious thing I noted the other day whilst playing with Pythagorean
      > triangles - you can use them as a method of factoring (sure - it
      doesn't win
      > you much [probably lose more actually ;-] when compared to other
      methods).
      > This may be known already, maybe not.
      >
      > Given a number e.g. 21 make a pythagorean triangle ensuring each
      side is a
      > whole number:
      >
      > Adjacent = 21
      > Opposite = 20
      > Hypotenuse = 29
      >
      > 29 + 20 = 49
      > 29 - 20 = 9
      >
      > 49 sqrt = 7
      > 9 sqrt = 3
      >
      > 3 * 7 = 21
      >
      > Sort of an opposite of Fermat's method. I haven't written a proof
      for this -
      > (probably wouldn't know how to in all honesty) but writing a simple
      C
      > program and testing this is seems to work out.
      > --------------------8<------------------------
      > #include <stdio.h>
      > #include <math.h>
      >
      > int main(int argc, char *argv[])
      > {
      > unsigned int number=0,count=0,res=0,t=0;
      > float foo=0,bar=0;
      >
      > if(argc !=2)
      > return printf("ARGS! Enter a number!");
      >
      > number = atoi(argv[1]);
      >
      > foo = (float) number;
      > count = 1;
      >
      > while(count<10000)
      > {
      > res = number * number + count * count;
      > foo = (float) res;
      > foo = sqrt(foo);
      > res = foo;
      > foo = foo - res;
      >
      > if(foo==0)
      > {
      >
      > foo = (float)(res - count);
      > bar = (float)(res + count);
      > foo = sqrt(foo);
      > bar = sqrt(bar);
      > if(foo * bar == number)
      > {
      > printf("%d\t%d\t%d\n",number,count,res);
      > printf("%.1f\t%.1f",foo,bar);
      > break;
      > }
      >
      > }
      >
      > count ++;
      > } return 0;
      > }
      >
      > --------------------->8--------------------------
      >
      > Some numbers produc many right angled triangles with whole number
      lengths -
      > some only 1 and these are prime numbers. Further to this some use
      given
      > number as the adjacent some as the opposite.
      >
      > 'Tis all,
      > Cheers,
      > David Litchfield
    • David Litchfield
      Hi All, Curious thing I noted the other day whilst playing with Pythagorean triangles - you can use them as a method of factoring (sure - it doesn t win you
      Message 2 of 9 , Nov 30, 2001
      • 0 Attachment
        Hi All,
        Curious thing I noted the other day whilst playing with Pythagorean
        triangles - you can use them as a method of factoring (sure - it doesn't win
        you much [probably lose more actually ;-] when compared to other methods).
        This may be known already, maybe not.

        Given a number e.g. 21 make a pythagorean triangle ensuring each side is a
        whole number:

        Adjacent = 21
        Opposite = 20
        Hypotenuse = 29

        29 + 20 = 49
        29 - 20 = 9

        49 sqrt = 7
        9 sqrt = 3

        3 * 7 = 21

        Sort of an opposite of Fermat's method. I haven't written a proof for this -
        (probably wouldn't know how to in all honesty) but writing a simple C
        program and testing this is seems to work out.
        --------------------8<------------------------
        #include <stdio.h>
        #include <math.h>

        int main(int argc, char *argv[])
        {
        unsigned int number=0,count=0,res=0,t=0;
        float foo=0,bar=0;

        if(argc !=2)
        return printf("ARGS! Enter a number!");

        number = atoi(argv[1]);

        foo = (float) number;
        count = 1;

        while(count<10000)
        {
        res = number * number + count * count;
        foo = (float) res;
        foo = sqrt(foo);
        res = foo;
        foo = foo - res;

        if(foo==0)
        {

        foo = (float)(res - count);
        bar = (float)(res + count);
        foo = sqrt(foo);
        bar = sqrt(bar);
        if(foo * bar == number)
        {
        printf("%d\t%d\t%d\n",number,count,res);
        printf("%.1f\t%.1f",foo,bar);
        break;
        }

        }

        count ++;
        } return 0;
        }

        --------------------->8--------------------------

        Some numbers produc many right angled triangles with whole number lengths -
        some only 1 and these are prime numbers. Further to this some use given
        number as the adjacent some as the opposite.

        'Tis all,
        Cheers,
        David Litchfield
      • David Litchfield
        ... But: 205 - 164 = 41 123 / 41 = 3 So we can get the factors straight out with this p. triangle. David
        Message 3 of 9 , Dec 1, 2001
        • 0 Attachment
          > Then B+C=(U+V)^2, B-C=(U-V)^2 as in your examples. But it is *not* common
          > solution!
          > For instance, the least solution to A^2+B^2=C^2 with A=123 is
          >
          > 123^2+164^2=205^2
          >
          > Both your C-program and my pascal one find this solution. But,alas
          >
          > 205-164=41 is *not* square, neither is
          > 205+164=369=3^2*41.
          >

          But: 205 - 164 = 41
          123 / 41 = 3
          So we can get the factors straight out with this p. triangle.

          David
        • Dick
          Hello, Is this formulation of Fermat s method a computationally faster way to apply Fermat s method because we are checking only for perfect integers vs
          Message 4 of 9 , Dec 1, 2001
          • 0 Attachment
            Hello,
            Is this formulation of Fermat's method a computationally faster way
            to apply Fermat's method because we are checking only for perfect
            integers vs perfect squares? Is this formulation unique?

            > To put it yet another way.
            > Factoring n is as easy as finding d such that
            > d/(n-2*d) is a natural number.
            >
            > -Dick Boland

            -Dick Boland

            >
            > --- In primenumbers@y..., "David Litchfield" <Mnemonix@g...> wrote:
            > > Hi All,
            > > Curious thing I noted the other day whilst playing with
            Pythagorean
            > > triangles - you can use them as a method of factoring (sure - it
            > doesn't win
            > > you much [probably lose more actually ;-] when compared to other
            > methods).
            > > This may be known already, maybe not.
            > >
            > > Given a number e.g. 21 make a pythagorean triangle ensuring each
            > side is a
            > > whole number:
            > >
            > > Adjacent = 21
            > > Opposite = 20
            > > Hypotenuse = 29
            > >
            > > 29 + 20 = 49
            > > 29 - 20 = 9
            > >
            > > 49 sqrt = 7
            > > 9 sqrt = 3
            > >
            > > 3 * 7 = 21
            > >
            > > Sort of an opposite of Fermat's method. I haven't written a proof
            > for this -
            > > (probably wouldn't know how to in all honesty) but writing a
            simple
            > C
            > > program and testing this is seems to work out.
            > > --------------------8<------------------------
            > > #include <stdio.h>
            > > #include <math.h>
            > >
            > > int main(int argc, char *argv[])
            > > {
            > > unsigned int number=0,count=0,res=0,t=0;
            > > float foo=0,bar=0;
            > >
            > > if(argc !=2)
            > > return printf("ARGS! Enter a number!");
            > >
            > > number = atoi(argv[1]);
            > >
            > > foo = (float) number;
            > > count = 1;
            > >
            > > while(count<10000)
            > > {
            > > res = number * number + count * count;
            > > foo = (float) res;
            > > foo = sqrt(foo);
            > > res = foo;
            > > foo = foo - res;
            > >
            > > if(foo==0)
            > > {
            > >
            > > foo = (float)(res - count);
            > > bar = (float)(res + count);
            > > foo = sqrt(foo);
            > > bar = sqrt(bar);
            > > if(foo * bar == number)
            > > {
            > > printf("%d\t%d\t%d\n",number,count,res);
            > > printf("%.1f\t%.1f",foo,bar);
            > > break;
            > > }
            > >
            > > }
            > >
            > > count ++;
            > > } return 0;
            > > }
            > >
            > > --------------------->8--------------------------
            > >
            > > Some numbers produc many right angled triangles with whole number
            > lengths -
            > > some only 1 and these are prime numbers. Further to this some use
            > given
            > > number as the adjacent some as the opposite.
            > >
            > > 'Tis all,
            > > Cheers,
            > > David Litchfield
          • David Litchfield
            ... ^ My method is not related to Fermat in the way you suggest (I qualify that with a big I think [and apology if I m thinking wrong]!) Your suggestion works
            Message 5 of 9 , Dec 2, 2001
            • 0 Attachment
              Marcel Martin wrote:
              >In your example, you split 21 using 21^2 = 29^2 - 20^2. With the Fermat
              >method, you would only need 21 = 5^2 - 2^2.
              >Notice that 29^2 - 20^2 = (5^2 + 2^2)^2 - (5^2 - 2^2)^2.
              ^
              My method is not related to Fermat in the way you suggest (I qualify that
              with a big I think [and apology if I'm thinking wrong]!)

              Your suggestion works for 21 but not, say, 35

              Adj = 35
              Hyp = 37
              Opp = 12

              37 + 12 = 49
              37 - 12 = 25
              49 sqrt = 7
              25 sqrt = 5
              5 * 7 = 35

              and so
              37^2 - 12^2 != (7^2 + 5^2)^2 - (7^2 - 5^2)^2

              I think it mere coincidence that it happens with 21 as most others I have
              tested do not follow A^2 - B^2 = (c^2 + d^2)^2 - (c^2- d^2) [29^2 - 20^2 =
              (5^2 + 2^2)^2 - (5^2 - 2^2)^2.]

              Will look deeper but perhaps the only relation to Fermat's method is that it
              uses squares.

              Cheers,
              David Litchfield
            • Mark Underwood
              Hello David, I don t even know what the Fermat method is, and I don t entirely comprehend what has been exchanged thus far, but here are my gleanings on the
              Message 6 of 9 , Dec 2, 2001
              • 0 Attachment
                Hello David,

                I don't even know what the 'Fermat method' is, and I don't entirely
                comprehend what has been exchanged thus far, but here are my
                gleanings on the matter:


                let a^2 + b^2 = c^2, a,b,c relatively prime. a or b must be even, so
                let us assume b is odd.

                b^2 = c^2 - a^2 = (c-a)(c+a)

                It is clear that c-a and c+a are relatively prime, so each of c-a and
                c+a must be squares themselves. So let

                r^2 = c-a
                s^2 = c+a

                So then,

                c = (s^2 + r^2)/2
                a = (s^2 - r^2)/2
                b = rs

                If b is 21, the only combinations possible for r and s are
                (r,s) = (1,21) and (3,7). That would make for two pythagorean
                triplets easily calculated with the equations just above.

                If b is 35, the only combinations possible for r and s are
                (r,s) = (1,35) and (5,7). Two pythagorean triplets.

                If b is 105 = 3*5*7, the combinations possible for r and s are
                (r,s) = (3,35), (5,21), (7,15) and (1,105). Four pythagorean triplets.

                More generally, if b is composed of x different prime factors, then
                the number of pythagorean triples possible is 2^(x-1).

                If b is a prime p, there is only one possible combination, and that is
                (r,s) = (1,p).

                In other words, if b is a prime p, the only pythagorean triplet
                possible would be

                b = p
                a = (p^2 - 1)/2
                c = (p^2 + 1)/2


                Examples: (b,a,c), where a^2 + b^2 = c^2, b is prime:

                (3,4,5), (5,12,13), (7,24,25), (11,60,61).

                a little more mud in the water,
                Mark





                --- In primenumbers@y..., "David Litchfield" <Mnemonix@g...> wrote:
                > > With you now, cheers. Does this explain the other two p.
                triangles:
                >
                > Bad form answering your own emails (sorry) but I've just seen the
                > relationship:
                >
                > Using 35 as the example
                >
                > 35 = 5 * 7
                > p. triangle is 35 -> 120 -> 125
                >
                > 120 / 5 = 24
                > 125 / 5 = 25
                > 24 + 25 = 49
                > 49 sqrt = 7
                >
                > and
                >
                > p. triangle is 35 -> 84 -> 91
                > 84 / 7 = 12
                > 91 / 7 = 13
                > 12 + 13 = 25
                > 25 sqrt = 5
                >
                >
                > David
              • David Litchfield
                ... Cheers, David ... From: Marcel Martin Cc: Sent: Sunday, December 02, 2001 10:16 PM Subject: Re:
                Message 7 of 9 , Dec 3, 2001
                • 0 Attachment
                  With you now, cheers. Does this explain the other two p. triangles:

                  > 21 -> 28 -> 35
                  > 21 -> 72 -> 75

                  > 15 -> 20 -> 25
                  > 15 -> 36 -> 39

                  > 33 -> 44 -> 55
                  > 33 -> 180 -> 183

                  > 35 -> 84 -> 91
                  > 35 -> 120 -> 125

                  > These dimensions are for such p. triangles that when you subtract
                  > the two dervied lengths from given number they produce the factors
                  > e.g.
                  > 77 -> 264 -> 275
                  > 77 -> 420 -> 427

                  > 275 - 264 = 11
                  > 427 - 420 = 7

                  > 7 * 11 = 77

                  Cheers,
                  David



                  ----- Original Message -----
                  From: "Marcel Martin" <znz@...>
                  Cc: <primenumbers@yahoogroups.com>
                  Sent: Sunday, December 02, 2001 10:16 PM
                  Subject: Re: [PrimeNumbers] Pythagoras and factoring


                  >
                  > I sent an other post in which I pointed out the typo I made in the
                  > first one. The right relation was
                  > 29^2 - 21^2 = (5^2 + 2^2)^2 - (5^2 - 2^2)^2.
                  >
                  > The link with your method and the Fermat's one is
                  >
                  > Fermat: N = u^2 - v^2
                  > Yours : N^2 = U^2 - V^2
                  >
                  > Assuming N = a*b, a and b odd, a > b.
                  > With Fermat, it comes, u = (a+b)/2 and v = (a-b)/2. Then your
                  > parameters are simply U = u^2 + v^2 and V = 2uv
                  >
                  > With 35 you get
                  > u = 6, v = 1 thus U = 37 and V = 12.
                  >
                  > >and so
                  > >37^2 - 12^2 != (7^2 + 5^2)^2 - (7^2 - 5^2)^2
                  >
                  > Of course. But
                  >
                  > 37^2 - 35^2 = (6^2 + 1^2)^2 - (6^2 - 1^2)^2
                  > U^2 - N^2 = (u^2 + v^2)^2 - (u^2 - v^2)^2
                  >
                  > >Will look deeper but perhaps the only relation to Fermat's method is that
                  it
                  > >uses squares.
                  >
                  > No. It is just a complication of Fermat method. And, except maybe
                  > some particular cases, it is much less efficient since you have to
                  > work with numbers that are twice greater than the ones required in
                  > the Fermat method.
                  >
                  > Marcel Martin
                  >
                  >
                  > Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
                  > The Prime Pages : http://www.primepages.org
                  >
                  >
                  >
                  > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
                  >
                  >
                  >
                • David Litchfield
                  ... Bad form answering your own emails (sorry) but I ve just seen the relationship: Using 35 as the example 35 = 5 * 7 p. triangle is 35 - 120 - 125 120 / 5
                  Message 8 of 9 , Dec 3, 2001
                  • 0 Attachment
                    > With you now, cheers. Does this explain the other two p. triangles:

                    Bad form answering your own emails (sorry) but I've just seen the
                    relationship:

                    Using 35 as the example

                    35 = 5 * 7
                    p. triangle is 35 -> 120 -> 125

                    120 / 5 = 24
                    125 / 5 = 25
                    24 + 25 = 49
                    49 sqrt = 7

                    and

                    p. triangle is 35 -> 84 -> 91
                    84 / 7 = 12
                    91 / 7 = 13
                    12 + 13 = 25
                    25 sqrt = 5


                    David
                  • David Litchfield
                    ... But: 205 - 164 = 41 123 / 41 = 3 So we can get the factors straight out with this p. triangle. David
                    Message 9 of 9 , Dec 3, 2001
                    • 0 Attachment
                      > Then B+C=(U+V)^2, B-C=(U-V)^2 as in your examples. But it is *not* common
                      > solution!
                      > For instance, the least solution to A^2+B^2=C^2 with A=123 is
                      >
                      > 123^2+164^2=205^2
                      >
                      > Both your C-program and my pascal one find this solution. But,alas
                      >
                      > 205-164=41 is *not* square, neither is
                      > 205+164=369=3^2*41.
                      >

                      But: 205 - 164 = 41
                      123 / 41 = 3
                      So we can get the factors straight out with this p. triangle.

                      David
                    Your message has been successfully submitted and would be delivered to recipients shortly.