Collatz-like conjecture using integer square root [Math]

From: Carl W. on 6 Jul 2010 18:23

A quick Google search for some of the numbers below doesn't seem to
turn anything up on this, so I thought I'd post it here to see if
anyone else has come across it, or finds it interesting.

Conjecture; the transformation:
x -> floor(sqrt(x)) * ( x - floor(sqrt(x))^2 )
[for x a non-negative integer, and floor and sqrt being "largest
integer <= x" and "positive square root of x" respectively, and the
asterisk, for the more pedantic, being defined as multiplication]
....will, under repeated iteration a) reach zero or b) become trapped
in a finite loop of integers, and c) NEVER diverge to infinity.

Several things become apparent without much work:
i) Starting with x = 0 is a self-terminating case by definition
ii) x = [any perfect square] necessarily leads to zero on the next
iteration, since the value of the subtraction will be zero
iii) x = 8 iterates back to 8 and is thus a loop of one integer.
Technically this also applies for zero, but since that is declared as
a final state, zero is considered not to be a loop.
iv) Every iteration generates a composite number
v) The average value of the right hand side is floor(sqrt(x))^2,
suggesting an overall drop in value
vi) As a direct consequence of (iv), there is a chance, should
floor(sqrt(x))^2 and (x-floor(sqrt(x))^2) share common factors, that
their product is a perfect square, effectively decreasing the naively
calculated average RHS further.
vii) None of this necessarily counters the fact that (naively
speaking) half the time, the value of the right hand side is greater
than x, which could, theoretically at least, contribute to a
divergence to infinity.
viii) Numbers one less than a perfect square (n^2-1) generate
2*(n-1)^2 as the next iteration, which guarantees at least one further
iteration (unless n was 1) since twice a nonzero perfect square is
never a square.

example:
Starting with 99 (10^2-1 to make things as interesting, yet hopefully
brief, as possible), we have
99
-> 9 * 18 = 162
-> 12 * 18 = 216
-> 14 * 20 = 280
-> 16 * 24 = 384
-> 19 * 23 = 437 -- odd composites are not impossible of course
-> 20 * 37 = 740 -- by this stage all looks hopeless. we seem to be
heading to infinity already
-> 27 * 11 = 297 -- a surprise. 740 was only 11 more than 27^2 and so
the next term is smaller
-> 17 * 8 = 136 -- now it seems we may reach zero soon
-> 11 * 15 = 165
-> 12 * 21 = 252
-> 15 * 27 = 405 -- but again we are heading in the wrong direction
-> 20 * 5 = 100 -- a product of non squares forming a square...
-> 10 * 0 = 0 -- .. and so the next term is necessarily zero, and we
have finished.

Much like the better known Collatz iteration, we seem to have
hailstone-like behaviour, rising and falling repeatedly before
reaching the goal.

Research with a computer suggests that approximately 95% of the
numbers below 2500000 reach zero in this manner. A further 3% reach 8
and become trapped in the loop mentioned in (iii) above.

The remainder become trapped in other, rarer, loops, of which I
suspect there to be an infinite number; A secondary conjecture if you
will, call it (d).

The first few loops, in order of probability of occurrence and
starting with smallest term, are:
# 8 -> 8 (1 term, included here for completeness)
# 1927 -> 3354 -> 5985 -> 4312 -> 5655 -> 2250 -> 1927 (6 terms)
# 18469 -> 32940 -> 32399 -> 64082 -> 18469 (4 terms)
# 46208 -> 88168 -> 163392 -> 71104 -> 92568 -> 46208 (5 terms)
# 39852 -> 49949 -> 49060 -> 48399 -> 95922 -> 136269 -> 39852 (6
terms, and peculiarly has a smaller smallest term than the more
frequently encountered loop above)
# 1816705 -> 3092712 -> 3776184 -> 1816705 (3 terms)

Curios:
# In a parallel with happy and unhappy/sad numbers (another integer
iterative ruleset which sometimes loops), I have been calling those
initial numbers that do not reach zero, 'melancholy' numbers.
# 881217 is the number less than one million with the longest path to
zero, with 220 steps required. The maximum 'hailstone height' on the
way is 5461962688.

The main question:
Is there any obvious way of proving (c) and (d) - as an amateur who
misses obvious things often, this is not necessarily clear to me - or
does this fall into the same category as the Collatz conjecture and
there is currently no means to do so?

Carl

From: Tim Little on 6 Jul 2010 23:28

