Problems & Puzzles: Puzzles

Puzzle 888. Prime-Squares

               To Harvey Heinz, In memoriam
 31st of August 1930- 6th of July 2013Ü

For sure you know the popular "word squares".

Here you have some examples in English, given in the "Word Squares" entry from the Wikipedia, for orders L=3 to L=8

Using only the standard words of this language, no solution is known for order L=10. This unsolved problem is known as the Holy Grail of logology.

Please notice that in these kind of squares the word of the i-th row is the same than the word of the i-th column.

Also please notice that the main positive diagonal (/) is necessarily a palindrome sequence of letters, no matter if this sequence is not a standard word.

The existence of the unsolved case for order L=10, is due to the little quantity of words composed by 10 or more letters. This is the case of all the natural languages of the world.

But what if we change to integers 0-9 in the cells of the square and ask for primes in each row and column when read from left to right and from up to down, respectively?

Due to the fact that there are more and more primes as L is increased (the opposite occurs with natural languages), is a kind of easy to get larger solutions with primes than with words of natural languages.

Here is a solution for L=79 gotten by me in less that 45 minutes using a simple code in Ubasic:

2526043551786910676189409087562603654055976928332256857447552489694009021952149
5581044595329599084501813374228355867564396811953353749155393365974172433190583
2818727506754099169366316843440437712746536652775019276379598680357165021873027
6186441215575809638996476941007947043027704075391184421215871307944874793006651
0074751088583382646488247558541630050094402591238120326762935602180983262269279
4424503729172189224384738241640601874468249434232063446747378721793807636940153
3471134379623282189907958544645657943991652346973621543786460750840695509153863
5552073607443816339945576200941410635524969690169416130679466578432803620533673
5901827015372228513890983886924865934729712539899399524049473523572565801843339
1565899758197925551240363513579107318458537850036118922420504205780302262558241
7375516431859183122187701886246868914601795701863716765351735040367168177426459
8257872479586071274251519035267187403453724488646854813880423317409029696292211
6945323327965991191195359133364216531493381665251038476824257009063399865978337
9508312829109934558161167587254688588257691130415873592910496094835572963816907
1990888122879380247981450878182573839437801630095808631977656576928638724912959
0999292685311408224642740919172074187023275243888510627535505945423422620038459
6016621355121522907681575290856993441994038838991456575257677584027314694456987
7863428315279542025209943224370363597257552216464891723578901109208438024154337
6498649931241874751082236704616693820516235580429886369492566157421174488254479
1539439982121196620759235097568784944717053805086535523873795010674065788302433
8069880494859684808532266804393937013091700124295191438604629634748445024265211
9166847500715112192924983022326352065338239698223526688080868444413213095911843
4834279593753147592229482271795684736498771502554463461969890359777124077202603
0117435786015654743368849629638812549436333327389925031715677368012172414793009
9366788633199700536563295305051094160861820260428033851705864199991484345761547
0389525285801589227080263702852159346797702247349314059078176308042296573153409
8744544081833871920902720002899663591181425098732574782697404428429646529838319
7431814063653789044742195226973269990246817121640054606507341550229570271511733
5240566995223211836533760889032170407405829273658613940981792831963442623206837
6240444427466587571692935597369092692500022721596149601517908241789147973795791
2807105149674422606836581293291532011811426531543162907728560283361139410095569
6349666481812650936793680162105660405824541473510871360149410374298608147798787
0534305160681877969835819566793665456955002276498575683688286137236052853951897
3577017057876834333472424939022053232876330810998503019105834628635692882302611
6870089693945581458900751359460442275862298534766623288771115784433134915350769
5614574331103838492416346499091053700740125026078941619281484491245432742115399
4723043548431897170435690610721562502335432564913337585960943497299883361788301
0570049574644240925703448712458898873493131258915641952243319250750942967420911
5642969225059532951193936984001257643939797778075960481560773706294167795867313
5467481498133773476718861716501456205395430656136564168748064390244955109981571
9357426975773682052072738748804503214174498334794178927231130713029508286815131
7930045613928907353503732021222403923393943812102423681550213478084146274647083
6664292927541115825309130257926120852170830113492434082543702551028057714488917
9860543658746162825816532201275428505276381346290489763625988835058736018467853
2157934935086334318029026492723771326575311477594826448202964218856969570768219
8125146090185003860548270781311360464886423675601367352561529378040497059840283
3973229180862408944022534376655549709901714256227511012202161752874701405611599
3579337693645198962892582434594199671173909990234686460466868595600422066166083
2351823996361558149653498920863088683556422041746137614820499468959962127192151
2301106431780885488515490350611855693695144483561488562079103377528157149298063
5518262191153701598392623175146770243466723826183880723103291507619805659595321
6394031698648380616516353444392153317104834967167803334816371561737633889998469
8724345159784566573546408076969360265941960743046573363394410819883543744398111
5472244322617932726238635580400681818586288645161623678839865586551931107772709
7961663042536217539388111926017039895218712382204234381153428428972586360632017
4132777604388995254860977065957161729257255625248018381861018207701513838091601
4571648742582173579708610790812480786464354206062701935645468075233046926701723
7595276990104075782340955877178985110308103521260936493157539028779056334022001
5358934445742465695768868143795428149370127995184123484045058023205261794735563
5997376670325950706926976704906183184176310862669097162163515174608953478821361
2381580634537665716598074641280064543934032849189311058889851774747972118734077
4363677552030059511064331345822316744273745823754355854200017823973889004675263
8680025720410974805134569025348732899509175317596706182072277259692552844100131
9507210835079465497044989880113478417060381588258771968758344391220960400664961
6939178457340894024674709042973226422722000080869567859727267962524226895353489
9754894378606322202741719422686933349594282554705213857037004792221211177927687
4474030220793583781483721299391865359044948860409897312139587320418713426949801
0118986853103564341042114265411606148919510794749186595500299859227346370047563
0767809060629732137641278947443059338465045369026503438145657856211480106037629
9254375352899282484553424660279822423275867697122753316366132920613603338872589
0407265682168976604700043552694188973971227050401168713893741084814313538065851
2329630206796622928829714727271458146690871175062458406323971040972703342511757
1313269012765340448845745391330732521759644809567999470864488440576068823792427
9180291585429890412329277185270793317489864478611259376070787616399008057604633
5970645345297113555061096531099950518268148664169999973902323706524437619074601
2036903338628628644251231381655812058071578780162858822112514504379772512443323
1506218632423994934428605437875786733935109822501034170670530219468565874663681
4825756734513055837314004013396891690117381518985626101020667636880628552302843
9371933391917799779313397993719771991131137393931319197131317311971399177313137

