COMETA Consortium, Project PI2S2

Looking for Class Records in the 3x+1 problem
by means of the Cometa grid

Giuseppe Scollo
University of Catania, DMI
Grid Open Days all'Università di Palermo
Palermo, 6-7.12.2007

Logo of Triple-A Level WCAG-1 Conformance, W3C-WAI Web Content Accessibility Guidelines 1.0 XHTML 1.0 validation CSS 2 validation


  1. Looking for Class Records in the 3x+1 problem by means of the Cometa grid
  2. the 3x+1 Problem
  3. 3x+1 trajectories and records
  4. distributed search of class records
  5. motivation for the search on the Cometa grid
  6. a basic parallel algorithm
  7. optimization (1): Sieving
  8. optimization (2): Tail cut-off
  9. optimization (3): Head cut-off
  10. Head and Tail cut-off in a picture
  11. optimization (4): Acceleration
  12. interference and smoothening of Acceleration
  13. performance figures
  14. state of the search and results
  15. questions?

the 3x+1 Problem

misty origins:

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)


3x+1 trajectories and records

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:


distributed search of class records

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


motivation for the search on the Cometa grid

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.1012

4 good reasons:

and, last but not least:


a basic parallel algorithm

assume all CRs below M are known

goal: find all new CRs below N > M

DAG structure of CR parallel search


optimization (1): Sieving

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 (2k-2 + (k mod 2)2k-1 - 1) (mod 2k), for k > 2

better off with a finite approximation (e.g. k=18), efficiently implemented by a sieve


optimization (2): Tail cut-off

all trajectories leading to 1 (veritably all, thus) sooner or later fall below 2t, for any given, fixed t

delay computation may thus get quicker by storing all delay(n) for n < 2t, 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


optimization (3): Head cut-off

two DRs are consecutive if there is no DR in between them

one can use this to stop the delay computation of hopeless trajectories ahead of time:

virtue of this technique: self-optimizing! CR search progress eventually leads to


Head and Tail cut-off in a picture

Head and Tail cut-off levels


optimization (4): Acceleration

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

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 2k), defined by the k-prefix of the so-called parity vector of T-trajectories, viz. the binary sequence, dependent on x, defined by vi(x) = (T ix) mod 2

thus one may define 2k distinct k-step composites of T, and decide which applies to x by only looking at x (mod 2k) : not so small acceleration, by clever programming techniques


interference and smoothening of Acceleration

optimal k for Acceleration depends on cache size, but:

Interference of Acceleration on Head cut-off

solution: smoothening of Acceleration, that is, shorten Acceleration extent


performance figures

approximate average CPU time h (in hours) to search an interval of size 244, in the neighbourhood of 256:

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


state of the search and results

search started on 25/09/2007, from 255 + 72 * 248

e-mail communication from Eric Roosendaal



big question mark