Of Reversible Primes
 

Find reversible prime p (with prime digit reversal p')
such that p*p' = n^2 +/- d for d = 1 or 2 (and integer n).

(I don't know how easy or hard this is.)

A quick program to check all possibilities up to p < 65536 gave two results:

[code]
41,14,574,575,576... is square!
33029,92033,3039757957,3039757958,3039757959,3039757956... is square!

[/code]

So p = 41 gives 41*14 = 24^2 - 2
and p = 33029 gives 33029*92033 = 55134^2 + 1

I'll extend this up to p < 2^32 here in a sec...

- ben.

[quote=bsquared;135097]

I'll extend this up to p < 2^32 here in a sec...

- ben.[/quote]

For all primes p < 4e9, I only found one more unique result...

[code]
Tue Jun 03 2008 15:07:04 v0.9.14, Initializing (x86-64 asm)...
Tue Jun 03 2008 15:07:04 v0.9.14, cached 664581 primes. pmax = 10000079
>> Welcome to YAFU (Yet Another Factoring Utility)
>> Type help at any time, or quit to quit
>> puzzle(4000000000)
41*14 = 24^2 - 2
33029*92033 = 55134^2 + 1
92033*33029 = 55134^2 + 1
2086361*1636802 = 1847961^2 + 1
Elapsed time = 316.8500 seconds.

[/code]
For an even harder problem, add the restriction that p and p' *both* be prime! The first one is shown... how big will the next one be? :smile:

Clearly, something other than brute force would be necessary to extend this much further, but I haven't come up with a simpler way.

[edit] just found a bug in my code... stay tuned.
[edit2] bug fixed, found one more:

[code]
2800581281*1821850082 = 2258813679^2 - 1
[/code]

- ben.

[quote=bsquared;135099]For an even harder problem, add the restriction that p and p' *both* be prime! The first one is shown... how big will the next one be? :smile:
[/quote]

That both p and p' should be prime (for p to be a 'reversible prime')
is what the problem intended (any number can be reversed, of course).
So you're solving the more general problem.

Also, the OP was asking for a solution for each of the four cases: +/- 1,2.
So I think you've shown there aren't any small ones for the other cases.

[quote=davar55;135104]That both p and p' should be prime (for p to be a 'reversible prime')
is what the problem intended (any number can be reversed, of course).
So you're solving the more general problem.

Also, the OP was asking for a solution for each of the four cases: +/- 1,2.
So I think you've shown there aren't any small ones for the other cases.[/quote]

Sorry, missed that :blush:. I took p to be prime but p' doesn't have to be.

I checked for each of the four cases for each prime p, so yes assuming the code is correct then there aren't any small ones for +2.

I just made my isSquare routine faster. The "All p < 4e9" test is now 4x faster. So thanks, davar55, for giving me an excuse to drag my code back out and improve it!

- ben.

[code]
2800581281*1821850082 = 2258813679^2 - 1
[/code]

no it doesn't, the product is 2258813679^2+1

[quote=fivemack;135213][code]
2800581281*1821850082 = 2258813679^2 - 1
[/code]

no it doesn't, the product is 2258813679^2+1[/quote]

Right you are, of course. Thanks for the doublecheck, and bugfix (simple printing error). I'm improving my sieve now, so that I can check to slightly higher bounds...

[QUOTE=davar55;135094]... prime p (with prime digit reversal p')...[/QUOTE]Must we assume decimal? Are other bases considered?

Finding primes reversible in other bases that have the desired property
is a reasonable extension of the problem beyond what was intended.
Is it likely that every base even has such solutions?

All p < 100e9, nothing new. Extending it that far took a couple hours of run time after some improvements to the code.

[quote=davar55;135247]Finding primes reversible in other bases that have the desired property
is a reasonable extension of the problem beyond what was intended.
Is it likely that every base even has such solutions?[/quote]

in hex, I get 3 results, all reversible, all of the -2 variant, p < 4e9
in octal, I get 4 results, none reversible, all of the +1 variant, p < 4e9

other bases are not as straightforward... I need to go write a general base conversion utility, I guess.