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