Problems & Puzzles:
R(p) is n^n.
In one of the the Prime Curios!
pages from Caldwell & Honaker, Jr. I found this
question, by Kulsha:
The reversal of
61277761 is 88. There should be infinitely many primes of
Q. Find the next
cases to R(p)=n^n.
R(n) means here
"reverse of n"
Contributions came from Giovanni Resta, Farideh Firoozbakht, Jeff Ellen,
W. Edwin Clark, J. K. Andersen, Thomas Ritschel, Dan Dima & Emmanuel
Tthe next prime of the form R(n^n) is R(5569^5569), a prime of 20861
digits. I obtained this result many years ago, so I do not remember
the boundary of my search. [has it been published?] I did not.[Prime
or PSP?] Just a probable prime (according to Mathematica
"Mathematica first tests for divisibility using small primes, then
uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and
then uses a Lucas test." The number has not a "form" that allows a
fast certification, and I'm not up-to-date in the game of proving
primality of large numbers.
b.t.w. No other solutions up to 16800.
5569 is the smallest prime p such that reversal(p^p) is prime
For puzzle 653 I have checked up to n=412 with no prime found. When
n=413 I get an overflow in UBasic.
W. E. Clark wrote:
It turns out that the next
value of n such that R(n^n) is (a probable) prime is 5569 and
was found by Farideh Firoozbakht in June 2010 see http://oeis.org/A178329
I checked all n up to 11100 and found only the two values n = 8 and
n = 5569
such that R(n^n) is prime.
I used Maple 16's probabilistic primality test isprime to check
the primality of R(5569^5569). This is a 20861 digit number and
it took 31 minutes to return true.
J. K. Andersen wrote:
The only other solution for n up to 25000 is a 20861-digit probable
R(9290666754...4901031171) = 5569^5569
I found it with PrimeForm/GW but http://oeis.org/A178329 shows
Farideh Firoozbakht already reported it in 2010.
I've tested all n<=6000
using a combination of a simple Pari script (for doing the
reversal) and PFGW.
The next case is found for
p=9290666...1031171 = R(5569^5569), having 20861 decimal
Meanwhile I extended my
search up to n=43200, e.g. numbers of about 200,000 decimal
digits. Since doing the reversal in Pari was too demanding I
modified the procedure to generating n^n in Pari, doing a simple
string reversal in Perl and trial factoring and PRP testing with
n's which are multiples of 3
or 10 were already discarded in the "Pari" stage.
And before the reversal the
Perl script checked for numbers starting with an even digit (or
"5"), for which the reverse would have trivial factors 2 (or 5).
All remaining candidates
were fed into PFGW.
During this extended search
I found another PRP which qualifies for the next member of the
= 9290666...4681311 (having 155815 decimal digits). It's found
to be Fermat and Lucas PRP, but is obviously too large for a
genuine primality test. Yes, appart from the default PRP test I
ran an additional "-tc" test in PFGW:
9290666...4681311 is 3-PRP!
9290666...4681311 is Fermat
and Lucas PRP! (14745.1088s+10.0309s)
There is no other such
solution for n <= 5569
5569^5569 has already 20,861
digits and it is a lot of time consuming
to test primality for larger
values with Pari code.
composite for all n such
that 8 < n < 5663.
I aborted the computation because, for bigger n the
eventual primality of R(n^n) will
be too hard to prove.
One day later, he added:
Afterwards, seeing the results of the other puzzlers, I went to
reread my results, I realized that I did not noticed that the
solution 5569 was an output of my search (done with Mathematica).
Anyhow, there is no further solution up to 5663.
About Thomas' result : Mathematica found R(34351^34351) prime after
more than 28 hours