## sum of two p-smooth numbers

Expand Messages
• 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
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:

 A002223 Smallest 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

• 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

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 :

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:

 A002223 Smallest 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

• 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

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

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 :

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:

 A002223 Smallest 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

• 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
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 :

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

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 :

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:

 A002223 Smallest 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

• 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

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

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 :

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

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 :

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:

 A002223 Smallest 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

• ... 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
2014-02-11 20:39 GMT+01:00 :

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
• 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
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)
• 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
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

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)
• ... 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
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.

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

David (subject to yahoo scrambling)

• 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
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.

• ... 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
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.