misty origins:
rediscoveredseveral times, whereby it is known under several names: Collatz, Syracuse, Kakutani, Hasse, Ulam, 3x+1, ...
official
statement of the Problem: let
f : N_{+}
→ N_{+}
be defined by the following rules:
is it true that repeated iteration of f always converges to 1 ?
or, in other words, that f^{*} has the 1 → 4 → 2 → 1 cycle as (unique) attractor?
Mathematics is not yet ready for such problems
(Erdös)
this work does not aim at solving the 3x+1 Problem
subject of interest here is the dynamical behaviour of f^{*}
basic concepts relating to the f^{*} dynamics:
the assessment that an x is a CR requires certainty that no lower y has the same delay
not really, since several laws relate delays of joining trajectories
such laws may speed-up delay computation, yet CR finding does need exhaustive search
this is easily parallelized by partitioning the search space into disjoint intervals, explored by independent jobs, each producing its own set of CR candidates
the final merge of distributed search results thus amounts to select
the best
,
i.e. smallest, candidate for each delay class
a distributed search effort, to find 3x+1 class records, is active since quite a few years
it has found 2014 CRs so far, exploring the search space up to 57780^{.}10^{12}
4 good reasons:
and, last but not least:
assume all CRs below M are known
goal: find all new CRs below N > M
the heart of CR finding is the delay computation function
the fastest execution is that which... need not start :)
coalescence of trajectories entails that
CRs fall outside certain congruence classes
for n>0, the trajectories of 8n+5 and 8n+4 coalesce at 6n+4 after the same number of steps (3), so delay(8n+5) = delay(8n+4) → 8n+5 cannot be a CR
this generalizes to congruence classes (2^{k-2} + (k mod 2)2^{k-1} - 1) (mod 2^{k}), for k > 2
better off with a finite approximation (e.g. k=18), efficiently implemented by a sieve
all trajectories leading to 1 (veritably all, thus) sooner or later fall below 2^{t}, for any given, fixed t
delay computation may thus get quicker by storing all delay(n) for n < 2^{t}, and then adding delay(n) to the partially computed delay of x as soon as the trajectory starting at x reaches such an n
by similar, architecture-dependent data as for the sieve size:
a surely lower threshold proves optimal (t between 12 and 16, usually), that depends on
two DRs are consecutive if there is no DR in between them
≤
delay(x_{1})
one can use this to stop the delay computation of
hopeless
trajectories ahead of time:
≥
M
may only be a CR if its delay is at least u
≤
d + delay(x_{1})
virtue of this technique:
self-optimizing
!
CR search progress eventually leads to
a small acceleration of delay computation comes from replacing the function f with T, defined as f on the even numbers, whereas for odd x one has
⌈
x/2⌉
clearly, if the T-trajectory from x to 1 has D applications of this rule and E applications of the halving rule, then delay(x) = 2D + E
the interest in T comes from the existence of a permutation of the residues (mod 2^{k}), defined by the k-prefix of the so-called parity vector of T-trajectories, viz. the binary sequence, dependent on x, defined by v_{i}(x) = (T^{ i}x) mod 2
thus one may define 2^{k} distinct k-step composites of T, and decide which applies to x by only looking at x (mod 2^{k}) : not so small acceleration, by clever programming techniques
optimal k for Acceleration depends on cache size, but:
solution: smoothening of Acceleration, that is, shorten Acceleration extent
approximate average CPU time h (in hours) to search an interval of size 2^{44}, in the neighbourhood of 2^{56}:
remark: the latest performance gain is also due to the introduction of a new pair of consecutive DRs, which has nearly doubled the highest Head cut-off threshold
search started on 25/09/2007, from 2^{55} + 72 * 2^{48}
truly new, that is, lower than the best known candidate until its discovery: