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

***

---