当前位置：文江博客话题详情

任意数字行的几何级数

发布于 2024-09-25 14:33:45 字数 381 浏览 9 评论 0原文

我可以拥有由 2 到 10 个数字组成的任何数字行。从这一行开始，我必须得到几何级数。

例如：给定数字行：125 5 625 我必须得到答案5。行：128 8 512 我必须得到答案4。

你能帮我个忙吗？我不求程序，只求一个提示，我想自己理解，自己写一段代码，但是妈的，我想了一整天，也想不出来。

谢谢。

不要写整个程序！

伙计们，你们不明白，我不能简单地进行除法。我实际上必须得到几何级数+显示所有数字。在 128 8 512 行中，所有数字均为：8 32 128 512

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

方觉久 2024-10-02 14:33:45

赛斯的答案是正确的。我将这个答案留在这里是为了帮助详细说明为什么 128 8 512 的答案是 4，因为人们似乎对此遇到了麻烦。

等比级数的元素可以写成 c*b^n 的形式，其中 b 是您要查找的数字（b 也是必然大于 1)，c 是一个常数，n 是某个任意数字。

因此，最好的选择是从最小的数字开始，将其分解并查看所有可能的解决方案，将其写入 c*b^n 形式，然后使用该 b关于剩余的数字。返回有效的最大结果。

因此，对于您的示例：

125 5 625

从 5 开始。5 是质数，因此只能用一种方式编写：5 = 1*5^1。所以你的 b 是 5。你现在可以停下来，假设你知道该行实际上是几何的。如果您需要确定它是否是几何图形，请在其余数字上测试 b。

128 8 512

8 可以用多种方式编写：8 = 1*8^1、8 = 2*2^2、8 = 2*4^1，8 = 4*2^1。因此，b 具有三个可能的值，c 具有几个不同的选项。首先尝试最大的。 8 不起作用。尝试4。有用！ 128 = 2*4^3 和 512 = 2*4^4。因此，b 为 4，c 为 2。

3 15 375

这个有点意思，因为第一个数字是素数，但不是 b，而是 c。因此，您需要确保如果您的第一个 b 候选数字对其余数字不起作用，您必须查看下一个最小的数字并将其分解。所以在这里你可以分解 15： 15 = 15*?^0 （退化情况），15 = 3*5^1，15 = 5*3 ^1，15 = 1*15^1。答案是 5，3 = 3*5^0，所以它是有效的。

Seth's answer is the right one. I'm leaving this answer here to help elaborate on why the answer to 128 8 512 is 4 because people seem to be having trouble with that.

A geometric progression's elements can be written in the form c*b^n where b is the number you're looking for (b is also necessarily greater than 1), c is a constant and n is some arbritrary number.

So the best bet is to start with the smallest number, factorize it and look at all possible solutions to writing it in the c*b^n form, then using that b on the remaining numbers. Return the largest result that works.

So for your examples:

125 5 625

Start with 5. 5 is prime, so it can be written in only one way: 5 = 1*5^1. So your b is 5. You can stop now, assuming you know the row is in fact geometric. If you need to determine whether it's geometric then test that b on the remaining numbers.

128 8 512

8 can be written in more than one way: 8 = 1*8^1, 8 = 2*2^2, 8 = 2*4^1, 8 = 4*2^1. So you have three possible values for b, with a few different options for c. Try the biggest first. 8 doesn't work. Try 4. It works! 128 = 2*4^3 and 512 = 2*4^4. So b is 4 and c is 2.

3 15 375

This one is a bit mean because the first number is prime but isn't b, it's c. So you'll need to make sure that if your first b-candidate doesn't work on the remaining numbers you have to look at the next smallest number and decompose it. So here you'd decompose 15: 15 = 15*?^0 (degenerate case), 15 = 3*5^1, 15 = 5*3^1, 15 = 1*15^1. The answer is 5, and 3 = 3*5^0, so it works out.

回复收藏 0 原文

已下线请稍等 2024-10-02 14:33:45

编辑：我认为现在应该是正确的。

该算法不依赖因式分解，仅依赖欧几里得算法及其近似变体。这使得它在数学上比使用因式分解的解决方案稍微复杂一些，但速度会快得多。如果您了解欧几里得算法和对数，那么数学应该不是问题。