On 2010-07-06, Carl W. <googlenews(a)phodd.net> wrote:
> iv) Every iteration generates a composite number

Not necessarily: x = p^2 + 1 for prime p leads to floor(sqrt(x)) = p,
with next iteration x' = p * 1 = p. This does cover all
counterexamples, though.

> The remainder become trapped in other, rarer, loops, of which I
> suspect there to be an infinite number; A secondary conjecture if
> you will, call it (d).

There can't be any further fixed points like 0 or 8, since that can
only happen for numbers of the form n^2 + k = k n which would imply
that n-1 is a divisor of n^2. That happens only for n=0 or 2.

There do not appear to be any cycles of length 2 up to 10^10, but I'm
not yet certain that none can possibly exist. Perhaps someone better
at number theory than I can prove it.

> The first few loops, in order of probability of occurrence and
[...]
> # 1816705 -> 3092712 -> 3776184 -> 1816705 (3 terms)

Cycles do appear to be somewhat sparse. There is only one other cycle
with least member less than 10^10:

583986267, 943449930, 1188824075, 780397686, 934733035, 755336538.

There was one interesting case in this range: with x=7322384871 one of
the iterates exceeded 2^62 so that subsequent iterations using a
64-bit signed variable might have been unreliable. I had to use a
different program to verify that the iteration did reach a loop. It
does terminate (in the 0 loop), after reaching a maximum value of
15030447462807185350. That's almost twice as many bits as the initial
value and does indeed exceed the range of a 64-bit signed variable.
So it is true that intermediate values can get rather large.

- Tim

From: Henry on 7 Jul 2010 04:38

On 7 July, 04:28, Tim Little <t...(a)little-possums.net> wrote:
> On 2010-07-06, Carl W. <googlen...(a)phodd.net> wrote:
>
> > iv) Every iteration generates a composite number
>
> Not necessarily: x = p^2 + 1 for prime p leads to floor(sqrt(x)) = p,
> with next iteration x' = p * 1 = p. This does cover all
> counterexamples, though.

There is one more counterexample:
not only do you have 5 -> 2, but also 3 -> 2.

Indeed in general, the number of starting points where the next step
gives n is equal to the number of divisors of n greater than or equal
to sqrt(n/2) [infinite for n=0 since all positive integers are
divisors of 0].

If d is such a divisor of n then (d^2 + n/d) -> d * n/d = n, and no
other starting values produce n.

From: master1729 on 7 Jul 2010 03:47

googlenews wrote :