Let's add two more conditions: the two main diagonals, when read from up to down must be primes too. Here is an example for L=41, obtained in around 7 hours:

08032103647457890844269732073931462629747
87283267601799164363773035829429208896033
02383186676404307787556780386505323110779
38889085333448283909548996135556839660153
23395359127657414969922887338790740941287
12103079401697708960526541920016705667299
06885768497734995512259056123600112259607
37659986184340185083056613550870575026973
66631441499907665195236783579266055141361
40732098988971896062462335572782883962903
71637174983706344455905432418260764028169
47446673997256010103082657749179615564279
59045934070500921012476402658074535129493
79487740716607767174185607572852258539909
81324791683097663203267677108290799945139
96081098694126667341419684895472595895749
04734855564017379216599067075802785895703
83799950104101232585287051146522008733057
46806618965017041867931975945283062958851
43799023525324316575135963023347634852131
27559520249041245291173606745788147775019
67542255360878619833752749198484204886041
93682696625265799715326491103962035743997
70798506734646660099674717861400863530511
33898451833500786576049123076712582164887
25067163352727747153691735505689680768123
08313915554765180190711805061240175775553
72833225771457097442490670603343768392343
39658030928982855653583165138990162135689
94557068272108248523749476239019467839691
32059107686775970284886018449129593785171
19560600620942022237842029030992567126121
42387715087652757006120856171455074664797
60234017586135998063403688766696704740169
28390525534558955824745320582737444246649
68169620190515988798787517731871672620733
29164652462623499355784366793382644232677
96001796128499555382563048525956406022631
70712269391249177081009581536611716766351
43758907606790340553149182548972964373547
73937973139939993711917173339111799371171