(1) 对数字集进行排序。您有以下形式的数字 ab^{n1} < ..< ab^{nk}。

示例： (3 * 2, 3*2^5, 3*2^7, 3*2^13)

(2) 形成一个新列表，其第 (n+1) 个元素中的第 n 个元素排序列表的元素除以第 (n) 个元素。您现在有 b^{n2 - n1}、b^{n3 - n2}、...、b^{nk - n(k-1)}。

（续）示例：(2^4, 2^2, 2^6)

定义 d_i = n_(i+1) - n_i （不要对此进行编程 --即使您想也不能这样做，因为 n_i 是未知的 - 这只是为了解释程序如何工作）。

（续）示例：d_1 = 4, d_2 = 2, d_3 = 6

请注意，在我们的示例问题中，我们可以自由选择 (a = 3, b = 2)< /code> 或 (a = 3/2, b = 4)。底线是“真实”b 的任何幂，它可以划分步骤 (2) 中列表中的所有条目，这就是正确答案。由此可见，我们可以将 b 求除所有 d_i 的任何幂（在本例中为除 4、2 和 6 的任何幂）。问题是我们既不知道 b 也不知道 d_i。但如果我们让m = gcd(d_1, ... d_(k-1))，那么我们就可以找到b^m，这就足够了。

注意：给定 b^i 和 b^j，我们可以使用以下方法找到 b^gcd(i, j)：

log( b^i) / log(b^j) = (i log b) / (j log b) = i/j

这允许我们使用欧几里得算法的修改版本来查找 b^ gcd(i, j) 。 “作用”全部在指数中：加法已被乘法取代，乘法被取幂，商（因此）被对数取代：

import math
def power_remainder(a, b):
    q = int(math.log(a) / math.log(b))
    return a / (b ** q)        

def power_gcd(a, b):
    while b != 1:
    a, b = b, power_remainder(a, b)
    return a

(3) 由于原始集合的所有元素因 r = b 的幂而异^gcd(d_1, ..., d_(k-1))，根据需要，它们都是 cr^n 形式。但是，c 可能不是整数。让我知道这是否有问题。

Edit: I think this should be correct now.

This algorithm does not rely on factoring, only on the Euclidean Algorithm, and a close variant thereof. This makes it slightly more mathematically sophisticated then a solution that uses factoring, but it will be MUCH faster. If you understand the Euclidean Algorithm and logarithms, the math should not be a problem.

(1) Sort the set of numbers. You have numbers of the form ab^{n1} < .. < ab^{nk}.

Example: (3 * 2, 3*2^5, 3*2^7, 3*2^13)

(2) Form a new list whose nth element of the (n+1)st element of the sorted list divided by the (n)th. You now have b^{n2 - n1}, b^{n3 - n2}, ..., b^{nk - n(k-1)}.

(Continued) Example: (2^4, 2^2, 2^6)

Define d_i = n_(i+1) - n_i (do not program this -- you couldn't even if you wanted to, since the n_i are unknown -- this is just to explain how the program works).

(Continued) Example: d_1 = 4, d_2 = 2, d_3 = 6

Note that in our example problem, we're free to take either (a = 3, b = 2) or (a = 3/2, b = 4). The bottom line is any power of the "real" b that divides all entries in the list from step (2) is a correct answer. It follows that we can raise b to any power that divides all the d_i (in this case any power that divides 4, 2, and 6). The problem is we know neither b nor the d_i. But if we let m = gcd(d_1, ... d_(k-1)), then we CAN find b^m, which is sufficient.

NOTE: Given b^i and b^j, we can find b^gcd(i, j) using:

log(b^i) / log(b^j) = (i log b) / (j log b) = i/j

This permits us to use a modified version of the Euclidean Algorithm to find b^gcd(i, j). The "action" is all in the exponents: addition has been replaced by multiplication, multiplication with exponentiation, and (consequently) quotients with logarithms:

import math
def power_remainder(a, b):
    q = int(math.log(a) / math.log(b))
    return a / (b ** q)        

def power_gcd(a, b):
    while b != 1:
    a, b = b, power_remainder(a, b)
    return a

(3) Since all the elements of the original set differ by powers of r = b^gcd(d_1, ..., d_(k-1)), they are all of the form cr^n, as desired. However, c may not be an integer. Let me know if this is a problem.

回复收藏 0 原文