## Re: 2^m+3^n and 2^n+3^m

Expand Messages
• ... Thank you David. At least I go into Good Friday with one less potential illusion. :) And that 1679,1743, .. sequence, it is not only hard computing, but
Message 1 of 22 , Apr 9, 2009
>
> Mark Underwood's most interesting sequence for the OEIS
> might be the cases for which his conjecture fails, namely
>
> "Numbers n such that there are no primes of the forms
> 2^m+3^n or 2^n+3^m for m < n"
>
> This sequence begins with
>
> n = 1679, 1743 ...
>
> but Mark would need two more entries to satisfy Neil Sloane.
> PFGW records that there are no more with n < 2500.
> Heuristics suggest that more exist, beyond that paltry limit.
>

Thank you David. At least I go into Good Friday with one less potential illusion. :)
And that 1679,1743, .. sequence, it is not only hard computing, but psychologically
difficult as well, to find a *lack* of primes. Actually finding primes (especially unique
ones) is so much more fun!

On that note, some 2-3 prime time fun, where a,b are 2-3 numbers and

both 2^a + 3^b and 3^b + 2^a are prime.

2^1 + 3^1
2^1 + 3^2 and 2^2+3^1
2^2 + 3^2
2^3 + 3^1 and 2^1 + 3^3
2^3 + 3^2 and 2^2 + 3^3
2^4 + 3^1 and 2^1 + 3^4
2^4 + 3^4
2^6 + 3^2 and 2^2 + 3^6
2^8 + 3^3 and 2^3 + 3^8
2^8 + 3^4 and 2^4 + 3^8
2^9 + 3^2 and 2^2 + 3^9
2^9 + 3^4 and 2^4 + 3^9
2^12 + 3^4 and 2^4 + 3^12.

Mark
• ... Des goûts et des couleurs, on ne discute pas. [About tastes and colours, one does not argue.] However, I remark that my sequence of blanks is *easier*
Message 2 of 22 , Apr 9, 2009
"Mark Underwood" <mark.underwood@...> wrote:

> that 1679,1743, .. sequence, it is not only hard computing,
> but psychologically difficult as well,
> to find a *lack* of primes.
> Actually finding primes (especially unique ones)
> is so much more fun!

"Des goûts et des couleurs, on ne discute pas."
[About tastes and colours, one does not argue.]

However, I remark that my sequence of blanks is *easier*
to generate, up to a given size of n, than is your
preferred sequence of unique hits, since for the former
we may "step to next n" after the first hit, but for the
latter only after the second.

David
• ... Other such numbers are n = 5314 and n = 6100, but PFGW is still running tests to determine whether there might be any more with n
Message 3 of 22 , Apr 10, 2009

> "Numbers n such that there are no primes of the forms
> 2^m+3^n or 2^n+3^m for m < n"
>
> This sequence begins with
>
> n = 1679, 1743 ...

Other such numbers are n = 5314 and n = 6100,
but PFGW is still running tests to determine
whether there might be any more with n < 6100,
so the sequence is not yet ready for OEIS.

David
• ... These numbers include 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 7251, 8218 but my coverage of the range n
Message 4 of 22 , Apr 11, 2009

> "Numbers n such that there are no primes of the forms
> 2^m+3^n or 2^n+3^m for m < n"

These numbers include

1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 7251, 8218

but my coverage of the range n < 8218 is not complete,
so this is not yet a bona fide sequence.

So far, I have tested more than 7000 values of n < 8300
and found these 10 examples.

This agrees tolerably well with my prior heuristics.

To make a rough estimate of the density of primes of the
form N = 2^a + 3^b, I sieved for prime factors < 10^5,
with a and b running from 5000 to 5200, and found that
5558 values of N survived. So I estimated the
probability of primality to be C/log(N), with

C =~ exp(Euler)*log(10^5)*5558/201^2 =~ 2.82.

Hence I guessed that the probability of finding that
a number n lies in this sequence exceeds

exp(-C/log(2))*exp(-C/log(3)) > 1/800.

I say "exceeds", since 2^n+3^m starts at size
O(2^n) and ends at size O(3^n), as m runs from
1 to n-1, while 2^m+3^n stays at size O(3^n).

David
• ... Wow, I am surprised you could go so high, so quickly. Very nice. Some days after you presented the first two numbers, 1679 and 1743, it occurred to me that
Message 5 of 22 , Apr 13, 2009
>
> > "Numbers n such that there are no primes of the forms
> > 2^m+3^n or 2^n+3^m for m < n"
>
> These numbers include
>
> 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 7251, 8218
>

