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

RE: [PrimeNumbers] The "twothree" numbers

Expand Messages
  • Jon Perry
    I was going to say your t numbers are denser than the triangular numbers, so the case for 4 has no solutions, but this doesn t seem to be true. I would have
    Message 1 of 10 , Aug 29, 2003
    • 0 Attachment
      I was going to say your t numbers are denser than the triangular numbers, so
      the case for 4 has no solutions, but this doesn't seem to be true.

      I would have compared the asymtopic formulae, unfortunately EIS doesn't seem
      to have one for the triangular numbers.

      Jon Perry
      perry@...
      http://www.users.globalnet.co.uk/~perry/maths/
      http://www.users.globalnet.co.uk/~perry/DIVMenu/
      BrainBench MVP for HTML and JavaScript
      http://www.brainbench.com

      -----Original Message-----
      From: Mark Underwood [mailto:mark.underwood@...]
      Sent: 29 August 2003 16:21
      To: primenumbers@yahoogroups.com
      Subject: [PrimeNumbers] The "twothree" numbers




      Hi all

      I would like to introduce the 'twothree' numbers, abbreviated as
      the 't' numbers. A 't' number is any number which has not factors
      other than 1 ,2 and 3. A 't' number is of the form (2^a)*(3^b) ,
      where a and b are non negatve integers. The 't' numbers are:
      1,2,3,4,6,8,9,12,16,18,24,27,32,36 and so on. The first number which
      doesn't qualify as a 't' number is a prime, 5.

      Now take any two 't' numbers and add them together. ie,

      1+1 = 2 ; 1+2 = 3 ; 1+3 = 4 ; 1+4 = 5 ; 2+4 = 6. ; 3+4 = 7, etc.

      It turns out that the first number greater than 1 which can't be
      expressed as the sum of two 't' numbers at least once is the number
      23. Upon some reflection we see that this number would have to be
      prime.

      Now take any three 't' numbers and add them together. ie,
      1+1+1 = 3 ; 1+1+2 = 4 ; 1+1+3 = 5 ; 1+1+4 = 6 ; 1+2+4 = 7, etc.

      The first number greater than 2 which can't be expressed as the sum
      of three 't' numbers at least once is the number 431. As we would
      expect, it is again a prime.

      Now take any four 't' numbers and add them together. ie,
      1+1+1+1 = 4; 1+1+1+2 = 5 ; 1+1+1+3 = 6, etc.

      I have not been able to find the first number (which would be a
      prime) which cannot be expressed as the sum of 4 't' numbers. I
      suspect it is huge but I'm not sure of what order. And it would
      certainly be a prime number.

      Here are some figures that give an idea of the number of solutions.
      It suffices to consider only prime numbers.

      5 = 1+1+1+2.
      7 = 1+1+1+4 = 1+1+2+3 = 1+2+2+2.
      11= 1+1+1+8 = 1+1+3+6 = 1+2+2+6 = 1+2+4+4 = 1+3+3+4 = 2+2+3+4 =
      2+3+3+3.

      In summary, 5 has one solution, 7 has 3 solutions and 11 has 7
      solutions, all expressed as (5,1) (7,3) (11,7). Here is a more
      comprehensive list:

      (5,1) (7,3) (11,7) (13,9) (17,13) (19,15) (23,19) (29,23) (31,24)
      (37,30) (41,32) (43,34) (47,34) (53,36) (59,37) (61,40) (67,41)
      (71,40) (73,42) (79,43) (83,45) (89,47) (97,48) (101,49) (103,50)
      (107,50) (109,52) (113,51) (127,51) (131,49) (137,54) (139,56)
      (149,53) (151,52) (157,56) (163,58) (167,53) (173,56) (179,56)
      (181,59) (191,48) (193,56) (197,52) (199,55) (211,55) (223,48)
      (227,58) (229,57) (233,58) (239,45) (241,56) (251,54) (257,59)
      (263,55) (269,57) (271,57) (277,62) (281,65) (283,63) (293,57)
      (307,71) (311,53) (313,67) (317,59) (331,67) (337,70) (347,62)
      (349,59) (353,67) (359,53) (367,54) (373,57) (379,64) (383,45)
      (389,54) (397,60) (401,58) (409,68) (419,60) (421,57) (431,36)
      (433,61) (439,51) (443,59) (449,54) (457,61) (461,53) (463,52)
      (467,57) (479,42) (487,51) (491,56) (499,64) (503,42) ...

      The computation time gets way out of hand as the numbers get larger.
      I tried computing the solutions for the single prime 100003 and after
      eight hours running it has given 10 solutions so far, the most recent
      being 243 + 432 + 16384 + 82944.

      Interesting and somewhat satisfied my curiousity but I can't see that
      this could lead anywhere useful.

      Mark





      Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      The Prime Pages : http://www.primepages.org/



      Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
    • jbrennen
      ... The first number not expressible as a sum of 4 or fewer t numbers is actually 18431, which is not prime at all, being equal to 7 * 2633. All numbers
      Message 2 of 10 , Aug 29, 2003
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, Mark Underwood wrote:
        > I would like to introduce the 'twothree' numbers, abbreviated as
        > the 't' numbers. A 't' number is any number which has not factors
        > other than 1 ,2 and 3. A 't' number is of the form (2^a)*(3^b) ,
        > where a and b are non negatve integers. The 't' numbers are:
        > 1,2,3,4,6,8,9,12,16,18,24,27,32,36 and so on. The first number which
        > doesn't qualify as a 't' number is a prime, 5.
        >
        > It turns out that the first number greater than 1 which can't be
        > expressed as the sum of two 't' numbers at least once is the number
        > 23. Upon some reflection we see that this number would have to be
        > prime.
        >
        > The first number greater than 2 which can't be expressed as the sum
        > of three 't' numbers at least once is the number 431. As we would
        > expect, it is again a prime.
        >
        > I have not been able to find the first number (which would be a
        > prime) which cannot be expressed as the sum of 4 't' numbers. I
        > suspect it is huge but I'm not sure of what order. And it would
        > certainly be a prime number.
        >

        The first number not expressible as a sum of 4 or fewer 't' numbers
        is actually 18431, which is not prime at all, being equal to
        7 * 2633.

        All numbers < 3000000 can be expressed as a sum of no more than
        5 't' numbers.

        Computing higher numbers in this sequence gets very expensive,
        because as you noted, the number of combinations grows exponentially.
      • Mark Underwood
        That it might have no solutions definitely crossed my mind as well! But you re right, there must eventually come a time when it fails. If it never fails that
        Message 3 of 10 , Aug 29, 2003
        • 0 Attachment
          That it might have no solutions definitely crossed my mind as well!

          But you're right, there must eventually come a time when it fails. If
          it never fails that would mean that every number n can be expressed
          as 8 numbers, each less than log2(n). When n starts approaching or
          exceeding something around the order of (log2(n))^8, then it will
          have no solutions for some n. That is when n is about 10^14.

          And now I want to retract something which I said earlier, that the
          first number with no solutions would 'certainly' be a prime. Mike
          Oakes brought it to my attention that there doesn't seem to be a
          reason why this must be so. I had the vague notion that two numbers
          of this form, when multiplied together, will have the same form, but
          this is clearly incorrect.

          Here are the numbers less than one hundred which can't be generated
          by adding two 't' numbers: 23,46,47,53,61,69,77,79,92,94,95

          Notice that 77 = 7*11 and 95 = 5*19, and each of 7,11,5 and 19 can be
          generated.

          But an interesting thing: When a number n appears which can not be
          generated from the addition of two 't' nummbers, it seems on cursory
          inspection that this n times any 't' number always yields a number
          which also cannot be expressed as the sum of two 't' numbers. For
          instance, 23 can't be expressed, and neither can 2*23, 3*23, 4*23,
          6*23, etc, etc.

          Mark


          --- In primenumbers@yahoogroups.com, "Jon Perry" <perry@g...> wrote:
          > I was going to say your t numbers are denser than the triangular
          numbers, so
          > the case for 4 has no solutions, but this doesn't seem to be true.
          >
          > I would have compared the asymtopic formulae, unfortunately EIS
          doesn't seem
          > to have one for the triangular numbers.
          >
          > Jon Perry
          > perry@g...
          > http://www.users.globalnet.co.uk/~perry/maths/
          > http://www.users.globalnet.co.uk/~perry/DIVMenu/
          > BrainBench MVP for HTML and JavaScript
          > http://www.brainbench.com
          >
          > -----Original Message-----
          > From: Mark Underwood [mailto:mark.underwood@s...]
          > Sent: 29 August 2003 16:21
          > To: primenumbers@yahoogroups.com
          > Subject: [PrimeNumbers] The "twothree" numbers
          >
          >
          >
          >
          > Hi all
          >
          > I would like to introduce the 'twothree' numbers, abbreviated as
          > the 't' numbers. A 't' number is any number which has not factors
          > other than 1 ,2 and 3. A 't' number is of the form (2^a)*(3^b) ,
          > where a and b are non negatve integers. The 't' numbers are:
          > 1,2,3,4,6,8,9,12,16,18,24,27,32,36 and so on. The first number which
          > doesn't qualify as a 't' number is a prime, 5.
          >
          > Now take any two 't' numbers and add them together. ie,
          >
          > 1+1 = 2 ; 1+2 = 3 ; 1+3 = 4 ; 1+4 = 5 ; 2+4 = 6. ; 3+4 = 7, etc.
          >
          > It turns out that the first number greater than 1 which can't be
          > expressed as the sum of two 't' numbers at least once is the number
          > 23. Upon some reflection we see that this number would have to be
          > prime.
          >
          > Now take any three 't' numbers and add them together. ie,
          > 1+1+1 = 3 ; 1+1+2 = 4 ; 1+1+3 = 5 ; 1+1+4 = 6 ; 1+2+4 = 7, etc.
          >
          > The first number greater than 2 which can't be expressed as the sum
          > of three 't' numbers at least once is the number 431. As we would
          > expect, it is again a prime.
          >
          > Now take any four 't' numbers and add them together. ie,
          > 1+1+1+1 = 4; 1+1+1+2 = 5 ; 1+1+1+3 = 6, etc.
          >
          > I have not been able to find the first number (which would be a
          > prime) which cannot be expressed as the sum of 4 't' numbers. I
          > suspect it is huge but I'm not sure of what order. And it would
          > certainly be a prime number.
          >
          > Here are some figures that give an idea of the number of solutions.
          > It suffices to consider only prime numbers.
          >
          > 5 = 1+1+1+2.
          > 7 = 1+1+1+4 = 1+1+2+3 = 1+2+2+2.
          > 11= 1+1+1+8 = 1+1+3+6 = 1+2+2+6 = 1+2+4+4 = 1+3+3+4 = 2+2+3+4 =
          > 2+3+3+3.
          >
          > In summary, 5 has one solution, 7 has 3 solutions and 11 has 7
          > solutions, all expressed as (5,1) (7,3) (11,7). Here is a more
          > comprehensive list:
          >
          > (5,1) (7,3) (11,7) (13,9) (17,13) (19,15) (23,19) (29,23) (31,24)
          > (37,30) (41,32) (43,34) (47,34) (53,36) (59,37) (61,40) (67,41)
          > (71,40) (73,42) (79,43) (83,45) (89,47) (97,48) (101,49) (103,50)
          > (107,50) (109,52) (113,51) (127,51) (131,49) (137,54) (139,56)
          > (149,53) (151,52) (157,56) (163,58) (167,53) (173,56) (179,56)
          > (181,59) (191,48) (193,56) (197,52) (199,55) (211,55) (223,48)
          > (227,58) (229,57) (233,58) (239,45) (241,56) (251,54) (257,59)
          > (263,55) (269,57) (271,57) (277,62) (281,65) (283,63) (293,57)
          > (307,71) (311,53) (313,67) (317,59) (331,67) (337,70) (347,62)
          > (349,59) (353,67) (359,53) (367,54) (373,57) (379,64) (383,45)
          > (389,54) (397,60) (401,58) (409,68) (419,60) (421,57) (431,36)
          > (433,61) (439,51) (443,59) (449,54) (457,61) (461,53) (463,52)
          > (467,57) (479,42) (487,51) (491,56) (499,64) (503,42) ...
          >
          > The computation time gets way out of hand as the numbers get larger.
          > I tried computing the solutions for the single prime 100003 and
          after
          > eight hours running it has given 10 solutions so far, the most
          recent
          > being 243 + 432 + 16384 + 82944.
          >
          > Interesting and somewhat satisfied my curiousity but I can't see
          that
          > this could lead anywhere useful.
          >
          > Mark
          >
          >
          >
          >
          >
          > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          > The Prime Pages : http://www.primepages.org/
          >
          >
          >
          > Your use of Yahoo! Groups is subject to
          http://docs.yahoo.com/info/terms/
        • Mark Underwood
          Wow, I am amazed it is that low , which throws my previous, ahem, heuristic to the wind. And I am amazed that you actually found it Jack, even at that
          Message 4 of 10 , Aug 29, 2003
          • 0 Attachment
            Wow, I am amazed it is that 'low', which throws my previous, ahem,
            heuristic to the wind. And I am amazed that you actually found it
            Jack, even at that altitude. And it is somewhat amazing it is not a
            prime! How on earth you coded so that you could determine so quickly
            that all numbers less than 3,000,000 can be expressed as the sum of
            5 't' numbers is beyond me!
            Mark


            --- In primenumbers@yahoogroups.com, "jbrennen" <jack@b...> wrote:
            > --- In primenumbers@yahoogroups.com, Mark Underwood wrote:
            > > I would like to introduce the 'twothree' numbers, abbreviated as
            > > the 't' numbers. A 't' number is any number which has not factors
            > > other than 1 ,2 and 3. A 't' number is of the form (2^a)*
            (3^b) ,
            > > where a and b are non negatve integers. The 't' numbers are:
            > > 1,2,3,4,6,8,9,12,16,18,24,27,32,36 and so on. The first number
            which
            > > doesn't qualify as a 't' number is a prime, 5.
            > >
            > > It turns out that the first number greater than 1 which can't be
            > > expressed as the sum of two 't' numbers at least once is the
            number
            > > 23. Upon some reflection we see that this number would have to
            be
            > > prime.
            > >
            > > The first number greater than 2 which can't be expressed as the
            sum
            > > of three 't' numbers at least once is the number 431. As we would
            > > expect, it is again a prime.
            > >
            > > I have not been able to find the first number (which would be a
            > > prime) which cannot be expressed as the sum of 4 't' numbers. I
            > > suspect it is huge but I'm not sure of what order. And it would
            > > certainly be a prime number.
            > >
            >
            > The first number not expressible as a sum of 4 or fewer 't' numbers
            > is actually 18431, which is not prime at all, being equal to
            > 7 * 2633.
            >
            > All numbers < 3000000 can be expressed as a sum of no more than
            > 5 't' numbers.
            >
            > Computing higher numbers in this sequence gets very expensive,
            > because as you noted, the number of combinations grows
            exponentially.
          • jbrennen
            ... Create a list L of all t numbers
            Message 5 of 10 , Aug 29, 2003
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, Mark Underwood wrote:
              > How on earth you coded so that you could determine so
              > quickly that all numbers less than 3,000,000 can be
              > expressed as the sum of 5 't' numbers is beyond me!

              Create a list L of all 't' numbers < 3000000.

              Create an array A[0...2999999]. All entries are 0, except A[0]=1.

              Begin a loop:

              * For each N going from 2999999 down to 0 which has A[N] equal to 1:

              * * For each number X in list L, if N+X < 3000000, set A[N+X]=1.

              * Find the smallest N such that A[N] is 0. Report the value of N.

              * Unless the entire array is now set to 1, go back and loop again.


              This algorithm prints out:

              5
              23
              431
              18431

              And then exits.

              It's just as simple as that... :)
            • Jack Brennen
              I know this is a bit off-topic, since we ve shown that the sequence of minimal not-summable numbers need not be prime. But I just wanted to report my latest
              Message 6 of 10 , Aug 30, 2003
              • 0 Attachment
                I know this is a bit off-topic, since we've shown that the sequence of
                minimal not-summable numbers need not be prime. But I just wanted to
                report my latest result and give somebody else with more RAM the
                opportunity to search further if desired.

                The smallest number not expressible as a sum of 5 't' numbers
                is the number 3448733 (37 * 83 * 1123).

                Here is the C program I used. If you have enough RAM, you can extend
                the search beyond the 20000000 that I searched to. This program should
                work unmodified for SLIM as high as 1400000000 (if you've got
                about 1.5 gigabytes of RAM). Go much beyond that and you'll have to
                solve some issues with arithmetic overflow.

                By the way, SLIM doesn't mean skinny -- think "Search LIMit" . :)

                /****************************************/

                #include <stdio.h>
                #include <stdlib.h>

                #define SLIM 20000000
                static unsigned L[10000];
                static unsigned lcnt;
                static unsigned char a[SLIM];

                static int Lcmp(const void *p, const void *q)
                {
                return (int)(*(const unsigned *)p) - (int)(*(const unsigned *)q);
                }

                int main(void)
                {
                unsigned j,n;

                for (n=1; n<SLIM; n*=2)
                for (j=n; j<SLIM; j*=3)
                L[lcnt++] = j;
                qsort(L, lcnt, sizeof(unsigned), Lcmp);
                a[0] = 1;
                for (;;) {
                n = SLIM;
                while (n)
                if (a[--n])
                for (j=0; j<lcnt && n+L[j]<SLIM; j++)
                a[n+L[j]] = 1;
                for (n=0; a[n] && ++n < SLIM; )
                ;
                if (n == SLIM)
                break;
                printf("%u\n", n);
                }

                return EXIT_SUCCESS;
                }
              • Michael Bell
                I ran this with SLIM set to 100 million with no 6 t numbers found. I would expect looking at the growth rate of the numbers for the first 6 t number to be
                Message 7 of 10 , Aug 30, 2003
                • 0 Attachment
                  I ran this with SLIM set to 100 million with no 6 t numbers found. I would
                  expect looking at the growth rate of the numbers for the first 6 t number to
                  be around 10^9. Anyone got a couple of gigs of RAM and a few hours spare?

                  Mike.

                  Jack Brennen wrote:
                  > I know this is a bit off-topic, since we've shown that the sequence of
                  > minimal not-summable numbers need not be prime. But I just wanted to
                  > report my latest result and give somebody else with more RAM the
                  > opportunity to search further if desired.
                  >
                  > The smallest number not expressible as a sum of 5 't' numbers
                  > is the number 3448733 (37 * 83 * 1123).
                  >
                • Jeff Wolfe
                  ... It struck me that the constraining element of this program is an array of 8-bit variables used to store 1-bit values. I changed the program to use all
                  Message 8 of 10 , Aug 30, 2003
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, Jack Brennen <jack@b...> wrote:
                    > The smallest number not expressible as a sum of 5 't' numbers
                    > is the number 3448733 (37 * 83 * 1123).
                    >
                    > Here is the C program I used. If you have enough RAM, you can extend
                    > the search beyond the 20000000 that I searched to. This program should
                    > work unmodified for SLIM as high as 1400000000 (if you've got
                    > about 1.5 gigabytes of RAM). Go much beyond that and you'll have to
                    > solve some issues with arithmetic overflow.

                    It struck me that the constraining element of this program is an array
                    of 8-bit variables used to store 1-bit values. I changed the program
                    to use all 8-bits of the array a[], which, of course, reduced the
                    memory requirements by nearly a factor of 8. I only tested it to
                    20000000, and there's still the overflow considerations, but someone
                    with much less memory should now be able to run it for high values of
                    SLIM.

                    Here it is.

                    /****************************************/

                    #include <stdio.h>
                    #include <stdlib.h>

                    #define SLIM 20000000
                    #define SLIMMER 2500000 /* SLIM / 8 */
                    static unsigned L[10000];
                    static unsigned lcnt;
                    static unsigned char a[SLIMMER];
                    static unsigned char pow2[8] = {1,2,4,8,16,32,64,128};

                    static int Lcmp(const void *p, const void *q)
                    {
                    return (int)(*(const unsigned *)p) - (int)(*(const unsigned *)q);
                    }

                    unsigned char geta (unsigned aflag) {
                    return ((a[aflag/8] & pow2[aflag%8])?1:0);
                    }

                    void seta (unsigned aflag) {
                    a[aflag/8] |= pow2[aflag%8];
                    }

                    int main(void)
                    {
                    unsigned j,n;

                    for (n=1; n<SLIM; n*=2)
                    for (j=n; j<SLIM; j*=3)
                    L[lcnt++] = j;
                    qsort(L, lcnt, sizeof(unsigned), Lcmp);
                    seta(0);
                    for (;;) {
                    n = SLIM;
                    while (n)
                    if (geta(--n))
                    for (j=0; j<lcnt && n+L[j]<SLIM; j++)
                    seta(n+L[j]);
                    for (n=0; geta(n) && ++n < SLIM; )
                    ;
                    if (n == SLIM)
                    break;
                    printf("%u\n", n);
                    }

                    return EXIT_SUCCESS;
                    }

                    - Jeff
                  • mikeoakes2@aol.com
                    In a message dated 30/08/03 08:04:45 GMT Daylight Time, jack@brennen.net ... I have recoded Jack s elegant algorithm in Pascal, at the same time changing his
                    Message 9 of 10 , Aug 30, 2003
                    • 0 Attachment
                      In a message dated 30/08/03 08:04:45 GMT Daylight Time, jack@...
                      writes:


                      > The smallest number not expressible as a sum of 5 't' numbers
                      > is the number 3448733 (37 * 83 * 1123).
                      >
                      > Here is the C program I used. If you have enough RAM, you can extend
                      > the search beyond the 20000000 that I searched to. This program should
                      > work unmodified for SLIM as high as 1400000000 (if you've got
                      > about 1.5 gigabytes of RAM). Go much beyond that and you'll have to
                      > solve some issues with arithmetic overflow.
                      >

                      I have recoded Jack's elegant algorithm in Pascal, at the same time changing
                      his char array to a bit-array, and run it for SLIM = 2*10^9, requiring a mere
                      250Mb of RAM.

                      An answer has just popped out after 6 hrs on an Athlon XP2800+ (2.08GHz):-
                      1441896119
                      This is prime, as it happens.

                      Mike


                      [Non-text portions of this message have been removed]
                    Your message has been successfully submitted and would be delivered to recipients shortly.