mersenneforum.org squarewise concatanation for the win
 Register FAQ Search Today's Posts Mark Forums Read

 2023-03-18, 21:22 #1 fatphil     May 2003 7·37 Posts squarewise concatanation for the win 1225172265625 is a lovely number 1 is a square 225 is a square put them together, and 1225 is a square 72265625 is a square put it together with what came before, and you get 122572265625 which is a square I don't know where I'm going with this, but I'm sure you guys can have fun. (oh, 4 and 9 have even shorter paths, but ones I've not probed as deeply)
2023-03-19, 13:12   #2
Dr Sardonicus

Feb 2017
Nowhere

23×17×47 Posts

Quote:
 Originally Posted by fatphil 1225172265625 is a lovely number 1 is a square 225 is a square put them together, and 1225 is a square
So far, so good.
Quote:
 72265625 is a square
Er, no.
Code:
? print(factor(72265625))
[5, 9; 37, 1]
Quote:
 put it together with what came before, and you get 122572265625 which is a square
Again, no.
Code:
? print(factor(122572265625))
[3, 2; 5, 9; 19, 1; 367, 1]

2023-03-19, 13:54   #3
fatphil

May 2003

7·37 Posts

Quote:
 Originally Posted by Dr Sardonicus So far, so good. Er, no. Code: ? print(factor(72265625)) [5, 9; 37, 1] Again, no. Code: ? print(factor(122572265625)) [3, 2; 5, 9; 19, 1; 367, 1]
Ooops, missed a character in the copy/paste:
? factor(172265625)

[3 2]
[5 8]
[7 2]

? factor(1225172265625)

[ 5 8]
[ 7 2]
[11 2]
[23 2]

2023-03-19, 14:21   #4
fatphil

May 2003

7×37 Posts

Quote:
 Originally Posted by fatphil 1225172265625 is a lovely number I don't know where I'm going with this, but I'm sure you guys can have fun. (oh, 4 and 9 have even shorter paths, but ones I've not probed as deeply)
It appears that probing's quite cheap:

4 -> 49 -> 49729 -> 4972922562328439750054749703581033600295913998934338451363146305084228515625

9 -> 950625 -> 95062561096409435940120435784167300872787977524634772310552222052137949503958225250244140625

 2023-03-22, 14:11 #5 Dr Sardonicus     Feb 2017 Nowhere 23×17×47 Posts 16, 1681, 1681236390625 Code: 4, 49, 49729, 497299167114067888529849495363612005139078505485784844495356082916259765625 Code: 9, 93025, 93025698201261719352105289560261241444780223428635104730773756605244766299827431245265431380975229558316641487181186676025390625 Last fiddled with by Dr Sardonicus on 2023-03-22 at 17:18 Reason: Additional examples
2023-03-22, 17:34   #6
fatphil

May 2003

7·37 Posts

Quote:
 Originally Posted by Dr Sardonicus Code: 4, 49, 49729, 497299167114067888529849495363612005139078505485784844495356082916259765625 Code: 9, 93025, 93025698201261719352105289560261241444780223428635104730773756605244766299827431245265431380975229558316641487181186676025390625
Yeah, I discovered 93025 first, but that was before I had written the faster (and apparently buggier) version of the algorithm to search for solutions. I had forgotten about its existence when I reran the search. The new buggy code does confirm your large extension in a tenth of a second, but clearly isn't to be trusted to find every solution. Technically, it's still horrifically inefficient as it will find your solution 10 times as it blends factors in from different directions, so needs a rewrite anyway.

Can I enquire your algorithm? Mine's an idiotic brute force:

To extend N by up to D_max digits:
For each length D <= D_max
Try to extend N by D digits

To extend N by D digits:
For each pair L,H : L*H=N
Look at the set of values L*2^x*5^y and H*2^(D-x)*5^(D-y), finding ones that are close to each other
If their difference is small enough, a solution can be found.

The only smarts I've added are traversing the 2D grid of x,y values by following a diagonal so that for each y you never look at more than two y values, as you zig-zag along.

