[?] Clusters of Collatz Steps
Quinn Tyler Jackson
thread is filtered by killfiles, so I'll ask it again in a new thread:
<<
Does anyone know if it has been
documented in the literature that 3,298,601,216 and all 254 numbers after it
have 218 Collatz steps? This is the longest such "cluster" of consecutive
numbers I've been able to identify in 2^32-1 space as having an identical
number of steps to reach 1. In a similar fashion, 2,226,009,089 appears to
have the same number of steps as all 127 numbers after it (189 steps to 1).
If either of these have been noted in the literature, I'd appreciate a
literature reference, since I've done some graphical representations of
these clusters and have been asked to submit them, and would like to point
out their original discoverers, thanks.
<<
(I didn't use brute force to find these sequences -- I used a genetic
algorithm s.t. the fitness function was the number of consecutive identical
Collatz steps. With a "bignum" library, I'm hoping to find longer clusters,
but I haven't yet plugged the one BigNum C++ library in that I managed to
find on the net.)
Any pointers to a mention of these numbers in the literature would be
greatly appreciated. I don't want to submit a paper with the graphics that
are based on these clusters without crediting the original discoverers of
these oddities.
Also, I noticed that with these two numbers, at least, the number of ascents
and the number of descents is identical, despite the fact that there are
multiple attractors, as shown by:
http://members.shaw.ca/the_grammar_forge/hailstone_descents.gif
As shown by the above, there is one major attractor near the bottom right,
but many attractors throughout each of the 255 paths to 1, and yet, the
number of ascents/descents is equal for all 255 numbers. (I'm calling
"ascents" the number of 3n+1 steps and "descents" the number of n/2 steps
during the trajectory towards 1.)
Thanks in advance for any pointers.
--
Quinn
Gerry Myerson
"Quinn Tyler Jackson" <qui...@shaw.ca> wrote:
> Does anyone know if it has been
> documented in the literature that 3,298,601,216 and all 254 numbers after it
> have 218 Collatz steps? This is the longest such "cluster" of consecutive
> numbers I've been able to identify in 2^32-1 space as having an identical
> number of steps to reach 1. In a similar fashion, 2,226,009,089 appears to
> have the same number of steps as all 127 numbers after it (189 steps to 1).
> If either of these have been noted in the literature, I'd appreciate a
> literature reference, since I've done some graphical representations of
> these clusters and have been asked to submit them, and would like to point
> out their original discoverers, thanks.
Have a look at
http://www.ieeta.pt/~tos/3x+1.html
I don't know whether your exact problem is discussed there,
but the fellow who maintains that page has done tons of computing
on the problem, and if he hasn't come across your numbers
he'll probably enjoy hearing about them from you.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Quinn Tyler Jackson
> > Does anyone know if it has been
> > documented in the literature that 3,298,601,216 and all 254 numbers
after it
> > have 218 Collatz steps? This is the longest such "cluster" of
consecutive
> > numbers I've been able to identify in 2^32-1 space as having an
identical
> > number of steps to reach 1. In a similar fashion, 2,226,009,089 appears
to
> > have the same number of steps as all 127 numbers after it (189 steps to
1).
> > If either of these have been noted in the literature, I'd appreciate a
> > literature reference, since I've done some graphical representations of
> > these clusters and have been asked to submit them, and would like to
point
> > out their original discoverers, thanks.
Gerry Myerson replied:
> Have a look at
> http://www.ieeta.pt/~tos/3x+1.html
> I don't know whether your exact problem is discussed there,
> but the fellow who maintains that page has done tons of computing
> on the problem, and if he hasn't come across your numbers
> he'll probably enjoy hearing about them from you.
Thanks! It looks like a good place to start.
I'm assuming (erring on the side of it's been done before) that those two
oddities are known because they are in 2^32-1 space. However, I was
specifically looking for such clusters to see if they could be used to good
graphical effect, and I used a genetic algorithm that specifically was tuned
to find such clusters -- so there is a small (for some very small value of
small) chance that these clusters are not known specifically. Also -- I'm
not sure if step-clusters are interesting -- so there might be no work in
this area. (I don't even know what to call such clusters, so I thought maybe
"Hailstorms" -- but they may already have a name.)
They are primarily interesting to me (especially the 255 consecutive 218's
one) because they all start so closely together, they all have the same
number of ascents and descents, and they all reach 1. This allows for a nice
graph that doesn't have too much initial, and no terminal variation. They
may or may not be interesting for other properties they display.
--
Quinn
mensanator
> I asked the following on another thread, but there's a chance that the other
> thread is filtered by killfiles, so I'll ask it again in a new thread:
>
> <<
> Does anyone know if it has been
> documented in the literature that 3,298,601,216 and all 254 numbers after it
> have 218 Collatz steps? This is the longest such "cluster" of consecutive
> numbers I've been able to identify in 2^32-1 space as having an identical
> number of steps to reach 1. In a similar fashion, 2,226,009,089 appears to
> have the same number of steps as all 127 numbers after it (189 steps to 1).
> If either of these have been noted in the literature, I'd appreciate a
> literature reference, since I've done some graphical representations of
> these clusters and have been asked to submit them, and would like to point
> out their original discoverers, thanks.
> <<
Very neat. It's not uncommon for adjacent integers to be on adjacent branches,
but I wouldn't have guessed you could have so many spread out so widely
across the tree.
>
> (I didn't use brute force to find these sequences -- I used a genetic
> algorithm s.t. the fitness function was the number of consecutive identical
> Collatz steps.
Could you elaborate on that, or will I have to read your paper?
> With a "bignum" library, I'm hoping to find longer clusters,
> but I haven't yet plugged the one BigNum C++ library in that I managed to
> find on the net.)
>
> Any pointers to a mention of these numbers in the literature would be
> greatly appreciated. I don't want to submit a paper with the graphics that
> are based on these clusters without crediting the original discoverers of
> these oddities.
Sorry, can't help there.
>
> Also, I noticed that with these two numbers, at least, the number of ascents
> and the number of descents is identical, despite the fact that there are
> multiple attractors, as shown by:
>
> http://members.shaw.ca/the_grammar_forge/hailstone_descents.gif
When you say "attractor", do you mean the number where two sequences converge?
>
> As shown by the above, there is one major attractor near the bottom right,
So this "major attractor" is 202 since every one of the 255 sequences ends in
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 ?
> but many attractors throughout each of the 255 paths to 1, and yet, the
> number of ascents/descents is equal for all 255 numbers.
And in the 7 sextillion pathways of length 218, there can be a lot of
different permutations of ascents/descents. It's also not unusual to run
into common pathways, such as
http://members.aol.com/mensanator666/Page.htm
but here the attractors occur very early in the sequences, so the similar
path lengths are to be expected. I was surprised to see so many attractors
occuring so late in the sequences.
> (I'm calling
> "ascents" the number of 3n+1 steps and "descents" the number of n/2 steps
> during the trajectory towards 1.)
>
> Thanks in advance for any pointers.
Always interesting to see new Collatz discoveries.
Quinn Tyler Jackson
branches,
> but I wouldn't have guessed you could have so many spread out so widely
> across the tree.
I wouldn't have guessed it either. It was a fluke that I came across the big
one. Total fluke.
> > (I didn't use brute force to find these sequences -- I used a genetic
> > algorithm s.t. the fitness function was the number of consecutive
identical
> > Collatz steps.
>
> Could you elaborate on that, or will I have to read your paper?
Well, the paper itself will only mention the numbers in passing -- their
[re?]discovery was an ancillary result.
Essentially, I used a 32-allele genome, s.t. each allele represented 1 bit
in 2^32 space. I used a population of about 100, and a mutation rate of
50%/generation. The five most fit carried to each new generation using
standard elitism. There was no fitness scaling. Parenting was based upon
weighted roulette. The PRNG was ISAAC seeded by the Windows GetTickCount
function.
The fitness function used was 0 = no subsequent integer with the same number
of Collatz steps, 1 = 1 subsequent integer with the same Collatz steps, to
some N. The highest N found was the number originally mentioned:
3,298,601,216.
If you want the C++ source for this -- just email me. I ask only that you
don't distribute the GA code -- since I've never released it and am not sure
I want it floating around just yet.
> When you say "attractor", do you mean the number where two sequences
converge?
Yes.
> As shown by the above, there is one major attractor near the bottom right,
> So this "major attractor" is 202 since every one of the 255 sequences ends
in
> 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 ?
Yes.
I apologize if my use of attractor is non-standard. If non-standard: please
enlighten me as to the correct term.
> And in the 7 sextillion pathways of length 218, there can be a lot of
> different permutations of ascents/descents. It's also not unusual to run
> into common pathways, such as
>
> http://members.aol.com/mensanator666/Page.htm
>
> but here the attractors occur very early in the sequences, so the similar
> path lengths are to be expected. I was surprised to see so many attractors
> occuring so late in the sequences.
As was I! I found a few "short" clusters of 4 or so where the convergence
occurs very early in the game. What I was not expecting at all is that
> Always interesting to see new Collatz discoveries.
I don't know if it's new -- which is why I posted my query. I'd love to find
out it is a re-discovery -- that would lift the obligation to write up too
much about it. ;-) I just wanted a "long" cluster, for graphics.
BTW, here's two such graphics:
http://members.shaw.ca/the_grammar_forge/collatz07.gif
http://members.shaw.ca/the_grammar_forge/collatz_09.jpg (lossy due to full
file size of original)
For reference, here are the C-steps graphed using the same method, for N = 1
to 1000:
http://members.shaw.ca/the_grammar_forge/collatz04.gif
And here are the integers, equidistributed, from 1 to about 13 billion:
http://members.shaw.ca/the_grammar_forge/collatz_eq.gif
The above simply shows 1 through 13 billion, graphed using the same method
as used for the others, to show how non-chaotic sequences graph using the
same method.
Here are the same ranges, but with random "weights" -- to show that the
Collatz graphics are not simply how "all" chaos appears using the graphing
method:
http://members.shaw.ca/the_grammar_forge/randomgraph.gif
Finally, here's what I call Collatz' Turtle -- did it for the kids:
http://members.shaw.ca/the_grammar_forge/collatz07.gif
;-)
--
Quinn
Quinn Tyler Jackson
>
> http://members.shaw.ca/the_grammar_forge/collatz07.gif
>
> ;-)
Whoops.
http://members.shaw.ca/the_grammar_forge/collatz03.gif
That is the turtle.
--
Quinn
Quinn Tyler Jackson
> If you want the C++ source for this -- just email me. I ask only that you
> don't distribute the GA code -- since I've never released it and am not
sure
> I want it floating around just yet.
Ah, what the heck.
The C++ source is here:
http://members.shaw.ca/the_grammar_forge/source/ga_hailstone.zip
The GA portion is released under the MIT License:
http://www.opensource.org/licenses/mit-license.php
Hope someone gets some use out of the GA classes.
Cheers.
--
Quinn
Mensanator
>From: "Quinn Tyler Jackson" qui...@shaw.ca
>Date: 6/16/2004 9:37 PM Central Standard Time
>Message-id: <Ut7Ac.772614$oR5.570630@pd7tw3no>
>
>> Very neat. It's not uncommon for adjacent integers to be on adjacent
>branches,
>> but I wouldn't have guessed you could have so many spread out so widely
>> across the tree.
>
>I wouldn't have guessed it either. It was a fluke that I came across the big
>one. Total fluke.
>
>> > (I didn't use brute force to find these sequences -- I used a genetic
>> > algorithm s.t. the fitness function was the number of consecutive
>identical
>> > Collatz steps.
>>
>> Could you elaborate on that, or will I have to read your paper?
>
>Well, the paper itself will only mention the numbers in passing -- their
>[re?]discovery was an ancillary result.
>
>Essentially, I used a 32-allele genome, s.t. each allele represented 1 bit
>in 2^32 space. I used a population of about 100, and a mutation rate of
>50%/generation. The five most fit carried to each new generation using
>standard elitism. There was no fitness scaling. Parenting was based upon
>weighted roulette. The PRNG was ISAAC seeded by the Windows GetTickCount
>function.
>
>The fitness function used was 0 = no subsequent integer with the same number
>of Collatz steps, 1 = 1 subsequent integer with the same Collatz steps, to
>some N. The highest N found was the number originally mentioned:
>3,298,601,216.
Eek! I don't picture myself doing any genetic programming in the near future.
>
>If you want the C++ source for this -- just email me. I ask only that you
>don't distribute the GA code -- since I've never released it and am not sure
>I want it floating around just yet.
It would probably be wasted on me as I'm not a C programmer.
>
>> When you say "attractor", do you mean the number where two sequences
>converge?
>
>Yes.
>
>> As shown by the above, there is one major attractor near the bottom right,
>
>> So this "major attractor" is 202 since every one of the 255 sequences ends
>in
>> 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 ?
>
>Yes.
>
>I apologize if my use of attractor is non-standard. If non-standard: please
>enlighten me as to the correct term.
The Collatz Conjecture is just a hobby of mine. I only know what I see
on other people's web sites and there doesn't seem to be a standard
terminology. The reason I asked is someone else used attractor to
refer to a looping point. If you don't halt at 1, the loop 4 2 1 4 2 1 4 2 1...
was said to have an attractor at 1.
Very nice.
>
>--
>Quinn
--
Mensanator
Ace of Clubs
Quinn Tyler Jackson
> >don't distribute the GA code -- since I've never released it and am not
sure
> >I want it floating around just yet.
>
> It would probably be wasted on me as I'm not a C programmer.
Well, I posted the C++ source with the hope that someone may find it useful
in some way or another. [See note 1 about some more Collatz related code
below.]
> The Collatz Conjecture is just a hobby of mine. I only know what I see
> on other people's web sites and there doesn't seem to be a standard
> terminology. The reason I asked is someone else used attractor to
> refer to a looping point. If you don't halt at 1, the loop 4 2 1 4 2 1 4 2
1...
>
> was said to have an attractor at 1.
Hmmm. The attractor terminology I was using was from here:
http://users.frii.com/davejen/hailston.htm
Right under the N vs. HailMax graph.
In re: the graphics:
> Very nice.
Thanks. The big problem, of course, is the scaling. There are only 218
steps, but 13 billion is the peak value (or thereabouts). To work with that,
I had to use 35*ln(n) or something like that, and that produces some
artifacts and interference patterns that required some fine tuning to try to
eliminate -- but I wasn't entirely successful.
My goal was to produce the graphics in 16 or so or less lines of C++ -- so I
couldn't color correct too much, and the moires appear.
--
Quinn
[1] Here's a nifty little bit of C++ template that compiles the peak and
step values for a given constant integer at compile time, rather than run
time.
// Collatz Template Explicit Instantiation.
// Author: Quinn Tyler Jackson
// Released to the public domain. Rope it, ride it, hang it out to dry. Just
don't blame me
// if it invites your inlaws over for dinner when you least expect it.
#include <iostream>
template <size_t N, bool __isodd__ = ((N&1)==1)>
class Collatz
{
const size_t _k;
};
template<size_t N>
class Collatz<N, true>
{
public:
typedef Collatz<3*N+1> base_t;
enum { v = base_t::v };
enum { k = base_t::k + 1 };
enum { p = (N > base_t::p) ? N : base_t::p };
};
template<size_t N>
class Collatz<N, false>
{
public:
typedef Collatz<N/2> base_t;
enum { v = base_t::v };
enum { k = base_t::k + 1 };
enum { p = (N > base_t::p) ? N : base_t::p };
};
template<>
class Collatz<1, true>
{
public:
enum { v = 0 };
enum { k = 0 };
enum { p = 1 };
};
int main(void)
{
std::cout // just some fun that amounts to 111 -- to test nesting.
<<
Collatz<
Collatz<
Collatz<
Collatz<
Collatz<
27
>::k
>::k
>::k
>::k + 10
>::k
<< std::endl;
std::cout << Collatz<27>::p << std::endl; // the peak value reached by 27
return 0;
}
Quinn Tyler Jackson
number
> >of Collatz steps, 1 = 1 subsequent integer with the same Collatz steps,
to
> >some N. The highest N found was the number originally mentioned:
> >3,298,601,216.
>
> Eek! I don't picture myself doing any genetic programming in the near
future.
Well, it's not all that scary when one has the majority of the code wrapped
up in the template. GA's can be tweaked to find lots of interesting things
about numbers without knowing what numbers one is even looking for.
In the code I put up, the key to changing "what" one is looking for, rests
in changing the fitness function in ga_hailstone.cpp.
For instance, to find long sequences of consecutive identical hailsteps, one
does this:
template <size_t N, size_t W, class T>
size_t fitness_function(const QGenetic::Chromosome<N,W,T>& g, void* p)
{
size_t f = 0;
size_t n = 0;
// turn the alleles into a 32-bit integer:
for(size_t i = 0; i < K; i++)
{
n += g.aa[i].v == 1 ? 1<<i : 0;
}
size_t hs = hailstone(n); // get the hailsteps for N
f = 1;
size_t fd = 0;
for(size_t i = 1; i < D; i++)
{
if(hs == hailstone(n+i))
{
f++; // for every subsequent identical hailstep -- add 1 to the
"fitness" measure of this chromosome
}
else
{
break;
}
}
if(f > mf)
{
mf = f;
// this is the "most fit match" found yet
cout << "--" << endl;
}
return f;
}
That's pretty straight forward. The main problem with this is that GAs tend
to optimize locally very quickly on problems such as "find the longest
sequence of consecutive hailsteps you can." They find a "good" answer
quickly enough -- but can totally miss the "best" answer. This is what I
meant when I said that the 255 sequence one was a fluke. I had to run the
thing quite a few times for the initial gene pool to happen upon that one.
If you change the "fitness" function, you can find just about anything in
the 2^32 space in quite reasonable time, without exhausing all 2^32
possibilities. For instance, you might say, "I'm interested in knowing which
consecutive integer pairs' hailsteps add up to 666."
How would you go about finding such a pair?
First, let's call the fitness of such a match F. Then, let's call the
fitness of a candidate genome F-D (where D is distance from F.) We then
modify the fitness function thus:
template <size_t N, size_t W, class T>
size_t fitness_function(const QGenetic::Chromosome<N,W,T>& g, void* p)
{
size_t f = 0;
size_t n = 0;
for(size_t i = 0; i < K; i++)
{
n += g.aa[i].v == 1 ? 1<<i : 0;
}
size_t hs = hailstone(n);
int sum = hs + hailstone(n+1);
f = 10000 - abs(666-sum);
if(f > mf)
{
mf = f;
std::cout << n << ":" << sum << std::endl;
}
return f;
}
Which produces the output:
1361944053:529
3139078170:609
4243168805:628
3992878932:664
1333738242:666
Very quickly. So:
HS(1333738242) + HS(1333738243) == 666
Less than a second to find that pair.
949554455:373
2256181445:440
4053248959:558
1729800855:610
2487648206:642
3708619903:643
1723013404:646
2723854072:668
1385171605:666
So:
HS(1385171605)+HS(1385171606) == 666
And so on, to your heart's content. No brute force required. Effective.
Possibly allows some mathematicians here to find interesting mathematical
properties of integers.
Hope someone finds some use for it -- which is why I've let it "out of the
lab" for general use. It's not a spectacular piece of code -- but it's
served me well for a few years.
--
Quinn