Problems & Puzzles: Puzzles

Puzzle 304. A larger square embedded


 Find a larger square than 870613156870773156 = 933066534^2 in the infinite sequence of concatenated primes

... .315687041.315687061.315687077.315687079. ...

 

Contributions came from: J. K. Andersen, Faride Firoozbakht, Andrew Rupinski, Nick McGrath, W. Edwin Clark, Luke Pebody and Jacques Tramu.

Looking at them I can truly say that here is not small puzzle for titanic puzzlers... Thanks for your solutions folks!

***

Andersen wrote:

I notice the puzzle does not ask for the first occurrence of the square, or a square spread on at least 2 primes.

The Prime Pages shows the Generalized Cullen prime 105994*10^105994+1 was found in 2000 by Guenter Loeh with Yves Gallot's Proth.exe. The digits are 105994z1 where z is 105993 0's. That means (2*10^52996)^2 is inside the prime.

It follows from Dirichlet's theorem that all numbers are inside infinitely many primes.

...

Now, let's say it must be the first occurrence of that square. The prime 4*10^103958+1 was found in 2004 by Peter Benson with PrimeForm, NewPGen, Proth.exe. Let z be 103956 0's. Then the prime is the concatenation 4z01 and contains 4z = (2*10^51978)^2.

No prime starts or ends with 0 so 4z must always be inside a single prime. The only smaller potential primes containing 4z are a4zb where a in {0,1,2,3} and b in {1,3,7,9}. 14 of the 16 combinations have a small factor, leaving 4z7 and 14z9.

PrimeForm/GW says:
4*10^103957+7 is composite: [38878A924E531158] (4940.4671s+5.4684s)
14*10^103957+9 is composite: [3F79E390541A6EB2] (4971.2671s+5.2233s)

This shows 4*10^103958+1 contains the first occurrence of (2*10^51978)^2.
 

***

Rupinski wrote:

Maybe for this puzzle you should specify that the embedded square must span at least 2 primes. Otherwise, let S be any square number with d digits. Then by Dirichlet's theorem, there are infinitely many primes of the form k*10^(d+1) + 10S + 1, hence S is embedded in each such prime. Thus, trivially we can find arbitrarily large squares in the concatenated primes.

...

Well, the Dirichlet approach was too easy, so I decided to tackle squares spanning 2 primes. The following is my method, along with some large examples.

This approach does not in general give the minimal occurrence, and the case of embedding N^2 among three or more consecutive primes is admittedly harder to tackle than this approach.

Given a integer N, we have a smart approach to finding a nontrivial embedding of N^2 in the concatenated primes sequence (i.e. N^2 spans more than 1 prime).Divide N^2 into two disjoint substrings, N^2 = AB such that the last digit of A is in {1,3,7,9} and the first digit of B is not 0. Now look for a prime of the form P = BXA where X is some string of digits. If X is sufficiently large, then N(P)* = BY where Y has the same number of digits as XA. So AB is embedded in the prime sequence BXA, BY (heuristically X = O(ln(N^2)) is big enough).
*Note: N(P) represents the next prime function.

Example:
N = 5435843213518378468914
N^2 = 29548391441953811533291712998397622864339396
Let
A = 29
B = 548391441953811533291712998397622864339396
So we look for P = 548391441953811533291712998397622864339396X29
We see X = 76 works.
Then N^2 is embedded in P, N(P):
5483914419538115332917129983976228643393967629
5483914419538115332917129983976228643393967759
Heuristically, any valid division of N = AB gives rise to other embeddings; for example we also have:
A = 2954839144195381153329171299839762286433939
B = 6
X = 31


Example:
N =
1936138664070082316347142505431232008266289761257156376190696241421501236985663/
7179096947335243680669607531475629148240284399976570
N^2 =
3748632926507083060689675232431057526363296984016957820023291355537216060405728/
3894456562160490961695402748580605657672693154046179510214673773807590533918575/
0198197106843379921587124266034636553907150573036803730528897231423233424032171/
010996820273016548964900
Let
A =
6752324310575263632969840169578200232913555372160604057283894456562160490961695/
4027485806056576726931540461795102146737738075905339185750198197106843379921587/
124266034636553907150573036803730528897231423233424032171010996820273016548964900
B = 3748632926507083060689
So we look for P =
67523243105752636329698401695782002329135553721606040572838944565621604909616954/
02748580605657672693154046179510214673773807590533918575019819710684337992158712/
4266034636553907150573036803730528897231423233424032171010996820273016548964900X/
3748632926507083060689
We see X =215 works.
Then N^2 is embedded in P, N(P):
67523243105752636329698401695782002329135553721606040572838944565621604909616954/
02748580605657672693154046179510214673773807590533918575019819710684337992158712/
42660346365539071505730368037305288972314232334240321710109968202730165489649002/
153748632926507083060689

