spø*_*ren 5 python primes memoization sequence collatz
我有一个任务,我需要在Python中找到包含超过65个素数的最低Collatz序列.
例如,19的Collatz序列是:
19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
该序列包含7个素数.
我还需要使用memoization,因此它不必运行"年"来找到它.我找到了Collatz序列记忆的代码,但是当我只需要素数时,我无法弄清楚如何让它工作.
这是我发现的Collatz记忆代码:
lookup = {}
def countTerms(n):
if n not in lookup:
if n == 1:
lookup[n] = 1
elif not n % 2:
lookup[n] = countTerms(n / 2)[0] + 1
else:
lookup[n] = countTerms(n*3 + 1)[0] + 1
return lookup[n], n
这是我的素数测试员:
def is_prime(a):
for i in xrange(2,a):
if a%i==0:
#print a, " is not a prime number"
return False
if a==1:
return False
else:
return True
您现有的代码缩进不正确。我认为此任务是一项家庭作业，因此我不会发布完整的工作解决方案，但我会给您一些有用的片段。
\n\n首先，这是一个稍微高效的素性测试器。它不是测试所有小于 的数字是否a是 的因子a，而是测试 的平方根a。
def is_prime(a):\n for i in xrange(2, int(1 + a ** 0.5)):\n if a % i == 0:\n return False\n return True\n请注意，此函数True返回a = 1。没关系，因为您不需要测试 1：您可以将其预加载到lookup字典中：
lookup = {1:0}\n您的countTerms函数需要稍微修改一下，以便在当前为质lookup数时仅将计数加一n。在 Python 中，False有一个数值 0 和True一个数值 1。这在这里非常方便：
def count_prime_terms(n):\n ''' Count the number of primes terms in a Collatz sequence '''\n if n not in lookup:\n if n % 2:\n next_n = n * 3 + 1\n else:\n next_n = n // 2\n\n lookup[n] = count_prime_terms(next_n) + is_prime(n)\n return lookup[n]\n我已将函数名称更改为更加Pythonic。
\n\nFWIW，第一个包含 65 个或更多素数的 Collatz 序列实际上包含 67 个素数。它的种子数量超过 180 万，在检查该种子之前的所有序列时需要进行素性测试的最高数量是 151629574372。完成后，该lookup字典包含 3920492 个条目。
为了回应 James Mills 关于递归的评论，我编写了一个非递归版本，并且为了方便地看到迭代和递归版本都产生相同的结果，我发布了一个完整的工作程序。我上面说过我不会这样做，但我认为现在应该可以这样做，因为 sp\xc3\xb8rreren 已经使用我在原始答案中提供的信息编写了他们的程序。
\n\n我完全同意避免递归是件好事，除非它适合问题域（例如，树遍历）。Python 不鼓励递归 - 它无法优化尾部调用递归，并且它施加了递归深度限制（尽管如果需要，可以修改该限制）。
\n\nCollatz 序列素数计数算法自然是递归表述的，但迭代执行起来并不难 - 我们只需要一个列表来临时保存序列，同时确定其所有成员的素数。确实，这个列表占用了 RAM，但它（可能）在空间方面比递归版本所需的堆栈帧要求要高效得多。
\n\n递归版本在解决OP中的问题时达到了343的递归深度。这完全在默认限制之内，但仍然不好，如果您想搜索包含更多素数的序列，您将达到该限制。
\n\n迭代和递归版本的运行速度大致相同（至少，它们在我的机器上是这样做的）。为了解决 OP 中提到的问题，他们都花费了不到 2 分钟的时间。这比我原来的解决方案要快得多，主要是由于素性测试的优化。
\n\n基本的 Collatz 序列生成步骤已经需要确定数字是奇数还是偶数。显然，如果我们已经知道一个数字是偶数，那么就不需要测试它是否是素数。:) 我们还可以消除对is_prime函数中偶数因子的测试。我们可以通过简单地将 2 的结果加载到缓存中来处理 2 是素数的事实lookup。
与此相关的是，当搜索包含给定数量的素数的第一个序列时，我们不需要测试任何以偶数开头的序列。偶数（除了 2）不会增加序列的素数计数，并且由于这样的序列中的第一个奇数将低于我们当前的数字，因此它的结果将已经在lookup，因此假设我们从3. 如果我们不从 3 开始搜索，我们只需要确保我们的起始种子足够低，这样我们就不会意外地错过包含所需素数数量的第一个序列。采用这种策略不仅减少了所需的时间，还减少了查找缓存中的条目数量。
#!/usr/bin/env python\n\n''' Find the 1st Collatz sequence containing a given number of prime terms\n\n From http://stackoverflow.com/q/29920691/4014959\n\n Written by PM 2Ring 2015.04.29\n\n [Seed == 1805311, prime count == 67]\n'''\n\nimport sys\n\ndef is_prime(a):\n ''' Test if odd `a` >= 3 is prime '''\n for i in xrange(3, int(1 + a ** 0.5), 2):\n if not a % i:\n return 0\n return 1\n\n\n#Track the highest number generated so far; use a list\n# so we don't have to declare it as global...\nhi = [2]\n\n#Cache for sequence prime counts. The key is the sequence seed,\n# the value is the number of primes in that sequence.\nlookup = {1:0, 2:1}\n\ndef count_prime_terms_iterative(n):\n ''' Count the number of primes terms in a Collatz sequence \n Iterative version '''\n seq = []\n while n not in lookup:\n if n > hi[0]:\n hi[0] = n\n\n if n % 2:\n seq.append((n, is_prime(n)))\n n = n * 3 + 1\n else:\n seq.append((n, 0))\n n = n // 2\n\n count = lookup[n]\n for n, isprime in reversed(seq):\n count += isprime\n lookup[n] = count\n\n return count\n\ndef count_prime_terms_recursive(n):\n ''' Count the number of primes terms in a Collatz sequence\n Recursive version '''\n if n not in lookup:\n if n > hi[0]:\n hi[0] = n\n\n if n % 2:\n next_n = n * 3 + 1\n isprime = is_prime(n)\n else:\n next_n = n // 2\n isprime = 0\n lookup[n] = count_prime_terms(next_n) + isprime\n\n return lookup[n]\n\n\ndef find_seed(numprimes, start):\n ''' Find the seed of the 1st Collatz sequence containing\n `numprimes` primes, starting from odd seed `start` '''\n i = start\n mcount = 0\n\n print 'seed, prime count, highest term, dict size'\n while mcount < numprimes:\n count = count_prime_terms(i)\n if count > mcount:\n mcount = count\n print i, count, hi[0], len(lookup)\n i += 2\n\n\n#count_prime_terms = count_prime_terms_recursive\ncount_prime_terms = count_prime_terms_iterative\n\ndef main():\n if len(sys.argv) > 1:\n numprimes = int(sys.argv[1])\n else:\n print 'Usage: %s numprimes [start]' % sys.argv[0]\n exit()\n\n start = int(sys.argv[2]) if len(sys.argv) > 2 else 3 \n\n #Round `start` up to the next odd number\n if start % 2 == 0:\n start += 1\n\n find_seed(numprimes, start)\n\n\nif __name__ == '__main__':\n main()\n当运行时
\n\n$ ./CollatzPrimes.py 65
输出是
\n\nseed, prime count, highest term, dict size\n3 3 16 8\n7 6 52 18\n19 7 160 35\n27 25 9232 136\n97 26 9232 230\n171 28 9232 354\n231 29 9232 459\n487 30 39364 933\n763 32 250504 1626\n1071 36 250504 2197\n4011 37 1276936 8009\n6171 43 8153620 12297\n10971 44 27114424 21969\n17647 48 27114424 35232\n47059 50 121012864 94058\n99151 51 1570824736 198927\n117511 52 2482111348 235686\n202471 53 17202377752 405273\n260847 55 17202377752 522704\n481959 59 24648077896 966011\n963919 61 56991483520 1929199\n1564063 62 151629574372 3136009\n1805311 67 151629574372 3619607\n