Wow, I am surprised you could go so high, so quickly. Very nice.

Some days after you presented the first two numbers, 1679 and 1743,
it occurred to me that the difference between them is 64 = 2^6.
Made me wonder if there might be a special "2-3" property to these
numbers themselves. But with the additional numbers it seems not.
Of course, if I stumble upon something I'll let you know! :)

Thanks David,

Mark
• ... So far I have 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578, 7251, 7406, 7642, 8218, 8331, 9475, 9578 but this is still not a sequence, as there are
Message 6 of 22 , Apr 13, 2009
--- In primenumbers@yahoogroups.com, "Mark Underwood" <mark.underwood@...> wrote:

> Wow, I am surprised you could go so high, so quickly. Very nice.

So far I have

1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578, 7251, 7406, 7642, 8218, 8331, 9475, 9578

but this is still not a sequence, as there are holes yet to
be looked at, for n < 9578.

David
• Submitted to OEIS: Numbers n such that 2^x + 3^y is never prime when max(x,y) = n 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578, 7251, 7406, 7642, 8218,
Message 7 of 22 , Apr 17, 2009
Submitted to OEIS:

Numbers n such that 2^x + 3^y is never prime when max(x,y) = n

1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578,
7251, 7406, 7642, 8218, 8331, 9475, 9578, 9749

Mark Underwood found that for each non-negative integer n < 1421
there is at least one prime of the form 2^m + 3^n or 2^n + 3^m
with m not exceeding n.

This sequence consists of numbers for which there is no such prime.

David Broadhurst estimated that a fraction in excess of 1/800
of the natural numbers belongs to this sequence and found
17 instances with n < 10^4.

For each of the remaining 9983 non-negative integers n < 10^4,
a prime or probable prime of the form 2^x + 3^y was found with
max(x,y) = n.

Each probable prime was subjected to a combination of
strong Fermat and strong Lucas tests.

• ... This form invites possibly the most bizarre, and remarkably efficient, sieve algorithm I ve yet had the misfortune of considering. Good job I m not coding
Message 8 of 22 , Apr 18, 2009
> Submitted to OEIS:
>
> Numbers n such that 2^x + 3^y is never prime when max(x,y) = n
>
> 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578,
> 7251, 7406, 7642, 8218, 8331, 9475, 9578, 9749
>
> Mark Underwood found that for each non-negative integer n < 1421
> there is at least one prime of the form 2^m + 3^n or 2^n + 3^m
> with m not exceeding n.
>
> This sequence consists of numbers for which there is no
> such prime.
>
> David Broadhurst estimated that a fraction in excess of 1/800
> of the natural numbers belongs to this sequence and found
> 17 instances with n < 10^4.
>
> For each of the remaining 9983 non-negative integers n < 10^4,
> a prime or probable prime of the form 2^x + 3^y was found with
> max(x,y) = n.
>
> Each probable prime was subjected to a combination of
> strong Fermat and strong Lucas tests.
>

This form invites possibly the most bizarre, and remarkably efficient, sieve algorithm I've yet had the misfortune of considering. Good job I'm not coding currently... I'm going to be a tortured soul for at least 2 days until I forget about it.

Phil
• ... 1) Put this script in a file called loop.txt : SCRIPT DIM bot,1678 DIM top,1680 DIM aa DIM bb DIM nn DIMS st SET aa,bot-1 LABEL loopa SET aa,aa+1 IF aa
Message 9 of 22 , Apr 18, 2009
"Mark Underwood" <mark.underwood@> wrote:

> Wow, I am surprised you could go so high, so quickly. Very nice.

1) Put this script in a file called "loop.txt":

SCRIPT
DIM bot,1678
DIM top,1680
DIM aa
DIM bb
DIM nn
DIMS st
SET aa,bot-1
LABEL loopa
SET aa,aa+1
IF aa > top THEN END
SET bb,-1
LABEL loopb
SET bb,bb+1
IF bb <= aa THEN GOTO notyet
SETS st,OEIS:%d;aa
PRP 2^127-1,st
GOTO loopa
LABEL notyet
SET nn,3^aa+2^bb
SETS st,3^%d+2^%d;aa;bb
PRP nn,st
IF ISPRIME THEN GOTO loopa
SET nn,2^aa+3^bb
SETS st,2^%d+3^%d;aa;bb
PRP nn,st
IF ISPRIME THEN GOTO loopa
GOTO loopb

2) In any sane environment, issue this command:

nohup pfgw -f loop.txt > & /dev/null &

In an insane environment, try: pfgw -f loop.txt > nul

