## RE: [PrimeNumbers] The "twothree" numbers

Expand Messages
• 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
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/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com

-----Original Message-----
From: Mark Underwood [mailto:mark.underwood@...]
Sent: 29 August 2003 16:21

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

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/
• ... 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
--- 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.
• 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
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/
> 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
> 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/
• 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
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.
• ... Create a list L of all t numbers
Message 5 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... :)
• 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
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;
}
• 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
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).
>
• ... 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
--- 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
• 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
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.