67523243105752636329698401695782002329135553721606040572838944565621604909616954/
02748580605657672693154046179510214673773807590533918575019819710684337992158712/
42660346365539071505730368037305288972314232334240321710109968202730165489649002/
153748632926507083061027

Note that if N^2 does not contain any of the digits {1,3,7,9}, then the only possible embedding of N^2 in the concatenated primes is within a single prime.

...

Carlos, I have continued working with my approach to finding squares embedded in the concatenated primes that I mentioned in my last email. I am happy to say that I have obtained a titanic square embedded
 between two titanic primes. The square is:
N^2 = (7*10^521+2357)^2
It is embedded between the 1046 digit consecutive primes
(98*10^525+55554492549)*10^519+329
(98*10^525+55554492549)*10^519+2777
 

***

Faride wrote:

We can find many large square by using only one prime or by concatenating two consecutive primes. But finding large squares by using n consecutive primes when n > 2 is difficult. For n=3 the largest square S that I found has 222 digits, S=m^2=(877*10^108+113)^2 and the three consecutive related primes p, q & r are :

p= q - 130
q= 69129*10^214 + 198202*10^106 + 127
r= q + 56

S= (877*10^108+113)^2= 769129*10^216 + 198202*10^108 + 12769

In fact if dot between numbers means concatenation we will have :

p= 69129.0(102).198201.9(105).7
q= 69129.0(102).198202.0(103).127
r= 69129.0(102).198202.0(103).183
S= 769129.0(102).198202.0(103).12769

So, p.q.r=
69129.0(102).198201.9(105).S.129.0(102).198202.0(103).183


For n=2 a large S that I found is S=((10^1003-1)/3+440)^2 so
S = (3.(1000).773)^2 = 1(1000).404.2(997).415529 (L(S)=2006) and the two consecutive primes
 p & q are :

p= 1(34).404.2(997).415529.1(966) (L(p)=2006)
q= 1(34).404.2(997).415529.1(963).823 (q=p+712)

and since S=1(1000).404.2(997).415529 we have :

p.q= 1(34).404.2(997).415529.S.1(963).823

I also found larger squares by using two large consecutive probable primes.

...

A larger square S that I found is S=((10^1911-1)/3+440)^2 (L(S)=3822), the related primes (probable primes) p & q
are:

p= 1(11).404.2(1905).415529.1(1897) (L(p)=3822)
q= 1(11).404.2(1905).415529.1(1893).4603 (q=p+3492)

and since S=((10^1911-1)/3+440)^2=1(1908).404.2(1905).415529
so,
p.q= 1(11).404.2(1905).415529.S.1(1893).4603 .
 

***

Pebody wrote:

358706131587369062251 is prime. It contains 870613158736906225=933066535^2.
Similarly every integer is contained.

***

McGrath wrote:

... As you know, Frank Rubin has this question on www.contestcen.com. I sent him the following 53 digit solution.

876 543209 876543 209876 543212 222222 222222 222222 222123 456790 123456 790123 456789
876 543209 876543 209876 543212 222222 222222 222222 222123 456790 123456 790123 456873

where the bold numbers are a 53 digit square 12345 679012 345679 012345 678987 654320 987654 320987 654321  = 111111111111111111111111111^2.

 

I found a neat but not very mathematically pleasing way to generate these and the only reason I arbitrarily chose 53 digits was because Frank claimed he had a 52 digit answer ... I used http://www.alpertron.com.ar/ECM.HTM to confirm that:

 

876 543209 876543 209876 543212 222222 222222 222222 222123 456790 123456 790123456789  and
876 543209 876543 209876 543212 222222 222222 222222 222123 456790 123456 790123 456873

 

are consecutive primes. Unfortunately .. I can assure that it is not the first occurrence. The first occurrence of 12345679012345679012345678987654320987654320987654321 appears (I think) in the "trivial"

1234567901234567901234567898765432098765432098765432131 which is prime

***

W. Wdwin Clark wrote:

Estos numeros son todos primos (por lo menos según la aplicación isprime de Maple) y cada uno "contiene" el cuadrado (10^(K))^2, K = 10, 11, 12, 14, 15, 17, 20 21,26, 27,29. Y sería fácil conseguir aún más grandes..

