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

sum of two p-smooth numbers

Expand Messages
  • marku606
    Given that a p-smooth number is a number with prime factors no greater than the prime p, 7 is the least number that can t be written as the sum of two 2-smooth
    Message 1 of 11 , Feb 10, 2014
    • 0 Attachment
      Given that a p-smooth number is a number with prime factors no greater than the prime p,

      7 is the least number that can't be written as the sum of two 2-smooth numbers.
      23 is the least number that can't be written as the sum of two 3-smooth numbers. 
      71 is the least number that can't be written as the sum of two 5-smooth numbers

      Continuing we get the sequence 7, 23, 71, 311, 479, 1559, 5711,10559, ...

      It wasn't surprising to find it already in oeis  ( http://oeis.org/A002223 ) ,  but the description of the sequence wasn't what I was expecting:

      A002223Smallest prime p of form p = 8k-1 such that first n primes (p_1=2, ..., p_n) are quadratic residues mod p. 

      EXAMPLE

      12^2 = 2 mod 71, 28^2 = 3 mod 71, 17^2 = 5 mod 71.


      I'm not quite understanding how the one is a match to the other, but perhaps others here might have an idea?

      Mark

    • Jaroslaw Wroblewski
      A partial answer: Let prime p be the smallest of the form p = 8k-1 such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p. Then p is the
      Message 2 of 11 , Feb 10, 2014
      • 0 Attachment
        A partial answer:

        Let prime p be the smallest of the form p = 8k-1 such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p.
        Then p is the smallest prime such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p while -1 is a quadratic nonresidue.

        Since -1 is a quadratic nonresidue, p is not a sum of 2 quadratic residues. But any p_n-smooth number is a quadratic residue, hence p is not a sum of 2 smooth numbers (moreover, no multiple of p is such a sum).

        This explains why A002223 contains numbers which are not sums of 2 smooth numbers, but not why those are the smallest. Perhaps a naive explanantion is that there are so many small smooth numbers that every small number is a sum of 2 such numbers if it is not somehow forbidden.

        Jarek



        2014-02-10 18:41 GMT+01:00 <mark.underwood@...>:
         

        Given that a p-smooth number is a number with prime factors no greater than the prime p,

        7 is the least number that can't be written as the sum of two 2-smooth numbers.
        23 is the least number that can't be written as the sum of two 3-smooth numbers. 
        71 is the least number that can't be written as the sum of two 5-smooth numbers

        Continuing we get the sequence 7, 23, 71, 311, 479, 1559, 5711,10559, ...

        It wasn't surprising to find it already in oeis  ( http://oeis.org/A002223 ) ,  but the description of the sequence wasn't what I was expecting:

        A002223Smallest prime p of form p = 8k-1 such that first n primes (p_1=2, ..., p_n) are quadratic residues mod p. 

        EXAMPLE

        12^2 = 2 mod 71, 28^2 = 3 mod 71, 17^2 = 5 mod 71.


        I'm not quite understanding how the one is a match to the other, but perhaps others here might have an idea?

        Mark


      • marku606
        Thanks Jarek, appreciated. Coming from the other direction, from the sum of two smooth numbers, I remain puzzled. I can t intuit why the least number is
        Message 3 of 11 , Feb 10, 2014
        • 0 Attachment


          Thanks Jarek, appreciated.   Coming from the other direction, from the sum of two smooth numbers,  I remain puzzled.  I can't intuit why the least number is necessarily even a prime, let alone a prime of the form 8n-1 !

          Mark
           
          ---In primenumbers@yahoogroups.com, <jaroslaw.wroblewski@...> wrote:

          A partial answer:

          Let prime p be the smallest of the form p = 8k-1 such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p.
          Then p is the smallest prime such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p while -1 is a quadratic nonresidue.

          Since -1 is a quadratic nonresidue, p is not a sum of 2 quadratic residues. But any p_n-smooth number is a quadratic residue, hence p is not a sum of 2 smooth numbers (moreover, no multiple of p is such a sum).

          This explains why A002223 contains numbers which are not sums of 2 smooth numbers, but not why those are the smallest. Perhaps a naive explanantion is that there are so many small smooth numbers that every small number is a sum of 2 such numbers if it is not somehow forbidden.

          Jarek



          2014-02-10 18:41 GMT+01:00 <mark.underwood@...>:
           
          Given that a p-smooth number is a number with prime factors no greater than the prime p,

          7 is the least number that can't be written as the sum of two 2-smooth numbers.
          23 is the least number that can't be written as the sum of two 3-smooth numbers. 
          71 is the least number that can't be written as the sum of two 5-smooth numbers

          Continuing we get the sequence 7, 23, 71, 311, 479, 1559, 5711,10559, ...

          It wasn't surprising to find it already in oeis  ( http://oeis.org/A002223 ) ,  but the description of the sequence wasn't what I was expecting:

          A002223Smallest prime p of form p = 8k-1 such that first n primes (p_1=2, ..., p_n) are quadratic residues mod p. 

          EXAMPLE

          12^2 = 2 mod 71, 28^2 = 3 mod 71, 17^2 = 5 mod 71.


          I'm not quite understanding how the one is a match to the other, but perhaps others here might have an idea?

          Mark


        • Jaroslaw Wroblewski
          I believe that my naive explanation is right, at least in some extent. Namely, there are so many small smooth numbers that each relatively small integer has
          Message 4 of 11 , Feb 10, 2014
          • 0 Attachment
            I believe that my "naive explanation" is right, at least in some extent.

            Namely, there are so many small smooth numbers that each relatively small integer has MANY decompositions into sums of 2 smoothies unless there is a strong reason not to have one.

            For example, consider 13-smooth numbers, and search for integers greater than 30, which have no more than 10 distinct decompositions as sums of 2 smooth numbers. We find:

            1123 10  {{1123, 1}}
            1151 10  {{1151, 1}}
            1319 10  {{1319, 1}}
            1553 9  {{1553, 1}}
            1559 0  {{1559, 1}}
            1607 10  {{1607, 1}}
            1613 10  {{1613, 1}}
            1657 9  {{1657, 1}}
            1691 9  {{19, 1}, {89, 1}}
            1747 7  {{1747, 1}}
            1853 10  {{17, 1}, {109, 1}}
            1861 10  {{1861, 1}}
            1879 10  {{1879, 1}}
            1889 9  {{1889, 1}}
            1909 10  {{23, 1}, {83, 1}}
            1987 10  {{1987, 1}}

            Note that the first example with ONLY 10 decompositions appears over 1000. Number 1747 with ONLY 7 decompositions seems to be outstanding (or shall I say downstanding) as being the only "honest" number below 2000 with less than 9 decompositions. Hence it is unlikely to have a number with very few decompositions, and extremely unlikely to have a number with no decompositions due to a pure random coincidence.

            The number 1559 has a "quadratic residue FIREWALL" against having any decompositions at all, and it seems to have no close competitors among other numbers of similar size.

            Jarek


            2014-02-11 1:04 GMT+01:00 <mark.underwood@...>:
             


            Thanks Jarek, appreciated.   Coming from the other direction, from the sum of two smooth numbers,  I remain puzzled.  I can't intuit why the least number is necessarily even a prime, let alone a prime of the form 8n-1 !

            Mark
             
            ---In primenumbers@yahoogroups.com, <jaroslaw.wroblewski@...> wrote:

            A partial answer:

            Let prime p be the smallest of the form p = 8k-1 such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p.
            Then p is the smallest prime such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p while -1 is a quadratic nonresidue.

            Since -1 is a quadratic nonresidue, p is not a sum of 2 quadratic residues. But any p_n-smooth number is a quadratic residue, hence p is not a sum of 2 smooth numbers (moreover, no multiple of p is such a sum).

            This explains why A002223 contains numbers which are not sums of 2 smooth numbers, but not why those are the smallest. Perhaps a naive explanantion is that there are so many small smooth numbers that every small number is a sum of 2 such numbers if it is not somehow forbidden.

            Jarek



            2014-02-10 18:41 GMT+01:00 <mark.underwood@...>:

             
            Given that a p-smooth number is a number with prime factors no greater than the prime p,

            7 is the least number that can't be written as the sum of two 2-smooth numbers.
            23 is the least number that can't be written as the sum of two 3-smooth numbers. 
            71 is the least number that can't be written as the sum of two 5-smooth numbers

            Continuing we get the sequence 7, 23, 71, 311, 479, 1559, 5711,10559, ...

            It wasn't surprising to find it already in oeis  ( http://oeis.org/A002223 ) ,  but the description of the sequence wasn't what I was expecting:

            A002223Smallest prime p of form p = 8k-1 such that first n primes (p_1=2, ..., p_n) are quadratic residues mod p. 

            EXAMPLE

            12^2 = 2 mod 71, 28^2 = 3 mod 71, 17^2 = 5 mod 71.


            I'm not quite understanding how the one is a match to the other, but perhaps others here might have an idea?

            Mark



          • marku606
            I like, that, a quadratic residue firewall hehe. Yes judging by the number of decompositions dropping suddenly down to zero on some numbers suggests that
            Message 5 of 11 , Feb 11, 2014
            • 0 Attachment

              I like, that, a quadratic residue firewall hehe.  Yes judging by the number of decompositions dropping suddenly down to zero on some numbers suggests that there is a definite and discrete cause of this happening. 


              Apart from those numbers being prime and of the form 8n-1, the only other thing I notice offhand is that, excepting the first number of the sequence (7) , all the numbers are all of the form 24n - 1.


              Mark



              ---In primenumbers@yahoogroups.com, <jaroslaw.wroblewski@...> wrote:

              I believe that my "naive explanation" is right, at least in some extent.

              Namely, there are so many small smooth numbers that each relatively small integer has MANY decompositions into sums of 2 smoothies unless there is a strong reason not to have one.

              For example, consider 13-smooth numbers, and search for integers greater than 30, which have no more than 10 distinct decompositions as sums of 2 smooth numbers. We find:

              1123 10  {{1123, 1}}
              1151 10  {{1151, 1}}
              1319 10  {{1319, 1}}
              1553 9  {{1553, 1}}
              1559 0  {{1559, 1}}
              1607 10  {{1607, 1}}
              1613 10  {{1613, 1}}
              1657 9  {{1657, 1}}
              1691 9  {{19, 1}, {89, 1}}
              1747 7  {{1747, 1}}
              1853 10  {{17, 1}, {109, 1}}
              1861 10  {{1861, 1}}
              1879 10  {{1879, 1}}
              1889 9  {{1889, 1}}
              1909 10  {{23, 1}, {83, 1}}
              1987 10  {{1987, 1}}

              Note that the first example with ONLY 10 decompositions appears over 1000. Number 1747 with ONLY 7 decompositions seems to be outstanding (or shall I say downstanding) as being the only "honest" number below 2000 with less than 9 decompositions. Hence it is unlikely to have a number with very few decompositions, and extremely unlikely to have a number with no decompositions due to a pure random coincidence.

              The number 1559 has a "quadratic residue FIREWALL" against having any decompositions at all, and it seems to have no close competitors among other numbers of similar size.

              Jarek


              2014-02-11 1:04 GMT+01:00 <mark.underwood@...>:
               


              Thanks Jarek, appreciated.   Coming from the other direction, from the sum of two smooth numbers,  I remain puzzled.  I can't intuit why the least number is necessarily even a prime, let alone a prime of the form 8n-1 !

              Mark
               
              ---In primenumbers@yahoogroups.com, <jaroslaw.wroblewski@...> wrote:

              A partial answer:

              Let prime p be the smallest of the form p = 8k-1 such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p.
              Then p is the smallest prime such that the first n primes (p_1=2, ..., p_n) are quadratic residues mod p while -1 is a quadratic nonresidue.

              Since -1 is a quadratic nonresidue, p is not a sum of 2 quadratic residues. But any p_n-smooth number is a quadratic residue, hence p is not a sum of 2 smooth numbers (moreover, no multiple of p is such a sum).

              This explains why A002223 contains numbers which are not sums of 2 smooth numbers, but not why those are the smallest. Perhaps a naive explanantion is that there are so many small smooth numbers that every small number is a sum of 2 such numbers if it is not somehow forbidden.

              Jarek



              2014-02-10 18:41 GMT+01:00 <mark.underwood@...>:

               
              Given that a p-smooth number is a number with prime factors no greater than the prime p,

              7 is the least number that can't be written as the sum of two 2-smooth numbers.
              23 is the least number that can't be written as the sum of two 3-smooth numbers. 
              71 is the least number that can't be written as the sum of two 5-smooth numbers

              Continuing we get the sequence 7, 23, 71, 311, 479, 1559, 5711,10559, ...

              It wasn't surprising to find it already in oeis  ( http://oeis.org/A002223 ) ,  but the description of the sequence wasn't what I was expecting:

              A002223Smallest prime p of form p = 8k-1 such that first n primes (p_1=2, ..., p_n) are quadratic residues mod p. 

              EXAMPLE

              12^2 = 2 mod 71, 28^2 = 3 mod 71, 17^2 = 5 mod 71.


              I'm not quite understanding how the one is a match to the other, but perhaps others here might have an idea?

              Mark



            • Jaroslaw Wroblewski
              ... That is because 3 is a quadratic residue. Similarly, 5 is a quadratic residue when primes are +/- 1 mod 5, so you can see the last digit being 1 or 9 (with
              Message 6 of 11 , Feb 12, 2014
              • 0 Attachment
                2014-02-11 20:39 GMT+01:00 <mark.underwood@...>:

                Apart from those numbers being prime and of the form 8n-1, the only other thing I notice offhand is that, excepting the first number of the sequence (7) , all the numbers are all of the form 24n - 1.


                That is because 3 is a quadratic residue.

                Similarly, 5 is a quadratic residue when primes are +/- 1 mod 5, so you can see the last digit being 1 or 9 (with 2 exceptins at the beginning).
                 
                Jarek
              • djbroadhurst
                From D. H. Lehmer, Emma Lehmer and Daniel Shanks http://www.ams.org/mcom/1970-24-110/S0025-5718-1970-0271006-X R. F. Lukes, C. D. Patterson and H. C. Williams
                Message 7 of 11 , Feb 13, 2014
                • 0 Attachment
                  From
                  D. H. Lehmer, Emma Lehmer and Daniel Shanks
                  http://www.ams.org/mcom/1970-24-110/S0025-5718-1970-0271006-X
                  R. F. Lukes, C. D. Patterson and H. C. Williams
                  http://www.ams.org/mcom/1996-65-213/S0025-5718-96-00678-3
                  it seems that the continuation of
                  http://oeis.org/A002223/b002223.txt
                  is as follows:
                  27 33857579279
                  28 89206899239
                  29 121560956039
                  30 328878692999
                  31 328878692999
                  32 513928659191
                  33 4306732833311
                  34 4306732833311
                  35 4306732833311
                  36 8402847753431
                  37 70864718555231
                  38 317398900373231
                  39 501108392233679
                  40 501108392233679
                  41 501108392233679
                  42 501108392233679
                  43 5551185799073591
                  44 5551185799073591
                  45 5551185799073591
                  46 7832488789769159
                  47 7832488789769159
                  48 102097158739597271
                  49 102097158739597271
                  50 315759454565514431
                  51 868116409360316399
                  52 3412527725201978759
                  53 3546374752298322551
                  54 3546374752298322551
                  55 3546374752298322551
                  56 3546374752298322551
                  57 3546374752298322551
                  However this needs checking by someone
                  better at cutting and pasting than I.
                  David (struggling with abominable yahoo interface)
                • marku606
                  Good find! And, your copy and paste looks accurate. From the AMS paper I see that starting at prime = 31 is a first occurrence where the least number solution
                  Message 8 of 11 , Feb 15, 2014
                  • 0 Attachment
                    Good find!  And, your copy and paste looks accurate.  

                    From the AMS paper I see that starting at prime = 31 is a first occurrence where the least number solution is not prime.   In that case, the least number solution is  307271 = 109 • 2819, and the least prime solution is 366791. 
                    Out of curiosity I decided to continue with my investigation past prime 19, up to prime 31, because I was curious.  Namely, would the least number that can't be written as the sum of two 31-smooth numbers correspond to the least number solution (307271) or the least prime solution (366791) ?
                    It turns out, neither!
                    The first 5 integers > 1 that can't be written as the sum of two 31-smooth numbers are

                    118271, 236542, 307271, 354813, 366791.

                    118281 = 101*1171.

                    Go figure...

                    Mark


                    ---In primenumbers@yahoogroups.com, <david.broadhurst@...> wrote:

                    From
                    D. H. Lehmer, Emma Lehmer and Daniel Shanks
                    http://www.ams.org/mcom/1970-24-110/S0025-5718-1970-0271006-X
                    R. F. Lukes, C. D. Patterson and H. C. Williams
                    http://www.ams.org/mcom/1996-65-213/S0025-5718-96-00678-3
                    it seems that the continuation of
                    http://oeis.org/A002223/b002223.txt
                    is as follows:
                    27 33857579279
                    28 89206899239
                    29 121560956039
                    30 328878692999
                    31 328878692999
                    32 513928659191
                    33 4306732833311
                    34 4306732833311
                    35 4306732833311
                    36 8402847753431
                    37 70864718555231
                    38 317398900373231
                    39 501108392233679
                    40 501108392233679
                    41 501108392233679
                    42 501108392233679
                    43 5551185799073591
                    44 5551185799073591
                    45 5551185799073591
                    46 7832488789769159
                    47 7832488789769159
                    48 102097158739597271
                    49 102097158739597271
                    50 315759454565514431
                    51 868116409360316399
                    52 3412527725201978759
                    53 3546374752298322551
                    54 3546374752298322551
                    55 3546374752298322551
                    56 3546374752298322551
                    57 3546374752298322551
                    However this needs checking by someone
                    better at cutting and pasting than I.
                    David (struggling with abominable yahoo interface)
                  • djbroadhurst
                    ... Of these the smallest prime is 366791, as per Jarek s heuristic argument. We already knew 118271 from http://oeis.org/A062241 ... which is subject of this
                    Message 9 of 11 , Feb 16, 2014
                    • 0 Attachment
                      Mark Underwood wrote:

                      > The first 5 integers that can't be written
                      > as the sum of two 31-smooth numbers are
                      > 118271, 236542, 307271, 354813, 366791.

                      Of these the smallest prime is 366791, as
                      per Jarek's heuristic argument.

                      We already knew 118271 from
                      http://oeis.org/A062241
                      > Smallest integer >= 2 that is not the sum of
                      > 2 positive integers whose prime factors are
                      > all <= p(n), the n-th prime.
                      which is subject of this thread and contains
                      far more values than Mark gave.

                      In conclusion, I recommend
                      http://oeis.org/search?q=1559+5711+10559+18191+31391
                      for 12 relevant sequences, of which the sequence
                      containing 307271 is "dead".

                      David (subject to yahoo scrambling)

                    • marku606
                      I m scratching my head, because when I originally searched for the sequence on oeis some days ago, I did *not* get all the hits that I am now getting. Odd.
                      Message 10 of 11 , Feb 16, 2014
                      • 0 Attachment
                        I'm scratching my head, because when I originally searched for the sequence on oeis some days ago, I did *not* get all the hits that I am now getting.  Odd.  

                      • djbroadhurst
                        ... The search that I recommended was http://oeis.org/search?q=1559+5711+10559+18191+31391 http://oeis.org/search?q=1559+5711+10559+18191+31391 which carefully
                        Message 11 of 11 , Feb 16, 2014
                        • 0 Attachment
                          Mark Underwood wrote:
                          > I did *not* get all the hits that I am now getting.
                          The search that I recommended was
                          http://oeis.org/search?q=1559+5711+10559+18191+31391
                          which carefully avoids commas, composites and small initial terms,
                          any of which may decrease my trawl of 12 hits

                          David

                           


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