M.Brushi's paper on Collatz generalizations

[Mensanator]

What was I thinking? Should have cross-posted this here.

-----------------------------------------------------------

http://arxiv.org/abs/0810.5169

This link was just added to Wikipedia.

Anyone have an opinion on it?

My opinions are:

<not worth reading>

This is what I think as of now:

From: Mensanator <mensana...@aol.com>
Newsgroups: sci.math
Subject: I got it now (was: M.Brushi's paper on Collatz
generalizations)
Date: Tue, 11 Nov 2008 18:02:25 -0800 (PST)

I think.

I admit I was baffled by the Bruschi extensions, mystified
by his non-standard approach and frustrated trying to
incorporate his extentions into my Sequence Vector theory.

But I think I succeeded. I had to go back to the algebra
of sequences and re-cast all my functions to accomodate
his extensions. Turns out the basic concepts work the same
but the details vary from 3n+1 (or the 3n+C extensions
I'm used to using).

Bruschi's system is more like Dn+C where D is a constant
once b & m are chosen but C is not. Also, with D being
b**m+1, none of the 3n+C extensions exist in Bruschi's
world.

Now, in 3n+C, C must be an odd number or you get parity
lock (the successor of an odd number is an odd number).
By dynamically changing C during the sequence, Bruschi
avoids parity lock and an "odd" number is always succeeded
by an "even" number (where "even" means congruent to
0 (mod b) and "odd" is any number not congruent to
0 (mod b)). This ensures that every Bruschi system exhibits
the desired hailstone effect.

Every sequence in a Bruschi system can be written as a
"parity" vector:

odd even odd even even

Since the successor of an "odd" is always "even", a
sequence cannot contain more than one consecutive "odd"
(but any number of consecutive "evens" - more on this later).
If I add the trivial requirement that a sequence start on
an "odd" number, the "parity" vector can be consolidated
as a Sequence Vector, a list of integers that count blocks
of consecutive "evens" and each block is assumed to be
preceeded by exactly one "odd". Thus, the parity vector

odd even odd even even

becomes the Sequence Vector

[1,2]

Note: no element of a Sequence vector can be 0 because that
would imply consecutive "odds" which can't happen (more on
this later).

So, we can take a starting number 'a', apply the Sequence
Vector to reach an ending number 'g'.

a ===> [1,2] ===> g

Or

a => 3*a + 1 # the "odd" rule preceeding the 1
=> (3*a + 1)/2 # the "even" rule applied once
=> (9*a + 5)/2 # the "odd" rule preceeding the 2
=> (9*a + 5)/8 # the "even" rule applied twice

Thus, g = (9*a + 5)/8.

In 3n+1, ALL sequences reduce to the form

Y*a + Z
g = --------- (Hailstone Function)
X

The constants X,Y,Z can be determined from the Sequence
Vector, so we can step directly from 'a' to 'g' without
having to iterate through all the intermediate values and
yet be assured they are all integers.

Furthermore, from the linear congruence

Y*a == -Z (mod X)

we can find the first number 'a0' that results in the given
Sequence Vector leading to 'g0'.

EXAMPLE: Sequence Vector [1,2,3,4] in 3n+1

Hailstone Function Parameters

X: 2**sum(SV) = 2**(10) = 1024
Y: 3**len(SV) = 3**(4) = 81
Z: 3**0 * 2**6 +
3**1 * 2**3 +
3**2 * 2**1 +
3**3 * 2**0 = 64+24+18+27 = 133

Note how Z is calculated. It's the sum of terms (as
many as elements in SV) that are powers of 3 times
a power of 2. The exponents of 3 simply count up from
0. The exponents of 2 are: the sum of SV elements
except the last one, the sum of SV elements except the
last two, the sum of elements of SV except the last
three, etc. The last term excepts all the elements so
is always 0. Yes, exponents of 0 make the power 1, they
are shown for completeness.

So for SV = [1,2,3,4] we have

g = (81*a+133)/1024

and solving the linear congruence

81*a == -133(mod 1024)

gives us an 'a0' of 11. Plugging 11 into the Hailstone
Function

81*11+133 891+133 1024
g = --------- = ------- = ------ = 1
1024 1024 1024

So 'g0' equals 1.

So 11 ==> [1,2,3,4] ==> 1.

Check: 11_34
17_52
26
13_40
20
10
5_16
8
4
2
1
QED

And, if a linear congruence has one solution, it has an
infinite number of solutions. We can find any of the
infinite places where SV=[1,2,3,4] occurs from the
Hailstone Function Parameters once we know 'a0':

ai = i*Y + a0

And

gi = i*X + g0

Finally, a sequence is a limit cycle (Bruschi's
terminology) if the Crossover Point (Z/(X-Y)) is an
integer.

That's for 3n+1. To use a 3n+C extension, all we have to do
is multiply the Z parameter by C. The Hailstone Function
becomes (Y*a+Z*C)/X and the Crossover Point becomes
Z*C/(X-Y).