p = 10^(2*10+2)+ 9 = 10000000000000000000009
p = 10^(2*10+2)+ 57 = 10000000000000000000057
p = 10^(2*10+2)+ 81 = 10000000000000000000081
p = 10^(2*11+2)+ 7 = 1000000000000000000000007
p = 10^(2*11+2)+ 49 = 1000000000000000000000049
p = 10^(2*12+2)+ 67 = 100000000000000000000000067
p = 10^(2*14+2)+ 57 = 1000000000000000000000000000057
p = 10^(2*14+2)+ 99 = 1000000000000000000000000000099
p = 10^(2*15+2)+ 49 = 100000000000000000000000000000049
p = 10^(2*17+2)+ 67 = 1000000000000000000000000000000000067
p = 10^(2*20+2)+ 63 = 1000000000000000000000000000000000000000063
p = 10^(2*21+2)+ 31 = 100000000000000000000000000000000000000000031
p = 10^(2*21+2)+ 57 = 100000000000000000000000000000000000000000057
p = 10^(2*26+2)+ 31 =
1000000000000000000000000000000000000000000000000000031
p = 10^(2*27+2)+ 3 =
100000000000000000000000000000000000000000000000000000003
p = 10^(2*27+2)+ 9 =
100000000000000000000000000000000000000000000000000000009
p = 10^(2*29+2)+ 7 =
1000000000000000000000000000000000000000000000000000000000007
p = 10^(2*29+2)+ 67 =
1000000000000000000000000000000000000000000000000000000000067
p = 10^(2*29+2)+ 79 =
1000000000000000000000000000000000000000000000000000000000079
p = 10^(2*29+2)+ 99 =
1000000000000000000000000000000000000000000000000000000000099
 

***

Jacques Tramu wrote:
In the infinite sequence of primes, we find :

 .37096750237|1.370967502419.3709675024|21.


13709675024193709675024 (23 digits) = 117088321468^2
 
Rem. Without concatenation we find also the probably (by FPGW) prime :
10^5543+7 which includes the square 10^5542

***

Andrew Rupisnki wrote, on 16/9/6:

On puzzle 304, I have some additional interesting results which dwarf most of the trivial solutions found by other searchers. In particular, I have finally found a 1664 digit square embedded among the 3 consecutive 1658 digit primes:
 
P1 = 361017320823744905 62299641090811382454 84205737525165360881
30381521082121329643 86199729272129755811 16240046209188823923
04131668447087469647 37054429277957473639 24538955737219571762
29017397591387809402 41785055292143401912 04617628967815275536
17436052527472724270 94419084258072601097 53898530121694669864
41301774509451887800 92612190873032108683 85114340696748250667
36890378885565395564 99043459922497005854 90681666037210327357
58252536798052915624 97683651808448182645 56215365319468866344
79492299045761638686 02228856825540050431 28710386111696201518
69315607913902130716 97464253436845894406 07675886401502477095
40479718552588327611 89172369383622839805 99276451299402199644
01393857002262133188 50787880283291291442 27617319329092681519
64673838546936572100 10335937849189937333 37529171562486933156
95611896906717888283 67415508992780440790 29544505053579571365
69094243950058418826 90924206952610567697 66260582387827830583
05279066524769957270 39593267529055955746 88052772330260169184
93054865294155884824 42418700345435786737 36410141840824292288
69792063139817151689 78436061236321890876 17737188911709406820
27336952549473897710 81611075170792233814 68435295808031872448
66604088955886464444 88350065102846077814 79782207958166430501
56570085633224360863 57820935041118179337 56078451992043736177
69373337120980610310 48265321401357676757 87886273063761007615
64658272913188761836 09905088653437160328 43354642208232247532
66600682079764892522 01399331835652120518 83412163448136940218
64755233023986940528 54455979862790360442 43477519978915729532
98129904796959865597 83095136883430697838 23438991951141569906
03234147133764649207 55601536169543843319 49215221394244277883
16041273836778892438 00462783649460190521
 
P2 = 361017320823744905 62299641090811382454 84205737525165360881
30381521082121329643 86199729272129755811 16240046209188823923
04131668447087469647 37054429277957473639 24538955737219571762
29017397591387809402 41785055292143401912 04617628967815275536
17436052527472724270 94419084258072601097 53898530121694669864
41301774509451887800 92612190873032108683 85114340696748250667
36890378885565395564 99043459922497005854 90681666037210327357
58252536798052915624 97683651808448182645 56215365319468866344
79492299045761638686 02228856825540050431 28710386111696201518
69315607913902130716 97464253436845894406 07675886401502477095
40479718552588327611 89172369383622839805 99276451299402199644
01393857002262133188 50787880283291291442 27617319329092681519
64673838546936572100 10335937849189937333 37529171562486933156
95611896906717888283 67415508992780440790 29544505053579571365
69094243950058418826 90924206952610567697 66260582387827830583
05279066524769957270 39593267529055955746 88052772330260169184
93054865294155884824 42418700345435786737 36410141840824292288
69792063139817151689 78436061236321890876 17737188911709406820
27336952549473897710 81611075170792233814 68435295808031872448
66604088955886464444 88350065102846077814 79782207958166430501
56570085633224360863 57820935041118179337 56078451992043736177
69373337120980610310 48265321401357676757 87886273063761007615
64658272913188761836 09905088653437160328 43354642208232247532
66600682079764892522 01399331835652120518 83412163448136940218
64755233023986940528 54455979862790360442 43477519978915729532
98129904796959865597 83095136883430697838 23438991951141569906
03234147133764649207 55601536169543843319 49215221394244277883
16041273836778892438 00462783649460196721
 
