new Collatz-related discovery
mensa...@aol.com
values of C that are not divisible by 3). The Collatz Conjecture is
equivalent to asserting that 3n+1 contains only one graph. This
single graph is trivial since the denominator of the Crossover Point
of the loop cycle at the root of the graph is a unit.
Every 3n+C also contains a trivial graph. But every 3n+C fails the
conjecture because every node on the trivial graph is a multiple of C
which means there must be at least one non-trivial graph where
non-multiples of C are found.
How many non-trivial graphs? Hard to say, it depends on C. It appears
to follow the rules:
- exactly one trivial graph
- one (or more) non-trivial graph for every divisor of C
For example, take C=35. The divisors are 1, 5, 7, 35, so there must
be four graphs. But there can be multiple graphs associated with the
same divisor, so 3n+35 actually has 9 graphs:
divisor 1: 2 graphs
divisor 5: 1 graph
divisor 7: 5 graphs
divisor 35: 1 graph
THE PROBLEM: How to graph hop?
If I'm on the trivial graph, I want to be able to hop to a different,
non-trivial graph. Simply changing to a value that's not a multiple
of C won't cut it as I want to hop to a specific non-trivial graph
having the same Sequence Vector as the graph I'm currently on.
Actually, I want any graph associated with a specific divisor, so I
don't care which of the divisor 7 graphs of 3n+35 I hop to.
Once you make the hop, you can easily verify because the Greastest
Common Divisor of the seed:hailstone of the Sequence Vector on that
graph will be a divisor of C (or possibly a multiple of the divisor).
But I want to choose BEFORE making the hop.
Now, I haven't solved it yet (and it may be intractable), but I
made a major breakthrough towards that end and discovered a new
relationship.
Every Sequence Vector has an associated Hailstone Function and
each Hailstone Function has an infinite number of integer solutions.
These solutions (ai) can be ordered by Hailstone Function Parameter
Y. Thus,
ai = Y*i + a0
But every Sequence Vector appears infinitely many times on EVERY
graph. That means in the ordered list of solutions, the indexes
are associated with the divisors:
for Sequence Vector [3] in 3n+35
+----+--div_1--+----+---------+---------+----+----+----+
| | | | | | | | |
a11 a12 a13 a14 a15 a16 a17 a18 a19 a20 a21 a22 a23
| | | |
+---div_5------|---------+ |
+--div_7 |
div_35-------------------+
Can we tell, not knowing what the divisors are, which indexes
are associated with a divisor that is neither 1 nor C (such as
a13, a16 or a18 above)?
Good News #1: we can use ANY Sequence Vector
Good News #2: if ai is associated with divisor D, then so is a(i+D)
Bad News : we don't know which index associated with D is the
first one
For example, the first solution in Sequence Vector [3] in 3n+35
where the gcd() is 35 has a solution index of 23, i.e., a23.
If we had picked [4] instead of [3], then a11 is the first
solution. Once we know these the other solutions occur at:
[3] a23 a58 a93...ai, a(i+35)
[4] a11 a46 a81...aj, a(j+35)
How do we find the first i? For small C, we could empirically find
it by testing all i from 1 to C as in the 3n+35 example. But what
if C is huge, say C = 31074182404900437213507500358885679300373460
228427275457201619488232064405180815045563468296717232867824379162
728380334154710731085019195485290073377248227835257423864540146917
36602477652346609?
My latest discovery is how to calculate i for the trivial graph
(where gcd=C) for any value of C. This one is easy since ALL
trivial graphs have the same structure.
>From the graph, we know that the first occurence of [3] is at node
2*C, so
ai = 2*C
We also know from the Hailstone Function that
8*a === 35 (mod 3)
so a0 must be 1. And, since Y=3,
ai = 3*i + 1
in other words
3*i + 1 = 2*C
or
2*C - 1
i = ---------
3
So, for [3] in 3n+35 we have
2*35 - 1
i = ----------
3
i = 23
which is exactly what we found empirically.
For [4], we see from the graph that the first solution has
hailstone 1*C and we have to re-calculate a0:
16*a === 35 (mod 3)
a0 = 2
Thus, i becomes
1*35 - 2
i = ----------
3
i = 11
which is what we found empirically.
But wait, the constants are instances of variables:
the 2 is the a0 of the 3n+C graph
the 3 is Y from the Hailstone Function (X*a-Z*C)/Y
the 1 is the a0 of the 3n+1 graph, which we'll call a00
The solution for i (gcdCindex) is thus (drum roll...):
*** ***
*** C*a00 - a0 ***
*** gcdCindex = ---------- ***
*** Y ***
*** ***
Let's see if this works for a REALLY BIG number, say
C = 31074182404900437213507500358885679300373460228427275457
201619488232064405180815045563468296717232867824379162728380
334154710731085019195485290073377248227835257423864540146917
36602477652346609?
I'm going to attemp to use a large Y in an effort to make
gcdCindex as small as possible, so I want to choose a Sequence
Vector where Y is similar in size to C.
< Python session follows >
# How big does the Sequence Vector have to be such that Y is
# just less than C?
# Y is a power of 3, so we need to find e such that 3**e <= C.
# I can't do base 3 logarithms on unlimited precision integers,
# but I can convert C to base 3 and count the digits.
>>> import collatz_functions as cf
>>> s3 = cf.gmpy.digits(C,3)
>>> s3
'11220010122200102221111000010201010111221112212210122002120
00111120110220211211220001110112201121200111010110102102002
21022210011102110101202020202121112012220212121122020110101
10201002121001122202110122221010111220110020202021022221122
22012201101220202001200221220100100110202110121110102001011
12202220202201221200211000020102100201111021001002001200111
20002211110110022200020000110002010000020000001012'
>>> print len(s3)
404
>>> C-3**404
-26071958375207756613588559617621505634997978957930450310724
07131127022489160136162126576351213494580028113222848015795
44575024013031587035369674450309253303573904072477057067685
1303472408781472L
# Slightly too big, so 1 less.
>>> C-3**403
120254688115310392711421470333832843219163138329747002012263
892217313013062534228232870576937665066451225420323255342379
506396869556265624778709005745237084377081468271248623554063
3827631970582L
# Now, make a Sequence Vector with 403 members (all 1's).
>>> sv = [1 for i in xrange(403)]
>>> sv
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1]
# Get the Hailstone Function Parameters for this Sequence Vector.
>>> xyz = cf.calc_xyz(sv)
>>> xyz
(mpz(2065799902469526871724735337602409499463764634263378810
2645274852325180976134729557037162826241102651487225375
781979947008L),
mpz(1904871359336939794236535332550239497845714639545257525
5975230266500763098927392222276410602950726222701837130
4028460962040710441293926330074191728027245193975492770
3741528456195968650020376027L),
mpz(1904871359336939794236535332550239497845714639545257525
5975230266500762892347401975323723430477192462460887184
0263826698661900176766441097556094114554289490259210146
2638876968970592868040429019L))
# Solve the Hailstone Function g0 = (X*a0 - Z*C)/Y
# First, the hailstone (using linear congruence).
>>> a0 = cf.gmpy.divm(C*xyz[2],xyz[0],xyz[1])
>>> a0
mpz(7023244781838358671223206292119110656540832562477875054
7488410447694617926739693989893529091842195775792950980
7731185825343135717376607052954827222820081095984113021
029042220655334822388405445L)
# Second, the seed.
>>> g0 = cf.seed_C(a0,xyz,C)
>>> g0
mpz(-310741824049004372135075003588856793003734602284272754
572016194882320639920208345516580939517701653473424792
699754534814789486781795221489816705506826570870920008
9904248711717285850913692452593L)
# Note to positive domain purists: 3n+C sytems can cross
# the y-axis, positive hailstones can have negative seeds.
# Find gcd(seed,hailstone).
>>> cf.gmpy.gcd(g0,a0)
mpz(1)
# As expected, gcd is 1. We need to find the first index where
# the gcd is C. But C is too large for a brute force search.
# Ah, but the trivial graph is identical in structure for all
# C in 3n+C and each node on the 3n+C graph is simply C times
# the equivalent node in the 3n+1 graph.
# So find the 3n+1 node for this sv.
>>> a00 = cf.gmpy.divm(xyz[2],xyz[0],xyz[1])
>>> a00
mpz(1904871359336939794236535332550239497845714639545257525
5975230266500763098927392222276410602950726222701837130
4028460962040710441293926330074191728027245193975492770
3741528456195968650020376026L)
# C*a00 - a0
# The 3n+C index will then be ----------
# Y
>>> gcdCindex = (C*a00 - a0)/xyz[1]
>>> gcdCindex
mpz(3107418240490043721350750035888567930037346022842727545
7201619488232064405180815045563468296717232867824379162
7283803341547107310850191954852900733772482278352574238
6454014691736602477652346607L)
# Now that we know the index, we can determine the hailstone.
>>> ai = xyz[1]*gcdCindex + a0
>>> ai
mpz(5919232007790671272016392533942262870859913860691816124
8846175563455937853724870598106111008765329420620907021
4903340891950027845394631634358393222732138181222995578
6974244765253197676215346843062883714292249198777668905
2692140458355039048178182463458002033377734530467685318
8732483925637959371296031717377143113204768878077406062
6161510485968762947787005407043998235534116483465995834L)
# And from the hailstone, the seed.
>>> gi = cf.seed_C(ai,xyz,C)
>>> gi
mpz(6419304298136361117139766274497550819061438634123659848
4787117228815725951840591624557803849314185663340918812
8478887788290501435080061235301374322479622383922951356
9022559559019320951536547983551912001133883046798271174
5352799022130596132403057133130439010879938598723206402
033625724487442001476810278075016149263L)
# Now, if all has worked correctly, this seed:hailstone pair is
# the first such in this Sequence Vector that has a gcd of C.
>>> gcdC = cf.gmpy.gcd(gi,ai)
>>> gcdC
mpz(3107418240490043721350750035888567930037346022842727545
7201619488232064405180815045563468296717232867824379162
7283803341547107310850191954852900733772482278352574238
6454014691736602477652346609L)
# Is it C?
>>> C - gcdC
mpz(0)
# QED
# And gcd=C occurrences happen at the every C indexes.
>>> gcdCindex2 = gcdCindex + C
>>> ai2 = xyz[1]*gcdCindex2 + a0
>>> gi2 = cf.seed_C(ai2,xyz,C)
>>> cf.gmpy.gcd(gi2,ai2)
mpz(3107418240490043721350750035888567930037346022842727545
7201619488232064405180815045563468296717232867824379162
7283803341547107310850191954852900733772482278352574238
6454014691736602477652346609L)
# Interestingly, C - gcdCindex = 2
# I was trying to get an index close to 0, but it seems I
# instead got just the opposite, an index close to C.
</Python session >
And anything I can do in a Python session I can do in a
Python program. I obviously mis-guessed how to get a low
gcdCindex, but with the program, I can experiment.
For example, by simply chaging the 403 Sequence Vector elements
from 1 to 2, I get
## s3: C in base 3
## 11220010122200102221111000010201010111221112212210122002
## 12000111120110220211211220001110112201121200111010110102
## 10200221022210011102110101202020202121112012220212121122
## 02011010110201002121001122202110122221010111220110020202
## 02102222112222012201101220202001200221220100100110202110
## 12111010200101112202220202201221200211000020102100201111
## 02100100200120011120002211110110022200020000110002010000
## 020000001012
##
## s3 digits
## 404
##
## new ls3
## 403
##
## sv: Sequence Vector
## [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
## 2, 2, 2, 2, 2, 2, 2]
##
## Hailstone Function Parameters
## X
## 42675292370431067354111051460616049901726453262821812226
## 53604999528983832203284525773716608557794746075475142779
## 79727388536883305863639365143254787349173122950090085088
## 89693174163701029835609758265376103269674252682820787439
## 8493522634488152064
##
## Y
## 19048713593369397942365353325502394978457146395452575255
## 97523026650076309892739222227641060295072622270183713040
## 28460962040710441293926330074191728027245193975492770374
## 1528456195968650020376027
##
## Z
## 42675292370431067354111051460616049901726453262821621739
## 40011630131041466849959023378738151411399293500219167549
## 53077312226990566641411724082959714726902939237049800479
## 27652463722407103505535566537348858075698759912446634594
## 2297553984467776037
##
## a0: first sv solution on the 3n+C trivial graph
## 12025468811531039271142147033383284321916313832974700201
## 22638922173130130625342282328705769376650664512254203232
## 55342379506396869556265624778709005745237084377081468271
## 2486235540633827631970582
##
## g0: seed of a0
## -4267529237043106735411105146061604990172645326282150148
## 47120009909177032470292564009441623509756631880001794116
## 03090418209636522435908301831358306406239068503381724705
## 54814606685285083788075685753160362099132167844417538597
## 06756920156835805455
##
## gcd0: Greatest Common Denominator of g0,a0
## 1
##
## a00: the number corresponding to a0 on the 3n+1 graph
## 1
##
## gcdCindex: index of the sv solutions where gcd(g0,a0)=C
## 1
##
## ai: the hailstone at this index
## 31074182404900437213507500358885679300373460228427275457
## 20161948823206440518081504556346829671723286782437916272
## 83803341547107310850191954852900733772482278352574238645
## 4014691736602477652346609
##
## gi: the seed at this index
## 31074182404900437213507500358885679300373460228427275457
## 20161948823206440518081504556346829671723286782437916272
## 83803341547107310850191954852900733772482278352574238645
## 4014691736602477652346609
##
## gcdC: gcd(gi,ai)
## 31074182404900437213507500358885679300373460228427275457
## 20161948823206440518081504556346829671723286782437916272
## 83803341547107310850191954852900733772482278352574238645
## 4014691736602477652346609
##
## QED
##
## indexDiff: relative position of gcdCindex to C
## 31074182404900437213507500358885679300373460228427275457
## 20161948823206440518081504556346829671723286782437916272
## 83803341547107310850191954852900733772482278352574238645
## 4014691736602477652346608
How about that? I'll take the gcdCindex of 1 as that's about
as small as you can get.
Now, if I can only identify the indexes of the other graphs...