ALL OF THE ABOVE FALLS APART IN BRUSCHI'S EXTENSIONS :(

Whenever m>1.

Furthermore, because C isn't constant, we can't simply
multiply the Z parameter by it. It has to be combined
with the terms that comprise Z and can be different for
every term.

To address that, we need a new list (which I call the
Residue Vector) which will be a list of (n % b**m) values
(which when subtracted from b**m gives the "parity" of
the "odd" numbers in the sequence.

Now, just as a Sequence Vector can't have a 0 element, a
Residue Vector element must be co-prime to b. Furthermore,
for Bruschi extensions, the Sequence Vector can't have an
element <m. Just as an odd number in 3n+1 must be followed
by at least one even, in Bruschi extensions, an "odd"
number must be followed by at least m "evens".

Given a valid Sequence Vector (no elements <m) coupled with
a valid Residue Vector (all elements co-prime to b), the
algebra of the Bruschi sequence where

b = 5 m = 4
SV = [8,5,10,7,5,5]
RV = [119,224,217,446,196,404]

works out to

g = (b**m+1)**6*a + (b**m+1)**5*RV[0]*b**0
+ (b**m+1)**4*RV[1]*b**8
+ (b**m+1)**3*RV[2]*b**13
+ (b**m+1)**2*RV[3]*b**23
+ (b**m+1)**1*RV[4]*b**30
+ (b**m+1)**0*RV[5]*b**35
---------------------------------------
b**40

which reduces to

60179143072269376*a + 1292147884073573925357403244
g = --------------------------------------------------
909494701772928379150390625

so a0 = 4448230751634496791125855506
g0 = 29432905359344748

And running the Bruschi sequence from a0 to g0

## 4448230751634496791125855506(o 506)
## 2784592450523194991244785546875(e(
## 556918490104638998248957109375(e)
## 111383698020927799649791421875(e)
## 22276739604185559929958284375(e)
## 4455347920837111985991656875(e)
## 891069584167422397198331375(e)
## 178213916833484479439666275(e)
## 35642783366696895887933255(e)
## 7128556673339379177586651(o 401)
## 4462476477510451365169243750(e)
## 892495295502090273033848750(e)
## 178499059100418054606769750(e)
## 35699811820083610921353950(e)
## 7139962364016722184270790(e)
## 1427992472803344436854158(o 408)
## 893923287974893617470703125(e)
## 178784657594978723494140625(e)
## 35756931518995744698828125(e)
## 7151386303799148939765625(e)
## 1430277260759829787953125(e)
## 286055452151965957590625(e)
## 57211090430393191518125(e)
## 11442218086078638303625(e)
## 2288443617215727660725(e)
## 457688723443145532145(e)
## 91537744688629106429(o 179)
## 57302628175081820625000(e)
## 11460525635016364125000(e)
## 2292105127003272825000(e)
## 458421025400654565000(e)
## 91684205080130913000(e)
## 18336841016026182600(e)
## 3667368203205236520(e)
## 733473640641047304(o 429)
## 459154499041295612500(e)
## 91830899808259122500(e)
## 18366179961651824500(e)
## 3673235992330364900(e)
## 734647198466072980(e)
## 146929439693214596(o 221)
## 91977829247952337500(e)
## 18395565849590467500(e)
## 3679113169918093500(e)
## 735822633983618700(e)
## 147164526796723740(e)
## 29432905359344748(o 373)

confirms that the blocks of "evens" match the given
Sequence Vector and that the "parity" of the "odd" numbers,
when added to the corresponding Residue Vector element,
add to a constant 625 (b**m).

For this example, evaluating the Crossover Point yields
a quotient of 0 and a remainder of 1292147884073573925357403244.
That is a LONG way from being an integer.

In fact, if we look closer at his given counter-examples
for m=1, we see a pattern in the Sequence Vectors:

b=3 [1,1,1,1,1,1,3]
b=4 [1,1,1,1,1,1,1,1,2,1,1,2]
b=6 [1,1,1,1,1,1,1,1,1,1,2]
b=7 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]

Looks like we need a long sequence of small numbers if the
Z parameter has any chance of being larger than X-Y so that
we can get a non-0 quotient. Now if m=4, the SV can't
contain any values <4 making the task MUCH more difficult,
but possible if we have ALL large Residue Vector elements
or a really long SV. With, say random RV elements and a
sparse SV (657 elements between 4 and 6 in a 8:1 ratio of
4s to 6s), Y was 626**657, X was 5**2852, the Z parameter
had 1996 digits, and 'a0' had 1994 digits and STILL the
Crossover Point quotient was no greater than 13!

Even if this was a limit cycle, it's unlikely Bruschi would
encounter it in his brute force testing. Not that this method
is any easier, but it helps to know what you're up against.

I would guess that the counter-examples Bruschi speculates
don't exist simply haven't been found as the search is
likely intractable as m increases.

And even if they don't exist, so what? How does being
limited to SVs that can't have an element less than 4 help
to understand a system where they can?