I am a student in programming and observed a pattern in a sequence. I wondered if it is a well-known principle so I can optimize the algorithm. I am not a mathematician, so I hope this will make sense.
There is one input resolving in one of two possible outputs. Let’s name these possible outputs A and B
We get the modulo 4 of the input as a first result. If the result is neither 0 nor half the divisor, the output is A. If the result is half the divisor, the output is B. If the result is 0, we multiply the divisor by 4, and restart.
Examples:
5 mod 4 = 1 (1 ≠ 4/2, output is A)
14 mod 4 = 2 (2 = 4/2, output is B)
12 mod 4 = 0
12 mod (4x4) = 12 (12 ≠ 16/2, output A)
64 mod 4 = 0
64 mod 16 = 0
64 mod 64 = 0
64 mod 256 = 64 (64 ≠ 256/2, output A)
384 mod 4 = 0
384 mod 16 = 0
384 mod 64 = 0
384 mod 256 = 128 (128 = 256/2, output B)
It seems that to output B, the number must be a “special divisible” which satisfy: for a given number, if remainder is half of divisor where divisor is the first ${4^n}$ that remainder is not 0.
My hope is that I stumble upon a well-known principle, that the “special divisible” has a name, and then to find a solution so the algorithm does not have to loop through all the 0, as for 64 or 384 above. This repetition can get relatively long for some higher numbers, or if it has to process, says, 10 000 numbers.
For every positive integer $n$, there is exactly one set of integers $k$ and $m$ such that $n=2^k\cdot(2m+1)$.
Your algorithm outputs B if $k$ is odd, and A if $k$ is even.
In mathematics, the dignified name for $k$ is the "2-adic order of $n$".
In programming terms, $k$ is simply the number of $0$ bits at the right (least significant) end of the binary representation of $n$. Modern hardware has special instructions for computing it quickly, and many higher programming languages provide a binding for them -- e.g. the
BSFinstuction on x86 or x64 processors, orInteger.numberOfTrailingZeroes(n)in Java.