Upside Down Primes
 

The digits 0, 1, 2, 5, 6, 8, and 9 have a kind of collective symmetry
upon turning a decimal number 180 degrees (clockwise), with 0, 1, and 8
transforming to themselves, 2 and 5 also (using some imagination),
and 6 and 9 transforming into each other.

If a number and its upside down transform are both prime (and different),
like 19 and 61, or 109 and 601, these numbers are "partners".

Find as large a pair of partners as possible that contain all 7 of these
digits at least once. (I include the last condition because it might be
too easy to find a rep-unit or a form 10^n + 9).

Starting off with a pair of "small" ones:

1<97>25689<63>1 and 1<63>68952<97>1 are a pair of 167 digit partners. The part in <> is the number of zeroes.

EDIT:- 305 digit solutions: 1<271>25689<27>1 and 1<27>68952<271>1

EDIT2:- 404 digits: 1<344>25689<53>1 and 1<53>68952<344>1

Slight improvement with a different pattern set.

426 digits: 1<386>98652<33>1 and 1<33>25986<386>1

two better results

595 digits: 1<276>98652<312>1 and 1<312>25986<276>1
596 digits: 1<401>98652<188>1 and 1<188>25986<401>1

Excellent results, a few (hundred) digits longer than I anticipated.

May I ask: since so far your prime finds all have the same basic pattern
(start and end in 1, many 0's, and one splash of the other five digits
somewhere in the middle), is your algorithm to generate increasingly
large numbers with these patterns and then test for dual-primality? If so,
it should be only a little harder to find a pair that "look" more random,
say by not having any repeated adjacent digits. All those zeros make
the generating pattern evident.

Not that there's anything wrong with that. :smile:

[QUOTE=davar55;235707]May I ask: since so far your prime finds all have the same basic pattern
(start and end in 1, many 0's, and one splash of the other five digits
somewhere in the middle), is your algorithm to generate increasingly
large numbers with these patterns and then test for dual-primality? If so,
it should be only a little harder to find a pair that "look" more random,
say by not having any repeated adjacent digits. All those zeros make
the generating pattern evident. [/QUOTE]

Indeed. I chose the approach for it's automatability, and brain-dead-ness:smile: -- takes all of two lines of pari code. Not sure I want to go to the randomness route -- I would have to think about how to automate that.

And the first titanic partners:

1110 digits: 1<878>98652<225>1 and 1<225>25986<878>1

Just because I'm not as familiar with the tools as I should be,
are these proven primes or probable primes? How do you check
a basically random 1110 digit number for proven primality?
If it's just a pari feature, do you know how it does it?

Pari's not good at proving primes of that size.

1420 digits: 1<431>98652<982>1 and 1<982>25986<431>1

Searching is only prp tests. All the smaller ones were proven using PARI. For the largest one, I used PARI to prove one of them quickly (the one with more trailing zeroes). Currently running PRIMO on the other.

EDIT:- The other one was just proved by pari in 15 minutes using APR-CL. On to the 1420 digits.

Primo has also certified the 1110 digit prime. Pari has proven the 1420 digit prime in 40 mins. Primo is currently running on it.

Pari's APR-CL is amazing, it outperforms anything else on its good sizes. But I didn't know it was still competitive at 1400 digits!

[QUOTE=CRGreathouse;235827]Pari's APR-CL is amazing, it outperforms anything else on its good sizes. But I didn't know it was still competitive at 1400 digits![/QUOTE]

64-bit -- that's the ticket. I'm sure a 32-bit build would've taken much longer.

Anyway, Primo has also now certified the 1420 digit prime.

[QUOTE=axn;235830]64-bit -- that's the ticket. I'm sure a 32-bit build would've taken much longer.[/QUOTE]

Got it. So my Linux binary will be fast even with large APR-CL tests, while the Windows binary (which comes only in 32-bit AFAIK) will be slow beyond some low barrier.

A 100 digit "random" example:

[CODE]6251819008108609189596199559212521890205619120810821098260051085182656115590152280982625995812869989
6866982185665292860822510655119592815801500928601280180216195020681252126556619656816098018006181529[/CODE]

and a 200 digit:
[CODE]11656108198915696525808686856699860995699900519880802615918508880102012126101891982602512250191269051209601510191152210810162966052968585011015190121958951555916915818509269655021861561890611262206919
61690229211906819519812055969260581851691655515685612106151011058589625099629101801225116101510960215069216105221520928616810192121020108880581651920808861500666956609866995898980852596951686180195911[/CODE]

