C++ 中的凯内亚数

Kynea 数 是数学中一类特殊的数，定义为以下形式的数：

Kn=(2n+1)2−2

其中 n 是一个非负整数。这些数具有独特的性质，是数论研究的一部分。

理解 Kynea 数

为了更好地理解 Kynea 数，我们来分解它们的数学表达式：

1. 基本表达式： 从 2n 开始，涉及指数运算。
2. 增量： 将 1 添加到 2n，得到 2n + 1。
3. 结果平方： 将和平方，得到 (2n+1)2。
4. 减去 2： 最后，减去 2 以计算 Kynea 数。

例如

• 对于 n = 0：K0 = (2⁰ + 1)² −2 = (1 + 1)² −2 = 4 − 2 = 2。
• 对于 n = 1：K1 = (2¹ + 1)² −2 = (2 + 1)² −2 = 9 − 2 = 7。
• 对于 n = 2：K2 = (2² + 1)² −2 = (4 + 1)² −2 = 25 − 2 = 23。

Kynea 数的主要特征

1. 增长： 随着 n 的增加，由于平方运算，Kynea 数呈指数级增长。
2. 奇偶性： 所有 Kynea 数都是奇数，因为 (2n+1)2 项总是奇数，而从奇数中减去 2 仍然是奇数。
3. 应用： Kynea 数在素性测试、序列生成和密码学研究中具有重要意义。

示例

让我们以一个例子来说明 C++ 中的 Kynea 数。

输出

Kynea numbers up to n = 5 are:
K_0 = 2
K_1 = 7
K_2 = 23
K_3 = 79
K_4 = 287
K_5 = 1087

算法

理解公式。Kynea 数公式是：

Kn=(2ⁿ+1)²−2

此公式计算给定值的 Kynea 数。

2ⁿ：将 2 提升到 n 次方。

+1：将 1 加到 2ⁿ 的结果上。

2 (平方)：将上一步的值平方。

-2：减去 2 得到最终的 Kynea 数。

确定计算范围： 我们直接决定要计算多少个 Kynea 数，而不是等待用户输入。例如，如果范围是从 n=0 到 n=5，程序将计算前 6 个 Kynea 数。

计算每个 n 的 Kynea 数

对于范围内的每个 n：

1. 将 2 提升到 n 次方：首先计算 2ⁿ。随着 n 的增加，这个值会迅速增长。
2. 加 1：将 1 加到 2ⁿ 的结果上，得到 2ⁿ + 1。
3. 平方该值：将 (2ⁿ + 1) 自乘，得到 (2ⁿ + 1)²。
4. 减 2：最后，减去 2 以计算 K_n = (2ⁿ + 1)² - 2。

存储结果： 将计算出的 Kynea 数存储在集合中（例如列表或向量）。这有助于跟踪所有数字并使它们更容易在以后显示。

显示结果： 对于每个 Kynea 数，打印其位置 n 和相应的 K_n 值。这显示了 n 与快速增长的 Kynea 数之间的关系。

复杂度分析

时间复杂度

计算 Kynea 数的时间复杂度是 O(n)，用于生成 n 个数。对于每个数，使用 pow() 函数计算 2n 的时间复杂度是 O(log n)。由于这重复了 n 次，因此总时间复杂度变为 O(n. log n)。

空间复杂度

Kynea 数算法的空间复杂度是 O(n)，因为 Kynea 数存储在向量中。每个数都存储在内存中，因此随着计算数量的增长，所需的空间与输入限制 n 的大小呈线性增长。