There's hopefully a proper mathematical solution that's better than this almost completely dumb brute force.

2023-03-22, 20:09   #7
Dr Sardonicus

Feb 2017
Nowhere

18F816 Posts

Quote:
 Originally Posted by fatphil Can I enquire your algorithm? There's hopefully a proper mathematical solution that's better than this almost completely dumb brute force.
We want solutions to N*10^D + y^2 = x^2 with y%10 <> 0 and 10^(D-1) < y^2 < 10^D.

So x - y and x + y are complementary divisors of N*10^D.

The inequalities force y to be rather small, so x + y and x - y will be just either side of the square root of N*10^D. The divisors x - y and x + y also have to be of the same parity.

I started just past the middle divisor and looked at successively larger divisors. You don't have to look far. As soon as two complementary divisors differ by more than 2*10^(D/2) you're done.

 2023-03-23, 13:30 #8 Dr Sardonicus     Feb 2017 Nowhere 23×17×47 Posts I do not know whether every square can be concatenated on the right with a square to form another square. If it is possible, of course, the operation could (in theory) be continued indefinitely starting with any given square. It was also not clear to me whether a given square has infinitely many "square right concatenands" irrespective of whether they are themselves concatenations of squares. I found the "least right square concatenands" for n^2, n = 1 to 100. For n = 1 to 32 we have (n, n^2, concatenand) Code: 1 1 225 2 4 9 3 9 3025 4 16 9 5 25 889914313729282379150390625 6 36 1 7 49 729 8 64 144101272782851806640625 9 81 225 10 100 126609965386962890625 11 121 84462890625 12 144 4 13 169 2601 14 196 11026550390625 15 225 625 16 256 14402025 17 289 1625853603515625 18 324 9 19 361 56169 20 400 225031640625 21 441 73530625 22 484 27228828515625 23 529 2976043447265625 24 576 9604 25 625 3516119384765625 26 676 50625 27 729 102515625 28 784 11025 29 841 118265625 30 900 1265625 31 961 38025 32 1024 144 The largest was for 100^2, and has 128 decimal digits: Code: 93992319734581661956387986883358273574988380195353931821736541786064242089305750894379955229229750557351508177816867828369140625 = 9694963627295445503856592180983186990852118469774723052978515625^2 1000093992319734581661956387986883358273574988380195353931821736541786064242089305750894379955229229750557351508177816867828369140625 = 1000046995055599665423155971380983186990852118469774723052978515625^2 It also occurred to me to look at concatenating on the left. This turned out to be more interesting from a number-theoretic standpoint. It appears that if there are any "left concatenands" there will be infinitely many, but it was not clear whether the construction could lead to successive concatenations. Consider the square 1. Concatenating on the left by the square 36 gives 361 = 19^2. But it is clear that there are infinitely many "left square concatenands" for 1. They are the solutions to the quadratic Diophantine equation 10*b^2 + 1 = a^2, which can be characterized by Mod(a + b*x, x^2 - 10) = Mod(19 + 6*x, x^2 - 10)^i, i = positive integer. For i = 2 we get 10*228^2 + 1 = 721^2. Multiplying through by 4 gives all "left concatenands" for 4. For the square 9, multiplying the solutions for the square 1 gives some, but not all, "left concatenands" for 9. There are two other families of solutions, beginning with 49 and 169, characterized by Mod(a + b*x, x^2 - 10) = Mod(7 + 2*x, x^2 - 10)*Mod(19 + 6*x, x^2 - 10)^i, i = non-negative integer and Mod(a + b*x, x^2 - 10) = Mod(13 + 4*x, x^2 - 10)*Mod(19 + 6*x, x^2 - 10)^i, i = non-negative integer. The next members of these families are 10*80^2 + 9 = 253^2 and 10*154^2 + 9 = 487^2 . Last fiddled with by Dr Sardonicus on 2023-03-23 at 14:23

All times are UTC. The time now is 14:35.

Sat Jun 10 14:35:56 UTC 2023 up 296 days, 12:04, 0 users, load averages: 0.96, 0.87, 0.84