07385066483207669565156725008022004632341
73704627026187146013131064178162072640737

Please observe again that the main (/) positive diagonal is necessarily a palprime.

Q1. Send your largest solution if all the primes involved must be emirps, the negative (\) main diagonals included (the positive (/) main diagonal is a palprime, as said before)

Q2. Send your largest solution if all the primes involved must be palindromes, the two main diagonals included.

 

Contributions came from Emmanuel Vantieghem and Jan van Delden

***

Emmanuel wrote:

Q1.
Contrary to my intuition, this is much more difficult.
It took about 1.5 hours to get the following 27x27 solution :
933913793317199119911111193
313719991997799773319311993
331713991397193197791199977
977911399977117317113771177
111119737777793199131331911
393191711731311313773913393
799377313177191179313319733
999931131991391999339373119
311971319993939717939713937
393977199177313133139973711
199773799731991377199371139
777771713719333319397339139
171173139393339191731137113
999191993193393177993171319
993731119313937311991319991
171313197133113939171333173
179191791371971319779977731
937793997379171997791139717
937117339113799177333993997
119137133399399779337199973
191313399997131191371133117
131739337933113391911025723
119731171773371373993279209
119113933319719379393591279
199193719711139177991722029
997719313133119731971207203
337713397199391317737399939

 
The main diagonal is : 911911339139397917331071009
The other one is : 399139339373999373933931993.

Q2.