300 digit:
[CODE]681206522556696105560255589009822608069551286209568058596565581025808029021210162601009980212668818820221889092928996216598005918809826660609581920962290018259092068889820256561012528110052505616116098081191551221191518908162958802156895529826990666918511699105625125158908062285599269919892156859181
181658951268616692665582290806851521529501669115816999066928625568951208856291806815161122155161180860911919505250011825210195952028688890260652810062296026185609099928608816500865912966826260688122028818899212086600109291012120620808520185595965850895602982155690809228600685552095501969955225902189[/CODE]

a couple more
 

500 digits:

[CODE]10052026115582591061802080695802268610510028100118806262896990592998186618611122526956861850215805598921889929116150206909906005915690829210505115622281581565261586599125295521096169186992562652919112901682298521182560960669215265905265560558916559600289618968515219916121216619980126125520885915618265985090212085820620560960911526655980682226612128669989096508259980610286066815550559158921125918880895068209256668168518216058682652920501599199092518902666915586808292295085258962210056905925216081
18091252650695001229685258056226280898551699920681526066166510502625928985091281589189995260289056808881652112685165505551899098201908665280596068669982121992228908655992511609609502902858021206058659281951658802552192108661991212191661251589681968200965591685509559250659251269909609528112586228910621161625929526698169196012556252166598519259518518222951150501262806951650090660690205191162668812686550851205819895692522111981998186626506696829290881100182001501989220856908020819016528551192025001[/CODE]

1000 digits:

[CODE]1655501699065280182255110282821295595562195518096610005501868619581606899056108962552698966080208989521862218118562018016625988169256802281222901096900111528588565282099198968502255825822090068801919862092092518885950051966160925186892959895258092255195109868258256062662060115020828952600862608108518818202960590255260860218606269556209162811168900059269182629695219989860011285215581168912929052082581156025528850561952020609062891686629699086569016600989616061528526608851591552108168659191865050061088181502801560509168180891912559956508221811508608126569560292198009655219606069266619186665886211102508628229658585251126109908959122959900019569206011156526605256155891662596529962116829122129928182825199890002101850591658288696591112892959582562868000528950816806510116916106956580860185201858820850892290205021916086856855089052518291116206810001252066522058825966866929101915802886890552596192961888868209812829212198081506262266695580229956081659801598501121692685228661968205122595180691559
6551690815652215028961998225892691211058651086591809566220855699922929051808612126282186028988881962619652550689882085161016269989965288502259902521000189029111628152506805589589809161205020622680580288581025810980859569019169110159089180568250008982952856562682111659698828591650581012000686615282818266212216289112966259652991685519525099259511109026956100066562216568066019211525858596228298052011129885999816199926909096125596008612620956959218098051181228059566552161680818916050951082051818801900505981616598918012551651588099258251909196860099106959806696299891682906090202561950588255209511852802506262168911855125821100986866125696292816926500068911182916029556929098120980925520650962028188158018092980092568280205110902992909528528986015615522608525686562689815260919961500565888152602602986161088900602285285522058968616602825958858251110069601062221822089526918865299108102958118122981256868020809968692552968019506689091856198981055000199608155612955655621282820115522810825906691055591
[/CODE]

That last one took a while to find... probably will stop here.

