LLG's blog

By LLG, history, 4 weeks ago, ,

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

• -13

 » 4 weeks ago, # |   0 $0^2 = 0 = 00$
•  » » 4 weeks ago, # ^ |   0 Not a 0
 » 4 weeks ago, # |   +19 1322314049613223140496=36363636364^2
 » 4 weeks ago, # | ← Rev. 2 →   +12 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 Solutionimport math def primeFactors(n): ans = {} while n % 2 == 0: if 2 in ans: ans[2] += 1 ; else: ans[2] = 1 n = n / 2 for i in range(3,int(math.sqrt(n))+1,2): while n % i== 0: if i in ans: ans[i] += 1 ; else: ans[i] = 1 n = n / i if n > 2: ans[n] = 1 ; return ans a = 10 r = 10 found = False while True: pf = primeFactors(a+1) ; for f,o in pf.items(): if o > 1: print (a+1) found = True break if found == True: ans = 1 for f,o in pf.items(): o %= 2 if o == 1: ans *= f print (ans*(a+1)) break a *= r  This 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}$.