I've noticed a linear pattern in the dropping time $C(n)$ of the Collatz iteration (A122437) when plotted against the number of digits $d(n)$ in the base-2 representation of $3^n$ (A020914).
Collatz iteration dropping time (vertical) versus the number of digits in the base-2 representation of $3^n$ (horizontal).
For this limited data set the connection can be described by something like $$C(n)=\lfloor1.635\cdot d(n)\rfloor$$ Is this connection known and if not would it be worth investigating further? Thanks in advance for sharing your ideas.
Here's how I found the pattern.
Given $n,b\in\mathbb{N}$ let $c(n,b)$ be the dropping time of the set $\{2^n\cdot k+b|k\in\mathbb{N}\}$ if it exists. E.g. $c(1,0)=1$ and $c(4,3)=6$ while $c(3,1)$ is not defined. We don't consider multiples of 2, because $c(3,2)$ is the same as $c(2,1)$, for instance.
From numerical observation it becomes apparent that $\{c(n,b)|b\in\mathbb{N}\wedge(n,b)\in\textrm{dom}(c)\}$ is a singleton, say $\{e(n)\}$. Finally, $e$ only seems to be defined on $\textrm{cod}(d)$ which yields the relation:
$$\forall n\in\mathbb{N}:C(n)=e(d(n))$$
Here's the C++ code I did the analysis with.
#include <fstream>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
template <typename T>
class residue_class {
public:
residue_class(T divisor, T remainder)
: divisor{divisor},
remainder{remainder},
divisor_orig{divisor},
remainder_orig{remainder} {}
std::vector<residue_class> solve(std::ostream& stream,
std::map<T, T>& steps_by_divisor) {
return solve_light(stream, steps_by_divisor)
? std::vector<residue_class>{}
: std::vector<residue_class>{create_even(), create_odd()};
}
bool solve_light(std::ostream& stream, std::map<T, T>& steps_by_divisor) {
while (step()) {
if (is_smaller()) {
print(stream);
auto found{steps_by_divisor.find(divisor_orig)};
if (found == steps_by_divisor.end()) {
steps_by_divisor.emplace(divisor_orig, steps);
} else if (found->second != steps) {
std::cout << "Found inconsistency in number of steps. Expected "
<< found->second << ", but found " << steps
<< " for divisor " << divisor_orig << '\n';
}
return true;
}
}
return false;
}
private:
// a | b | n | a*n+b (mod 2)
// -----------------
// 0 | 0 | * | 0
// 0 | 1 | * | 1
// 1 | 0 | * | ?
// 1 | 1 | * | ?
bool step() {
bool success{false};
if (divisor % 2 == 0) {
if (remainder % 2 == 0) {
divisor /= 2;
remainder /= 2;
} else {
detect_overflow(3);
divisor *= 3;
remainder *= 3;
++remainder;
if (divisor == remainder) {
remainder = 0;
}
}
++steps;
success = true;
}
return success;
}
bool is_smaller() {
return divisor < divisor_orig ||
(divisor == divisor_orig && remainder < remainder_orig);
}
residue_class create_even() const {
residue_class even{*this};
detect_overflow(2);
even.divisor *= 2;
even.divisor_orig *= 2;
return even;
}
residue_class create_odd() const {
residue_class odd{*this};
odd.remainder += odd.divisor;
odd.remainder_orig += odd.divisor_orig;
detect_overflow(2);
odd.divisor *= 2;
odd.divisor_orig *= 2;
odd.remainder %= odd.divisor;
odd.remainder_orig %= odd.divisor_orig;
return odd;
}
void print(std::ostream& stream) const {
stream << divisor_orig << "n+" << remainder_orig << "->" << divisor << "n+"
<< remainder << " in " << steps << "\n";
}
void detect_overflow(std::int8_t modulus) const {
if (divisor >= std::numeric_limits<T>::max() / modulus) {
std::cout << "Overflow detected: ";
print(std::cout);
}
}
private:
T divisor;
T remainder;
T steps{0u};
T divisor_orig;
T remainder_orig;
};
int main() {
std::ofstream file{"out.txt"};
using T = std::int64_t;
std::map<T, T> steps_by_divisor;
std::queue<residue_class<T>> todo;
todo.emplace(2, 0);
todo.emplace(2, 1);
std::size_t solved{0u};
for (auto j{1}; j < 7; ++j) {
for (auto i{0}; i < std::pow(10, j) && !todo.empty(); ++i) {
auto modular{std::move(todo.front())};
todo.pop();
auto followup{modular.solve(file, steps_by_divisor)};
if (followup.empty()) {
++solved;
}
for (auto& task : followup) {
todo.emplace(std::move(task));
}
}
std::cout << "Summary: " << todo.size() << " unknowns and " << solved
<< " solved with ratio "
<< static_cast<double>(solved) / static_cast<double>(todo.size())
<< '\n';
}
std::size_t unknowns{0u};
while (!todo.empty()) {
auto modular{std::move(todo.front())};
todo.pop();
if (modular.solve_light(file, steps_by_divisor)) {
++solved;
} else {
++unknowns;
}
}
std::cout << "Summary: " << unknowns << " unknowns and " << solved
<< " solved with ratio "
<< static_cast<double>(solved) / static_cast<double>(unknowns)
<< '\n';
std::cout << "log2(a)\t#steps\n";
for (auto const& pair : steps_by_divisor) {
std::cout << std::log2(pair.first) << "\t" << pair.second << '\n';
}
return 0;
}
Mostly to get this out of the unanswered queue but this should be fairly simple to show:
$$r\bmod 2= 2^nx+r\bmod 2$$ so until all the factors of 2 are gone, the two have the same pattern in dropping. The residues $r$ that survive $n=11$ without dropping below their starting points are:
$$27, 31, 47, 63, 71, 91, 103, 111, 127, 155, 159, 167, 191, 207, 223, 231, 239, 251, 255, 283, 303, 319, 327, 359, 383, 411, 415, 447, 463, 479, 487, 495, 511, 539, 543, 559, 603, 615, 623, 639, 667, 671, 679, 703, 719, 743, 751, 763, 767, 795, 799, 831, 839, 859, 871, 879, 895, 927, 935, 959, 991, 1007, 1019, 1023, 1051, 1055, 1071, 1087, 1095, 1115, 1127, 1135, 1151, 1179, 1183, 1191, 1215, 1231, 1247, 1255, 1263, 1275, 1279, 1307, 1327, 1343, 1351, 1383, 1407, 1435, 1439, 1471, 1487, 1503, 1511, 1519, 1535, 1563, 1567, 1583, 1627, 1639, 1647, 1663, 1691, 1695, 1703, 1727, 1743, 1767, 1775, 1787, 1791, 1819, 1823, 1855, 1863, 1883, 1895, 1903, 1919, 1951, 1959, 1983, 2015, 2031, 2043, 2047$$
These are the only residues that could be minimal escapes or minimum in a loop.