This was the easiest job.
I found a 101x101  example in a few minutes: 
17717331191917733733797117999737979997799131391377777319313199779997973799971179733733771919113371771
70327800180797592799653667586313999138614474099542624599047441683199931368576635699729579708100872307
73789422955815570579397018972218414294756269065968586956096265749241481227981079397507551855922498737
12830597975043709870221336810574132716525603931640404613930652561723147501863312207890734057979503821
77904197714941342614535372543980477794838063076299299267036083849777408934527353541624314941779140977
38451217969973360111517599812773633157964783206703430760238746975133637721899571511106337996971215483
30299133256232608807410521789460312945370523704196969140732507354921306498712501470880623265233199203
10277739741885325653581963751263829971338190714965356941709183317992836215736918535652358814793777201
11997927801948659933607628101186844189071572907540704570927517098144868110182670633995684910872979911
98571654093717496192439818204482340124950175097418681479057105942104328440281893429169471739045617589
10554961131980620217832757570153677193333490199780508799109433339177635107575723871202608913116945501
97809928979860953338672625578801078526107174043989998934047170162587010887552627683335906897982990879
19144738418666039222261528625902464324257693976492929467939675242346420952682516222293066681483744191
77531325870063446147748755968726037386129067085980008958076092168373062786955784774164436007852313577
75573363646904442159533557703557897381732415735254845253751423718379875530775533595124440964636337557
39704602592534407141641592439050251262162582255937973955228526126215205093429514614170443529520640793
32092085960396275651837751394869391316592228174346164347182229561319396849315773815657269306958029023
77586186912321116477371824571585761019137553694821612849635573191016758517542817377461112321968168577
39771105391324545780760355853629423292302552143549694534125520329232492635855306708754542319350117793
39904173327827911703551208827273898819903165650673437605656130991889837272880215530711972872337140993
76325545648627568375549307611236309878374407118333133381170447387890363211670394557386572684654552367
95923118033764343765416720520826288700010563386445354468336501000788262802502761456734346733081132959
73715701792218317101961787103620107294863524121603630612142536849270102630178716910171381229710751737
16033559687657557832377047965956376562731898941259295214989813726567365956974077323875575678695533061
16137926215225595250028443825773432621823088164760506746188032812623437752834482005259552251262973161
77862913887585721458707738115150955127447587139650505693178574472155905151183770785412758578831926877
95985877125569743588651981268778558505477317292392229329271377450585587786218915688534796552177858959
98714185007726039752120621699187202135929630733802620833703692953120278199612602125793062770058141789
96203291140858394137103555890040053311778880959992829995908887711335004009855530173149385804119230269
73259742141897508562286971710392056193416107696119791169670161439165029301717968226580579814124795237
31178766885002556827322575784936747103939777444452125444477793930174763948757522372865520058866787113
73840303623126709593660630870263910007008301487926862978410380070001936207803606639590762132630304837
99414638836040823748321349520079865434171316469794949796461317143456897002594312384732804063883641499
79137312447763959629080735505541662871672205270243034207250227617826614550553708092695936774421373197
99427329407847711138987625823670523929767579298453435489297576792932507632852678983111774870492372499
91277199111533323028872561513110489815111947774323832347774911151898401131516527882032333511199177219
93919547829228861191709622031900372113021057846850305864875012031127300913022690719116882292874591939
78464751943646126929804217551337419536985646543490209434564658963591473315571240892962164634915746487
76758933093121715139308784497490167109845751964061116046915754890176109479448780393151712139033985767
91523673753052369300716324727130776128496013095164246159031069482167703172742361700396325035737632519
94658408103779222723403137798698127115566804610862326801640866551172189689773130432722297730180485649
14260751514160452551455805368173325906708229063986268936092280760952337186350855415525406141515706241
37606829779796182556062988138070107454510212736673337663721201545470107083188926065528169797792860673
14933330250437528325734887700771659776134925136279597263152943167795617700778843752382573405203333941
30090277901090721616131911279644422785906071733425252433717060958722444697211913161612709010977209003
99637001099478357945182463935948679744691633317058885071333619644797684953936428154975387499010073699
19516644779365554430861149239647908463450366370017971007366305436480974693294116803445556397744661591
35962719547949293856346276389149724384018962400731913700426981048342794198367264365839294974591726953
74649096418898534247340565909152945259666877251376267315277866695254925190956504374243589881469094647
72809365080920476193353900222926433300142639587169496178593624100333462922200935339167402908056390827
76542493765990891664136255268718904832123235289924142998253232123840981786255263146619809956739424567
72809365080920476193353900222926433300142639587169496178593624100333462922200935339167402908056390827
74649096418898534247340565909152945259666877251376267315277866695254925190956504374243589881469094647
35962719547949293856346276389149724384018962400731913700426981048342794198367264365839294974591726953
19516644779365554430861149239647908463450366370017971007366305436480974693294116803445556397744661591
99637001099478357945182463935948679744691633317058885071333619644797684953936428154975387499010073699
30090277901090721616131911279644422785906071733425252433717060958722444697211913161612709010977209003
14933330250437528325734887700771659776134925136279597263152943167795617700778843752382573405203333941
37606829779796182556062988138070107454510212736673337663721201545470107083188926065528169797792860673
14260751514160452551455805368173325906708229063986268936092280760952337186350855415525406141515706241
94658408103779222723403137798698127115566804610862326801640866551172189689773130432722297730180485649
91523673753052369300716324727130776128496013095164246159031069482167703172742361700396325035737632519
76758933093121715139308784497490167109845751964061116046915754890176109479448780393151712139033985767
78464751943646126929804217551337419536985646543490209434564658963591473315571240892962164634915746487
93919547829228861191709622031900372113021057846850305864875012031127300913022690719116882292874591939
91277199111533323028872561513110489815111947774323832347774911151898401131516527882032333511199177219
99427329407847711138987625823670523929767579298453435489297576792932507632852678983111774870492372499
79137312447763959629080735505541662871672205270243034207250227617826614550553708092695936774421373197
99414638836040823748321349520079865434171316469794949796461317143456897002594312384732804063883641499
73840303623126709593660630870263910007008301487926862978410380070001936207803606639590762132630304837
31178766885002556827322575784936747103939777444452125444477793930174763948757522372865520058866787113
73259742141897508562286971710392056193416107696119791169670161439165029301717968226580579814124795237
96203291140858394137103555890040053311778880959992829995908887711335004009855530173149385804119230269
98714185007726039752120621699187202135929630733802620833703692953120278199612602125793062770058141789
95985877125569743588651981268778558505477317292392229329271377450585587786218915688534796552177858959
77862913887585721458707738115150955127447587139650505693178574472155905151183770785412758578831926877
16137926215225595250028443825773432621823088164760506746188032812623437752834482005259552251262973161
16033559687657557832377047965956376562731898941259295214989813726567365956974077323875575678695533061
73715701792218317101961787103620107294863524121603630612142536849270102630178716910171381229710751737
95923118033764343765416720520826288700010563386445354468336501000788262802502761456734346733081132959
76325545648627568375549307611236309878374407118333133381170447387890363211670394557386572684654552367
39904173327827911703551208827273898819903165650673437605656130991889837272880215530711972872337140993
39771105391324545780760355853629423292302552143549694534125520329232492635855306708754542319350117793
77586186912321116477371824571585761019137553694821612849635573191016758517542817377461112321968168577
32092085960396275651837751394869391316592228174346164347182229561319396849315773815657269306958029023
39704602592534407141641592439050251262162582255937973955228526126215205093429514614170443529520640793
75573363646904442159533557703557897381732415735254845253751423718379875530775533595124440964636337557
77531325870063446147748755968726037386129067085980008958076092168373062786955784774164436007852313577
19144738418666039222261528625902464324257693976492929467939675242346420952682516222293066681483744191
97809928979860953338672625578801078526107174043989998934047170162587010887552627683335906897982990879
10554961131980620217832757570153677193333490199780508799109433339177635107575723871202608913116945501
98571654093717496192439818204482340124950175097418681479057105942104328440281893429169471739045617589
11997927801948659933607628101186844189071572907540704570927517098144868110182670633995684910872979911
10277739741885325653581963751263829971338190714965356941709183317992836215736918535652358814793777201
30299133256232608807410521789460312945370523704196969140732507354921306498712501470880623265233199203
38451217969973360111517599812773633157964783206703430760238746975133637721899571511106337996971215483
77904197714941342614535372543980477794838063076299299267036083849777408934527353541624314941779140977
12830597975043709870221336810574132716525603931640404613930652561723147501863312207890734057979503821
73789422955815570579397018972218414294756269065968586956096265749241481227981079397507551855922498737
70327800180797592799653667586313999138614474099542624599047441683199931368576635699729579708100872307
17717331191917733733797117999737979997799131391377777319313199779997973799971179733733771919113371771
 

