Of Reversible Primes

davar55 · 2008-06-03, 18:27

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.)

bsquared · 2008-06-03, 19:17

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!

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.

bsquared · 2008-06-03, 20:15

Quote:

Originally Posted by bsquared

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

- ben.

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.

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?

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

- ben.

davar55 · 2008-06-03, 21:31

Quote:

Originally Posted by bsquared

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?

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.

bsquared · 2008-06-03, 22:14

Quote:

Originally Posted by davar55

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.

Sorry, missed that

. 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.

fivemack · 2008-06-05, 10:58

Code:

2800581281*1821850082 = 2258813679^2 - 1

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

bsquared · 2008-06-05, 13:49

Quote:

Originally Posted by fivemack

Code:

2800581281*1821850082 = 2258813679^2 - 1

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

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...

retina · 2008-06-05, 14:06

Quote:

Originally Posted by davar55

... prime p (with prime digit reversal p')...

Must we assume decimal? Are other bases considered?

davar55 · 2008-06-05, 17:50

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?

bsquared · 2008-06-05, 21:18

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

bsquared · 2008-06-05, 21:40

Quote:

Originally Posted by davar55

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?

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.

2008-06-03, 18:27	#1
davar55 May 2004 New York City 5·7·11² Posts	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.)

2008-06-03, 19:17	#2
bsquared "Ben" Feb 2007 7·503 Posts	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! So p = 41 gives 4114 = 24^2 - 2 and p = 33029 gives 3302992033 = 55134^2 + 1 I'll extend this up to p < 2^32 here in a sec... - ben.

2008-06-05, 10:58	#6
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6424₁₀ Posts	Code: 2800581281*1821850082 = 2258813679^2 - 1 no it doesn't, the product is 2258813679^2+1

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Mersenne Primes p which are in a set of twin primes is finite?	carpetpool	Miscellaneous Math	3	2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found	emily	Math	34	2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2	Mickey1	Miscellaneous Math	1	2013-05-30 12:32
A conjecture about Mersenne primes and non-primes	Unregistered	Information & Answers	0	2011-01-31 15:41
possible primes (real primes & poss.prime products)	troels munkner	Miscellaneous Math	4	2006-06-02 08:35

2008-06-05, 17:50	#9
davar55 May 2004 New York City 10213₈ Posts	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?

2008-06-05, 21:18	#10
bsquared "Ben" Feb 2007 110111000001₂ Posts	All p < 100e9, nothing new. Extending it that far took a couple hours of run time after some improvements to the code.