Prime numbers and primality testing Yahoo Group The "twothree" numbers =============================================== Mark Underwood Message 1 of 10 Aug 29, 2003 ----------------------------------------------- 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 =============================================== Jon Perry Message 2 of 10 Aug 29, 2003 ----------------------------------------------- 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 Message 3 of 10 Aug 29, 2003 ----------------------------------------------- --- 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 Message 4 of 10 Aug 29, 2003 ----------------------------------------------- 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 Message 5 of 10 Aug 29, 2003 ----------------------------------------------- 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 Message 6 of 10 Aug 29, 2003 ----------------------------------------------- --- 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 Message 7 of 10 Aug 30, 2003 ----------------------------------------------- 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 Message 8 of 10 Aug 30, 2003 ----------------------------------------------- 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 Message 9 of 10 Aug 30, 2003 ----------------------------------------------- --- 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 Message 10 of 10 Aug 30, 2003 ----------------------------------------------- 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] =============================================== Cached by Georg Fischer at Nov 14 2019 10:04 with clean_yahoo.pl V1.3