3) The output file "pfgw.log" should contain:

3^1678+2^47
OEIS:1679
2^1680+3^67

4) Now split up the job according as how many cores you
have available, adjusting "bot" and "top" in each script.

Thanks, Mark, for the stimulus to test the PNT heuristic.

David
• ... I have today uploaded a file containing the results of my search for all primes of this form for 2
Message 10 of 22 , May 7 8:29 AM
--- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:
>
> --- In primenumbers@yahoogroups.com, "j_chrtn" <j_chrtn@> wrote:
> >
> > --- In primenumbers@yahoogroups.com, "Maximilian Hasler" <maximilian.hasler@> wrote:
> > >
> > > Dear prime number fans,
> > > is there anything available about possible finiteness of primes of the form (x+1)^p-x^p ?
> > > Specifically, some curios reasons led me to look at 7^p-6^p.
> > > It seems that 1399 and 2027 are the largest known p for which this is prime (Sloane's A062573). According to my calculations, the next such p must be larger than 17900.
> > > Also, 2027 is (so far) the only such p of the form n^2+2, n>1.
> > >
> >
> > Hi Maximilian,
> >
> > p=1399 and 2027 are not the current records for base 7. My personal
> > records are p=69371 and p=86689 for 7^p-6^p. And the largest PRP I have found of this form is currently 8^336419-7^336419.
> >
> > Take a look at Henry Lifchitz's PRP records page
> > www.primenumbers.net/prptop/prptop.php for much more primes/PRP of this form.
> >
> > I believe that (1) for any integer n >= 1, there are infinitely many
> > primes p such that (n+1)^p-n^p is prime and that (2) for any prime p,
> > there are infinitely many integers n such that (n+1)^p-n^p is prime as
> > well.
> > But, unfortunately, proving (or disproving) (1) and (2) is far from being trivial I'm afraid.
> >
> > And now, just for fun, a litle challenge for you: find a prime p such that 138^p-137^p is prime or PRP.
> > Good luck ;-)
> >
> > JL
>
> I have done quite a lot of work on this form, initially summarised in my May 2001 post to the NMBRTHRY list:
> http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0105&L=NMBRTHRY&P=R359&I=-3
>
> Since then, Jean-Louis in particular has devoted seemingly enormous numbers of cpu cycles to extending the list of known PRPs.

I have today uploaded a file containing the results of my search for all primes of this form for 2<=b<=1000, 2<=p<10000, done in the years 2000-2008.

It is the file "b^p-(b-1)^p.txt", within the "Prime Tables" folder in the Files area of this site.

-Mike Oakes
• ... Here is a simple link to Mike s interesting table: http://tinyurl.com/d3nf9w David
Message 11 of 22 , May 7 12:10 PM
"Mike Oakes" <mikeoakes2@...> wrote:

> I have today uploaded a file containing the results of my search
> for all primes of this form for 2<=b<=1000, 2<=p<10000, done in
> the years 2000-2008.

Here is a simple link to Mike's interesting table:

http://tinyurl.com/d3nf9w

David
• ... (Thanks, Mike !) ... Thanks, David! (Remark: These tiny urls are nice, but can be quite annoying when they point to a website that re-arranged its
Message 12 of 22 , May 7 12:51 PM
> --- In primenumbers@yahoogroups.com, "Mike Oakes" wrote:
> > I have today uploaded a file containing the results of my search
> > for all primes of this form for 2<=b<=1000, 2<=p<10000, done in
> > the years 2000-2008.

(Thanks, Mike !)

> Here is a simple link to Mike's interesting table:
> http://tinyurl.com/d3nf9w

Thanks, David!
(Remark: These tiny urls are nice, but can be quite annoying when they point to a website that re-arranged its directory structure - with tinyurls ultra-efficient and discreet forwarding system you sometimes can't get the slightest info about where/what you had been pointed to and try to find it "by hand"...Â [this happened to me a few days ago - but I forgot where & what is was about...])

OTOH:

p=2 : A006254 Numbers n such that 2n-1 is prime.

p=3 : A002504 numbers such that 1+3x(x-1) is (a "cuban") prime.

p=5 : A121617 Nexus numbers of order 5 (or A022521[n-1] = n^5 - (n-1)^5) are primes.

p=7 : A121619 Nexus numbers of order 7 (A022523[n-1] = n^7 - (n-1)^7) are primes

p >= 11 seems not yet there, so Mike could enter his numbers into OEIS, starting there !

Maximilian, per proxy SOSR
(Society for On-line Sequence Recovery)
Your message has been successfully submitted and would be delivered to recipients shortly.