Sisyphus sequence: Difference between revisions

Content added Content deleted

Inline

@@ Line 196: / Line 196: @@
 Integers in 1..250 that occur most often ( 6 times ) up to element 10000000:
 57 65 85 114 125 130 170 228
+</pre>
+=={{header|C++}}==
+{{libheader|Primesieve}}
+<syntaxhighlight lang="cpp">#include <algorithm>
+#include <iomanip>
+#include <iostream>
+#include <primesieve.hpp>
+class sisyphus_iterator {
+public:
+    uint64_t next() {
+        uint64_t n = next_;
+        if (next_ % 2 == 0) {
+            next_ /= 2;
+        } else {
+            prime_ = pi_.next_prime();
+            next_ += prime_;
+        }
+        return n;
+    }
+    uint64_t prime() const { return prime_; }
+private:
+    primesieve::iterator pi_;
+    uint64_t next_ = 1;
+    uint64_t prime_ = 0;
+};
+int main() {
+    std::cout.imbue(std::locale(""));
+    sisyphus_iterator si;
+    int found[250] = {};
+    std::cout << "The first 100 members of the Sisyphus sequence are:\n";
+    uint64_t count = 1;
+    const uint64_t limit = 100000000;
+    for (uint64_t n = 1000; n <= limit; ++count) {
+        uint64_t next = si.next();
+        if (next < 250)
+            ++found[next];
+        if (count <= 100) {
+            std::cout << std::setw(3) << next << (count % 10 == 0 ? '\n' : ' ');
+            if (count == 100)
+                std::cout << '\n';
+        } else if (count == n) {
+            std::cout << std::setw(11) << n << "th member is " << std::setw(13)
+                      << next << " and highest prime needed is "
+                      << std::setw(11) << si.prime() << '\n';
+            n *= 10;
+        }
+    }
+    auto f = [&found](int n) {
+        bool first = true;
+        for (int i = 1; i < 250; ++i) {
+            if (found[i] == n) {
+                if (first)
+                    first = false;
+                else
+                    std::cout << ", ";
+                std::cout << i;
+            }
+        }
+    };
+    std::cout << "\nThese numbers under 250 do not occur in the first " << limit
+              << " terms:\n";
+    f(0);
+    int max = *std::max_element(std::begin(found), std::end(found));
+    std::cout << "\n\nThese numbers under 250 occur the most in the first "
+              << limit << " terms:\n";
+    f(max);
+    std::cout << " all occur " << max << " times.\n\n";
+    for (;; ++count) {
+        uint64_t next = si.next();
+        if (next == 36) {
+            std::cout << count << "th member is " << 36
+                      << " and highest prime needed is " << si.prime() << '\n';
+            break;
+        }
+    }
+}</syntaxhighlight>
+{{out}}
+<pre>
+The first 100 members of the Sisyphus sequence are:
+3   6   3   8   4   2   1   8   4
+1  12   6   3  16   8   4   2   1
+9  28  14   7  30  15  44  22  11
+21  58  29  70  35  78  39  86  43
+48  24  12   6   3  62  31  92  46
+90  45 116  58  29 102  51 130  65
+74  37 126  63 160  80  40  20  10
+106  53 156  78  39 146  73 182  91
+102  51 178  89 220 110  55 192  96
+24  12   6   3 142  71 220 110  55
+,000th member is           990 and highest prime needed is       2,273
+,000th member is        24,975 and highest prime needed is      30,727
+,000th member is       265,781 and highest prime needed is     392,113
+,000,000th member is     8,820,834 and highest prime needed is   4,761,697
+,000,000th member is    41,369,713 and highest prime needed is  55,900,837
+,000,000th member is 1,179,614,168 and highest prime needed is 640,692,323
+These numbers under 250 do not occur in the first 100,000,000 terms:
+, 72, 97, 107, 115, 127, 144, 167, 194, 211, 214, 230, 232
+These numbers under 250 occur the most in the first 100,000,000 terms:
+, 14, 28 all occur 7 times.
+,534,485,877th member is 36 and highest prime needed is 677,121,348,413
 </pre>