Mathematics Asked on January 5, 2022

I’ve noticed that $a bmod b$ (with ‘mod’ in the operational sense) can also be represented using various tricks of formulation. For instance, that

$$a bmod b = a – bleftlfloorfrac{a}{b}rightrfloor .$$

There are several ways to do it by (ab)using various functions like ceiling, max, abs, and the like. However, I realized yesterday that

$$a bmod 2 = frac{1-(-1)^a}{2}.$$

I find this interesting as I consider basic exponentiation to be a purer operation in some sense than something like floor, perhaps in that it doesn’t have a built-in sense of conditionality or knowledge of fractional parts. Furthermore, you can use substitution to reach arbitrarily high powers of $2$, as in

$$a bmod 4 = frac{1-(-1)^a}{2}+1-(-1)^{frac{a-frac{1-(-1)^a}{2}}{2}},$$

which amounts to right-shifting $a$ by one spot and repeating the process to get the second bit you need for the $bmod 4$. I realize that’s not pretty, but I’m interested that it’s possible. The motivation here is identifying situations where formulae may implicitly support a richness of computational complexity one wouldn’t expect, which parity detection and manipulation goes a long way towards. Which leads me to my question:

**Is there some way using exponentiation or other basic operations to find a comparable expression for $a bmod 3$, or ideally, $a bmod b$?**

Note that $sin(2pi n/3)=0, dfrac{sqrt3}2, $ or $-dfrac{sqrt3}2$, according as $nequiv0, 1, $ or $2bmod3$, respectively.

Furthermore, $f(x)=dfrac{xleft(x-dfrac{sqrt3}2right)2}{-dfrac{sqrt3}2left(dfrac{sqrt3}2-dfrac{sqrt3}2right)}+dfrac{xleft(x+dfrac{sqrt3}2right)1}{dfrac{sqrt3}2left(dfrac{sqrt3}2+dfrac{sqrt3}2right)}=dfrac{3x^2-dfrac{sqrt3}2x}{dfrac 32}=2x^2-dfrac x{sqrt3}$

has the property that $f(0)=0, fleft(dfrac{sqrt3}2right)=1, $ and $fleft(-dfrac{sqrt3}2right)=2$.

Therefore, $f(sin(2pi n/3))=2sin^2(2pi n/3)-dfrac {sin(2pi n/3)}{sqrt3}=n bmod 3.$

Answered by J. W. Tanner on January 5, 2022

Any function $f(n)$ on the integers that is periodic with period $m$ can be written in terms of powers of $zeta=e^{2pi i/m}$, a primitive $m$th root of unity: $$ f(n) = sum_{k=0}^{m-1} hat f(k) zeta^{nk}, quadtext{where } hat f(k) = frac1m sum_{j=0}^{m-1} f(j) zeta^{-jk}. $$ Notice that when $m=2$, we have $zeta=-1$ and this formula becomes $$ f(n) = hat f(0) + hat f(1)(-1)^n, quadtext{where } hat f(0) = frac12(f(0)+f(1)) text{ and } hat f(1) = frac12(f(0)-f(1)); $$ this is the formula you included when $f(n) = nmod 2$.

When $m=3$, we have $zeta=e^{2pi i/3} = frac12(-1+isqrt3)$ and $zeta^2=barzeta=frac12(-1-isqrt3)$, and $$ f(n) = hat f(0) + hat f(1) zeta^n + hat f(2) barzeta^n. $$ In the specific case $f(n)=nmod 3$, the coefficients are begin{align*} hat f(0) &= frac13(0+1+2) = 1, \ hat f(1) &= frac13(0+1barzeta+2zeta) = -frac12+frac i{2sqrt3}, \ hat f(2) &= frac13(0+1zeta+2barzeta) = -frac12-frac i{2sqrt3}. end{align*} Putting it all together, $$ nmod3 = 1 + bigg({-}frac12+frac i{2sqrt3}bigg)bigg(frac{-1+isqrt3}2bigg)^n + bigg({-}frac12-frac i{2sqrt3}bigg)bigg(frac{-1-isqrt3}2bigg)^n. $$

Answered by Greg Martin on January 5, 2022

0 Asked on January 11, 2021

1 Asked on January 11, 2021 by xiao

1 Asked on January 11, 2021 by lucas-peres

1 Asked on January 10, 2021 by applesauce44

0 Asked on January 10, 2021 by emptyvessel

3 Asked on January 10, 2021 by turingtester69

2 Asked on January 10, 2021 by monoidaltransform

connections differential geometry riemannian geometry smooth manifolds

2 Asked on January 10, 2021 by user3133165

0 Asked on January 10, 2021 by xhsbm

3 Asked on January 9, 2021 by landon-carter

1 Asked on January 9, 2021 by socket1814

combinatorics discrete mathematics inclusion exclusion integer partitions recreational mathematics

0 Asked on January 9, 2021 by jojo

eigenvalues eigenvectors linear algebra numerical linear algebra

0 Asked on January 9, 2021 by user193319

abstract algebra finitely generated modules principal ideal domains

1 Asked on January 9, 2021 by thenac

3 Asked on January 9, 2021 by robertoherb

1 Asked on January 8, 2021 by momo

2 Asked on January 8, 2021 by ryan-soh

2 Asked on January 8, 2021

1 Asked on January 8, 2021

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP