sequence of Zak Seidov needs extending

[Alex Healy]

> Alex, I wonder how did you get this far. Did you use advanced 
> methods (like the Meissel-Lehmer method) to compute pi(x) or 
> nthprime(x)?

I used Mathematica, which fortunately has some sophisticated pi(x) routines
built-in.  The implementation notes say that the Lagarias-Miller-Odlyzko
algorithm (an improvement on the Meissel-Lehmer Algorithm that I once knew
in some detail, but never dared implement myself) is used for large x's.
Naturally, nthPrime() is computed by "inverting pi(x)", presumably by binary
search after a good guess based on known asymptotics of these functions.
Thankfully, Mathematica also takes care of that for me too.

In any case, the rough structure of my (very simple) program is:

Loop over palindromes k
	If k is prime, then check if nthPrime(k) is a palindrome

I chose this ordering based on the same kind of heuristics that you mention
in your last email (e.g. a "random" number is much less likely to be a
palindrome than prime) together with the fact that it's easier to generate
palindromes in order than primes (even with non-trivial routines for the
latter).

Alex


> Alex Healy wrote:
> > I also threw together a quick program for this, and can't 
> seem to find 
> > any other terms less than (2.5)*10^12.  (That's just where 
> my program 
> > was when I woke up this morning.)
> > 
> > For what it's worth, the first four terms of the same sequence in 
> > binary (i.e. requiring that the primes be palindromic in 
> base two) are:
> > 
> > 5, 17, 127, 296713
> > 
> > and there don't seem to be any others less than 10^11.
> > 
> > Alex
> > 
> > 
> >>-----Original Message-----
> >>From: Jud McCranie [mailto:j.mccranie at adelphia.net]
> >>Sent: Thursday, February 03, 2005 12:52 AM
> >>To: njas at research.att.com
> >>Cc: seqfan at ext.jussieu.fr; zakseidov at yahoo.com
> >>Subject: Re: sequence of Zak Seidov needs extending
> >>
> >>At 11:00 PM 2/2/2005, N. J. A. Sloane wrote:
> >>
> >>>Dear Seqfans, Zak submitted this, but I can't use it without
> >>
> >>at least
> >>
> >>>one more term. Can anyone extend it?
> >>>
> >>>
> >>>%I A103359
> >>>%S A103359 3,5,11
> >>>%N A103359 Prime palindromic n such that pi(n) [A000720] is
> >>
> >>prime palindromic.
> >>
> >>>%C A103359 No further terms with n less than 3000000. 
> >>
> >>Palindromic pi(n)
> >>
> >>>of palindromic n A103357,A103358.
> >>>%e A103359 pi(3)=2, pi(5)=3,pi(11)=5
> >>>%Y A103359 Cf. A103357, A103358.
> >>>%O A103359 0,1
> >>>%K A103359 more,nonn,base,bref
> >>>%A A103359 Zak Seidov (zakseidov(AT)yahoo.com), Feb 02 2005
> >>
> >>My quick and dirty program doesn't find any more terms < 10^10.  
> >>Tomorrow I can modify it to go higher.
> >>
> >>More terms are going to be hard to find.
> >>
> >>pi(143787341) =  8114118, a palindrome, but not prime - is 
> the closest 
> >>I've found. (143787341 is a palindromic prime).
> >>
> >>You might have to relax the condition that pi(n) be a 
> prime, and just 
> >>require it to be palindromic, while n is a palindromic prime.
> >>
> >>
> > 
> > 
> > 
> >