寻找一个4位数，其平方是8位数且最后4位数与原数相同。

Question

从我的答案评论中，问题被问到（转述）：

编写一个Python程序，以找到一个4位整数，当它与自己相乘时，得到一个8位整数，其最后4位数字与原始数字相等。

我会发布我的答案，但我更感兴趣的是更加简洁但易于阅读的解决方案！ （新手能理解吗？）

- Aaron N. Brock

---

@xoxel 我的意思是应该通过编程来解决...我会编辑问题以明确说明。 - Aaron N. Brock

这类问题很少见，但在这里确实是相关话题。 - Gabriel

我认为这更适合于编程谜题和代码高尔夫。 - AJF

我觉得有趣的是，一个知道规则的人提出了问题，其他熟悉范围的人回答了问题，另一些人来赞扬并投票支持这个问题和答案，但仍然有一些人无法接受，并希望将其从SO中删除。我觉得这有点不尊重。 - adrin

@OlivierMelançon 我应该指出，在问题被暂停后，我将问题更改为表明我想要“可读性”，它曾经说过“优雅”（如删除线所示）。 - Aaron N. Brock

Answer 1

这是一个不需要任何模块的一行代码解决方案:

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

- Austin

---

从技术角度来讲，如果在1000和3163之间存在一个满足条件的数字，那么这个答案就是错误的，因为它的平方是七位数。 - adrin

@adrin，这是一个很好的发现。也许从“3163”开始迭代会更优化。 - Austin

需要注意的是，3163是10000000（最小的8位数）的平方根，这个数字并非凭空捏造。 - Aaron N. Brock

3163 × 3163 = 10004569，这是最小的8位完全平方数。 - Austin

关于优化循环，可以指出最后一位数字必须是0、1、5或6，因为只有这些数字乘以自己才会在结果的低位上得到它们自己。因此，通过不尝试其他低位数字（2、3、4、7、8、9），可以消除60%的计算量。但我不懂Python，所以不知道如何在您的一行解决方案中实现。 - MarkL

Answer 2

如果您愿意使用第三方库，可以使用 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)

- jpp

---

我清楚地感觉到这个程序似乎过于复杂，但它肯定是有效的 ^^ ! - N.K

说实话，这个问题有歧义。它说“优雅”，这是主观的。如果你是程序员，你可能会觉得JIT编译很优雅：）。即使不优雅，至少它更快。 - jpp

确实是这样^^我并不是有意冒犯的。 - N.K

我同意“优雅”是主观的，但我不确定有没有客观的方法来找到哪个解决方案是“最佳”的。 - Aaron N. Brock

@jpp 我真正想要的是基于“我”的优雅定义的最“优雅”的解决方案！我想我已经把自己逼到了一个角落，下一步明确的步骤是将我的意识转移到计算机中，并创建一个每个人都可以进行优化的API。 - Aaron N. Brock

Answer 3

[近乎]一行代码：

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的回答（字符最少）：

%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)

- adrin

---

对我来说，这算是一行代码，math 应该是语言的一部分。此外，我没有考虑使用 sqrt 函数，在我的答案中，我正在无用地测试平方不是 8 位数字的答案。 - Aaron N. Brock

@theausomes的回答从哪里节省了额外的时间？逻辑上它们看起来差不多，是string转换吗？ - Aaron N. Brock

str 是一项，而从1000开始，而不是3163则是另一项。 - adrin

公平，我已添加了时间。 - adrin

你可以将第一个代码压成一行：print(next(x for x in range(__import__('math').ceil(__import__('math').sqrt(10 ** 7)), __import__('math').floor(__import__('math').sqrt(10 ** 8 - 1))) if x == (x * x) % 10000)) - Gabriel

Answer 4

以下解决方案不如其他答案易读。但是它在效率上的缺失得到了弥补。

暴力方法检查给定范围内的每个数字，使其为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，除了0和1外，最多只有两个解。而任何解都是由较小数字位数的解构建而来。

因此，尽管存在递归，该算法需要O(n)步才能找到解决方案。

现在，每一步都必须执行一些乘法和转换。整数转换的O(n²)，Python中的乘法使用Karatsuba算法，其小于转换。

总体而言，这产生了一个O(n³)的时间复杂度。

通过使用线性整数转换算法可以改进这一点，然后提供O(n^(1 + log(3)))的复杂度。

- Olivier Melançon

---

对于任何 n，最多有 2 种解决方案。我们正在寻找 k^2 = k (mod 10^n) 或等价的 k*(k-1) = 0 (mod 10^n) 的解决方案。这意味着要么 k 是 2^n 的倍数且 k-1 是 5^n 的倍数，要么反之亦然。根据中国剩余定理，这足以确定 k 的值为 2 种可能性之一，其中一种可能会因前导零而被消除。 - user2357112

此外，我们只需要同时跟踪一个候选解决方案，因为如果 k 是一个候选项，另一个就是 (1 - k) % 10**n。 - user2357112

