squarewise concatanation for the win

[fatphil]

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)

[Dr Sardonicus]

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.

72265625 is a square

Er, no.

? print(factor(72265625))
[5, 9; 37, 1]

put it together with what came before, and you get
122572265625 which is a square
<snip>

Again, no.

? print(factor(122572265625))
[3, 2; 5, 9; 19, 1; 367, 1]

[fatphil]

Originally Posted by Dr Sardonicus

So far, so good.
Er, no.

? print(factor(72265625))
[5, 9; 37, 1]

Again, no.

? 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]

[fatphil]

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

[Dr Sardonicus]

16, 1681, 1681236390625

4, 49, 49729, 497299167114067888529849495363612005139078505485784844495356082916259765625

9, 93025, 93025698201261719352105289560261241444780223428635104730773756605244766299827431245265431380975229558316641487181186676025390625

[fatphil]

Originally Posted by Dr Sardonicus

4, 49, 49729, 497299167114067888529849495363612005139078505485784844495356082916259765625

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.

[Dr Sardonicus]

Originally Posted by fatphil

Can I enquire your algorithm?
<snip>
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.

[Dr Sardonicus]

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)

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:

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 .