My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

LinkBack Thread Tools Display Modes
September 1st, 2017, 03:12 PM   #1
Joined: Sep 2017
From: UK

Posts: 3
Thanks: 0

Repetition in an Equation


Could anyone please tell me why it is that the numbers returned from this equation, repeat (but upon the repeat they are 65535-x). Start with x=1 then keep looping this:

x=(75*(x+1))-INT ((75*(x+1))/65537)*65537-1

That is: x=MOD(75*(x+1),65537)-1

Upon 32768 iterations of this equation the next number will again start the sequence, but it will be of the form 65535-x=x(1)

What I'm trying to say is that 65535-x(32769)=x(1). I hope I am making it clear that 65535 minus the 32769th iteration is the same as the first iteration.

I expected that the numbers would repeat after 65536 iterations, but not half way through.

Any ideas on why it happens?

Thanks for any help guys,


Last edited by skipjack; September 2nd, 2017 at 01:54 AM.
matalog is offline  
September 1st, 2017, 04:17 PM   #2
Math Team
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 10,900
Thanks: 716

Wolfram|Alpha: Computational Knowledge Engine)
Denis is offline  
September 1st, 2017, 11:07 PM   #3
Joined: Sep 2017
From: UK

Posts: 3
Thanks: 0

Thanks for replying, but I'm not exactly sure how that W|A link you have provided helps to answer my question.

Could you explain a bit more please?



Last edited by skipjack; September 2nd, 2017 at 01:44 AM.
matalog is offline  
September 2nd, 2017, 03:14 AM   #4
Global Moderator
Joined: Dec 2006

Posts: 18,149
Thanks: 1418

Let m denote your constant, 75, and s denote your starting value (of x), 1.

Let p denote the minimum number of iterations that results in x becoming 65535 - s.

It's easy to show that further iterations continue in that manner (so that the sum of the results of the 2nd and (p+1)th iterations is 65535, and so on).

I think it would be fairly easy to show that p is a function of m alone, which means that p divides 65536. It's easy to find values of m for which p < 32768. I haven't found a value of m for which p = 65536.
skipjack is online now  
September 2nd, 2017, 08:13 AM   #5
Joined: Sep 2017
From: UK

Posts: 3
Thanks: 0

Yes, a lot of modulos like this behave in a similar way.

I would like to know though, why they repeat 65535-x in the second half?

They seem to do an interesting thing, each iteration of this particular equation, returns an original number between 1 and 65536, between x(1) to x(65536), and half way through that, it uses the very same pattern, albeit 65535-x(32769)=x(1).

It seems special in some way, can anyone explain it to me in simple terms, why I should not be surprised by what this equation (and others like it) does?

Thanks again, for any help,

matalog is offline  

  My Math Forum > College Math Forum > Number Theory

equation, modulo, repetition

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Combination with repetition taylor_1989_2012 Probability and Statistics 5 September 25th, 2016 01:15 PM
Indexing a permutation with repetition SabinManiac Advanced Statistics 0 February 1st, 2012 08:08 AM
Drawing balls with repetition butabi Advanced Statistics 1 November 27th, 2011 09:19 AM

Copyright © 2017 My Math Forum. All rights reserved.