How to find the smallest perfect square which is a concatenation of the same number two times ?

# | User | Rating |
---|---|---|

1 | Benq | 3539 |

2 | tourist | 3532 |

3 | wxhtxdy | 3425 |

4 | Radewoosh | 3316 |

5 | ecnerwala | 3297 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | Um_nik | 3260 |

9 | yutaka1999 | 3190 |

10 | TLE | 3145 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 192 |

2 | Radewoosh | 179 |

3 | tourist | 172 |

4 | Vovuh | 167 |

4 | antontrygubO_o | 167 |

6 | PikMike | 166 |

7 | rng_58 | 160 |

8 | majk | 157 |

9 | Um_nik | 154 |

9 | 300iq | 154 |

How to find the smallest perfect square which is a concatenation of the same number two times ?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/14/2019 05:25:46 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

$$$0^2 = 0 = 00$$$

Not a 0

1322314049613223140496=36363636364^2

Suppose the number is $$${m}$$$. Then $$${mm}$$$ is a perfect square.

$$${mm}={m}*{(10^{n}+1)}$$$

Note that the number of digits in $$${m}$$$ should be less than or equal to $$${n}$$$. Thus,

$$${(10^{n}+1)}\gt{m}$$$

We can now look at the prime factorisation of $$${(10^{n}+1)}$$$. If any prime factor has frequency more than $$${1}$$$, then we can remove that prime factor in pairs until its number of occurrences is either $$${0}$$$ or $$${1}$$$. Having done so we are left with the smallest possible $$${m}$$$. Multiplying the two will give us the smallest $$${mm}$$$.

Naive Python SolutionThis gives $$${mm}={82644628100826446281}$$$ assuming $$${m}$$$ can contain leading zeroes.

Edit :

We can also solve this for $$${m}$$$ without leading zeroes. Using the previous solution we can get the smallest $$${n}$$$ for which $$${(10^{n}+1)}$$$ contains a prime factor with exponent more than $$${1}$$$ (i.e. $$${n} = {11}$$$ and there is only one prime factor which is $$${11}$$$ with exponent $$${2}$$$). First, we have to remove some prime factor pairs from $$${(10^{n}+1)}$$$ because we need $$${m}$$$ smaller than $$${(10^{n}+1)}$$$. We have only one option of removing $$${11}^{2}$$$ here. Now our number is $$${826446281}$$$. We have to multiply this number with perfect squares(i.e. $$${2}^{2}, {3}^{2}, ... $$$) until our number becomes $$${11}$$$ digit. Our final $$${m}$$$ is $$${826446281}*({4}^{2}) = {13223140496}$$$ thus, $$${mm}$$$ is $$${1322314049613223140496}$$$.