> A quick Google search for some of the numbers below
> doesn't seem to
> turn anything up on this, so I thought I'd post it
> here to see if
> anyone else has come across it, or finds it
> interesting.
>
> Conjecture; the transformation:
> x -> floor(sqrt(x)) * ( x - floor(sqrt(x))^2 )
> [for x a non-negative integer, and floor and sqrt
> rt being "largest
> integer <= x" and "positive square root of x"
> respectively, and the
> asterisk, for the more pedantic, being defined as
> multiplication]
> ...will, under repeated iteration a) reach zero or b)
> become trapped
> in a finite loop of integers, and c) NEVER diverge to
> infinity.
>
> Several things become apparent without much work:
> i) Starting with x = 0 is a self-terminating case by
> definition
> ii) x = [any perfect square] necessarily leads to
> zero on the next
> iteration, since the value of the subtraction will be
> zero
> iii) x = 8 iterates back to 8 and is thus a loop of
> one integer.
> Technically this also applies for zero, but since
> that is declared as
> a final state, zero is considered not to be a loop.
> iv) Every iteration generates a composite number
> v) The average value of the right hand side is
> floor(sqrt(x))^2,
> suggesting an overall drop in value
> vi) As a direct consequence of (iv), there is a
> chance, should
> floor(sqrt(x))^2 and (x-floor(sqrt(x))^2) share
> common factors, that
> their product is a perfect square, effectively
> decreasing the naively
> calculated average RHS further.
> vii) None of this necessarily counters the fact that
> (naively
> speaking) half the time, the value of the right hand
> side is greater
> than x, which could, theoretically at least,
> contribute to a
> divergence to infinity.
> viii) Numbers one less than a perfect square (n^2-1)
> generate
> 2*(n-1)^2 as the next iteration, which guarantees at
> least one further
> iteration (unless n was 1) since twice a nonzero
> perfect square is
> never a square.
>
> example:
> Starting with 99 (10^2-1 to make things as
> interesting, yet hopefully
> brief, as possible), we have
> 99
> -> 9 * 18 = 162
> -> 12 * 18 = 216
> -> 14 * 20 = 280
> -> 16 * 24 = 384
> -> 19 * 23 = 437 -- odd composites are not impossible
> of course
> -> 20 * 37 = 740 -- by this stage all looks hopeless.
> we seem to be
> heading to infinity already
> -> 27 * 11 = 297 -- a surprise. 740 was only 11 more
> than 27^2 and so
> the next term is smaller
> -> 17 * 8 = 136 -- now it seems we may reach zero
> soon
> -> 11 * 15 = 165
> -> 12 * 21 = 252
> -> 15 * 27 = 405 -- but again we are heading in the
> wrong direction
> -> 20 * 5 = 100 -- a product of non squares forming a
> square...
> -> 10 * 0 = 0 -- .. and so the next term is
> necessarily zero, and we
> have finished.
>
> Much like the better known Collatz iteration, we seem
> to have
> hailstone-like behaviour, rising and falling
> repeatedly before
> reaching the goal.
>
> Research with a computer suggests that approximately
> 95% of the
> numbers below 2500000 reach zero in this manner. A
> further 3% reach 8
> and become trapped in the loop mentioned in (iii)
> above.
>
> The remainder become trapped in other, rarer, loops,
> of which I
> suspect there to be an infinite number; A secondary
> conjecture if you
> will, call it (d).
>
> The first few loops, in order of probability of
> occurrence and
> starting with smallest term, are:
> # 8 -> 8 (1 term, included here for completeness)
> # 1927 -> 3354 -> 5985 -> 4312 -> 5655 -> 2250 ->
> 1927 (6 terms)
> # 18469 -> 32940 -> 32399 -> 64082 -> 18469 (4 terms)
> # 46208 -> 88168 -> 163392 -> 71104 -> 92568 -> 46208
> (5 terms)
> # 39852 -> 49949 -> 49060 -> 48399 -> 95922 -> 136269
> -> 39852 (6
> terms, and peculiarly has a smaller smallest term
> than the more
> frequently encountered loop above)
> # 1816705 -> 3092712 -> 3776184 -> 1816705 (3 terms)
>
> Curios:
> # In a parallel with happy and unhappy/sad numbers
> (another integer
> iterative ruleset which sometimes loops), I have been
> calling those
> initial numbers that do not reach zero, 'melancholy'
> numbers.
> # 881217 is the number less than one million with the
> longest path to
> zero, with 220 steps required. The maximum 'hailstone
> height' on the
> way is 5461962688.
>
> The main question:
> Is there any obvious way of proving (c) and (d) - as
> an amateur who
> misses obvious things often, this is not necessarily
> clear to me - or
> does this fall into the same category as the Collatz
> conjecture and
> there is currently no means to do so?
>
> Carl
>

your not the first to notice this intresting iteration.

the master , tommy1729 , has already considered it and posted about it on sci.math a few years ago.

back in the good old times when quasi and galathaea were still around.

hell , i could even state you stole the idea from me , since it also appeared on sci.math , however i will be nice today and give you the benefit of the doubt that you rediscovered this.

i wish you luck , more luck than i got here ...

regards

the master

tommy1729

From: Carl W. on 7 Jul 2010 08:02

On 7 July, 09:38, Henry <s...(a)btinternet.com> wrote:
> On 7 July, 04:28, Tim Little <t...(a)little-possums.net> wrote:
>
> > On 2010-07-06, Carl W. <googlen...(a)phodd.net> wrote:
>
> > > iv) Every iteration generates a composite number
>
> > Not necessarily: x = p^2 + 1 for prime p leads to floor(sqrt(x)) = p,
> > with next iteration x' = p * 1 = p. This does cover all
> > counterexamples, though.
>
> There is one more counterexample:
> not only do you have 5 -> 2, but also 3 -> 2.
>
> Indeed in general, the number of starting points where the next step
> gives n is equal to the number of divisors of n greater than or equal
> to sqrt(n/2) [infinite for n=0 since all positive integers are
> divisors of 0].
>
> If d is such a divisor of n then (d^2 + n/d) -> d * n/d = n, and no
> other starting values produce n.

Good catches Tim and Henry both. I had not properly examined cases
where x=n^2+1 for some integer n, and 2's evenness must have
temporarily blinded me to its primality.

Feeling slightly foolish (not for the first time),
Carl