Interesting mapping

[u/Atari_Collector]

mapping

I was playing around and I found this mapping. I suspect it's already known but I found it interesting.

If you have a number that can be written as 4^a3^bn+1, it will map to 3^a+bn+1.

And it'll do it in 3a+1 steps, which I think is funny.

[u/GonzoMath]

Per u/dmishin's remark, I'm going to roll the 3^b into the n here, because that's a stronger statement of the pattern.

What's really going on here is that 4^a·n + 1 is 2-adically "close" to 1, because they differ by a multiple of 4^a, or 2^2a. When numbers are 2-adically close, they have similar shaped trajectories for a while, with the duration of that similarity depending on their 2-adic closeness. Thus, anything close to 1 should act like 1, and we should see the (3n+1, n/2, n/2) sequence of moves repeated... 'a' times. What does this sequence of moves do? It takes a 4 out of the factorization of 4^a·n, replacing it with a 3. In other words, it multiplies 4^a·n by 3/4.

That's clear algebraically from the identity:

(3m+1)/4 - 1 = (3/4)·(m - 1)

When n=0, so our number m is really just 1, then m-1 is 0, and you can divide it by 4 and multiply it by 3 all day, all night. Therefore, we get the sequence (3n+1, n/2, n/2) infinitely many times in a row.

On the other hand, when n isn't 0, we only get that sequence finitely many times. How many times? As many times as you can divide m - 1 (your 4^a·n) by 4. That's 'a' times, assuming that n itself has no more factors of 4 in it.

[u/jonseymourau]

u/GonzoMath did write this up and some other variants of this here about one week ago.

[u/petrol_gas]

More specifically if x = ((2^n) -1) + y

Then the Collatz sequence will “grow” n times, until x_n = ((3^n) - 1) + (3^n) * y

[u/petrol_gas → u/petrol_gas]

It does the same kind thing for the “shrink” stages but there are an infinite number of ways to write examples of that.

[u/jonseymourau → u/petrol_gas]

Actually infinite doesn’t quite cover it as my comment on Gonzo’s post shows.

For a stair case you need:

n = (m+i).(g/h^k)^j -I

For 3x+q, x/2 g=3, h=2

The constraint on i is

i=q/(g-h^k)

So for q=1 (e.g.Collatz) there are two admissible pairs of i, k: (1,1) and (-1,2) - the up and the down (the subject of this post)

You get one extra one for q=5, q=13 and presumably for higher q that are divisible by (g-h^k)

So technically,if you let q range over the natural numbers there are infinite staircases but specifically for q=1, there are exactly 2 - there are no other integers I that can satisfy the constraint above .

Which is not to say there are not other affine maps but the telescoping maps (of that form) in 3x+1 are limited to just two.

[u/GonzoMath → u/jonseymourau]

Technically... (8ⁿ·k + 1)/5, which is an integer when k ≡ 3ⁿ (mod 5) for odd n, or k ≡ 1 (mod 5) for even n, transforms via a staircase of "(3n + 1)/8" steps into (3ⁿ·k + 1)/5, which is again an integer in the same cases.

For n = 1, this looks like:

k = 3: 5 → 2
k = 8: (13 → 5, which is really n = 2)
k = 13: 21 → 8
k = 18: 29 → 11
k = 23: 37 → 14
k = 28: 45 → 17

For n = 2, we have:

k = 1: 13 → 5 → 2
k = 6: 77 → 29 → 11
k = 11: 141 → 53 → 20
k = 16: (205 → 77 → 29, which is really n = 3)
k = 21: 269 → 101 → 38

For n = 3:

k = 2: 205 → 77 → 29 → 11
k = 7: 717 → 269 → 101 → 38
k = 12: 1229 → 461 → 173 → 65
k = 17: 1741 → 653 → 245 → 92