The two diagonals are equal to each other and to :

10734239891863405483511048290333863816896215710779197701751269861836833309284011538450436819893243701

 

***

Jan wrote:

My contribution, only to Q2. Feel free to downsize the picture. It is also included as an attachment. The colored squares are 4x4 pixels.

 

Given the conditions I found a solution to L=351 but I thought it was boring, a lot of the palprimes involved are the same.

Therefore I sought a solution where are the palprimes including the palprime defining both diagonals are different.

 

It is in the following picture, L=301:

Colors:  Red=1, Yellow=3, White=5, Green=7, Cyan=9. [So I didnít use the even digits].

Due to symmetry around L^2/8 digits have to be computed, and nearly every digit is can be chosen out of 5 possible values.

It took 10 hours, using Maple. The primes involved are only SPRP.

 

 

As a special case one could consider these squares where only the digits 0 and 1 are involved (0=White, 1=black):

Above are a few solutions to L=23, different palprimes are not imposed here.

Totally black squares (using only digit 1) are possible if the repunit R(L) is prime. So for L=2,19,23, 317, 1031, sequence A004023 in OEIS.

 

I tried to find a nice black and white square for L=317, but ran out of time. Maybe due to the fact that my current routine is looking for a certain pattern. (Too many restrictions).

***


Records   |  Conjectures  |  Problems  |  Puzzles