P3 = 361017320823744905 62299641090811382454 84205737525165360881
30381521082121329643 86199729272129755811 16240046209188823923
04131668447087469647 37054429277957473639 24538955737219571762
29017397591387809402 41785055292143401912 04617628967815275536
17436052527472724270 94419084258072601097 53898530121694669864
41301774509451887800 92612190873032108683 85114340696748250667
36890378885565395564 99043459922497005854 90681666037210327357
58252536798052915624 97683651808448182645 56215365319468866344
79492299045761638686 02228856825540050431 28710386111696201518
69315607913902130716 97464253436845894406 07675886401502477095
40479718552588327611 89172369383622839805 99276451299402199644
01393857002262133188 50787880283291291442 27617319329092681519
64673838546936572100 10335937849189937333 37529171562486933156
95611896906717888283 67415508992780440790 29544505053579571365
69094243950058418826 90924206952610567697 66260582387827830583
05279066524769957270 39593267529055955746 88052772330260169184
93054865294155884824 42418700345435786737 36410141840824292288
69792063139817151689 78436061236321890876 17737188911709406820
27336952549473897710 81611075170792233814 68435295808031872448
66604088955886464444 88350065102846077814 79782207958166430501
56570085633224360863 57820935041118179337 56078451992043736177
69373337120980610310 48265321401357676757 87886273063761007615
64658272913188761836 09905088653437160328 43354642208232247532
66600682079764892522 01399331835652120518 83412163448136940218
64755233023986940528 54455979862790360442 43477519978915729532
98129904796959865597 83095136883430697838 23438991951141569906
03234147133764649207 55601536169543843319 49215221394244277883
16041273836778892438 00462783649460204699
 
Square = 722053334124 85794358927057480602 02439255643592774592 70253955913963395304 92500829953270003855 03905872949811273667 40448594395084103564 98072882610398300789 45399024097134242107 50123099707343238709 03781653707920608856 16779512794956849525 32743954434986631691 72168193780124545019 59015565772238598541 88407070761467200516 37399672756564460043 55936111491005509763 36759996054133980302 18014896898264854546 40835616326440078470 62718015549805435058 03072258122472537816 68748780954267584861 63842781644513186703 93846810457017034469 77536781669772047373 97333466395075841183 34237384117066272559 68466489566280475289 93929573517807793550 91122120625898536385 11753980835249093432 20656064002172386227 79446236297647951781 36006259516064994079 32512472780629953518 17741345848857022753 80255768653216424628 03236552267981098054 31097932942159306974 28365009506236145481^2
 
 
I have also a much larger nontrivial example of 2 consecutive primes containing an embedded square:
 
(63760683*2^15133+1)^2 is embedded between the 9133 digit consecutive PRPs:
 
P1 = ((63760683*2^{15133}+1)^2 - 3827*10^{9123})*10^{10}+1067983827
P2 = ((63760683*2^{15133}+1)^2 - 3827*10^{9123})*10^{10}+1067991839
 
In this latter case, the seed 63760683*2^15133+1 is itself prime.

***

On Nov 1, 2018, Paul Cleary wrote:

I currently have a 6000 digit square spanning 3 primes 5996 digits each... the first number is the square, it is last 2 digits of the first prime, all the second prime and the first 2 digits of the third prime. In this .txt file you can see the square, the first, second and third prime, and also the square root of the square integer.

***

On Nov 18, 2018, Paul added:

... my method of finding embedded squares in concatenated primes, i.e. puzzle 304.

 

Having decided what size square I want to find, generate a random integer between 10^n and 10^n-1where n is the digit length of the square.  Then take the integer part of the square root and then square that, test this number to see if the second digit is odd and the 3rd and 4th digits are equal to 21 and the last 2 digits are also equal to 21, 21 is chosen as one of the ending two digits of a square.  Repeat this process until all 3 criteria are met.  At this point we now test the 3rd to n-2 digits inclusive and see if it is a prime and test if the previous primes last 2 digits are equal to the first 2 digits of the square, if so we have a solution, if not increase the square root of the square by 50, re-square it and test again.  This stage of adding 50 I do say 1000 times, and adding 50 ensures the square ends in 21 again.  if there is no solution, jump back to the beginning and generate another random square.  The 6000 digit square took approx. 18 hours to find, where as 100 digit squares are approx. 1 every 5 seconds.

***
 

 

 
Records   |  Conjectures  |  Problems  |  Puzzles