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

Re: Formula

Expand Messages
  • marku606
    ... I would like to hear more after you investigate further. You may or may not be aware that every prime of the form 8n + 1 and 8n + 5 can be written as a sum
    Message 1 of 11 , Oct 3, 2009
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, Lowell Rice <lowellcrice@...> wrote:
      >
      > I'm new to this whole concept of talking about only primes, but I randomly came up with a formula to help find just some random primes. It may seem ludicrous, but bear with me. If two numbers have a GCF of 1, and have the same number of the same values of powers in their prime factorization, the the some of their squares will usually be a prime. I haven't fully tested it, and it does need narrowing down as to more limitations on when it'll work, but it's a start.
      >

      I would like to hear more after you investigate further.


      You may or may not be aware that every prime of the form 8n + 1 and 8n + 5 can be written as a sum of two squares.

      x^2 + y^2 = p

      I recall from someone that Euler proved this, or perhaps went further and proved that such primes can be written as the sum of two squares in only one way. Furthermore, by observation it seems that *only* primes and powers of primes can be expressed as the sum of two squares in only one way.

      (This is only part of the story as I shared on this group some time ago.)


      Mark
    • djbroadhurst
      ... 45 = 3^2 + 6^2 is not a prime or a power of a prime David
      Message 2 of 11 , Oct 3, 2009
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "marku606" <mark.underwood@...> wrote:

        > *only* primes and powers of primes can be
        > expressed as the sum of two squares in only one way.

        45 = 3^2 + 6^2 is not a prime or a power of a prime

        David
      • maximilian_hasler
        ... nor is 10=1^2+3^2. See http://www.research.att.com/~njas/sequences/A025284 Numbers that are the sum of 2 nonzero squares in exactly 1 way. Maximilian
        Message 3 of 11 , Oct 3, 2009
        • 0 Attachment
          > > *only* primes and powers of primes can be
          > > expressed as the sum of two squares in only one way.
          >
          > 45 = 3^2 + 6^2 is not a prime or a power of a prime

          nor is 10=1^2+3^2.
          See
          http://www.research.att.com/~njas/sequences/A025284
          Numbers that are the sum of 2 nonzero squares in exactly 1 way.

          Maximilian
        • marku606
          ... That s the problem with posting in haste, I forgot to mention a couple of things outright: 1) I was assuming Lowell s constraint that the two squares are
          Message 4 of 11 , Oct 3, 2009
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "maximilian_hasler" <maximilian.hasler@...> wrote:
            >
            >
            > > > *only* primes and powers of primes can be
            > > > expressed as the sum of two squares in only one way.
            > >
            > > 45 = 3^2 + 6^2 is not a prime or a power of a prime
            >
            > nor is 10=1^2+3^2.
            > See
            > http://www.research.att.com/~njas/sequences/A025284
            > Numbers that are the sum of 2 nonzero squares in exactly 1 way.
            >


            That's the problem with posting in haste, I forgot to mention a couple of things outright: 1) I was assuming Lowell's constraint that the two squares are relatively prime, and 2) the number expressed as the sum of two squares is odd.

            Mark
          • marku606
            ... Just checked up to 300,000 for numbers of the form 8n+5: 6531 of such numbers are primes or prime powers, and they can all be written as the sum of two
            Message 5 of 11 , Oct 3, 2009
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "marku606" <mark.underwood@...> wrote:
              >

              >
              > That's the problem with posting in haste, I forgot to mention a couple of things outright: 1) I was assuming Lowell's constraint that the two squares are relatively prime, and 2) the number expressed as the sum of two squares is odd.
              >


              Just checked up to 300,000 for numbers of the form 8n+5: 6531 of such numbers are primes or prime powers, and they can all be written as the sum of two relatively prime squares only once. It appears that numbers of the form 8n+5 which are not prime or prime powers cannot be written as the sum of two relatively prime powers only once.


              For number of the form 8n+1: 6572 of such numbers are primes or prime powers, but only 6510 of these can be written as the sum of two relatively prime squares only once. The sixty two that cannot are all primes powers, specifically, primes raised to an even power.

              As in the case for numbers of the form 8n+5, it appears that numbers of the form 8n+1 which are not prime or prime powers cannot be written as the sum of two relatively prime powers only once.

              Mark
            • powellarp
              ... Lowell Am I missing something: 85 = 6^2 + 7^2 205 = 3^2 + 14^2 221 = 5^2 + 14^2 365 = 2^2 + 19^2 445 = 2^2 + 21^2 etc etc etc Alan
              Message 6 of 11 , Oct 3, 2009
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, Lowell Rice <lowellcrice@...> wrote:
                >
                > I'm new to this whole concept of talking about only primes, but I randomly came up with a formula to help find just some random primes.  It may seem ludicrous, but bear with me.  If two numbers have a GCF of 1, and have the same number of the same values of powers in their prime factorization, the the some of their squares will usually be a prime.  I haven't fully tested it, and it does need narrowing down as to more limitations on when it'll work, but it's a start.
                >
                >
                >
                >
                > [Non-text portions of this message have been removed]
                >

                Lowell

                Am I missing something:
                85 = 6^2 + 7^2
                205 = 3^2 + 14^2
                221 = 5^2 + 14^2
                365 = 2^2 + 19^2
                445 = 2^2 + 21^2
                etc etc etc

                Alan
              • djbroadhurst
                ... 6531 of such numbers are primes or prime powers, and they can all be written as the sum of two relatively prime squares only once. It appears that numbers
                Message 7 of 11 , Oct 3, 2009
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com,
                  "marku606" <mark.underwood@...> wrote:

                  >> Just checked up to 300,000 for numbers of the form 8n+5:
                  6531 of such numbers are primes or prime powers, and they
                  can all be written as the sum of two relatively prime
                  squares only once. It appears that numbers of the form 8n+5
                  which are not prime or prime powers cannot be written as the
                  sum of two relatively prime powers only once.
                  For number of the form 8n+1: 6572 of such numbers are
                  primes or prime powers, but only 6510 of these can be
                  written as the sum of two relatively prime squares only
                  once. The sixty two that cannot are all primes powers,
                  specifically, primes raised to an even power.
                  As in the case for numbers of the form 8n+5, it appears
                  that numbers of the form 8n+1 which are not prime or prime
                  powers cannot be written as the sum of two relatively prime
                  powers only once. <<

                  All this is very simply explained
                  by unique factorization in K(sqrt(-1)).

                  1) A number N is the sum of two squares if and only if
                  every prime divisor of N that is congruent to 3 mod 4
                  occurs to an even power.

                  2) An odd number N is the sum of two coprime squares in precisely
                  one way if only if N is a prime congruent to 1 mod 4
                  or a power of such a prime.

                  Note that (1) is a consequence of Theorem 252 of Hardy and Wright,
                  that the primes of K(sqrt(-1)) are: 1 + I, the rational primes
                  congruent to 3 mod 4, the factors a + b*I of the rational primes
                  congruent to 1 mod 4, and the associates of these primes.

                  To understand (2), suppose that
                  p = norm(a+I*b) = a^2 + b^2 and
                  q = norm(c+I*d) = c^2 + d^2
                  are distinct rational primes congruent to 1 mod 4.
                  Then we may write
                  p*q = norm((a+I*b)*(c+I*d)) = (a*c-b*d)^2 + (b*c+a*d)^2
                  p*q = norm((a+I*b)*(c-I*d)) = (a*c+b*d)^2 + (b*c-a*d)^2
                  in two essentially different ways.
                  But for any power k of p, the only sum of coprime squares is
                  p^k = norm((a+I*b)^k)
                  since if we try something like
                  p^k = norm((a+I*b)^(k-j)*(a-I*b)^j)
                  with k > j > 0, then p will divide both of the resultant squares.

                  David
                • marku606
                  ... Yes, of course. :) Simplicity is one thing; understanding the simple can be downright elusive to the untrained. Thank you David for your explanation. By
                  Message 8 of 11 , Oct 3, 2009
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                    >

                    > All this is very simply explained
                    > by unique factorization in K(sqrt(-1)).

                    Yes, of course. :)

                    Simplicity is one thing; understanding the simple can be downright elusive to the untrained. Thank you David for your explanation. By the powers of heaven, one day I'm going to understand it.

                    Mark
                  • djbroadhurst
                    In primenumbers@yahoogroups.com, ... This is clearly false. Simply consider 20 = 2^2 + 4^2. David
                    Message 9 of 11 , Oct 4, 2009
                    • 0 Attachment
                      In primenumbers@yahoogroups.com,
                      Kermit Rose <kermit@...> wrote:

                      > An integer z is a sum of two squares in exactly one way
                      > if and only if it is one of the following forms:
                      > (1) an odd power of 2, z = 2**(2*m+1) for m > 0
                      > (2) a prime equal to 1 mod 4
                      > (3) the square of a prime equal to 1 mod 4 or
                      > (4) z = p*h**2 where p is either 2, or an odd prime
                      > equal to 1 mod 4, or the square of an odd prime equal
                      > to 1 mod 4, and h has all prime factors equal to 3 mod 4.

                      This is clearly false. Simply consider 20 = 2^2 + 4^2.

                      David
                    • djbroadhurst
                      ... and then Kermit Rose mistakenly claimed ... with the irrelevant observations ... Note that 10^2 and 5^2 are not coprime. David
                      Message 10 of 11 , Oct 4, 2009
                      • 0 Attachment
                        I wrote:

                        > An odd number N is the sum of two coprime squares in precisely
                        > one way if and only if N is a prime congruent to 1 mod 4
                        > or a power of such a prime.

                        and then "Kermit Rose" mistakenly claimed

                        > David, a Minor correction is needed here

                        with the irrelevant observations

                        > 2**2 + 11**2 = 5**3
                        > 10**2 + 5**2 = 5**3

                        Note that 10^2 and 5^2 are not coprime.

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