Prime numbers and primality testing is a Restricted Group with 1114 members.
 Prime numbers and primality testing

 Restricted Group,
 1114 members
Primary Navigation
sum of two psmooth numbers
 0 Attachment
Given that a psmooth 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 2smooth numbers.23 is the least number that can't be written as the sum of two 3smooth numbers.71 is the least number that can't be written as the sum of two 5smooth numbersContinuing 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 = 8k1 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 0 Attachment
A partial answer:Let prime p be the smallest of the form p = 8k1 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_nsmooth 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.Jarek20140210 18:41 GMT+01:00 <mark.underwood@...>:Given that a psmooth 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 2smooth numbers.23 is the least number that can't be written as the sum of two 3smooth numbers.71 is the least number that can't be written as the sum of two 5smooth numbersContinuing 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 = 8k1 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 0 Attachment
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 8n1 !MarkIn primenumbers@yahoogroups.com, <jaroslaw.wroblewski@...> wrote:A partial answer:Let prime p be the smallest of the form p = 8k1 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_nsmooth 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.Jarek20140210 18:41 GMT+01:00 <mark.underwood@...>:Given that a psmooth 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 2smooth numbers.23 is the least number that can't be written as the sum of two 3smooth numbers.71 is the least number that can't be written as the sum of two 5smooth numbersContinuing 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 = 8k1 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 0 Attachment
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 13smooth 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.Jarek20140211 1:04 GMT+01:00 <mark.underwood@...>: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 8n1 !MarkIn primenumbers@yahoogroups.com, <jaroslaw.wroblewski@...> wrote:
A partial answer:Let prime p be the smallest of the form p = 8k1 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_nsmooth 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.Jarek20140210 18:41 GMT+01:00 <mark.underwood@...>:Given that a psmooth 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 2smooth numbers.23 is the least number that can't be written as the sum of two 3smooth numbers.71 is the least number that can't be written as the sum of two 5smooth numbersContinuing 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 = 8k1 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 0 Attachment
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 8n1, 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
In primenumbers@yahoogroups.com, <jaroslaw.wroblewski@...> wrote:
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 13smooth 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.Jarek20140211 1:04 GMT+01:00 <mark.underwood@...>: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 8n1 !MarkIn primenumbers@yahoogroups.com, <jaroslaw.wroblewski@...> wrote:
A partial answer:Let prime p be the smallest of the form p = 8k1 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_nsmooth 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.Jarek20140210 18:41 GMT+01:00 <mark.underwood@...>:Given that a psmooth 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 2smooth numbers.23 is the least number that can't be written as the sum of two 3smooth numbers.71 is the least number that can't be written as the sum of two 5smooth numbersContinuing 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 = 8k1 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 0 Attachment
20140211 20:39 GMT+01:00 <mark.underwood@...>:Apart from those numbers being prime and of the form 8n1, 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 0 Attachment
From
D. H. Lehmer, Emma Lehmer and Daniel Shanks
http://www.ams.org/mcom/197024110/S0025571819700271006X
R. F. Lukes, C. D. Patterson and H. C. Williams
http://www.ams.org/mcom/199665213/S0025571896006783
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) 0 Attachment
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 31smooth 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 31smooth numbers are118271, 236542, 307271, 354813, 366791.
118281 = 101*1171.
Go figure...
Mark
In primenumbers@yahoogroups.com, <david.broadhurst@...> wrote:
From
D. H. Lehmer, Emma Lehmer and Daniel Shanks
http://www.ams.org/mcom/197024110/S0025571819700271006X
R. F. Lukes, C. D. Patterson and H. C. Williams
http://www.ams.org/mcom/199665213/S0025571896006783
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) 0 Attachment
Mark Underwood wrote:> The first 5 integers that can't be written
Of these the smallest prime is 366791, as
> as the sum of two 31smooth numbers are
> 118271, 236542, 307271, 354813, 366791.
per Jarek's heuristic argument.
We already knew 118271 from
http://oeis.org/A062241> Smallest integer >= 2 that is not the sum of
which is subject of this thread and contains
> 2 positive integers whose prime factors are
> all <= p(n), the nth prime.
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
containing 307271 is "dead".
David (subject to yahoo scrambling) 0 Attachment
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. 0 Attachment
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