34 views

Skip to first unread message

Jul 6, 2010, 6:23:44 PM7/6/10

to

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.

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

Jul 6, 2010, 11:28:48 PM7/6/10

to

On 2010-07-06, Carl W. <googl...@phodd.net> wrote:

> iv) Every iteration generates a composite number

> 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

Jul 7, 2010, 4:38:55 AM7/7/10

to

On 7 July, 04:28, Tim Little <t...@little-possums.net> wrote:

> 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.

> 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.

Jul 7, 2010, 7:47:38 AM7/7/10

to

googlenews wrote :

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

Jul 7, 2010, 8:02:53 AM7/7/10

to

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

Jul 7, 2010, 8:07:12 AM7/7/10

to

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu