'An efficient routine to find cycles in qx+1 sequences
I am searching for cycles of so-called qx+1 sequences. Those who are interested in the deeper background of such sequences may take a look into the paper On a conjecture of Crandall concerning the qx + 1 problem.
For some q-values there are cycles known. For example, we have the cycle [13,33,83] in the 5x+1 sequence.
def exact_divisibility_two(x):
d = 0
while x%2 == 0:
x //= 2
d+=1
return d
def generate_collatz_set(q, v1, n):
collatz_set = []
if n<1 or v1%2==0:
return collatz_set
vi = v1
collatz_set.append(vi)
for i in range(n-1):
vi = q*vi+1
while vi%2 == 0:
vi //= 2**(exact_divisibility_two(vi))
collatz_set.append(int(vi))
return collatz_set
There exist three more cycles. By running
print(generate_collatz_set(5,13,6))
print(generate_collatz_set(5,27,6))
print(generate_collatz_set(181,27,6))
print(generate_collatz_set(181,35,6))
we obtain
[13, 33, 83, 13, 33, 83]
[27, 17, 43, 27, 17, 43]
[27, 611, 27, 611, 27, 611]
[35, 99, 35, 99, 35, 99]
I am searching for a highly efficient routine to search for more of such qx+1 cycles including higher q values.
Solution 1:[1]
As it appeared, there are very many cycles exist.
In code below I re-implemented your Python functions into C++ functions.
Also I implemented my own version find_collatz(), which searches all possible cycles with given constraints q, n, x0.
After code you can see console output of all cycles.
In console output you can see 4 parts. First part shows all possible found cycles for given q, n, x0, actually not all but just part of them. Second part shows only unique but full (including even numbers) cycles. Third part shows only odd unique cycles. Fourth part shows all odd unique cycles which are same up to rotation.
#include <cstdint>
#include <vector>
#include <iostream>
#include <functional>
#include <string>
#include <sstream>
#include <cstring>
#include <stdexcept>
#include <unordered_set>
#include <map>
#include <tuple>
#include <set>
#include <algorithm>
#define ASSERT_MSG(cond, msg) { if (!(cond)) throw std::runtime_error("Assertion (" #cond ") failed at line " + std::to_string(__LINE__) + "! Msg: '" + std::string(msg) + "'."); }
#define ASSERT(cond) ASSERT_MSG(cond, "")
inline bool exact_divisibility_two(int64_t x) {
int64_t d = 0;
while (x % 2 == 0) {
x /= 2;
d += 1;
}
return d;
}
std::vector<int64_t> generate_collatz_set(
int64_t q, int64_t v1, int64_t n) {
std::vector<int64_t> collatz_set;
if (n < 1 || v1 % 2 == 0)
return collatz_set;
int64_t vi = v1;
collatz_set.push_back(vi);
for (int64_t i = 0; i < n - 1; ++i) {
vi = q * vi + 1;
while (vi % 2 == 0) {
vi /= 1 << exact_divisibility_two(vi);
collatz_set.push_back(vi);
}
}
return collatz_set;
}
static std::map<std::string, std::string> po;
std::string const & PO(std::string const & key, std::string const & def_val = "<THROW>") {
if (def_val == "<THROW>") {
ASSERT_MSG(po.count(key), "Program option '--" + key + "' not found!");
return po.at(key);
} else {
return po.count(key) ? po.at(key) : def_val;
}
}
void find_collatz(
int64_t q_begin, int64_t q_end,
int64_t x0_begin, int64_t x0_end,
int64_t n_lim, bool show_all) {
std::cout << "q_begin " << q_begin << ", q_end " << q_end << ", x0_begin " << x0_begin
<< ", x0_end " << x0_end << ", n " << n_lim << std::endl << std::endl;
std::cout << "___CYCLES_BEGIN___" << std::endl;
std::unordered_set<int64_t> present;
std::vector<int64_t> seq;
std::map<std::string, std::map<int64_t, std::vector<int64_t>>> ans_all, ans_odd, ans_rot;
auto FindCycle = [&](std::vector<int64_t> const & v) {
std::vector<int64_t> r;
for (ptrdiff_t i = ptrdiff_t(v.size()) - 2; i >= 0; --i)
if (v[i] == v.back()) {
for (size_t j = i; j < v.size() - 1; ++j)
r.push_back(v[j]);
return r;
}
return r;
};
auto CycleRot = [&](std::vector<int64_t> v) {
std::rotate(v.begin(), std::min_element(v.begin(), v.end()), v.end());
return v;
};
std::function<bool(bool, int, int, int)> F =
[&](bool capture, auto q, auto x0, auto n) {
int64_t x = x0;
seq.clear();
present.clear();
for (int64_t icycle = 0; icycle < n; ++icycle) {
if (present.count(x)) {
seq.push_back(x);
if (!capture)
return F(true, q, x0, n_lim);
if (show_all) {
std::cout
<< "q " << q << " x0 " << x0
<< " len " << icycle << std::endl;
for (auto x: seq)
std::cout << x << ", ";
std::cout << std::endl;
}
auto const res = FindCycle(seq);
if (show_all) {
for (auto x: res)
std::cout << x << ", ";
std::cout << "(";
for (auto x: res)
if (x & 1)
std::cout << x << ", ";
std::cout << ")" << std::endl;
}
std::stringstream ss, ss2, ss3;
for (auto x: res)
ss << x << ", ";
ss << " (";
for (auto x: res)
if (x & 1) {
ss << x << ", ";
ss2 << x << ", ";
}
ss << ")";
ans_all[ss.str()][q].push_back(x0);
ans_odd[ss2.str()][q].push_back(x0);
auto const cycle_rot = CycleRot(res);
for (auto x: cycle_rot)
if (x & 1)
ss3 << x << ", ";
if (!ans_rot.count(ss3.str()) || !ans_rot.at(ss3.str()).count(q))
std::cout << ss3.str() << "; q = " << q << std::endl << std::flush;
ans_rot[ss3.str()][q].push_back(x0);
return true;
}
present.insert(x);
if (capture)
seq.push_back(x);
if (x >= (1ULL << 50))
break;
x = x & 1 ? q * x + 1 : x >> 1;
}
return false;
};
if (show_all)
std::cout << "All found sequences:" << std::endl;
for (int64_t q = q_begin | 1; q < q_end; q += 2)
for (int64_t x0 = std::max<int64_t>(1, x0_begin); x0 < x0_end; ++x0)
F(false, q, x0, n_lim);
std::cout << "___CYCLES_END___" << std::endl;
auto OutSeq = [&](auto const & ans){
for (auto const & [k, v]: ans) {
std::cout << k << " (";
for (auto const & [q_, x0v]: v) {
std::cout << "q = " << q_ << " (x0 = ";
int64_t x0_start = x0v.at(0), x0_prev = x0_start;
for (size_t i = 1; i <= x0v.size(); ++i) {
if (i >= x0v.size() || x0_prev + 1 < x0v[i]) {
if (x0_start == x0_prev)
std::cout << x0_start << " ";
else
std::cout << x0_start << "-" << x0_prev << " ";
if (i < x0v.size())
x0_start = x0v[i];
}
if (i < x0v.size())
x0_prev = x0v[i];
}
std::cout << "), ";
}
std::cout << ")" << std::endl;
}
};
std::cout << std::endl << "All found cycles:" << std::endl;
OutSeq(ans_all);
std::cout << std::endl << "All found odd cycles:" << std::endl;
OutSeq(ans_odd);
std::cout << std::endl << "All found odd rotated cycles:" << std::endl;
OutSeq(ans_rot);
}
auto ParseProgOpts(int argc, char ** argv) {
std::vector<std::string> args;
for (size_t i = 1; i < argc; ++i)
args.emplace_back(argv[i]);
std::map<std::string, std::string> m;
size_t ipos = 0;
for (auto e: args) {
if (e.empty() || e.at(0) != '-') {
m["pos" + std::to_string(ipos++)] = e;
continue;
}
ASSERT(e.at(0) == '-');
e.erase(0, 1);
if (!e.empty() && e.at(0) == '-')
e.erase(0, 1);
auto const eq_pos = e.find('=');
if (eq_pos == std::string::npos) {
m[e] = "";
continue;
}
std::string const key = e.substr(0, eq_pos),
val = e.substr(eq_pos + 1);
m[key] = val;
}
return m;
}
int main(int argc, char ** argv) {
try {
po = ParseProgOpts(argc, argv);
find_collatz(
std::stoll(PO("q-begin", "0")), std::stoll(PO("q-end", "4100")),
std::stoll(PO("x0-begin", "0")), std::stoll(PO("x0-end", "1050")),
std::stoll(PO("n", "1050")), false);
return 0;
} catch (std::exception const & ex) {
std::cout << "Exception: " << ex.what() << std::endl;
return -1;
}
}
First part, all sequences (partially):
All found sequences:
q 3 x0 1 len 3
1, 4, 2, 1,
1, 4, 2, (1, )
q 3 x0 2 len 3
2, 1, 4, 2,
2, 1, 4, (1, )
q 3 x0 3 len 8
3, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 4 len 3
4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 5 len 6
5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 6 len 9
6, 3, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 7 len 17
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 8 len 4
8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 9 len 20
9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 10 len 7
10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 11 len 15
11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 12 len 10
12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 13 len 10
13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 14 len 18
14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 15 len 18
15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 16 len 5
16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 17 len 13
17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 18 len 21
18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 19 len 21
19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 20 len 8
20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 21 len 8
21, 64, 32, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 22 len 16
22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 23 len 16
23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 24 len 11
24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 25 len 24
25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 26 len 11
26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 27 len 112
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 28 len 19
28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 29 len 19
29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 30 len 19
30, 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 31 len 107
31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 32 len 6
32, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 33 len 27
33, 100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 34 len 14
34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 35 len 14
35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 36 len 22
36, 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 37 len 22
37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 38 len 22
38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 39 len 35
39, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 40 len 9
40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 41 len 110
41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 42 len 9
42, 21, 64, 32, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 43 len 30
43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 44 len 17
44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 45 len 17
45, 136, 68, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 46 len 17
46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 47 len 105
47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 48 len 12
48, 24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 49 len 25
49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
q 3 x0 50 len 25
50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4,
4, 2, 1, (1, )
Second part, unique odd+even cycles:
All found cycles:
1, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, (1, )
1, 128, 64, 32, 16, 8, 4, 2, (1, )
1, 16, 8, 4, 2, (1, )
1, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, (1, )
1, 256, 128, 64, 32, 16, 8, 4, 2, (1, )
1, 32, 16, 8, 4, 2, (1, )
1, 4, 2, (1, )
1, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, (1, )
1, 512, 256, 128, 64, 32, 16, 8, 4, 2, (1, )
1, 6, 3, 16, 8, 4, 2, (1, 3, )
1, 64, 32, 16, 8, 4, 2, (1, )
1, 8, 4, 2, (1, )
1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, (1, )
104, 52, 26, 13, 66, 33, 166, 83, 416, 208, (13, 33, 83, )
108, 54, 27, 136, 68, 34, 17, 86, 43, 216, (27, 17, 43, )
108, 54, 27, 4888, 2444, 1222, 611, 110592, 55296, 27648, 13824, 6912, 3456, 1728, 864, 432, 216, (27, 611, )
128, 64, 32, 16, 8, 4, 2, 1, (1, )
128, 64, 32, 16, 8, 4, 2, 1, 1024, 512, 256, (1, )
128, 64, 32, 16, 8, 4, 2, 1, 2048, 1024, 512, 256, (1, )
128, 64, 32, 16, 8, 4, 2, 1, 256, (1, )
128, 64, 32, 16, 8, 4, 2, 1, 4096, 2048, 1024, 512, 256, (1, )
128, 64, 32, 16, 8, 4, 2, 1, 512, 256, (1, )
13, 66, 33, 166, 83, 416, 208, 104, 52, 26, (13, 33, 83, )
136, 68, 34, 17, 86, 43, 216, 108, 54, 27, (17, 43, 27, )
140, 70, 35, 6336, 3168, 1584, 792, 396, 198, 99, 17920, 8960, 4480, 2240, 1120, 560, 280, (35, 99, )
16, 8, 4, 2, 1, (1, )
16, 8, 4, 2, 1, 1024, 512, 256, 128, 64, 32, (1, )
16, 8, 4, 2, 1, 128, 64, 32, (1, )
16, 8, 4, 2, 1, 2048, 1024, 512, 256, 128, 64, 32, (1, )
16, 8, 4, 2, 1, 256, 128, 64, 32, (1, )
16, 8, 4, 2, 1, 32, (1, )
16, 8, 4, 2, 1, 4096, 2048, 1024, 512, 256, 128, 64, 32, (1, )
16, 8, 4, 2, 1, 512, 256, 128, 64, 32, (1, )
16, 8, 4, 2, 1, 6, 3, (1, 3, )
16, 8, 4, 2, 1, 64, 32, (1, )
166, 83, 416, 208, 104, 52, 26, 13, 66, 33, (83, 13, 33, )
17, 86, 43, 216, 108, 54, 27, 136, 68, 34, (17, 43, 27, )
198, 99, 17920, 8960, 4480, 2240, 1120, 560, 280, 140, 70, 35, 6336, 3168, 1584, 792, 396, (99, 35, )
2, 1, 1024, 512, 256, 128, 64, 32, 16, 8, 4, (1, )
2, 1, 128, 64, 32, 16, 8, 4, (1, )
2, 1, 16, 8, 4, (1, )
2, 1, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, (1, )
2, 1, 256, 128, 64, 32, 16, 8, 4, (1, )
2, 1, 32, 16, 8, 4, (1, )
2, 1, 4, (1, )
2, 1, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, (1, )
2, 1, 512, 256, 128, 64, 32, 16, 8, 4, (1, )
2, 1, 6, 3, 16, 8, 4, (1, 3, )
2, 1, 64, 32, 16, 8, 4, (1, )
2, 1, 8, 4, (1, )
208, 104, 52, 26, 13, 66, 33, 166, 83, 416, (13, 33, 83, )
216, 108, 54, 27, 136, 68, 34, 17, 86, 43, (27, 17, 43, )
216, 108, 54, 27, 4888, 2444, 1222, 611, 110592, 55296, 27648, 13824, 6912, 3456, 1728, 864, 432, (27, 611, )
256, 128, 64, 32, 16, 8, 4, 2, 1, (1, )
256, 128, 64, 32, 16, 8, 4, 2, 1, 1024, 512, (1, )
256, 128, 64, 32, 16, 8, 4, 2, 1, 2048, 1024, 512, (1, )
256, 128, 64, 32, 16, 8, 4, 2, 1, 4096, 2048, 1024, 512, (1, )
256, 128, 64, 32, 16, 8, 4, 2, 1, 512, (1, )
26, 13, 66, 33, 166, 83, 416, 208, 104, 52, (13, 33, 83, )
27, 136, 68, 34, 17, 86, 43, 216, 108, 54, (27, 17, 43, )
27, 4888, 2444, 1222, 611, 110592, 55296, 27648, 13824, 6912, 3456, 1728, 864, 432, 216, 108, 54, (27, 611, )
280, 140, 70, 35, 6336, 3168, 1584, 792, 396, 198, 99, 17920, 8960, 4480, 2240, 1120, 560, (35, 99, )
3, 16, 8, 4, 2, 1, 6, (3, 1, )
32, 16, 8, 4, 2, 1, (1, )
32, 16, 8, 4, 2, 1, 1024, 512, 256, 128, 64, (1, )
32, 16, 8, 4, 2, 1, 128, 64, (1, )
32, 16, 8, 4, 2, 1, 2048, 1024, 512, 256, 128, 64, (1, )
32, 16, 8, 4, 2, 1, 256, 128, 64, (1, )
32, 16, 8, 4, 2, 1, 4096, 2048, 1024, 512, 256, 128, 64, (1, )
32, 16, 8, 4, 2, 1, 512, 256, 128, 64, (1, )
32, 16, 8, 4, 2, 1, 64, (1, )
33, 166, 83, 416, 208, 104, 52, 26, 13, 66, (33, 83, 13, )
34, 17, 86, 43, 216, 108, 54, 27, 136, 68, (17, 43, 27, )
35, 6336, 3168, 1584, 792, 396, 198, 99, 17920, 8960, 4480, 2240, 1120, 560, 280, 140, 70, (35, 99, )
396, 198, 99, 17920, 8960, 4480, 2240, 1120, 560, 280, 140, 70, 35, 6336, 3168, 1584, 792, (99, 35, )
4, 2, 1, (1, )
4, 2, 1, 1024, 512, 256, 128, 64, 32, 16, 8, (1, )
4, 2, 1, 128, 64, 32, 16, 8, (1, )
4, 2, 1, 16, 8, (1, )
4, 2, 1, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, (1, )
4, 2, 1, 256, 128, 64, 32, 16, 8, (1, )
4, 2, 1, 32, 16, 8, (1, )
4, 2, 1, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, (1, )
4, 2, 1, 512, 256, 128, 64, 32, 16, 8, (1, )
4, 2, 1, 6, 3, 16, 8, (1, 3, )
4, 2, 1, 64, 32, 16, 8, (1, )
4, 2, 1, 8, (1, )
416, 208, 104, 52, 26, 13, 66, 33, 166, 83, (13, 33, 83, )
43, 216, 108, 54, 27, 136, 68, 34, 17, 86, (43, 27, 17, )
432, 216, 108, 54, 27, 4888, 2444, 1222, 611, 110592, 55296, 27648, 13824, 6912, 3456, 1728, 864, (27, 611, )
512, 256, 128, 64, 32, 16, 8, 4, 2, 1, (1, )
512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 1024, (1, )
512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 2048, 1024, (1, )
512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 4096, 2048, 1024, (1, )
52, 26, 13, 66, 33, 166, 83, 416, 208, 104, (13, 33, 83, )
54, 27, 136, 68, 34, 17, 86, 43, 216, 108, (27, 17, 43, )
54, 27, 4888, 2444, 1222, 611, 110592, 55296, 27648, 13824, 6912, 3456, 1728, 864, 432, 216, 108, (27, 611, )
560, 280, 140, 70, 35, 6336, 3168, 1584, 792, 396, 198, 99, 17920, 8960, 4480, 2240, 1120, (35, 99, )
6, 3, 16, 8, 4, 2, 1, (3, 1, )
611, 110592, 55296, 27648, 13824, 6912, 3456, 1728, 864, 432, 216, 108, 54, 27, 4888, 2444, 1222, (611, 27, )
64, 32, 16, 8, 4, 2, 1, (1, )
64, 32, 16, 8, 4, 2, 1, 1024, 512, 256, 128, (1, )
64, 32, 16, 8, 4, 2, 1, 128, (1, )
64, 32, 16, 8, 4, 2, 1, 2048, 1024, 512, 256, 128, (1, )
64, 32, 16, 8, 4, 2, 1, 256, 128, (1, )
64, 32, 16, 8, 4, 2, 1, 4096, 2048, 1024, 512, 256, 128, (1, )
64, 32, 16, 8, 4, 2, 1, 512, 256, 128, (1, )
66, 33, 166, 83, 416, 208, 104, 52, 26, 13, (33, 83, 13, )
68, 34, 17, 86, 43, 216, 108, 54, 27, 136, (17, 43, 27, )
70, 35, 6336, 3168, 1584, 792, 396, 198, 99, 17920, 8960, 4480, 2240, 1120, 560, 280, 140, (35, 99, )
792, 396, 198, 99, 17920, 8960, 4480, 2240, 1120, 560, 280, 140, 70, 35, 6336, 3168, 1584, (99, 35, )
8, 4, 2, 1, (1, )
8, 4, 2, 1, 1024, 512, 256, 128, 64, 32, 16, (1, )
8, 4, 2, 1, 128, 64, 32, 16, (1, )
8, 4, 2, 1, 16, (1, )
8, 4, 2, 1, 2048, 1024, 512, 256, 128, 64, 32, 16, (1, )
8, 4, 2, 1, 256, 128, 64, 32, 16, (1, )
8, 4, 2, 1, 32, 16, (1, )
8, 4, 2, 1, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, (1, )
8, 4, 2, 1, 512, 256, 128, 64, 32, 16, (1, )
8, 4, 2, 1, 6, 3, 16, (1, 3, )
8, 4, 2, 1, 64, 32, 16, (1, )
83, 416, 208, 104, 52, 26, 13, 66, 33, 166, (83, 13, 33, )
86, 43, 216, 108, 54, 27, 136, 68, 34, 17, (43, 27, 17, )
864, 432, 216, 108, 54, 27, 4888, 2444, 1222, 611, 110592, 55296, 27648, 13824, 6912, 3456, 1728, (27, 611, )
99, 17920, 8960, 4480, 2240, 1120, 560, 280, 140, 70, 35, 6336, 3168, 1584, 792, 396, 198, (99, 35, )
Third part, unique odd cycles:
All found odd cycles:
1,
1, 3,
13, 33, 83,
17, 43, 27,
27, 17, 43,
27, 611,
3, 1,
33, 83, 13,
35, 99,
43, 27, 17,
611, 27,
83, 13, 33,
99, 35,
Part four, all unique odd cycles up to rotation:
All found odd rotated cycles:
1,
1, 3,
13, 33, 83,
17, 43, 27,
27, 611,
35, 99,
You may use following Python code in order to parallelize above C++ program on many cores on one machine. It uses all CPU cores.
As in previous program you provide same params --q_begin=... --q_end=... --x0_begin=... --x0_end=... --n=....
Python code splits whole range into around 48 sub-tasks and then runs on all cores.
All results are saved into files marked with q-range and x0-range and n.
After whole run is finished you can read those files.
As you can see code uses C++ program name a.exe, if you have other name you may rename program file or fix name in Python code.
import argparse, sys, subprocess, threading, multiprocessing.pool, json, os
def Proc(out, *, d = {'cycles': set(), 'lock': threading.RLock()}):
with d['lock']:
out = out.decode('utf-8')
out = out.partition('___CYCLES_BEGIN___')[2].partition('___CYCLES_END___')[0].strip()
for cycle in [e.strip() for e in out.split('\n') if e.strip()]:
if cycle in d['cycles']:
continue
d['cycles'].add(cycle)
print(cycle, flush = True)
def Run(nargs):
q_begin, q_end, x0_begin, x0_end, n = [nargs[k] for k in 'q_begin q_end x0_begin x0_end n'.split()]
cmd_line = ['a.exe', f'--q-begin={q_begin}', f'--q-end={q_end}', f'--x0-begin={x0_begin}', f'--x0-end={x0_end}', f'--n={n}']
p = subprocess.run(cmd_line, check = True, capture_output = True)
os.makedirs('cycles_logs/', exist_ok = True)
fname = f'cycles_logs/cycles.{str(q_begin).zfill(6)}_{str(q_end).zfill(6)}.{str(x0_begin).zfill(6)}_{str(x0_end).zfill(6)}.{str(n).zfill(6)}'
with open(fname, 'wb') as f:
f.write((' '.join(cmd_line) + '\n\n').encode('utf-8'))
f.write(p.stdout)
Proc(p.stdout)
parser = argparse.ArgumentParser()
parser.add_argument('--q-begin', type = int, help = 'Q search range begin')
parser.add_argument('--q-end', type = int, help = 'Q search range end')
parser.add_argument('--x0-begin', type = int, help = 'X0 search range begin')
parser.add_argument('--x0-end', type = int, help = 'X0 search range end')
parser.add_argument('--n', type = int, help = 'N')
args = parser.parse_args()
with multiprocessing.pool.ThreadPool(multiprocessing.cpu_count()) as pool:
block_q = (args.q_end - args.q_begin + 15) // 16
block_x0 = (args.x0_end - args.x0_begin + 15) // 16
pool.map(Run,
[dict(q_begin = i, q_end = min(i + block_q, args.q_end), x0_begin = j, x0_end = min(j + block_x0, args.x0_end), n = args.n)
for i in range(args.q_begin, args.q_end, block_q) for j in range(args.x0_begin, args.x0_end, block_x0)],
)
Command line:
python script.py --q-begin=0 --q-end=200000 --x0-begin=0 --x0-end=1000 --n=1000
Output:
1, ; q = 32767
1, ; q = 16383
1, ; q = 1
1, ; q = 3
1, 3, ; q = 5
13, 33, 83, ; q = 5
17, 43, 27, ; q = 5
1, ; q = 7
1, ; q = 15
1, ; q = 31
1, ; q = 63
1, ; q = 127
35, 99, ; q = 181
1, ; q = 255
1, ; q = 511
1, ; q = 1023
1, ; q = 2047
1, ; q = 4095
1, ; q = 8191
27, 611, ; q = 181
1, ; q = 65535
1, ; q = 131071
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 |