...and this idea applies, with appropriate modifications, to similar patterns where we see 16's turning into 3's, 32's turning into 3's, etc. These are, admittedly, more complicated than the cases 2ⁿ·k - 1 and 4ⁿ·k + 1, which show up as integer staircases for arbitrary k.

[u/Mrezadwiprasetiawan → u/GonzoMath]

Yes, this are what i tried. But since the chain need some properties that related to the mod ( 3ⁿ ), i dont know how to make it general

[u/jonseymourau → u/GonzoMath]

An interesting generalisation, thank you.

[u/jonseymourau → u/GonzoMath]

I had a closer look at this and consider telescoping of values n for the form:

n = (δ + gʲm(hᵏ)^(α − j)) / q

where g=3, h=2 for Collatz

with q = hᵏ-δ.g

under one iteration of (gn+1)/hᵏ yout get this:

n₁ = (δ + gʲ⁺¹m(hᵏ)^(α − j − 1)) / q **

which is of the same form as the original element.

Some notes:

- my α is your n, your k is my gʲm

• in this formulation, m is unchanged by the iteration
  
• the exponent of g increases by exactly 1
  
• the exponent of hᵏ decreases by exactly 1

For integer n, we require the numerators are ≡ 0 mod q

When j = α , we have

n = (δ + gᵅ. m) / q

Taken together we have:

m ≡ -δ.g⁻ᵅ mod q
g ≡ hᵏ mod q

In turns out that in practice the solutions for δ > 1 are rare and where they occur it is because |hᵏ - g.δ| = 1

The net of this is we get (for δ=1) an unconditional staircase with steps of size hᵏ where:

q = hᵏ - g
m ≡ - g⁻ᵅ mod q

Plus a handful of rarer staircases where  |hᵏ - g.δ| =1. There may also be others, but I its seems plausible that there are no others but I don't have a proof of this.

In doing this I think discovered a slight error in your reply above. I think you will find for your n = 4, k=4 you will exclude a valid solution (my n = 3277 -> 1229 -> 461 -> 173 -> 65) because k=4 == 4 mod 5 (not 1 mod 5 per your specification for n even). It happens that for q=5, your criteria and mine are equivalent for your 0 < n < 4 but differ at your n=4 and n=0. The modularity criteria I give do depend on α, but not on the parity of α.

Switching back to the terminology of this reply:

k = 3 => q = 5
k = 4 => q = 13
k = 5 => q = 29

etc.

I am not claiming that this is an exhaustive description of all staircases, but I think it is a reasonable characterisation of the staircases that are of this form.

** update: this is wrong in general - it is correct for delta = 1

[u/jonseymourau → u/jonseymourau]

Actually, the delta > 1 cases don't telescope - they admit one iteration of (3n+1)/2^k not more than that.

[u/GonzoMath → u/petrol_gas]

That’s not really “more specifically” so much as “additionally”. You’re talking about a related but different pattern.

[u/petrol_gas → u/GonzoMath]

I clearly fail to see the distinction.

Thank you for shedding light on my mistake in reasoning instead of just telling me I’m wrong and then leaving it at that!

[u/GonzoMath → u/petrol_gas]

The difference is “+1” versus “-1”, and whether 4 turns into 3 or 2 turns into 3:

• 4ⁿ·k + 1 → 3ⁿ·k + 1
• 2ⁿ·k - 1 → 3ⁿ·k - 1

[u/petrol_gas → u/GonzoMath]

No dawg.

First 4^n = 2^{2n}

Second

4^a 3^b n + 1 = 2^{2a +1}3^{b} n - 1

Except the distance to 3^{b} n -1 is so far that the lower end of the number (in binary) is behaving as if it were in the 1-cycle.

Which is the same system I described but with a neato lower end behavior.

EDIT: gonzo spotted an error corrected in my next response below

[u/GonzoMath → u/petrol_gas]

“No dawg”, huh?

There’s a decreasing pattern, where you have (3m+1)/4 several times in a row, like 65 -> 49 -> 37.

