As I’ve discussed before, many great findings in mathematics have arisen from the study of silly arbitrary functions. These functions often look quite simple but produce surprising results when carried out at length. Occasionally I attempt to come up with my own novel routine and almost always find that they collapse to something well known or something not the least bit intriguing.
A couple of weeks ago I was studying one-way cryptographic hashing functions and got off on a tangent regarding their heavy reliance on modulo operations. I constructed a simple repeating modulo function for fun and I became rather absorbed in the resulting sequence it generated.
My Simple MOD Algorithm
The recursive procedure is as follows: Pick a modulo number M and a seed number S. The sequence starts with S. Each subsequent number is simply the prior number + prior number mod M.
Example using M=9 and S=5:
- 5
- 5 + (5 mod 9) = 5 + 5 = 10
- 10 + (10 mod 9) = 10 + 1 = 11
- 11 + (11 mod 9) = 11 + 2 = 13
- 13 + (13 mod 9) = 13 + 4 = 17
- 17 + (17 mod 9) = 17 + 8 = 25
- 25 + (25 mod 9) = 25 + 7 = 32
- 32 + (32 mod 9) = 32 + 5 = 37
- 37 + (37 mod 9) = 37 + 1 = 38
- 38 + (38 mod 9) = 38 + 2 = 40
- 40 + (40 mod 9) = 40 + 4 = 44
- 44 + (44 mod 9) = 44 + 8 = 52
- 52 + (52 mod 9) = 52 + 7 = 59
Well I lied a little about my sequence… because what was far more interesting to me was actually just looking at the value of new modulo value you are adding to the previous value. In the example above you can see these numbers bold and underlined. In that example they form a pattern with a period of 6 (5, 1, 2, 4, 8, 7, …repeat…). As you test other values for M and S you find other repetitions but you also find that some iterations terminate after a number of steps. Here is a snap shot of M=19, S=1. As you can see the value cycles after 18 steps which you can see depicted in the chart in the lower left as well.
And here is one M=8, S=3. Notice how after 3 steps the sequence simply terminates.
I became interested in the following aspects of this sequence:
- How is the pattern related to the selection of M and S?
- Can you predict which will Terminate and which will continue indefinitely?
- Is the result always a repeating pattern?
- Can you predict the period/length of the pattern?
- Can you predict the sum of the values within the pattern?
- How can we use prime factorization to draw further insight on these patterns?
To support this analysis I developed a piece of software (in C#) to precalculate the sequences for M and N from 1 to 1000. With this data set available to explore in excel I began to work through my analysis, here are my findings:
Will the sequence terminate or repeat?
It is important to recognize that many of the patterns we see emerge are bound to the powers of 2. This is due to how the additive value keeps doubling until it rolls over the modulo value. Here are the first several M, S combinations that terminate:
What you may notice is that this includes all S where M is a power of 2 and certain other S values for other even values of M. If you study this further you may spot the connection with the prime factorization: S is always divisible by M where M has 2x removed from its prime factorization. Example: M=20, S=10 on last row. 20 = 1 x 22 x 5. Removing 2x results in 1 x 5 = 5. S of 10 is divisible by 5 and so we can predict that the pattern will terminate!
Values before a pattern is established
For some numbers, several values will appear in the sequence before a repeating pattern is established. For instance with M=768, S=1 we can see that this pre-pattern length is 8 before it settles into a pattern of length 2 (256, 512, 256, …). You can see this as a little tail in the chart in the bottom left as well.
If we look at the range of S values for a given M we will see that the PrePattern lengths are evenly distributed between the S values that Terminate; if there are no Terminating S values for a given M then there are no S values with PrePattern lengths. Here is M=20 which illustrates this well as you can see the prepattern lengths distributed about the termination points as S=5, 10 and 15:
Again, if we study the prime factorization for M, S combos that have PrePattern lengths and what those lengths are we will discover that the length is equal to the difference between M and S in their count of factors of 2. For example take M=20, S=19 on the last row. 20 = 1 x 22 x 5 contains 2 factors of 2 while 19 = 1 x 19 contains 0 factors of 2. 2-0 = 2 which is the PrePattern Length. Notice though that if the value terminates this difference equates to the number of steps until termination (For example: [20,5], [20,10] & [20,15]). Also note that if S contains more factors of 2 than M the PrePattern Length is simply 0, such as with M=20, S=16 where S contains 4 factors of 2 and M only 2.
Length of the Pattern
Looking at the length of the pattern as a function of M and S proved quite daunting. I was able to find interesting correlations between certain factors always (but not exclusively) being associated with a certain length. I also noticed that these corresponding factors – 1 are divisible by the length. For instance, a pattern length of 9 seems to be associated with M values that have a Prime Factorization containing 73. I was not able to draw conclusions exploring down this road but I think there is something there…
I also felt as though I might be on to something by recognizing if you divide the aggregate of the pattern by the length of the pattern for each S for a given M, then average those values it is always half the M value. Once again, I was not able to draw any conclusions…
Finally I turned to “cheating” as my best approach and visited one of the nerdiest websites that exists, The Online Encyclopedia of Integer Sequences (https://oeis.org/)! They have an astounding catalog of just about any sequence you can imagine and I have used them quite a number of times to get to the bottom of a pattern that I couldn’t crack. Well I looked up the sequence of Pattern Lengths built for every value of M with S=1 as follows:
Well, sure enough, I got a hit! https://oeis.org/A007733 (zeros needs to be considered as ones in this pattern, but just ignore that!)
It makes sense that this pattern of the periods of binary representations appears in my sequence given the connection between binary and powers of 2. If you recall this pattern came from looking at all M for S=1, well the pattern repeats for all other values of S which simply shift the pattern S positions.
Aggregation of the Pattern
If we take all the numbers that make up the pattern and we add them up, what can we say about this total? For example M=19, S=1 has a pattern of length 18, if you sum those 18 numbers in the repeating pattern they are 171.
If you look at the aggregate over a range of M you may notice that the aggregate is always a multiple of M.
Looking at the sequence of the multiple (right most column above) I was again unable to discern a pattern, so once again I consulted OEIS and again I found a match! https://oeis.org/A136043 (again zeros appear as ones, ignore that again!)
MR-expansions? What are those? Best I can tell, that is a term that only appears in OEIS and is defined as such:
The base-m MR-expansion of a positive real number x, denoted by MR(x,m), is the integer sequence {s(1),s(2),s(3),…}, where s(i) is the smallest exponent d such that (m^d)x(i)>1 and where x(i+1)=(2^d)x(i)-1, with the initialization x(1)=x. The base-2 MR-expansion of 1/29 is periodic with period length 14. Further computational results (see A136043) suggest that if p is a prime with 2 as a primitive root, then the base-2 MR-expansion of 1/p is periodic with period (p-1)/2. This has been confirmed for primes up to 2000. The base-2 MR-expansion of e-2.71828… is given in A136044.
That is awfully dense to parse… I worked through it and get it and I am happy to have “explained” what I am seeing but I don’t feel like I got that “aha!” sensation on this one, oh well.
Closing
That was a lot of boring stuff, I can’t believe you read this far, thank you 🙂
I’m satisfied to have come up with a relatively novel sequence, identify a number of interesting resultant sequences it produces and stuck with it to come up with answers to crack them all (with some help from OEIS). I find modulo to be an operator that holds some mystique for me. It is so simple and useful but in some sense it is more a shorthand for an algorithm in and of itself and so it injects a lot of nuance into the resultant values it returns. I would not be surprised if the next funky function I come up with to explore will be based on modulo as well!
