寻找一个能够检测类似于Collatz猜想的序列是否终止的C程序

Question

我正在寻找一个C语言的程序，它可以：

• 扫描一个可以大到10^14的无符号数字
• 如果是偶数除以2
• 否则替换为3*n+3(n为数字被扫描的(，使其成为偶数
• 多做这个根据需要乘以，以查看它在末尾是否等于1。如果是，请打印"是"，否则打印"否">

问题是我不知道什么时候停止操作，我也不确定除了2^x之外的任何数字最后是否可以等于1，但我认为我错了。有人能帮我吗？

Answer 1

一个问题是，在循环查找过程中，您可能会得到一些相当大的数字，这些数字会溢出所有内置类型的C.

相反，你可以用数学方法解决这个问题。还有一个更困难、类似的问题：https://en.wikipedia.org/wiki/Collatz_conjecture，但是这个很容易。考虑3n + 3 = 3(n + 1)-3的倍数。3的倍数不可能是2的幂。

因此，要么初始数字是2的幂(然后打印"是"(，要么永远不会变成2的幂。

#include <stdint.h>
#include <stdio.h>
#include <inttypes.h>
int main() {
uint64_t n;
// get the input
scanf("%" SCNu64, &n);
// detect whether n is a power of 2
while(n > 1) {
if(n % 2 != 0) {
printf("non"); // not a power of 2
return 0;
}
n /= 2;
}
// is a power of 2
printf("yesn");
}