Collatz-like conjecture using integer square root
Carl W.
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
Tim Little
> 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
Henry
> On 2010-07-06, Carl W. <googlen...@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.
master1729
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
Carl W.
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
Carl W.
My apologies to thee, master tommy of the taxicab number. I searched
sci.math with the terms 1927 and 18469 since these would have been
likely to reveal another's work on the same subject, but found
nothing. Perhaps I should have searched 1729 instead.
Carl