These prime partnerable numbers depend on decimal digit properties.
Even so, they form a non-trivial sequence. I'd be curious to see what
the first 100 of these numbers look like. If someone wants to write
(I'm guessing) a one-liner?

1762 digits: 1<687>98652<1068>1 and 1<1068>25986<687>1

[QUOTE=axn;235932]1762 digits: 1<687>98652<1068>1 and 1<1068>25986<687>1[/QUOTE]

are you making a string reversing code I've tried but I can't get tit to work right now lol if i do maybe i can finally care about this.

[QUOTE=science_man_88;235935]are you making a string reversing code I've tried but I can't get tit to work right now lol if i do maybe i can finally care about this.[/QUOTE]

There's a GP script in [url=http://oeis.org/classic/A004086]A004086[/url]. The code I have in my script file is

[code]rev(n:int,B=10)={
my(m=n%B);
n\=B;
while(n>0,
m=m*B+n%B;
n\=B
);
m
};
addhelp(rev, "rev(n, {B=10}): Base-B digit reversal of n. Sloane's A004086.");[/code]

But I imagine the other code is faster, since mine is about as naive as could be.

[QUOTE=CRGreathouse;235941]There's a GP script in [url=http://oeis.org/classic/A004086]A004086[/url]. The code I have in my script file is

[code]rev(n:int,B=10)={
my(m=n%B);
n\=B;
while(n>0,
m=m*B+n%B;
n\=B
);
m
};
addhelp(rev, "rev(n, {B=10}): Base-B digit reversal of n. Sloane's A004086.");[/code]

But I imagine the other code is faster, since mine is about as naive as could be.[/QUOTE]

see my first idea was to invert a vector of some kind but I bet that's slow as well.

[QUOTE=science_man_88;235935]are you making a string reversing code I've tried but I can't get [U][I]tit [/I][/U]to work right now lol if i do maybe i can finally care about this.[/QUOTE]

please edit this out lol

[QUOTE=science_man_88;235945]see my first idea was to invert a vector of some kind but I bet that's slow as well.[/QUOTE]

Probably, especially since I don't know of a fast way to re-join it.

[QUOTE=CRGreathouse;235947]Probably, especially since I don't know of a fast way to re-join it.[/QUOTE]

I was thinking of just inverting the index but that overwrites half the indexes improperly lol

[CODE]v=vector(input());a=#v;forstep(i=a,1,-1,v=concat(v,v[i]));[/CODE]

this might work with you vector shift code on the end to shift out the first a values.

and i may change it to Vec to allow the <93> stuff then the hard part is making a code to convert the strings into individual or groups of digits to test the primality.

[B][U]NOTE[/U][/B]:this was not my original code.

That would be extremely slow. Here's the right way of doing that:

[code]rev(n)={
my(v=eval(Vec(Str(n))),u=vector(#v,i,v[#v+1-i]));
sum(i=0,#u-1,u[#u-i]*10^i)
};[/code]

My code (last post) takes 4.17 seconds to reverse the numbers from 1 to a million; this code takes 9.2 seconds. Both can be improved substantially, but I would rather start from that one than this.

True story
 

[QUOTE=davar55;235544]The digits 0, 1, 2, 5, 6, 8, and 9 have a kind of collective symmetry
upon turning a decimal number 180 degrees (clockwise), with 0, 1, and 8
transforming to themselves, 2 and 5 also (using some imagination),
and 6 and 9 transforming into each other.

If a number and its upside down transform are both prime (and different),
like 19 and 61, or 109 and 601, these numbers are "partners".

Find as large a pair of partners as possible that contain all 7 of these
digits at least once. (I include the last condition because it might be
too easy to find a rep-unit or a form 10^n + 9).[/QUOTE]

The other day, my front door was repainted. I opted for Oxford blue.
The painter jested that the whole estate would end up looking like
a Butlin's holiday camp. He needed to unscrew the number 19 from
the door, and we jested about the four different ways they might get
reinstated.
The numbers sat outside for a few days until some well-meaning
person screwed them back on.
I now live at number16.

David

[URL="http://www.youtube.com/watch?v=Hr97qzUVdgE"]You're Sixteen[/URL]

[QUOTE=science_man_88;235935]are you making a string reversing code I've tried but I can't get tit to work right now lol if i do maybe i can finally care about this.[/QUOTE]

String reversal is not enough. We're talking about string "rotation". And no, I don't do string reversal/rotation -- instead I've chosen patterns that gives me matched pairs directly.

[QUOTE=science_man_88;235935]are you making a string reversing code I've tried but I can't get tit to work right now lol if i do maybe i can finally care about this.[/QUOTE]

As others have said, you need rotation, not reversal. I do it with a vector of bytes:

[CODE]void rotVec(char *vecin, char *vecout, int num)
{
int i;

for (i=0; i<num; i++)
{
switch (vecin[i])
{
case 0:
case 1:
case 8:
case 2:
case 5:
vecout[num-i-1] = vecin[i];
break;
case 6:
vecout[num-i-1] = 9;
break;
case 9:
vecout[num-i-1] = 6;
break;
}
}


return;
}[/CODE]

Extremely straightforward... but effective enough. It can rotate a vector of 10 million entries in 50 milliseconds or so, but of course I never need to rotate anything that big.

1268*10^3605+8951 and 1268*10^3605+8951 ? :rolleyes:

Yeah, ok, you want different. Let's search for these now.

[QUOTE=Batalov;236029]1268*10^3605+8951 and 1268*10^3605+8951 ? :rolleyes:

Yeah, ok, you want different. Let's search for these now.[/QUOTE]

it must be a A002385 because you list the same number twice hence it's the same backwards and forwards.

[quote=science_man_88;236065]it must be a A002385 because you list the same number twice hence it's the same backwards and forwards.[/quote]

I really specified the OP to make this an interesting and solvable puzzle.

This last result is a perfect extension, and would make a nice sequence too.

Anyone want to work on the first 100 integers in those two sequences?

The OP defined upside down partnered primes.
The example of a big one that partnered itself
was an add-on to the original puzzle, and the
sequence of these would be another related
new sequence.

If anyone would compute, say, the first 100 terms
of each of these sequences, it might be interesting.
We already have some big ones.

Just learned that M1061 has been factored, as P1 x P2 (two prime factors).

Since 1061 and 1901 are prime upside-down partners ,
I ran factorbd on 2^1901-1 and found a P501 as largest factor.

I think it computed rather than did a lookup.

Is this P501 previously unrecorded? Just thought I'd ask.

[QUOTE=davar55;306967]Just learned that M1061 has been factored, as P1 x P2 (two prime factors).

Since 1061 and 1901 are prime upside-down partners ,
I ran factorbd on 2^1901-1 and found a P501 as largest factor.

I think it computed rather than did a lookup.

Is this P501 previously unrecorded? Just thought I'd ask.[/QUOTE]

That 501 is not prime. Black numbers are prime, red are unknown, red/brown are probably prime, and blue is known composite. The [URL="http://factordb.com/index.php?id=1100000000216805652"]C501[/URL] has been in the database since before March 2011. (Follow the link and click on more info.) Edit: If you click more info on M1901 itself, it has the same entry-creation date, which is probably a date the DB underwent maintenance or something. GIMPS has probably gotten the ECM up to t60 or beyond, so there's little hope of factoring it anytime in the near future.

[QUOTE=Dubslow;306970]That 501 is not prime. Black numbers are prime, red are unknown, red/brown are probably prime, and blue is known composite. The [URL="http://factordb.com/index.php?id=1100000000216805652"]C501[/URL] has been in the database since before March 2011. (Follow the link and click on more info.) Edit: If you click more info on M1901 itself, it has the same entry-creation date, which is probably a date the DB underwent maintenance or something. GIMPS has probably gotten the ECM up to [B]t60[/B] or
beyond, so there's little hope of factoring it anytime in the near future.[/QUOTE]

Thanks. What does t60 mean, to ECM?

Thought I had lucked onto a big special form prime. Not this time.

[QUOTE=davar55;306978]Thanks. What does t60 mean, to ECM?

Thought I had lucked onto a big special form prime. Not this time.[/QUOTE]

txx is a commonly used term to mean enough ECM has been run up that it's 1-[URL="http://www.wolframalpha.com/input/?i=exp(-1)&t=crmtb01"]exp(-1)=~%67[/URL] likely that there's no factor less than xx digits. Less commonly seen is something like 2t60, meaning there's a [URL="http://www.wolframalpha.com/input/?i=exp%28-2%29"]exp(-2)[/URL]~=13.5% chance of having missed a 60 digit factor.

From [URL="http://www.mersenneforum.org/forumdisplay.php?f=96"]YAFU[/URL]'s docfile:
[quote]------------
T-levels
------------

A note on the "t-level" terminology used in factor(). Something that has
received, say, "t30", has had enough ecm curves run on it so that the probability
that a factor of size 30 has been missed is exp(-1) (about 37%). Likewise,
t35 indicates that factors of size 35 are expected to be missed about 37%
of the time (at which point a 30 digit factor would only be expected to be
missed ~5% of the time). t-levels are calculated from tabulated data extracted
by A. Schindel from GMP-ECM in verbose mode. See also the GMP-ECM README file.[/quote]

Looking at PrimeNet's [URL="http://mersenne.org/report_ECM/"]ECM Progress[/URL], M1901 has been taken to t50, and has around 17% of the necessary work to get to t55.

1 - exp(-1) =~ 0.63 = 63%