Factor Congruence - a case study
mensa...@aol.com
by searching only those Sequence Vectors whose Hailstone Function
parameters had matching congruence classes mod C.
But not all matching parameters generated attractors. And what
if C were composite, say 85085. Why 85085? Beacuse it is the
composite of the 5 primes > 3: 85085 = 5 * 7 * 11 * 13 * 17.
Thus, there will be a lot of factors available to the Crossover
Point Function to form attractors.
Running the collatz_C function for C=85085 over the range
-2000000 to +2000000, a total of 156 attractors were located.
When C is composite, some of its factors may not be necessary to
form an attractor. In such cases, the unused factors will appear
as the greatest common divisor of the odd numbers in the loop
sequence. So the gcd will tell us the divisor whose congruence
classes must be matched:
divisor = 85085/gcd
And just as factor congruence matching is necessary but not
sufficient for attractors, there can be any number of attractors
found for any given divisor.
Since there are 5 factors in 85085 any of which may or may not
be canceled, there are 32 possible gcd|divisor pairs:
fac5 fac7 fac11 fac13 fac17 divisor gcd
1 1 1 1 1 1 85085
1 1 1 1 17 17 5005
1 1 1 13 1 13 6545
1 1 1 13 17 221 385
1 1 11 1 1 11 7735
1 1 11 1 17 187 455
1 1 11 13 1 143 595
1 1 11 13 17 2431 35
1 7 1 1 1 7 12155
1 7 1 1 17 119 715
1 7 1 13 1 91 935
1 7 1 13 17 1547 55
1 7 11 1 1 77 1105
1 7 11 1 17 1309 65
1 7 11 13 1 1001 85
1 7 11 13 17 17017 5
5 1 1 1 1 5 17017
5 1 1 1 17 85 1001
5 1 1 13 1 65 1309
5 1 1 13 17 1105 77
5 1 11 1 1 55 1547
5 1 11 1 17 935 91
5 1 11 13 1 715 119
5 1 11 13 17 12155 7
5 7 1 1 1 35 2431
5 7 1 1 17 595 143
5 7 1 13 1 455 187
5 7 1 13 17 7735 11
5 7 11 1 1 385 221
5 7 11 1 17 6545 13
5 7 11 13 1 5005 17
5 7 11 13 17 85085 1
The 156 attractors are distributed such that all possible gcds
are represented. So we have to calculate matches for each of the
32 divisors.
gcd count of attractors
1 23
5 5
7 17
11 10
13 4
17 7
35 6
55 3
65 3
77 6
85 2
91 2
119 4
143 3
187 4
221 7
385 1
455 2
595 3
715 6
935 3
1001 2
1105 4
1309 1
1547 3
2431 2
5005 4
6545 8
7735 3
12155 1
17017 3
85085 4
But we're just trying to verify that Factor Congruence matching
actually works, so instead, we'll take the known attractors and
see if they hold up to the congruence matching scrutiny:
http://members.aol.com/mensanator666/collatz/85085_cc_verify.htm
Which they do. That means we can verify the attractors with the
partition generator program. Generating every partition of
P items in Q groups is equivalent to creating every possible
Sequence Vector whose sum is P and count is Q.
So, grabbing a P,Q pair from the stats table
python partition_generator.py 4 3
searching: 3 Sequence Vectors
[1,1,2] -146965 *
[1,2,1] -177905
[2,1,1] -224315
we get three Sequence Vectors with integer Crossover Points
(the one marked * is the attractor shown on the stats table).
But note that the three vectors are all cyclic permutations
of the same numbers. that means they are all part of the same
loop:
-146965__-355810
-177905__-448630
-224315__-587860
-293930
-146965
So the partition generator will return exactly Q Sequence Vectors
for each attractor found.
Exactly?
python partition_generator.py 4 2
searching: 3 Sequence Vectors
[1,3] 60775
[3,1] 133705
[2,2] 85085
Here Q is 2 but we got 3 vectors. But that's because the third
vector is a different loop. But it only has 1 vector. That's
because it's actually a second generation type [2] vector, so
we'll mark these false positives with an x. The multi-generation
attractors will always have less than Q vectors.
python partition_generator.py 6 4
searching: 10 Sequence Vectors
[1,1,1,3] -325325 *
[1,1,3,1] -445445
[1,3,1,1] -625625
[3,1,1,1] -895895
[1,1,2,2] -365365 *
[1,2,2,1] -505505
[2,2,1,1] -715715
[2,1,1,2] -515515
[1,2,1,2] -425425 x
[2,1,2,1] -595595
Here the stats table shows two attrators for P=6 Q=4 and that's
what we got, not counting the multi-generation vector.
More interesting is the set of attractors found for P=8 Q=5
python partition_generator.py 8 5
searching: 35 Sequence Vectors
[1,1,1,1,4] 1380995 *
[1,1,1,4,1] 2114035
[1,1,4,1,1] 3213595
[1,4,1,1,1] 4862935
[4,1,1,1,1] 7336945
[1,1,1,2,3] 1485715 *
[1,1,2,3,1] 2271115
[1,2,3,1,1] 3449215
[2,3,1,1,1] 5216365
[3,1,1,1,2] 3933545
[2,1,1,1,3] 2231845
[1,1,1,3,2] 1695155 *
[1,1,3,2,1] 2585275
[1,3,2,1,1] 3920455
[3,2,1,1,1] 5923225
[1,1,2,1,3] 1642795 *
[1,2,1,3,1] 2506735
[2,1,3,1,1] 3802645
[1,3,1,1,2] 2873255
[3,1,1,2,1] 4352425
[1,1,2,2,2] 1852235 *
[1,2,2,2,1] 2820895
[2,2,2,1,1] 4273885
[2,2,1,1,2] 3226685
[2,1,1,2,2] 2441285
[1,2,1,1,3] 1878415 *
[2,1,1,3,1] 2860165
[1,1,3,1,2] 2166395
[1,3,1,2,1] 3292135
[3,1,2,1,1] 4980745
[1,2,1,2,2] 2087855 *
[2,1,2,2,1] 3174325
[1,2,2,1,2] 2402015
[2,2,1,2,1] 3645565
[2,1,2,1,2] 2755445
Once seperated into groups of cyclic permutations, we find we
have seven groups - seven attractors. But the stats table only
lists six. Look at the attractor on the last loop: 2087855.
The original attractor search only extended to 2000000, so the
partition generator found one missed in the original search.
The Sequence Vector search will always find all the attractors...
...provided we know what P and Q to test. Doubling the collatz_C
test range, we find yet another attractor: 3182179.
This one didn't get picked up in the Sequence Vector search
because its loop has P=27 Q=17 and that combination hadn't
appeared before in the stats table. That warrants another
run of the partition generator.
python partition_generator.py 27 17
searching: 5,311,735 Sequence Vectors
[1,1,1,1,1,2,1,1,2,1,2,3,2,1,1,1,5] 3182179 *
[1,1,1,1,2,1,1,2,1,2,3,2,1,1,1,5,1] 4815811
[1,1,1,2,1,1,2,1,2,3,2,1,1,1,5,1,1] 7266259
[1,1,2,1,1,2,1,2,3,2,1,1,1,5,1,1,1] 10941931
[1,2,1,1,2,1,2,3,2,1,1,1,5,1,1,1,1] 16455439
[2,1,1,2,1,2,3,2,1,1,1,5,1,1,1,1,1] 24725701
[1,1,2,1,2,3,2,1,1,1,5,1,1,1,1,1,2] 18565547
[1,2,1,2,3,2,1,1,1,5,1,1,1,1,1,2,1] 27890863
[2,1,2,3,2,1,1,1,5,1,1,1,1,1,2,1,1] 41878837
[1,2,3,2,1,1,1,5,1,1,1,1,1,2,1,1,2] 31430399
[2,3,2,1,1,1,5,1,1,1,1,1,2,1,1,2,1] 47188141
[3,2,1,1,1,5,1,1,1,1,1,2,1,1,2,1,2] 35412377
[2,1,1,1,5,1,1,1,1,1,2,1,1,2,1,2,3] 13290277
[1,1,1,5,1,1,1,1,1,2,1,1,2,1,2,3,2] 9988979
[1,1,5,1,1,1,1,1,2,1,1,2,1,2,3,2,1] 15026011
[1,5,1,1,1,1,1,2,1,1,2,1,2,3,2,1,1] 22581559
[5,1,1,1,1,1,2,1,1,2,1,2,3,2,1,1,1] 33914881
[1,2,1,2,2,1,1,1,1,3,1,1,1,1,2,2,4] 6109103
[2,1,2,2,1,1,1,1,3,1,1,1,1,2,2,4,1] 9206197
[1,2,2,1,1,1,1,3,1,1,1,1,2,2,4,1,2] 6925919
[2,2,1,1,1,1,3,1,1,1,1,2,2,4,1,2,1] 10431421
[2,1,1,1,1,3,1,1,1,1,2,2,4,1,2,1,2] 7844837
[1,1,1,1,3,1,1,1,1,2,2,4,1,2,1,2,2] 5904899 *
[1,1,1,3,1,1,1,1,2,2,4,1,2,1,2,2,1] 8899891
[1,1,3,1,1,1,1,2,2,4,1,2,1,2,2,1,1] 13392379
[1,3,1,1,1,1,2,2,4,1,2,1,2,2,1,1,1] 20131111
[3,1,1,1,1,2,2,4,1,2,1,2,2,1,1,1,1] 30239209
[1,1,1,1,2,2,4,1,2,1,2,2,1,1,1,1,3] 11350339
[1,1,1,2,2,4,1,2,1,2,2,1,1,1,1,3,1] 17068051
[1,1,2,2,4,1,2,1,2,2,1,1,1,1,3,1,1] 25644619
[1,2,2,4,1,2,1,2,2,1,1,1,1,3,1,1,1] 38509471
[2,2,4,1,2,1,2,2,1,1,1,1,3,1,1,1,1] 57806749
[2,4,1,2,1,2,2,1,1,1,1,3,1,1,1,1,2] 43376333
[4,1,2,1,2,2,1,1,1,1,3,1,1,1,1,2,2] 32553521
And, lo and behold, another attractor is found: 5904899.
Unfortunately, verification was halted before the end of the
stats table was reached. For the simple reason that as P and Q
get large, Sequence Vector searching becomes intractable:
python partition_generator.py 48 24
searching: 16,123,801,841,550 Sequence Vectors
python partition_generator.py 52 24
searching: 196,793,068,630,200 Sequence Vectors
python partition_generator.py 56 32
searching: 2,488,589,544,741,300 Sequence Vectors
python partition_generator.py 60 30
searching: 59,132,290,782,430,712 Sequence Vectors
.
.
.
python partition_generator.py 492 264
searching:
66189415264331559482776409694993032407028709677550596291300
19289014193777349831417543311612293951363412449123374691245
6893016976209252459301489030
Sequence Vectors
And there may be some more hiding in other congruence match
pairs that aren't on the original stats table. Noting that
the congruence generations reach as high as 13, 4 there may
be others.
And if there are, they'll fall into their proper place in the
Factor Congruence table.