找到一个四位数的数字，其平方是 8 位，最后 4 位是原始数字
Find the a 4 digit number whose square is 8 digits AND last 4 digits are the original number
从my answer here的评论中，提出的问题（释义）：
写一个Python程序求一个4位整数，当它与它自身相乘时，你得到一个8位整数，它的最后4位等于原来的数。
我会 post 我的答案，但我对更 优雅的解决方案感兴趣 简洁但易于阅读的解决方案！ （新手 python 能看懂吗？）
我想到的解决办法是：
# Loop over all 4 digit numbers
for x in range(1000, 10000):
# Multiply x*x
square = x*x
# Convert to a string
square = str(square)
# Check if the square is 8 digits long
if len(square) == 8:
# Check if the last 4 digets match x
if square.endswith(str(x)):
# print the number and it's square
print('x = {}\nx**2 = {}'.format(str(x), square))
输出：
x = 9376
x**2 = 87909376
[差不多] 1 行:
from math import sqrt, ceil, floor
print(next(x for x in range(ceil(sqrt(10 ** 7)), floor(sqrt(10 ** 8 - 1))) if x == (x * x) % 10000))
打印：
9376
时间：
%timeit next(x for x in range(ceil(sqrt(10 ** 7)), floor(sqrt(10 ** 8 - 1))) if x == (x * x) % 10000)
546 µs ± 32.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
@theausome 的回答（最短的（character-wise））：
%timeit next((x for x in range(3163, 10000) if str(x*x)[-4:] == str(x)), None)
3.09 ms ± 119 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
@jpp 的回答（最快）：
import numpy as np
from numba import jit
@jit(nopython=True)
def find_result():
for x in range(1e7**0.5, 1e9**0.5):
i = x**2
if i % 1e4 == x:
return (x, i)
%timeit find_result()
61.8 µs ± 1.46 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
这是一个 1-liner 解决方案，没有任何模块：
>>> next((x for x in range(1000, 10000) if str(x*x)[-4:] == str(x)), None)
9376
如果你考虑从 1000 到 3162 的数字，它们的平方会给你一个 7 数字。所以从 3163 迭代会更优化，因为正方形应该是 8 数字。感谢@adrin 提出了这么好的观点。
>>> next((x for x in range(3163, 10000) if str(x*x)[-4:] == str(x)), None)
9376
如果您对使用第 3 方库感到满意，可以使用 numpy。此版本结合numba进行优化
import numpy as np
from numba import jit
@jit(nopython=True)
def find_result():
for x in range(1e7**0.5, 1e9**0.5):
i = x**2
if i % 1e4 == x:
return (x, i)
print(find_result())
# (9376, 87909376)
以下解决方案不如其他答案可读。但它缺乏可读性，却提高了效率。
蛮力方法检查给定范围内的每个数字，使其成为 O(10^n) 其中 n 是数字所需数字的数量（如果我们考虑乘法和转换，则最差）。
相反，我们可以从右到左构建所需的数字，只要生成的数字形成其平方的尾部数字，就添加数字。这提供了一个 O(n³) 算法（见底部的时间复杂度部分）。
def get_all_numbers(n, _digits=None):
# We are provided digits that form a number with desired properties
digits = [] if _digits is None else _digits
# Base case: if we attained the number of digits, return those digits
if len(digits) >= n:
return [int(''.join(digits))]
solutions = []
# Add digits from 0 to 9 and check if the new number satisfies our property
for x in range(10):
next_digits = [str(x)] + digits if x else ['0'] + digits
next_number = int(''.join(next_digits))
# If it does try adding yet another digit
if int(str(next_number ** 2)[-len(next_digits):]) == next_number:
solutions.extend(get_all_numbers(n, next_digits))
# Filter out solutions with too few digits
# Necessary as we could have prepended only zeros to an existing solution
return [sol for sol in solutions if sol >= 10 ** (n - 1)]
def get_numbers(n, sqr_length=None):
if sqr_length:
return [x for x in get_all_numbers(n) if len(str(x ** 2)) == sqr_length]
else:
return get_all_numbers(n)
get_numbers(4, 8) # [9376]
这对于少量数字来说不是必需的，但可以解决较大输入的问题，而蛮力解决方案需要永远。
get_numbers(100) # Outputs in a few milliseconds
时间复杂度
对于给定数量的数字 n，there can only exist at most two solutions 除了 0 和 1。并且任何解决方案都是从较少数字的解决方案构建的。
由此我们得出结论，尽管存在递归，该算法仍需要 O(n) 步才能找到解决方案。
现在，每一步都要执行一些乘法和转换。整数转换为 O(n²) and multiplication in Python uses Karatsuba's algorithm，小于转换。
总体而言，这会产生 O(n³) 时间复杂度。
这可以通过使用线性整数转换算法来改进，然后会提供 O(n^(1 + log(3))) 复杂度。
这里有一个班轮，就
print(9376)
这是一个动态规划版本：
我们从右到左构建，利用这样的知识，即对于一个数字与其自身平方的知识，每个较低有效数字也必须如此（在 post 上，这与@Olivier Melançon 所采用的方法相同):
def dynamic(currents, tens, goal):
if tens == goal:
return [i for i in currents if len(str(i)) == tens]
else:
out = []
for x in currents:
for i in range(0,10):
val = x + i *10**tens
if val**2 % 10**(tens+1) == val:
out.append(val)
currents = out
tens +=1
return dynamic(currents, tens, goal)
我们用 'current goal'、当前十位和目标十位来称呼它：
dynamic([0],0,4)
#[9376]
在不到一秒的时间内很好地处理超大数：
dynamic([0],0,100)
#[3953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625,6046992680891830197061490109937833490419136188999442576576769103890995893380022607743740081787109376]
这是 one-line 的实现，它排除了 97.24% 的候选人：
import itertools
step = itertools.cycle((24, 1, 24, 51))
[x for x in range(3176, 10000, next(step)) if str(x*x)[-4:] == str(x) ]
拨打号码abcd。可以通过限制最后两位cd进行优化，合法的可能性只有4种，排除了96%的cd候选。同样我们只需要测试31 <= ab < 100，排除31%的候选人ab。因此我们排除了 97.24%
cd_cands = set((n**2) % 100 for n in range(0,99+1) if ((n**2 % 100) == n))
cd_cands = sorted(cd_cands)
[0, 1, 25, 76]
for ab in range(31,99+1):
for cd in cd_cands:
n = ab*100 + cd
if n**2 % 10**4 == n :
print("Solution: {}".format(n))
#break if you only want the lowest/unique solution
...
Solution: 9376
（当然你可以将其压缩到 one-line 列表理解中，但这会很丑陋）
现在我们可以通过以下观察将倍数 for-loops 分开：严格来说，我们只需要从 3162 以上的第一个合法候选开始测试，即 3176。然后，我们通过连续添加步长 (100 -76、1-0、25-1、76-25) = (24、1、24、51)
import itertools
step = itertools.cycle((24, 1, 24, 51))
abcd = 3176
while abcd < 10**4:
if abcd**2 % 10000 == abcd:
print("Solution: {}".format(abcd))
abcd += next(step)
又可以简化为顶部显示的 one-liner(/two-liner)。
更新：如@mathmandan 所示，我们可以进一步改进 step = itertools.cycle((1, 624))，消除 99.68% 的候选人。并从 625 * 6 = 3750
处开始搜索
使用模运算符 % 而不是字符串
的简单 one-liner
print [x for x in range(3163, 10000) if x*x % 10000 == x]
# [9376]
范围的下限 3163 是平方为八位数的最小四位数。
我们只需要测试625个候选号码中的1个
任一解决方案A：
upper_limit = 10**4
lower_limit = int(10**3.5) + 1
rem = lower_limit % 625
if rem > 0:
lower_limit = lower_limit - rem + 625
for n in xrange(lower_limit, upper_limit, 625):
if n % 16 in [1, 15]:
print {1: n, 15: n+1}[n%16]
break
或解决方案 B：
print (1 * (-39) * 16 + 0 * 1 * 625) % 10000
继续阅读以获取解释。
从测试所有考生的brute-forcelist-comprehension开始：
from math import ceil
[n for n in xrange(ceil(10**3.5), 10000) if (n*n) % 10000 == n]
（ceil 将 10**7 的平方根四舍五入到最接近的整数）。
（请注意，10000 是第一个平方数为 9 位的数字，循环不会测试该数字。）
... 或者如果您想 early-terminate 一旦找到解决方案：
for n in xrange(ceil(10**3.5), 10000):
if (n*n) % 10000 == n:
print n
break
但考虑一下：我们正在寻找可被 10**4 = 2**4 * 5**4 整除的数字 n**2 - n = n*(n-1)。
n或n-1是奇数；所以另一个必须能被完整的 2**4 = 16 整除。同样，你不能让 n 和 (n-1) 都被 5;- 所以我们需要
n 或 (n-1) 被 5**4 = 625 整除。
- 如果其中一个（
n 或 (n-1)）可以同时被 625 和 16 整除，则该数字可以被 10000 整除。没有这样的数是四位数的，所以一定是n或(n-1)中的一个能被625整除，另一个能被16整除。 ]
- 因此我们可以限制我们的搜索space只看
625的倍数，它有四位数；我们只需要小心记住 625 的倍数可能是 n 或 (n-1)；另一个必须能被 16. 整除
所以：
upper_limit = 10**4
lower_limit = ceil(10**3.5)
rem = lower_limit % 625
if rem > 0:
lower_limit = lower_limit - rem + 625
for n in xrange(lower_limit, upper_limit, 625):
if (n-1) % 16 == 0:
print n
break
if (n+1) % 16 == 0:
print n+1
break
或者，如果您测试 n 而不是 (n-1)，并将两个条件分支合并为 n % 16 in [1, 15]，为了紧凑，您可以 print {1: n, 15: n+1}[n%16].
这是解决方案 A。（此外，如果您愿意，您当然可以将 n%16 替换为 n & 0xf。）
但是等等！ 事实上，所有这些都可以使用...
Chinese Remainder Theorem
我们想要找到 n 使得：
n = 0 (mod 625) 和 n - 1 = 0 (mod 16),
要么：
n - 1 = 0 (mod 625) 和 n = 0 (mod 16).
所以在每种情况下我们都有两个方程，具有互质模，求解相同的数 n:
n = 0 (mod 625) 和 n = 1 (mod 16),
要不然
n = 1 (mod 625) 和 n = 0 (mod 16).
现在（在这两种情况下）我们将使用扩展欧几里得算法来找到 m1 和 m2 使得 16*m1 + 625*m2 = 1。结果是-39*16 + 1*625 = 1，从第二种情况引出上面的解B。 （注意：第一种情况会产生 625，其正方形确实以 0625 结尾，但不算作解决方案。）
为了完整起见，这里是扩展欧几里得算法的实现。第二个和第三个输出是 m1 和 m2；在我们的例子中 1 和 -39 以某种顺序排列。
def extended_gcd(a, b):
last_remainder, remainder = abs(a), abs(b)
x, last_x, y, last_y = 0, 1, 1, 0
while remainder:
last_remainder, (quotient, remainder) = remainder, divmod(last_remainder, remainder)
x, last_x = last_x - quotient*x, x
y, last_y = last_y - quotient*y, y
return last_remainder, last_x * ((-1)**(a < 0)), last_y * ((-1)**(b < 0))
从my answer here的评论中，提出的问题（释义）：
写一个Python程序求一个4位整数，当它与它自身相乘时，你得到一个8位整数，它的最后4位等于原来的数。
我会 post 我的答案，但我对更 优雅的解决方案感兴趣 简洁但易于阅读的解决方案！ （新手 python 能看懂吗？）
我想到的解决办法是：
# Loop over all 4 digit numbers
for x in range(1000, 10000):
# Multiply x*x
square = x*x
# Convert to a string
square = str(square)
# Check if the square is 8 digits long
if len(square) == 8:
# Check if the last 4 digets match x
if square.endswith(str(x)):
# print the number and it's square
print('x = {}\nx**2 = {}'.format(str(x), square))
输出：
x = 9376
x**2 = 87909376
[差不多] 1 行:
from math import sqrt, ceil, floor
print(next(x for x in range(ceil(sqrt(10 ** 7)), floor(sqrt(10 ** 8 - 1))) if x == (x * x) % 10000))
打印：
9376
时间：
%timeit next(x for x in range(ceil(sqrt(10 ** 7)), floor(sqrt(10 ** 8 - 1))) if x == (x * x) % 10000)
546 µs ± 32.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
@theausome 的回答（最短的（character-wise））：
%timeit next((x for x in range(3163, 10000) if str(x*x)[-4:] == str(x)), None)
3.09 ms ± 119 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
@jpp 的回答（最快）：
import numpy as np
from numba import jit
@jit(nopython=True)
def find_result():
for x in range(1e7**0.5, 1e9**0.5):
i = x**2
if i % 1e4 == x:
return (x, i)
%timeit find_result()
61.8 µs ± 1.46 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
这是一个 1-liner 解决方案，没有任何模块：
>>> next((x for x in range(1000, 10000) if str(x*x)[-4:] == str(x)), None)
9376
如果你考虑从 1000 到 3162 的数字，它们的平方会给你一个 7 数字。所以从 3163 迭代会更优化，因为正方形应该是 8 数字。感谢@adrin 提出了这么好的观点。
>>> next((x for x in range(3163, 10000) if str(x*x)[-4:] == str(x)), None)
9376
如果您对使用第 3 方库感到满意，可以使用 numpy。此版本结合numba进行优化
import numpy as np
from numba import jit
@jit(nopython=True)
def find_result():
for x in range(1e7**0.5, 1e9**0.5):
i = x**2
if i % 1e4 == x:
return (x, i)
print(find_result())
# (9376, 87909376)
以下解决方案不如其他答案可读。但它缺乏可读性，却提高了效率。
蛮力方法检查给定范围内的每个数字，使其成为 O(10^n) 其中 n 是数字所需数字的数量（如果我们考虑乘法和转换，则最差）。
相反，我们可以从右到左构建所需的数字，只要生成的数字形成其平方的尾部数字，就添加数字。这提供了一个 O(n³) 算法（见底部的时间复杂度部分）。
def get_all_numbers(n, _digits=None):
# We are provided digits that form a number with desired properties
digits = [] if _digits is None else _digits
# Base case: if we attained the number of digits, return those digits
if len(digits) >= n:
return [int(''.join(digits))]
solutions = []
# Add digits from 0 to 9 and check if the new number satisfies our property
for x in range(10):
next_digits = [str(x)] + digits if x else ['0'] + digits
next_number = int(''.join(next_digits))
# If it does try adding yet another digit
if int(str(next_number ** 2)[-len(next_digits):]) == next_number:
solutions.extend(get_all_numbers(n, next_digits))
# Filter out solutions with too few digits
# Necessary as we could have prepended only zeros to an existing solution
return [sol for sol in solutions if sol >= 10 ** (n - 1)]
def get_numbers(n, sqr_length=None):
if sqr_length:
return [x for x in get_all_numbers(n) if len(str(x ** 2)) == sqr_length]
else:
return get_all_numbers(n)
get_numbers(4, 8) # [9376]
这对于少量数字来说不是必需的，但可以解决较大输入的问题，而蛮力解决方案需要永远。
get_numbers(100) # Outputs in a few milliseconds
时间复杂度
对于给定数量的数字 n，there can only exist at most two solutions 除了 0 和 1。并且任何解决方案都是从较少数字的解决方案构建的。
由此我们得出结论，尽管存在递归，该算法仍需要 O(n) 步才能找到解决方案。
现在，每一步都要执行一些乘法和转换。整数转换为 O(n²) and multiplication in Python uses Karatsuba's algorithm，小于转换。
总体而言，这会产生 O(n³) 时间复杂度。
这可以通过使用线性整数转换算法来改进，然后会提供 O(n^(1 + log(3))) 复杂度。
这里有一个班轮，就
print(9376)
这是一个动态规划版本：
我们从右到左构建，利用这样的知识，即对于一个数字与其自身平方的知识，每个较低有效数字也必须如此（在 post 上，这与@Olivier Melançon 所采用的方法相同):
def dynamic(currents, tens, goal):
if tens == goal:
return [i for i in currents if len(str(i)) == tens]
else:
out = []
for x in currents:
for i in range(0,10):
val = x + i *10**tens
if val**2 % 10**(tens+1) == val:
out.append(val)
currents = out
tens +=1
return dynamic(currents, tens, goal)
我们用 'current goal'、当前十位和目标十位来称呼它：
dynamic([0],0,4)
#[9376]
在不到一秒的时间内很好地处理超大数：
dynamic([0],0,100)
#[3953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625,6046992680891830197061490109937833490419136188999442576576769103890995893380022607743740081787109376]
这是 one-line 的实现，它排除了 97.24% 的候选人：
import itertools
step = itertools.cycle((24, 1, 24, 51))
[x for x in range(3176, 10000, next(step)) if str(x*x)[-4:] == str(x) ]
拨打号码abcd。可以通过限制最后两位cd进行优化，合法的可能性只有4种，排除了96%的cd候选。同样我们只需要测试31 <= ab < 100，排除31%的候选人ab。因此我们排除了 97.24%
cd_cands = set((n**2) % 100 for n in range(0,99+1) if ((n**2 % 100) == n))
cd_cands = sorted(cd_cands)
[0, 1, 25, 76]
for ab in range(31,99+1):
for cd in cd_cands:
n = ab*100 + cd
if n**2 % 10**4 == n :
print("Solution: {}".format(n))
#break if you only want the lowest/unique solution
...
Solution: 9376
（当然你可以将其压缩到 one-line 列表理解中，但这会很丑陋）
现在我们可以通过以下观察将倍数 for-loops 分开：严格来说，我们只需要从 3162 以上的第一个合法候选开始测试，即 3176。然后，我们通过连续添加步长 (100 -76、1-0、25-1、76-25) = (24、1、24、51)
import itertools
step = itertools.cycle((24, 1, 24, 51))
abcd = 3176
while abcd < 10**4:
if abcd**2 % 10000 == abcd:
print("Solution: {}".format(abcd))
abcd += next(step)
又可以简化为顶部显示的 one-liner(/two-liner)。
更新：如@mathmandan 所示，我们可以进一步改进 step = itertools.cycle((1, 624))，消除 99.68% 的候选人。并从 625 * 6 = 3750
使用模运算符 % 而不是字符串
print [x for x in range(3163, 10000) if x*x % 10000 == x]
# [9376]
范围的下限 3163 是平方为八位数的最小四位数。
我们只需要测试625个候选号码中的1个
任一解决方案A：
upper_limit = 10**4
lower_limit = int(10**3.5) + 1
rem = lower_limit % 625
if rem > 0:
lower_limit = lower_limit - rem + 625
for n in xrange(lower_limit, upper_limit, 625):
if n % 16 in [1, 15]:
print {1: n, 15: n+1}[n%16]
break
或解决方案 B：
print (1 * (-39) * 16 + 0 * 1 * 625) % 10000
继续阅读以获取解释。
从测试所有考生的brute-forcelist-comprehension开始：
from math import ceil
[n for n in xrange(ceil(10**3.5), 10000) if (n*n) % 10000 == n]
（ceil 将 10**7 的平方根四舍五入到最接近的整数）。
（请注意，10000 是第一个平方数为 9 位的数字，循环不会测试该数字。）
... 或者如果您想 early-terminate 一旦找到解决方案：
for n in xrange(ceil(10**3.5), 10000):
if (n*n) % 10000 == n:
print n
break
但考虑一下：我们正在寻找可被 10**4 = 2**4 * 5**4 整除的数字 n**2 - n = n*(n-1)。
n或n-1是奇数；所以另一个必须能被完整的2**4 = 16整除。同样，你不能让n和(n-1)都被5; 整除
- 所以我们需要
n或(n-1)被5**4 = 625整除。 - 如果其中一个（
n或(n-1)）可以同时被625和16整除，则该数字可以被10000整除。没有这样的数是四位数的，所以一定是n或(n-1)中的一个能被625整除，另一个能被16整除。 ]
- 因此我们可以限制我们的搜索space只看
625的倍数，它有四位数；我们只需要小心记住625的倍数可能是n或(n-1)；另一个必须能被16. 整除
所以：
upper_limit = 10**4
lower_limit = ceil(10**3.5)
rem = lower_limit % 625
if rem > 0:
lower_limit = lower_limit - rem + 625
for n in xrange(lower_limit, upper_limit, 625):
if (n-1) % 16 == 0:
print n
break
if (n+1) % 16 == 0:
print n+1
break
或者，如果您测试 n 而不是 (n-1)，并将两个条件分支合并为 n % 16 in [1, 15]，为了紧凑，您可以 print {1: n, 15: n+1}[n%16].
这是解决方案 A。（此外，如果您愿意，您当然可以将 n%16 替换为 n & 0xf。）
但是等等！ 事实上，所有这些都可以使用...
Chinese Remainder Theorem
我们想要找到 n 使得：
n = 0 (mod 625) 和 n - 1 = 0 (mod 16),
要么：
n - 1 = 0 (mod 625) 和 n = 0 (mod 16).
所以在每种情况下我们都有两个方程，具有互质模，求解相同的数 n:
n = 0 (mod 625) 和 n = 1 (mod 16),
要不然
n = 1 (mod 625) 和 n = 0 (mod 16).
现在（在这两种情况下）我们将使用扩展欧几里得算法来找到 m1 和 m2 使得 16*m1 + 625*m2 = 1。结果是-39*16 + 1*625 = 1，从第二种情况引出上面的解B。 （注意：第一种情况会产生 625，其正方形确实以 0625 结尾，但不算作解决方案。）
为了完整起见，这里是扩展欧几里得算法的实现。第二个和第三个输出是 m1 和 m2；在我们的例子中 1 和 -39 以某种顺序排列。
def extended_gcd(a, b):
last_remainder, remainder = abs(a), abs(b)
x, last_x, y, last_y = 0, 1, 1, 0
while remainder:
last_remainder, (quotient, remainder) = remainder, divmod(last_remainder, remainder)
x, last_x = last_x - quotient*x, x
y, last_y = last_y - quotient*y, y
return last_remainder, last_x * ((-1)**(a < 0)), last_y * ((-1)**(b < 0))