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 | an+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;
}
a(n) = floor((1+log(2)/log(3))*A020914(n-1)). - K. Spage, Oct 22 2009 a(n) = A020914(n+1)+n-1. - K. Spage, Oct 23 2009. (A relation equivalent to the second remark is also present in A020914) This shows that a connection between the two sequences is known. – player3236 Mar 07 '21 at 01:52