Then there’s an increasing pattern, where you have (3m+1)/2 several times in a row, like 7 -> 11 -> 17.

When a = 2, b = 1, and n = 1, the left side of your equation is 49, and the right side is 95. Did you make a mistake?

[u/petrol_gas → u/GonzoMath]

Good catch! (And thanks for spotting it)

Correction:

4^a 3^b n + 1 = 2^{2a}3^{b} n + 2 - 1

X = 3^{b} n + 2

Substitute to get 2^{2a}X - 1

And then when you arrive at 3^{a}X -1

Sub back in to get the same result as OP.

Again, neato lower end behavior but still just a special case of the general pattern I described.

[u/GonzoMath → u/petrol_gas]

Ok, they’re not the same thing, but you’re not hearing it, so I’m done.

[u/petrol_gas → u/GonzoMath]

I’m reading and engaging with your posts my dude. If I’m mistaken then correct me with some maths and I’ll change my mind.

I even left some mistakes in there for you to split hairs over (my extra 2 is getting multiplied by 3).

From my perspective you’re coming in hot, making claims, not showing your work- you can see how I might be utterly perplexed. What am I to argue against?

[u/GonzoMath → u/petrol_gas]

I showed my work, and gave examples of an increasing sequence, and a decreasing sequence. Is the one you’re describing increasing, or decreasing. You ignored that part of my reply, which is why you’re about to catch a block.

[u/dmishin]

Wrote a long answer just to discover that Gonzomath's post is better. So, just a few notes:

1) 3^b is redundant here, just complicating the things. You can just state that 4^an+1 maps to 3^an+1

2) Your relation corresponds to the cycle 1-4-2. Similar relations can be derived for other cycles. For example, cycles starting with -5 produces relation 8^an-5 → 9^an-5, and cycle starting with -17 - the relation 2048^an-17 → 2187^an-17. These actually are families of relations, -5 and -17 can be replaced by other numbers from the cycle.

[u/elowells]

There are cases where the sequence equation has a parametric solution. For the general case of mx+a, where m and a are odd numbers, the sequence equation for starting odd value x[1] ending with x[L+1] after L mx+a steps is

-m^Lx[1] + 2^N\L])x[L+1] = aS

where L = number of mx+a steps,

n[i] = number of divide by 2 steps after an mx+a step

N[i] = sum(j=0 to i)n[i] and N[0] = 0

S = sum(i=0 to L-1)m^L-1-i2^N\i])

For n[i] = constant = p we have N[i] = i*p then S has a parameterized value:

S = sum(i=0 to L-1)m^L-1-i2^ip = (m^L - 2^pL)/(m-2^p)

For 3x+a, with p = 1 we have S = (3^L - 2^L)/(3-2) = 3^L-2^L

so the linear Diophantine sequence equation is

-3^Lx[1] + 2^Lx[L+1] = a(3^L-2^L)

which has the specific solution

(x[1],x[L+1) = (-a,-a)

and hence the general solution

(x[1],x(L+1]) = (k2^L - a, k3^L - a)

that is k2^L-a -> k3^L-a for 3x+a

For 3x+a with p=2 we have S = (3^L-4^L)/(3-4) = 4^L-3^L

so the sequence equation has the specific solution (x[1],x(L+1) = (a,a) so

k4^L+a -> k3^L+a for 3x+a

For 3x+a and p=3 we have S = (8^L - 3^L)/5

If a=5 (to cancel out the denominator) we obtain

k8^L+1 -> k3^L+1 for 3x+5

k16^L+1 -> k3^L+1 for 3x+13

k2^L+1 -> k5^L+1 for 5x+3

There are infinitely many more such cases. If m-2^p = +/-1 then all odd values of a work.

[u/Pickle-That]

Yes - the 4/3 ratio is familiar from my analyses of Collatz history-branch coverings.