{"id":654,"date":"2021-05-05T12:00:00","date_gmt":"2021-05-05T04:00:00","guid":{"rendered":"https:\/\/blog.cruciferslab.net\/?p=654"},"modified":"2024-03-08T11:15:45","modified_gmt":"2024-03-08T03:15:45","slug":"project-euler-%e8%a7%a3%e9%a1%8c%e7%ad%86%e8%a8%98-3-167","status":"publish","type":"post","link":"https:\/\/blog.cruciferslab.net\/?p=654","title":{"rendered":"Project Euler \u89e3\u984c\u7b46\u8a18 (3) &#8211; #167"},"content":{"rendered":"\n<p>\u4f86\u628a\u984c\u865f\u64fa\u5728\u6a19\u984c\u4e0a\u597d\u4e86\u3002\u539f\u672c\u4e0d\u653e\u7684\u539f\u56e0\u662f\u6253\u7b97\u4e00\u7bc7\u53ef\u4ee5\u64e0\u597d\u5e7e\u500b\uff0c\u4e0d\u904e\u5f8c\u4f86\u60f3\u60f3\u6703\u80fd\u5beb\u7b46\u8a18\u7684\u90fd\u61c9\u8a72\u4e0d\u662f\u4e09\u8a00\u5169\u8a9e\u80fd\u89e3\u6c7a\u7684\u6771\u897f\u7684\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><a href=\"https:\/\/projecteuler.net\/problem=167\">#167 Investigating Ulam sequences<\/a> (\u96e3\u5ea6 75%)<\/h2>\n\n\n\n<p>\u6240\u8b02 Ulam sequence \u662f\u6307\u9019\u6a23\u7684\u6578\u5217\uff1a\u7d66\u5b9a\u958b\u982d\u5169\u500b\u6b63\u6574\u6578 a &lt; b\uff0c\u6bcf\u6b21\u90fd\u627e\u5927\u65bc\u6700\u5f8c\u4e00\u9805\u7684\u6574\u6578\u7576\u4e2d\uff0c\u80fd\u5920\u552f\u4e00\u5730\u8868\u793a\u70ba\u4e4b\u524d\u6578\u5217\u7576\u4e2d\u7684\u5169\u9805\u548c\u7684\u6578\u4e2d\u6700\u5c0f\u7684\u90a3\u4e00\u500b\u3002\u984c\u76ee\u7d66\u7684\u4f8b\u5b50\u662f\u6700\u7c21\u55ae\u7684 a=1, b=2 \u6240\u7522\u751f\u7684\u6578\u5217 (<a href=\"http:\/\/oeis.org\/A002858\">OEIS A002858<\/a>)\uff1a1, 2, 3, 4, 6, 8, 11, \u2026\u2026\u3002\u56e0\u70ba 5 = 1+4 = 2+3 \u6709\u5169\u7a2e\u5169\u9805\u548c\u8868\u793a\u6cd5\uff0c\u6240\u4ee5\u4e0d\u5728\u6578\u5217\u4e2d\uff1b\u56e0\u6b64 6 \u5c31\u5728\u6578\u5217\u4e2d\u4e86 (\u53ea\u6709 2+4 \u4e00\u7a2e)\u3002\u4ee4\u9019\u6a23\u7684\u6578\u5217\u7b2c \\(k\\) \u9805\u8a18\u70ba \\(U(a,b)_k\\)\u3002<\/p>\n\n\n\n<p>\u8a66\u6c42 \\(\\sum_{n=2}^{10} U(2,2n+1)_k\\)\uff0c\u5176\u4e2d \\(k=10^{11}\\)\u3002<\/p>\n\n\n\n<p>\u4e00\u822c\u5316\u7684 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Ulam_number\">Ulam sequence<\/a> \u5176\u5be6\u6709\u5f88\u591a\u5f88\u8a6d\u7570\u7684\u6027\u8cea\uff0c\u4f8b\u5982\u55ae\u5c31\u4e0a\u9762\u63d0\u7684 a=1, b=2 \u7522\u751f\u7684\u6578\u5217\u4f86\u8aaa\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u5b83\u662f\u4e00\u500b\u5b8c\u5168\u5e8f\u5217\uff0c\u8868\u793a\u4efb\u4f55\u6b63\u6574\u6578\u90fd\u53ef\u4ee5\u8868\u793a\u6210\u6578\u500b\u9019\u500b\u6578\u5217\u4e2d\u7684\u9805\u7684\u548c\uff1b<\/li>\n\n\n\n<li>\u9664\u4e86\u958b\u982d\u4e09\u9805 1, 2, 3\uff0c\u5176\u4ed6\u4efb\u4f55\u9023\u7e8c\u4e09\u9805\u90fd\u6eff\u8db3\u4e09\u89d2\u4e0d\u7b49\u5f0f\uff1b<\/li>\n\n\n\n<li>\u5728\u6578\u503c\u65b9\u9762\u5b83\u6709\u4e00\u500b\u5f88\u5927\u7565\u7684\u898f\u5f8b\uff1a\u5982\u679c\u628a\u6240\u6709\u6b63\u6574\u6578\u6392\u6210 216 \u500b\u4e00\u6392\uff0c\u9ede\u51fa\u5728\u6578\u5217\u4e2d\u7684\u6578\uff0c\u6703\u767c\u73fe\u5b83\u5011\u5927\u81f4\u5730\u6392\u6210\u5341\u689d\u5e36\u72c0\u5716\uff0c\u5e36\u8207\u5e36\u4e4b\u9593\u6709\u500b\u9084\u4e0d\u932f\u660e\u986f\u7684\u7a7a\u767d\uff0c\u4e5f\u5c31\u662f\u6578\u503c\u4e0a\u5927\u7d04\u6709\u500b\u5dee 21.6 \u5de6\u53f3\u7684\u300c\u9031\u671f\u95dc\u4fc2\u300d\u5728\uff1b<\/li>\n\n\n\n<li>\u5982\u679c\u53ea\u8003\u616e\u6578\u5217\u672c\u8eab\u7684\u8a71\uff0c\u5b83\u4e5f\u88ab\u4eba\u767c\u73fe\u5176\u5085\u7acb\u8449\u8f49\u63db\u7576\u4e2d\u6709\u5169\u500b\u7570\u5e38\u7a81\u51fa\u7684\u983b\u7387\uff1a\u5c0d\u9019\u6578\u5217\u7684\u524d\u5341\u5104\u9805\uff0c\u5b58\u5728\u4e00\u500b\u6578 \\(\\theta\\approx2.5714474995\\)\uff0c\u4f7f\u5f97\u9019\u5341\u5104\u9805\u7576\u4e2d\u9664\u4e86\u56db\u500b\u90fd\u6eff\u8db3 \\(\\cos(\\theta a_n)&lt;0\\)\u3002<\/li>\n<\/ul>\n\n\n\n<p>\u7b49\u7b49\u3002\u4e0d\u904e\u9019\u4e9b\u90fd\u7121\u52a9\u65bc\u6211\u5011\u6c42\u51fa\u7b2c 10<sup>11<\/sup> \u9805\uff0d\uff0d\u9019\u500b\u9805\u6578\u5be6\u5728\u662f\u592a\u5f8c\u9762\u4e86\uff0c\u6f38\u8fd1\u6027\u8cea\u6c92\u8fa6\u6cd5\u7cbe\u6e96\u9ede\u5230\u7279\u5b9a\u7684\u67d0\u4e00\u9805\u4f86\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/projecteuler.net\/profile\/progheal.png\" alt=\"\"\/><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<!--more-->\n\n\n\n<p>\u9019\u984c\u7684\u7dda\u7d22\u5176\u5be6\u5728\u4e0a\u9762\u9023\u7d50\u5230\u7684 Ulam number \u689d\u76ee\u88e1\u5c31\u6709\u63d0\u5230\u4e86\uff1a<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>A sequence of (<em>u<\/em>, <em>v<\/em>)-Ulam numbers is <em>regular<\/em> if the sequence of differences between consecutive numbers in the sequence is eventually periodic. When <em>v<\/em> is an odd number greater than three, the (2, <em>v<\/em>)-Ulam numbers are regular.<\/p>\n<cite>&#8212; \u82f1\u6587\u7dad\u57fa\u767e\u79d1 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Ulam_number\">Ulam number<\/a> \u689d\u76ee<\/cite><\/blockquote>\n\n\n\n<p>\u6b63\u597d\uff0c\u984c\u76ee\u8981\u6c42\u7684\u9019\u500b\u5e8f\u5217\u6709\u500b\u5f88\u7279\u5225\u7684\u6027\u8cea\uff1a\u5982\u679c\u958b\u982d\u5169\u9805\u662f 2 \u548c\u6bd4 3 \u5927\u7684\u4e00\u500b\u5947\u6578\u6642\uff0c\u76f8\u9130\u5169\u9805\u7684\u5dee\u5728\u4e00\u5b9a\u9805\u6578\u4e4b\u5f8c\u6703\u5faa\u74b0\u3002\u56e0\u6b64\u6211\u5011\u53ea\u8981\u80fd\u6c42\u51fa\u9019\u662f\u4ec0\u9ebc\u6a23\u7684\u5faa\u74b0\uff0c\u5c31\u80fd\u76f4\u63a5\u63a8\u7b97\u51fa\u7b2c 10<sup>11<\/sup> \u9805\u662f\u4ec0\u9ebc\u6578\u4e86\u3002<\/p>\n\n\n\n<p>\u9019\u662f\u4ec0\u9ebc\u6a23\u7684\u5faa\u74b0\uff1f\u5c31\u5148\u7c21\u55ae\u4e00\u9ede\uff0c\u770b \\(n=2\\) \u7684\u5e8f\u5217\u9577\u600e\u6a23\uff1a<\/p>\n\n\n\n<p>2, 5, 7, 9, 11, 12, 13, 15, 19, 23, 27, 29, 35, 37, 41, 43, 45, 49, 51, 55, 61, 67, 69, 71, 79, 83, 85, 87, 89, 95, 99, \u2026\u2026<\/p>\n\n\n\n<p>\u2026\u2026\u597d\u50cf\u9664\u4e86 2 \u548c 12 \u4e4b\u5916\u90fd\u662f\u5947\u6578?!<\/p>\n\n\n\n<p>2 \u4e4b\u5f8c\u7684\u4e0b\u4e00\u500b\u5076\u6578\u662f 12 \u5f88\u5bb9\u6613\u770b\u5f97\u51fa\u4f86\uff0c\u4f46\u9019\u4e4b\u5f8c\u70ba\u4ec0\u9ebc\u6703\u4e00\u500b\u5076\u6578\u90fd\u6c92\u6709\u5c31\u5f88\u4ee4\u4eba\u8cbb\u89e3\u4e86\u3002\u4e0d\u904e\u5982\u679c\u5047\u5b9a\u9019\u4e4b\u5f8c\u771f\u7684\u6c92\u6709\u5176\u4ed6\u5076\u6578\uff0c\u90a3\u5947\u6578\u7684\u51fa\u73fe\u6a23\u5f0f\u5c31\u53ef\u4ee5\u7528\u9019\u500b\u6558\u8ff0\u63cf\u8ff0\uff1a\u7576\u5947\u6578 \\(p\\) \u6eff\u8db3 \\(p-2\\) \u548c \\(p-12\\) \u6070\u6709\u4e00\u500b\u5728\u6578\u5217\u4e2d\uff0c\u5247 \\(p\\) \u5c31\u5728\u6578\u5217\u4e2d\u3002<\/p>\n\n\n\n<p>\u56e0\u6b64\u7531 5 \u5230 15 \u9023\u7e8c\u516d\u500b\u5947\u6578\u90fd\u5728\u5176\u4e2d\uff1b5 \u548c 15 \u90fd\u5728\u6240\u4ee5 17 \u4e0d\u5728\u6578\u5217\u4e2d\uff1b7 \u5728\u4f46 17 \u4e0d\u5728\u6240\u4ee5 19 \u5728\uff1b9 \u548c 19 \u90fd\u5728\u6240\u4ee5 21 \u4e0d\u5728\uff1b\u2026\u2026\u3002<\/p>\n\n\n\n<p>\u6216\u8a31\u662f\u56e0\u70ba<a href=\"https:\/\/blog.cruciferslab.net\/?p=599\" data-type=\"post\" data-id=\"599\">\u4e0a\u4e00\u7bc7\u6587\u7ae0<\/a>\u5728\u8ac7\u507d\u96a8\u6a5f\u4e82\u6578\u5427\uff0c\u9019\u6a23\u7684\u7d50\u69cb\u5176\u5be6\u7acb\u523b\u8b93\u6211\u60f3\u5230\u53ea\u6709\u5728\u6587\u7ae0\u4e2d\u63d0\u904e\u540d\u5b57\u7684 LFSR \u7522\u751f\u5668\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">LFSR<\/h2>\n\n\n\n<p>LFSR\uff0c\u5168\u540d Linear Feedback Shift Register (<a href=\"https:\/\/zh.wikipedia.org\/wiki\/%E7%BA%BF%E6%80%A7%E5%8F%8D%E9%A6%88%E7%A7%BB%E4%BD%8D%E5%AF%84%E5%AD%98%E5%99%A8\">\u7dda\u6027\u53cd\u994b\u79fb\u4f4d\u66ab\u5b58\u5668<\/a>)\uff0c\u7dad\u57fa\u767e\u79d1\u4e0a\u5beb\u8aaa\u5b83\u662f\u300c\u7d66\u5b9a\u524d\u4e00\u72c0\u614b\u7684\u8f38\u51fa\uff0c\u5c07\u8a72\u8f38\u51fa\u7684\u7dda\u6027\u51fd\u6578\u518d\u7528\u4f5c\u8f38\u5165\u7684\u79fb\u4f4d\u66ab\u5b58\u5668\u300d\u3002\u9019\u500b\u300c\u66ab\u5b58\u5668\u300d\uff0c\u5b83\u7576\u4e2d\u7684\u4f4d\u5143\u9032\u884c\u300c\u7dda\u6027\u300d\u51fd\u6578\u7d44\u5408\uff0c\u5176\u7d50\u679c\u300c\u53cd\u994b\u300d\u56de\u5230\u539f\u66ab\u5b58\u5668\u4e2d\uff0c\u5c07\u66ab\u5b58\u5668\u4e2d\u7684\u539f\u503c\u300c\u79fb\u4f4d\u300d\u4ee5\u653e\u5165\u65b0\u7d50\u679c\uff0c\u6240\u4ee5\u53eb\u505a\u9019\u500b\u540d\u5b57\u3002\u6700\u5e38\u898b\u7684\u7dda\u6027\u51fd\u6578\u662f XOR\uff0c\u4e5f\u5c31\u662f\u53cd\u994b\u7684\u516c\u5f0f\u5c31\u662f\u66ab\u5b58\u5668\u4e2d\u7684\u67d0\u4e9b\u4f4d\u5143\u9032\u884c XOR \u5f8c\u4f5c\u70ba\u65b0\u7d50\u679c\u79fb\u56de\u66ab\u5b58\u5668\u4e2d\u3002\u7dad\u57fa\u767e\u79d1\u4e0a\u8209\u4e86\u4e00\u500b 16 \u4f4d\u5143\u7684\u4f8b\u5b50\uff0c\u516c\u5f0f\u53d6\u7b2c 11\u300113\u300114\u300116 \u4f4d\u5143\u9032\u884c XOR \u518d\u79fb\u56de\u53bb\u3002<\/p>\n\n\n\n<p>\u6578\u5b78\u4e0a\uff0c\u9019\u6a23\u7684 LFSR \u53ef\u4ee5\u8b49\u660e\u662f \\(GF(2^n)\\) (\u5927\u5c0f\u70ba \\(2^n\\) \u7684\u6709\u9650\u9ad4) \u7684\u64cd\u4f5c\u3002\u4e8b\u60c5\u662f\u9019\u6a23\u7684\uff1aLFSR \u5176\u5be6\u6709\u5169\u7a2e\u5b9a\u7fa9\u578b\u5f0f\uff0c\u4e0a\u9762\u63d0\u7684\u7a31\u505a Fibonacci \u5f0f (\u56e0\u70ba\u5b83\u548c\u8cbb\u6c0f\u6578\u5217\u7684\u905e\u8ff4\u5f0f\u5f88\u50cf\uff0c\u4e0b\u4e00\u9805\u7522\u751f\u4f7f\u7528\u5230\u524d\u9762\u5e7e\u9805\u7684\u904b\u7b97)\uff1b\u53e6\u4e00\u7a2e\u7a31\u505a Galois \u5f0f\uff0c\u5b83\u7684\u5b9a\u7fa9\u662f\u5728\u79fb\u4f4d\u6642\u628a\u79fb\u6389\u7684\u8f38\u51fa\u4f4d\u5143\u548c\u5c0d\u61c9\u4f4d\u7f6e\u7684\u4f4d\u5143\u9032\u884c XOR\u3002\u5982\u679c\u5c0d\u5229\u7528 \\(\\mathbb{Z}_2\\) \u4fc2\u6578\u591a\u9805\u5f0f\u5b9a\u7fa9 \\(GF(2^n)\\) \u7684\u904b\u7b97\u5f88\u719f\u7684\u8a71\uff0c\u5c31\u80fd\u770b\u5f97\u51fa\u4f86 Galois \u5f0f LFSR \u5176\u5be6\u5c31\u662f\u5728\u9019\u7a2e\u904b\u7b97\u4e4b\u4e0b\u300c\u4e58\u300d\u4ee5\u591a\u9805\u5f0f \\(x\\) \u7684\u904b\u7b97 (\u9019\u6642\u6240\u53d6\u7684\u4f4d\u5143\u8b8a\u6210\u4e86\u6709\u9650\u9ad4\u7684\u9664\u591a\u9805\u5f0f)\uff1b\u5b83\u548c\u6709\u9650\u9ad4 (Galois Field) \u4e4b\u9593\u7684\u9019\u7a2e\u76f4\u63a5\u95dc\u9023\u6b63\u662f\u9019\u7a2e\u578b\u5f0f\u88ab\u7a31\u505a Galois \u5f0f\u7684\u539f\u56e0\u3002<\/p>\n\n\n\n<p>\u9019\u5169\u7a2e\u5b9a\u7fa9\u578b\u5f0f\u4e4b\u9593\u6709\u500b\u5f88\u6709\u8da3\u7684\u95dc\u9023\uff1a<strong>\u5b83\u5011\u6240\u6c42\u51fa\u7684\u8f38\u51fa\u4f4d\u5143\u9664\u4e86\u5728\u6642\u9593\u4e0a\u5e73\u79fb\u4e4b\u5916\u662f\u4e00\u6a21\u4e00\u6a23\u7684\u5e8f\u5217<\/strong>\u3002\u9019\u662f\u53ef\u4ee5\u7531\u5167\u90e8\u72c0\u614b\u7684\u5c0d\u61c9\u65b9\u5f0f\u4f86\u8b49\u660e\u7684\uff0c\u4e0d\u904e\u6709\u9ede\u7e41\u7463\u5c31\u7565\u904e\u4e0d\u8ac7\uff1b\u4f46\u9019\u500b\u5c0d\u61c9\u7d66\u4e86\u6211\u5011\u4f7f\u7528\u6709\u9650\u9ad4\u7406\u8ad6\u6c42\u5f97\u5468\u671f\u7684\u6a5f\u6703\uff1a\u6709\u9650\u9ad4\u7406\u8ad6\u544a\u8a34\u6211\u5011\uff0c\u7576\u9664\u591a\u9805\u5f0f \\(p(x)\\) \u662f\u5728 \\(\\mathbb{Z}_2[x]\\) \u4e2d\u7684\u4e0d\u53ef\u7d04\u591a\u9805\u5f0f\u6642\uff0c\u4e58\u4ee5 \\(x\\) \u9019\u500b\u64cd\u4f5c (\u9023\u5e36\u5730\uff0cLFSR \u7684\u64cd\u4f5c) \u6703\u6709\u6700\u5927\u9031\u671f \\(2^n-1\\)\u3002\u9019\u5c31\u662f\u6211\u5011\u60f3\u627e\u7684\u9031\u671f\u6027\u8cea\u3002<\/p>\n\n\n\n<p>\u4ee5\u4e0a\u9762 2, 5 \u958b\u59cb\u7684\u5e8f\u5217\u70ba\u4f8b\uff0c\u82e5\u628a\u9023\u7e8c\u5947\u6578\u6709\u6c92\u6709\u5728\u6578\u5217\u4e2d\u4ee5 1 \u548c 0 \u63cf\u8ff0\u7684\u8a71\uff0c\u5247\u9019\u500b\u6578\u5217\u6b63\u597d\u5c31\u662f\u4ee5 \\(x^6+x+1\\) \u63cf\u8ff0\u7684 LFSR \u5f9e 000001 (\u8868\u793a 5 \u5728\u6578\u5217\u4e2d, \u4f46\u5b83\u524d\u9762\u7684\u5947\u6578\u90fd\u4e0d\u5728) \u958b\u59cb\u6240\u7522\u751f\u7684\u5e8f\u5217\u3002\u7531\u65bc \\(x^6+x+1\\) \u5728 \\(\\mathbb{Z}_2[x]\\) \u4e2d\u4e0d\u53ef\u7d04\uff0c\u56e0\u6b64\u6211\u5011\u7acb\u523b\u5c31\u77e5\u9053 LFSR \u9031\u671f\u662f \\(2^6-1=63\\)\u3002\u9019\u4ee3\u8868\uff0c\u5947\u6578 \\(p\\) \u548c \\(p+63\\times2\\) \u8981\u561b\u90fd\u5728\u6578\u5217\u4e2d\uff0c\u8981\u561b\u90fd\u4e0d\u5728\u6578\u5217\u4e2d\u3002<\/p>\n\n\n\n<p>\u5be6\u969b\u5217\u51fa\u4f86\u770b\u770b\u5427\uff1a\u5b83\u662f <a href=\"http:\/\/oeis.org\/A007300\">OEIS A007300<\/a>\u3002\u53ef\u4ee5\u770b\u5230 5+126=131 \u5230 141 \u4e5f\u662f\u9023\u7e8c\u516d\u500b\u5947\u6578\u51fa\u73fe\uff0c\u800c\u5982\u679c\u628a\u5b83\u8ddf 5 \u958b\u59cb\u7684\u5947\u6578\u4f75\u6392\u7684\u8a71\uff1a<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"raw\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">  5,   7,   9,  11,  13,  15,  19,  23,  27,  29,  35,  37,  41,  43,  45,  49,\n      51,  55,  61,  67,  69,  71,  79,  83,  85,  87,  89,  95,  99, 107, 109, 119,\n131, 133, 135, 137, 139, 141, 145, 149, 153, 155, 161, 163, 167, 169, 171, 175,\n     177, 181, 187, 193, 195, 197, 205, 209, 211, 213, 215, 221, 225, 233, 235, 245,\n...<\/pre>\n\n\n\n<p>\u4e0a\u9762\u9019\u500b\u4f75\u6392\u53ef\u4ee5\u770b\u5230\u524d 32 \u500b\u5947\u6578\u52a0\u4e0a 126 \u6b63\u597d\u5c31\u662f\u63a5\u4e0b\u4f86 32 \u500b\u5947\u6578\u3002\u9019\u5c31\u662f\u4e0a\u9762\u5f15\u6587\u63d0\u5230\u7684\u300cregular\u300d\u6027\u8cea\u3002<\/p>\n\n\n\n<p>\u9019\u500b\u6027\u8cea\u5176\u5be6\u9084\u53ef\u4ee5\u56de\u982d\u8aaa\u660e\u70ba\u4ec0\u9ebc\u5076\u6578\u5728 12 \u4e4b\u5f8c\u5c31\u90fd\u4e0d\u6703\u51fa\u73fe\u4e86\uff1a\u4efb\u610f\u9078\u5927\u65bc 15 \u7684\u516d\u500b\u9023\u7e8c\u5947\u6578 \\(p, p+2, \\dots, p+10\\)\u3002\u5982\u679c\u9019\u516d\u500b\u9023\u7e8c\u5947\u6578\u88e1\u6709\u81f3\u5c11\u5169\u500b\u5728\u6578\u5217\u4e2d\uff0c\u90a3\u5b83\u5011\u548c 5~15 \u4e4b\u9593\u5c31\u6703\u51fa\u73fe\u81f3\u5c11\u5169\u500b \\(p+15\\) \u7684\u7d44\u5408\uff0c\u56e0\u6b64\u4e0d\u5728\u6578\u5217\u4e2d\u3002\u5982\u679c\u53ea\u6709\u4e00\u500b\uff0c\u5b83\u53ea\u6703\u5728\u8de8\u9031\u671f\u9644\u8fd1\u51fa\u73fe (\u4f8b\u5982 119 \u9644\u8fd1\u7684 111~121 \u6216 121~131)\uff1b\u5c0d\u61c9\u8981\u627e\u7684\u5076\u6578\u662f 126\u3001128\u3001\u2026\u2026\u3001136\uff0c\u9019\u4e9b\u5076\u6578\u53ef\u4ee5\u88ab 107 \u6216 109 \u6293\u4f4f\u53e6\u4e00\u500b\u7d44\u5408\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>126 = 119+7 = 107+19<\/li>\n\n\n\n<li>128 = 119+9 = 109+19<\/li>\n\n\n\n<li>130 = 119+11 = 107+23<\/li>\n\n\n\n<li>132 = 119+13 = 109+23<\/li>\n\n\n\n<li>134 = 119+15 = 107+27<\/li>\n\n\n\n<li>136 = 131+5 = 109+27<\/li>\n<\/ul>\n\n\n\n<p>\u56e0\u6b64\u9019\u4e9b\u5076\u6578\u4e5f\u90fd\u4e0d\u6703\u5728\u6578\u5217\u7576\u4e2d\u3002\u7531\u65bc\u5947\u6578\u6709\u9019\u6a23\u7684\u9031\u671f\u6027\uff0c\u540c\u6a23\u7684\u8ad6\u8b49\u53ef\u4ee5\u9069\u7528\u5728\u5176\u4ed6\u9031\u671f\u4e0a\uff0c\u56e0\u6b64\u5c31\u80fd\u5f97\u5230\u7d50\u8ad6\uff1a\u5927\u65bc 12 \u7684\u5076\u6578\u901a\u901a\u4e0d\u6703\u51fa\u73fe\u5728\u6578\u5217\u7576\u4e2d\u3002<sup data-fn=\"4bbcbf8f-d52f-452b-81e1-fddc4ffb0779\" class=\"fn\"><a href=\"#4bbcbf8f-d52f-452b-81e1-fddc4ffb0779\" id=\"4bbcbf8f-d52f-452b-81e1-fddc4ffb0779-link\">1<\/a><\/sup><\/p>\n\n\n\n<p>\u90a3\u9ebc\uff0c\u6211\u5011\u5c31\u80fd\u5f9e\u9019\u88e1\u6c42\u51fa \\(U(2,5)_{10^{11}}\\) \u4e86\uff1a\u9019 \\(10^{11}\\) \u9805\u4e2d\uff0c\u6263\u6389\u5169\u500b\u5076\u6578\uff0c\u5269\u4e0b\u7684\u6bcf 32 \u500b\u4e00\u7d44\u3002\u505a\u9664\u6cd5\u5f97\u5230 \\((10^{11}-2)\\div32=3,124,999,999\\cdots30\\)\uff0c\u5373\u662f\u6240\u6c42\u70ba\u7b2c 3,124,999,999+1=3,125,000,000 \u7d44\uff0c\u7576\u4e2d\u7684\u7b2c 30 \u500b\u6578\u3002\u7b2c\u4e00\u7d44\u7684\u7b2c 30 \u500b\u6578\u662f 107\uff0c\u6240\u4ee5\u7b2c 3,125,000,000 \u7d44\u7684\u7b2c 30 \u500b\u6578\u5c31\u662f<br>$$U(2,5)_{10^{11}}=107+3,124,999,999\\times126=393,749,999,981$$<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u53ef\u7d04\u591a\u9805\u5f0f<\/h2>\n\n\n\n<p>\u55ef\uff0c\u9451\u65bc\u4e0d\u634f\u4ed6\u539f\u5247\uff0c\u4e0a\u9762\u6211\u65e2\u7136\u5beb\u51fa\u90e8\u4efd\u7b54\u6848\u51fa\u4f86\u4e86\u5c31\u8868\u793a\u9019\u984c\u5176\u5be6\u9084\u6709\u5176\u4ed6\u554f\u984c\u3002<\/p>\n\n\n\n<p>\u4f86\u770b\u4e0b\u4e00\u7d44 \\(U(2,7)\\) \u5427\u3002\u985e\u4f3c\u7684\u65b9\u5f0f\u53ef\u4ee5\u767c\u73fe\u5b83\u662f\u4ee5 \\(x^8+x+1\\) \u63cf\u8ff0\u7684 LFSR (\u56e0\u70ba\u552f\u4e8c\u7684\u5076\u6578\u662f 2 \u548c 16)\uff0c\u540c\u6a23\u7531 00000001 \u958b\u59cb (\u8868\u793a 7 \u5728\u6578\u5217\u4e2d)\u3002\u4f46\u662f\u554f\u984c\u4f86\u4e86\uff0c\u5728 \\(\\mathbb{Z}_2[x]\\) \u7576\u4e2d\u6709\uff1a<br>$$x^8+x+1=(x^2+x+1)(x^6+x^5+x^3+x^2+1)$$<br>\u56e0\u6b64\u5b83\u7684\u9031\u671f\u4e26\u4e0d\u662f \\(2^8-1=127\\)\u3002<\/p>\n\n\n\n<p>\u90a3\u9019\u8981\u600e\u9ebc\u6c42\u9031\u671f\uff1f\u9019\u88e1\u7d66\u6211\u5011\u7dda\u7d22\u7684\u662f<a href=\"https:\/\/zh.wikipedia.org\/wiki\/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86\">\u4e2d\u570b\u5269\u9918\u5b9a\u7406<\/a>\u3002\u9084\u8a18\u5f97\u4e0a\u9762\u6211\u5011\u8aaa\u904e Fibonacci LFSR \u7684\u64cd\u4f5c\u53ef\u4ee5\u5c0d\u61c9\u5230 Galois LFSR (\u53ca\u5176\u5c0d\u61c9\u7684\u6709\u9650\u9ad4\u4e2d) \u4e58\u4ee5 \\(x\\) \u7684\u64cd\u4f5c\u55ce\uff1f\u5982\u679c\u9664\u6cd5\u7fa4\u7684\u9664\u5f0f \\(p(x)\\) \u53ef\u5206\u89e3\u4f46\u6c92\u6709\u56e0\u5f0f\u91cd\u8986\u7684\u8a71\uff0c\u90a3\u9664\u6cd5\u7fa4\u4e2d\u9664\u4ee5 \\(p(x)\\) \u53d6\u9918\u7684\u64cd\u4f5c\u5176\u5be6\u53ef\u4ee5\u5206\u5225\u5c0d\u5176\u56e0\u5f0f\u53d6\u9918\uff0c\u7136\u5f8c\u518d\u7531\u4e2d\u570b\u5269\u9918\u5b9a\u7406\u5408\u4f75\u8d77\u4f86\u3002\u9019\u6a23\u4e00\u4f86\uff0c\u4e58\u4ee5 \\(x\\) \u518d\u9664\u4ee5 \\(p(x)\\) \u53d6\u9918\u64cd\u4f5c\u7684\u5faa\u74b0\u5c31\u80fd\u5920\u300c\u5206\u89e3\u300d\u6210\u5c0d\u56e0\u5f0f\u53d6\u9918\u7684\u5faa\u74b0\uff0c\u518d\u5408\u4f75\u8d77\u4f86\u3002<\/p>\n\n\n\n<p>\u4ee5 \\(x^8+x+1=(x^2+x+1)(x^6+x^5+x^3+x^2+1)\\) \u70ba\u4f8b\uff0c\u9019\u4ee3\u8868\u5b83\u7684\u9031\u671f\u53ef\u4ee5\u62c6\u6210\u9664\u4ee5 \\(x^2+x+1\\) \u548c\u9664\u4ee5 \\(x^6+x^5+x^3+x^2+1\\) \u7684\u5169\u500b\u9031\u671f\uff1b\u9019\u5169\u500b\u90fd\u662f\u4e0d\u53ef\u7d04\u591a\u9805\u5f0f\u4e86\uff0c\u6240\u4ee5\u53ef\u4ee5\u5957\u5df2\u77e5\u7d50\u8ad6\uff0c\u524d\u8005\u9031\u671f \\(2^2-1=3\\)\uff0c\u5f8c\u8005\u9031\u671f \\(2^6-1=63\\)\uff0c\u56e0\u6b64\u5168\u90e8\u7684\u9031\u671f\u5c31\u662f\u9019\u5169\u8005\u7684\u6700\u5c0f\u516c\u500d\u6578\uff0c\u4e5f\u5c31\u662f 63\u3002<\/p>\n\n\n\n<p>\u90a3\u9ebc\u6211\u5011\u5c31\u53ea\u8981\u5c0d\u6240\u6709 \\(x^{2n+2}+x+1\\) \u5206\u89e3\uff0c\u6293\u51fa\u4e0d\u53ef\u7d04\u56e0\u5f0f\u7684\u6700\u9ad8\u6b21\u6c42\u500b\u5225\u9031\u671f (\u597d\u5728\u56e0\u5f0f\u90fd\u6c92\u6709\u91cd\u8986\u7684)\uff0c\u5c31\u80fd\u6c42\u5f97 LFSR \u9031\u671f\u4e86\u3002\u77e5\u9053 LFSR \u9031\u671f\u4ee3\u8868\u6bcf\u4e00\u6bb5\u5dee\u662f\u5df2\u77e5\uff0c\u90a3\u5c31\u53ea\u8981\u5beb\u652f\u7a0b\u5f0f\u7b97\u904e\u53bb\uff0c\u6c42\u51fa\u9019\u4e00\u6bb5\u6578\u5b57\u5167\u6709\u591a\u5c11\u6578\u6709\u9078\u4e2d\u5c31\u662f\u6578\u5217\u9031\u671f\uff1b\u6709\u4e86\u6578\u5217\u9031\u671f\uff0c\u518d\u7528\u548c\u4e0a\u9762\u4e00\u6a23\u7684\u65b9\u5f0f\u5c31\u80fd\u6c42\u5f97\u6240\u8981\u6c42\u7684\u7b2c \\(10^{11}\\) \u9805\u4e86\u3002<\/p>\n\n\n\n<p>\u63d0\u4ef6\u7a0d\u5fae\u503c\u5f97\u4e00\u63d0\u7684\u4e8b\u7576\u7d50\u5c3e\uff1a\u53ea\u8981\u4e0a\u9762\u62c6\u5206\u56e0\u5f0f\u5f8c\u7684\u5404\u9031\u671f\u6c92\u6709\u516c\u56e0\u6578\uff0c\u6240\u6c42\u51fa\u4f86\u7684\u7b2c \\(10^{11}\\) \u9805\u7684\u503c\u90fd\u6703\u7d04\u7565\u5728 \\(4\\times10^{11}\\) \u5de6\u53f3\u3002\u9019\u5176\u5be6\u662f\u53ef\u4ee5\u89e3\u91cb\u7684\uff1a\u5728\u55ae\u4e00\u56e0\u5f0f\u7684\u5168\u9031\u671f\u7576\u4e2d\uff0c0 \u6703\u6bd4 1 \u5c11\u4e00\u500b (\u56e0\u70ba\u9019\u500b\u5168\u9031\u671f\u53ea\u6709\u591a\u9805\u5f0f 0 \u7121\u6cd5\u7372\u5f97)\uff0c\u4e5f\u5c31\u662f 1 \u6703\u5927\u7d04\u6709\u4e00\u534a\uff0c\u90a3\u8981\u53d6\u5230 \\(10^{11}\\) \u500b\u5947\u6578\uff0c\u5c31\u8981\u6383\u904e\u5927\u7d04 \\(2\\times10^{11}\\) \u500b\u5947\u6578\uff0c\u81ea\u7136\u7d04\u7565\u5728 \\(4\\times10^{11}\\) \u9644\u8fd1\u4e86\u3002\u591a\u500b\u9031\u671f\u5982\u679c\u6c92\u6709\u516c\u56e0\u6578\uff0c\u90a3\u6240\u6709\u9031\u671f\u7684\u6240\u6709\u7d44\u5408\u90fd\u6703\u8dd1\u904e\u4e00\u6b21\uff0c\u56e0\u6b64 1 \u5927\u7d04\u6709\u4e00\u534a\u7684\u9019\u500b\u4f30\u8a08\u4ecd\u7136\u6210\u7acb\uff1b\u4f46\u5982\u679c\u6709\u516c\u56e0\u6578\u5247\u5c31\u6703\u6709\u6c92\u51fa\u73fe\u904e\u7684\u7d44\u5408\uff0c\u7e3d\u9ad4\u4f86\u8aaa 1 \u7684\u500b\u6578\u5c31\u6703\u5c11\u65bc\u9031\u671f\u7684\u4e00\u534a\uff0c\u56e0\u6b64\u7d50\u679c\u5c31\u6703\u6bd4 \\(4\\times10^{11}\\) \u5927\u5f88\u591a\u4e86\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u8a3b\u8173<\/h2>\n\n\n<ol class=\"wp-block-footnotes\"><li id=\"4bbcbf8f-d52f-452b-81e1-fddc4ffb0779\">\u5c0d\u8b49\u660e\u7d30\u7bc0\u6709\u4e9b\u654f\u92b3\u7684\u4eba\u53ef\u80fd\u6ce8\u610f\u5230\u6211\u9019\u88e1\u7684\u5beb\u6cd5\u5176\u5be6\u6709\u9ede\u602a\u602a\u7684\u3002\u7406\u8ad6\u4e0a\uff0c\u6b63\u78ba\u7684\u8b49\u660e\u6703\u9700\u8981\u7528\u6578\u5b78\u6b78\u7d0d\u6cd5\uff0c\u5047\u8a2d\u9019\u5169\u500b\u6027\u8cea (\u5076\u6578\u53ea\u6709 2 \u548c 12\u3001\u5947\u6578\u9075\u5faa\u9019 32 \u500b\u6578\u4e00\u300c\u5faa\u74b0\u300d\u7684\u65b9\u5f0f) \u5c0d\u67d0\u500b\u6578\u4ee5\u4e0b\u6210\u7acb\uff0c\u7136\u5f8c\u7528\u5176\u63a8\u51fa\u5927\u4e00\u4e9b\u4e9b\u7684\u7bc4\u570d\u6210\u7acb\uff0c\u6700\u5f8c\u7528\u6578\u5b78\u6b78\u7d0d\u6cd5\u5f97\u5230\u9019\u5169\u500b\u6027\u8cea\u5168\u90e8\u6210\u7acb\uff1b\u4e00\u4e9b\u7d30\u7bc0\u50cf\u662f\u5982 119 \u9019\u7a2e\u300c\u5b64\u7acb\u300d\u7684\u6578\uff0c\u4e5f\u80fd\u8b49\u660e\u5b83\u524d\u5169\u9805\u4e00\u5b9a\u6703\u662f\u9023\u7e8c\u5169\u500b\u5947\u6578\uff0c\u9032\u800c\u5b8c\u6210\u8b49\u660e\u3002\u9019\u500b\u63a8\u8ad6\u908f\u8f2f\u8a8d\u771f\u770b\u7684\u8a71\u6703\u767c\u73fe\u5b83\u5176\u5be6\u662f\u4ea4\u932f\u5f0f\u7684\uff1a\u5947\u6578\u6027\u8cea\u63a8\u51fa\u5927\u4e00\u4e9b\u7bc4\u570d\u7684\u5076\u6578\u6027\u8cea\u3001\u5076\u6578\u6027\u8cea\u63a8\u51fa\u5927\u4e00\u9ede\u7684\u5947\u6578\u6027\u8cea\u3002\u8981\u7528\u9019\u7a2e\u884c\u6587\u65b9\u5f0f\u7684\u8a71\u6703\u8b93\u6574\u4e32\u6587\u7ae0\u88ab\u9019\u7a2e\u4ea4\u932f\u5f0f\u7684\u908f\u8f2f\u7d66\u5361\u4f4f\uff0c\u9084\u4e0d\u5982\u5148\u8b1b\u5b8c\u6bd4\u8f03\u9ebb\u7169\u7684\u5947\u6578\u6027\u8cea\uff0c\u518d\u56de\u982d\u628a\u6bd4\u8f03\u7c21\u55ae\u7684\u5076\u6578\u6027\u8cea\u88dc\u5b8c\u3002 <a href=\"#4bbcbf8f-d52f-452b-81e1-fddc4ffb0779-link\" aria-label=\"\u8fd4\u56de\u8a3b\u8173\u53c3\u7167 1\">\u21a9\ufe0e<\/a><\/li><\/ol>","protected":false},"excerpt":{"rendered":"<p>\u4f86\u628a\u984c\u865f\u64fa\u5728\u6a19\u984c\u4e0a\u597d\u4e86\u3002\u539f\u672c\u4e0d\u653e\u7684\u539f\u56e0\u662f\u6253\u7b97\u4e00\u7bc7\u53ef\u4ee5\u64e0\u597d\u5e7e\u500b\uff0c\u4e0d\u904e\u5f8c\u4f86\u60f3\u60f3\u6703\u80fd\u5beb\u7b46\u8a18\u7684\u90fd\u61c9\u8a72\u4e0d\u662f\u4e09\u8a00\u5169\u8a9e\u80fd\u89e3\u6c7a [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":"[{\"content\":\"\u5c0d\u8b49\u660e\u7d30\u7bc0\u6709\u4e9b\u654f\u92b3\u7684\u4eba\u53ef\u80fd\u6ce8\u610f\u5230\u6211\u9019\u88e1\u7684\u5beb\u6cd5\u5176\u5be6\u6709\u9ede\u602a\u602a\u7684\u3002\u7406\u8ad6\u4e0a\uff0c\u6b63\u78ba\u7684\u8b49\u660e\u6703\u9700\u8981\u7528\u6578\u5b78\u6b78\u7d0d\u6cd5\uff0c\u5047\u8a2d\u9019\u5169\u500b\u6027\u8cea (\u5076\u6578\u53ea\u6709 2 \u548c 12\u3001\u5947\u6578\u9075\u5faa\u9019 32 \u500b\u6578\u4e00\u300c\u5faa\u74b0\u300d\u7684\u65b9\u5f0f) \u5c0d\u67d0\u500b\u6578\u4ee5\u4e0b\u6210\u7acb\uff0c\u7136\u5f8c\u7528\u5176\u63a8\u51fa\u5927\u4e00\u4e9b\u4e9b\u7684\u7bc4\u570d\u6210\u7acb\uff0c\u6700\u5f8c\u7528\u6578\u5b78\u6b78\u7d0d\u6cd5\u5f97\u5230\u9019\u5169\u500b\u6027\u8cea\u5168\u90e8\u6210\u7acb\uff1b\u4e00\u4e9b\u7d30\u7bc0\u50cf\u662f\u5982 119 \u9019\u7a2e\u300c\u5b64\u7acb\u300d\u7684\u6578\uff0c\u4e5f\u80fd\u8b49\u660e\u5b83\u524d\u5169\u9805\u4e00\u5b9a\u6703\u662f\u9023\u7e8c\u5169\u500b\u5947\u6578\uff0c\u9032\u800c\u5b8c\u6210\u8b49\u660e\u3002\u9019\u500b\u63a8\u8ad6\u908f\u8f2f\u8a8d\u771f\u770b\u7684\u8a71\u6703\u767c\u73fe\u5b83\u5176\u5be6\u662f\u4ea4\u932f\u5f0f\u7684\uff1a\u5947\u6578\u6027\u8cea\u63a8\u51fa\u5927\u4e00\u4e9b\u7bc4\u570d\u7684\u5076\u6578\u6027\u8cea\u3001\u5076\u6578\u6027\u8cea\u63a8\u51fa\u5927\u4e00\u9ede\u7684\u5947\u6578\u6027\u8cea\u3002\u8981\u7528\u9019\u7a2e\u884c\u6587\u65b9\u5f0f\u7684\u8a71\u6703\u8b93\u6574\u4e32\u6587\u7ae0\u88ab\u9019\u7a2e\u4ea4\u932f\u5f0f\u7684\u908f\u8f2f\u7d66\u5361\u4f4f\uff0c\u9084\u4e0d\u5982\u5148\u8b1b\u5b8c\u6bd4\u8f03\u9ebb\u7169\u7684\u5947\u6578\u6027\u8cea\uff0c\u518d\u56de\u982d\u628a\u6bd4\u8f03\u7c21\u55ae\u7684\u5076\u6578\u6027\u8cea\u88dc\u5b8c\u3002\",\"id\":\"4bbcbf8f-d52f-452b-81e1-fddc4ffb0779\"}]"},"categories":[8,3,4],"tags":[],"class_list":["post-654","post","type-post","status-publish","format-standard","hentry","category-projecteuler","category-math","category-programming"],"_links":{"self":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/654","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=654"}],"version-history":[{"count":28,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/654\/revisions"}],"predecessor-version":[{"id":1752,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/654\/revisions\/1752"}],"wp:attachment":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=654"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=654"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=654"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}