我看到你在 MSE 上得到了类似的回复（包括我可能应该明确提到的 0 和 1 的情况）。至于 O(n^2)，那不太对，因为它似乎忽略了进制转换和乘法的时间复杂度。 - user2357112

等等，你是把所有时间复杂度都乘在一起了吗？那不对啊；你只做了O(n)的进制转换和O(n)的乘法，所以应该是O(n^3)，主要受到进制转换的影响。（无论如何，在运行时间成为问题之前，你都会很快达到递归限制。） - user2357112

哦，是的，我明白你的意思了，转换占主导地位。愚蠢的错误。 - Olivier Melançon

Answer 5

这里是一行代码实现，它可以排除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

当然，你可以把它压缩成一行列表推导式，但那会很丑陋。

现在，我们可以用以下观察结果将多个for循环分开：严格地说，我们只需要从第一个合法的候选者（大于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)

并且这可以被简化为顶部显示的一行（或两行）代码。

更新：正如@mathmandan展示的那样，我们可以进一步改进step = itertools.cycle((1, 624))，消除99.68％的候选项。 并从3750开始搜索。

- smci

---

不错(+1)! 顺便说一下，我相信我有一种方法可以排除每625个候选人中除了2个以外的所有人(大约99.7%)。如果感兴趣，请查看我的答案：https://dev59.com/t6rka4cB1Zd3GeqPc2E2#49682351。 - mathmandan

正如 @mathmandan 所示，我们可以进一步改进为 step = itertools.cycle((1, 624))，消除了99.68%的候选项。并从625 * 6 = 3750开始搜索。 - smci

Answer 6

这里是动态规划版本：

我们从右到左建立，利用这个知识：为了使一个数字平方等于它本身，每个更低位的数字也必须如此（在帖子上，@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)

我们称之为“当前位数”、“当前十进制位数”和“目标十进制位数”：

dynamic([0],0,4)
#[9376]

在不到一秒的时间内，可以在超大的数字上进行良好的工作：

dynamic([0],0,100)
#[3953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625,6046992680891830197061490109937833490419136188999442576576769103890995893380022607743740081787109376]

- jeremycg

---

我很高兴有人和我想到了同样的主意。我正在尝试弄清楚这种方法的时间复杂度。请看我的答案。我知道它最多是O(n²)，但我有一种感觉它比那更好。 - Olivier Melançon

Answer 7

使用取模运算符%而不是字符串的简单一行代码

print [x for x in range(3163, 10000) if x*x % 10000 == x]
# [9376]

范围的下限3163是最小的四位数，其平方是八位数。

- user3386109

---

取模运算符比使用字符串更好，因为你不需要进行转换！ - Aaron N. Brock

Answer 8

我提出的解决方案是：

# 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

- Aaron N. Brock

Answer 9

我们只需要测试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

请继续阅读以获取解释。

从测试所有候选项的暴力列表推导式开始：

from math import ceil

[n for n in xrange(ceil(10**3.5), 10000) if (n*n) % 10000 == n]

将平方根为10的7次方向上取整，得到最接近的整数。

请注意，10000是第一个平方值有9位数字的数字，循环不会测试该数字。

... 或者如果您想尽快找到解决方案并提前终止：

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整除。
• 因此，我们可以将搜索空间限制为只查看有四位数字的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 & 0xf代替n%16。）

但等等！实际上，所有这些都可以用...

中国剩余定理

我们想要找到一个n，使得：

• n = 0 (mod 625) 并且 n - 1 = 0 (mod 16),
• 或者：
• n - 1 = 0 (mod 625) 并且 n = 0 (mod 16)。

因此，在每种情况下，我们有两个具有互质模数的方程式，解决同一个数字n：

"n = 0 (mod 625) and n = 1 (mod 16)"或者"n = 1 (mod 625) and 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))

- mathmandan

---

这很整洁，但太长了，需要更简洁地进行注释。 - smci

对于获取10**3.5的整数上限，from math import ceil, sqrt; ... ceil(10**3.5) - smci

整个侧边栏关于用加法替换乘法的内容是不必要的，而且会掩盖你的重点；在CPU周期中，32位整数的乘法和加法成本相同。 - smci

从编程角度来看，你的方法改进了我的step = itertools.cycle((1, 624))，并且从625 * 6 = 3750开始搜索。 - smci

@smci 感谢您的编辑！ - mathmandan

Answer 10

这里只有一句话，就是：

print(9376)

- Abdelhamid Belarbi

---

这个绝对是性能最好的！ - Aaron N. Brock

这就是为什么“代码高尔夫”交流平台上会有“标准漏洞适用”的原因。不过，我们现在不在“代码高尔夫”交流平台上。 - Cort Ammon

@CortAmmon 这就是为什么这些类型的问题被反对的原因。 - piRSquared

我确定这是OP真实代码中的瓶颈，因此您应该使用sys.stdout.buffer.raw.write(b'9376\n')来减少几微秒的时间。 :P - abarnert