Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Need help solving mathematical recursive modular arithmetic problem
Replies: 0

 Morten Leikvoll Posts: 2 Registered: 4/15/13
Need help solving mathematical recursive modular arithmetic problem
Posted: Apr 15, 2013 8:33 AM

I need to find a general formula for a(n,m)=f(n,m,b,c) for this recursive
(circular) sequence, if possible at all:

a(n,0)=n
a(n,m)=(a(n,m-1) mod b)*c+(a(n,m-1) div b), for m>0

where (x mod y) is the modulo/modulus (remainder of x divided by y) function
and (x div y) is the integer of x divided by y.

AS a second challenge for curiosity, what m gives a(n,m)=a(n,0) (sequence
repeat)?

Does this challenge have a name?
Thanks for any input.
------------------------
Example series for b=4,c=3, showing sequence for n=0..11 and m=0..5
a(n,0)=0,1,2,3,4,5,6,7,8,9,10,11
a(n,1)=0,4,8,1,5,9,2,6,10,3,7,11
a(n,2)=0,5,10,4,9,3,8,2,7,1,6,11
a(n,3)=0,9,7,5,3,1,10,8,6,4,2,11
a(n,4)=0,3,6,9,1,4,7,10,2,5,8,11
a(n,5)=0,1,2,3,4,5,6,7,8,9,10,11
This sequence repeats for every 5th value of m

Example series for b=10,c=3, showing sequence for n=0..29 and m=0..28
a(n,0)=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29
a(n,1)=0,10,20,1,11,21,2,12,22,3,13,23,4,14,24,5,15,25,6,16,26,7,17,27,8,18,28,9,19,29
a(n,2)=0,13,26,10,23,7,20,4,17,1,14,27,11,24,8,21,5,18,2,15,28,12,25,9,22,6,19,3,16,29
a(n,3)=0,14,28,13,27,12,26,11,25,10,24,9,23,8,22,7,21,6,20,5,19,4,18,3,17,2,16,1,15,29
a(n,4)=0,24,19,14,9,4,28,23,18,13,8,3,27,22,17,12,7,2,26,21,16,11,6,1,25,20,15,10,5,29
a(n,5)=0,8,16,24,3,11,19,27,6,14,22,1,9,17,25,4,12,20,28,7,15,23,2,10,18,26,5,13,21,29
a(n,6)=0,22,15,8,1,23,16,9,2,24,17,10,3,25,18,11,4,26,19,12,5,27,20,13,6,28,21,14,7,29
a(n,7)=0,17,5,22,10,27,15,3,20,8,25,13,1,18,6,23,11,28,16,4,21,9,26,14,2,19,7,24,12,29
a(n,8)=0,25,21,17,13,9,5,1,26,22,18,14,10,6,2,27,23,19,15,11,7,3,28,24,20,16,12,8,4,29
a(n,9)=0,18,7,25,14,3,21,10,28,17,6,24,13,2,20,9,27,16,5,23,12,1,19,8,26,15,4,22,11,29
a(n,10)=0,6,12,18,24,1,7,13,19,25,2,8,14,20,26,3,9,15,21,27,4,10,16,22,28,5,11,17,23,29
a(n,11)=0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29
a(n,12)=0,20,11,2,22,13,4,24,15,6,26,17,8,28,19,10,1,21,12,3,23,14,5,25,16,7,27,18,9,29
a(n,13)=0,26,23,20,17,14,11,8,5,2,28,25,22,19,16,13,10,7,4,1,27,24,21,18,15,12,9,6,3,29
a(n,14)=0,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,29
a(n,15)=0,19,9,28,18,8,27,17,7,26,16,6,25,15,5,24,14,4,23,13,3,22,12,2,21,11,1,20,10,29
a(n,16)=0,16,3,19,6,22,9,25,12,28,15,2,18,5,21,8,24,11,27,14,1,17,4,20,7,23,10,26,13,29
a(n,17)=0,15,1,16,2,17,3,18,4,19,5,20,6,21,7,22,8,23,9,24,10,25,11,26,12,27,13,28,14,29
a(n,18)=0,5,10,15,20,25,1,6,11,16,21,26,2,7,12,17,22,27,3,8,13,18,23,28,4,9,14,19,24,29
a(n,19)=0,21,13,5,26,18,10,2,23,15,7,28,20,12,4,25,17,9,1,22,14,6,27,19,11,3,24,16,8,29
a(n,20)=0,7,14,21,28,6,13,20,27,5,12,19,26,4,11,18,25,3,10,17,24,2,9,16,23,1,8,15,22,29
a(n,21)=0,12,24,7,19,2,14,26,9,21,4,16,28,11,23,6,18,1,13,25,8,20,3,15,27,10,22,5,17,29
a(n,22)=0,4,8,12,16,20,24,28,3,7,11,15,19,23,27,2,6,10,14,18,22,26,1,5,9,13,17,21,25,29
a(n,23)=0,11,22,4,15,26,8,19,1,12,23,5,16,27,9,20,2,13,24,6,17,28,10,21,3,14,25,7,18,29
a(n,24)=0,23,17,11,5,28,22,16,10,4,27,21,15,9,3,26,20,14,8,2,25,19,13,7,1,24,18,12,6,29
a(n,25)=0,27,25,23,21,19,17,15,13,11,9,7,5,3,1,28,26,24,22,20,18,16,14,12,10,8,6,4,2,29
a(n,26)=0,9,18,27,7,16,25,5,14,23,3,12,21,1,10,19,28,8,17,26,6,15,24,4,13,22,2,11,20,29
a(n,27)=0,3,6,9,12,15,18,21,24,27,1,4,7,10,13,16,19,22,25,28,2,5,8,11,14,17,20,23,26,29
a(n,28)=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29
This sequence repeats for every 28th value of m