[math-fun] Iterated Modulus
for any number n and m<n, define the list m, Mod[n,m], Mod[n,Mod[n,m]], Mod[n,Mod[n,Mod[n,m]]], Mod[n,Mod[n,Mod[n,Mod[n,m]]]], .... stopping on Mod[n, 1 ] as the iterated modulus list on n started from m. It has the property that it is a strictly decreasing list since Mod[n,m] < m. This descent can only proceed until Mod[n, 1 ] is reached. Call the length of the resulting list modlen[n,m] example: the iterated modulus list of n=1439 started from m=20 is with length 12. Now, look at the modlen(n,k) with k running from 1 up to n. Call it the "fullmodlist". This list (length n) is not symmetric, but it has : n - 2 * S = 3 for n odd and n - 2 * S = 2 for n even where S equals the sum over last half of fullmodlist(n) - first half of fullmodlist(n) and that, I think, is curious. Wouter. -------------Mathematica---------------------------- mo[n_,m_]:= NestWhileList[Mod[n,#]&,m,#>1&] modlen[n_,m_]:=Length[NestWhileList[Mod[n,#]&,m,#>1&]] Table[p=2n+1;it=modlen[p,#]&/@Range[p];p-2 Plus@@Take[Reverse[it]-it,Floor[Length[it]/2]],{n,99}] Table[p=2n ;it=modlen[p,#]&/@Range[p];p-2 Plus@@Take[Reverse[it]-it,Floor[Length[it]/2]],{n,99}] =============================== This email is confidential and intended solely for the use of the individual to whom it is addressed. If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited. You are explicitly requested to notify the sender of this email that the intended recipient was not reached.
What you call modlen[n,m] is the length of the continued fraction of m/n (perhaps +/- 1, I haven't checked). This has been studied a lot. For example there's a famous theorem of Heilbronn about the average length, which is referred to here http://matwbn.icm.edu.pl/ksiazki/aa/aa37/aa3717.pdf Victor On Fri, Apr 30, 2010 at 10:07 AM, Meeussen Wouter (bkarnd) < wouter.meeussen@vandemoortele.com> wrote:
for any number n and m<n, define the list m, Mod[n,m], Mod[n,Mod[n,m]], Mod[n,Mod[n,Mod[n,m]]], Mod[n,Mod[n,Mod[n,Mod[n,m]]]], .... stopping on Mod[n, 1 ]
as the iterated modulus list on n started from m. It has the property that it is a strictly decreasing list since Mod[n,m] < m. This descent can only proceed until Mod[n, 1 ] is reached.
Call the length of the resulting list modlen[n,m]
example: the iterated modulus list of n=1439 started from m=20 is
with length 12.
Now, look at the modlen(n,k) with k running from 1 up to n. Call it the "fullmodlist". This list (length n) is not symmetric, but it has :
n - 2 * S = 3 for n odd and n - 2 * S = 2 for n even
where S equals the sum over last half of fullmodlist(n) - first half of fullmodlist(n)
and that, I think, is curious.
Wouter.
-------------Mathematica---------------------------- mo[n_,m_]:= NestWhileList[Mod[n,#]&,m,#>1&] modlen[n_,m_]:=Length[NestWhileList[Mod[n,#]&,m,#>1&]]
Table[p=2n+1;it=modlen[p,#]&/@Range[p];p-2 Plus@ @Take[Reverse[it]-it,Floor[Length[it]/2]],{n,99}] Table[p=2n ;it=modlen[p,#]&/@Range[p];p-2 Plus@ @Take[Reverse[it]-it,Floor[Length[it]/2]],{n,99}]
=============================== This email is confidential and intended solely for the use of the individual to whom it is addressed. If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited. You are explicitly requested to notify the sender of this email that the intended recipient was not reached.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
a last bit, after which I'll stop it: it is straightforward to reconstruct n from modlist(n,m) in those cases when lcm(modlist(n,m)) > n, which is true in about 83% of the cases (upto 1024) take for instance the couples {n,m} with record holders of 'modlen': {5,3},{8,5},{11,7},{19,12},{34,25},{46,29},{53,32},{95,61},{103,65}, {179,115},{251,161},{299,189},{503,296},{743,470},{1006,641} they produce 'iterated modulus list' as follows: {3,2,1}, {5,3,2,0}, {7,4,3,2,1}, {12,7,5,4,3,1}, {25,9,7,6,4,2,0}, {29,17,12,10,6,4,2,0}, {32,21,11,9,8,5,3,2,1}, {61,34,27,14,11,7,4,3,2,1}, {65,38,27,22,15,13,12,7,5,3,1}, {115,64,51,26,23,18,17,9,8,3,2,1}, {161,90,71,38,23,21,20,11,9,8,3,2,1}, {189,110,79,62,51,44,35,19,14,5,4,3,2,1}, {296,207,89,58,39,35,13,9,8,7,6,5,3,2,1}, {470,273,197,152,135,68,63,50,43,12,11,6,5,3,2,1}, {641,365,276,178,116,78,70,26,18,16,14,12,10,6,4,2,0}} to inverse, simply do ChineseRemainder( list_without_first_element , list_without_last_element ) Cute : chinese remainder with a single argument. Wouter. -------------Mathematica---------------------------- Table[Max[modlen[n, #1]& /@ Range[n]],{n,1024}]; Flatten[Position[%,#,1,1]&/@ Range[17]]; Function[n,modlen[n, #1]& /@ Range[n]]/@ %; Flatten[First/@ (Position[#,Max[#]]&/@ %)]; Drop[Transpose[{%%%,%}],2] {5,3},{8,5},{11,7},{19,12},{34,25},etc mo @@@ % {3,2,1}, {5,3,2,0}, {7,4,3,2,1}, etc ChineseRemainder[Rest[#],Drop[#,-1]]&/@ % {5,8,11,19,34,46,53,95,103,179,251,299,503,743,1006}
-------------Mathematica---------------------------- mo[n_,m_]:= NestWhileList[Mod[n,#]&,m,#>1&] modlen[n_,m_]:=Length[NestWhileList[Mod[n,#]&,m,#>1&]]
Table[p=2n+1;it=modlen[p,#]&/@Range[p];p-2 Plus @@Take[Reverse[it]-it,Floor[Length[it]/2]],{n,99}] Table[p=2n ;it=modlen[p,#]&/@Range[p];p-2 Plus @@Take[Reverse[it]-it,Floor[Length[it]/2]],{n,99}]
finis
participants (3)
-
Meeussen Wouter (bkarnd) -
Victor Miller -
wouter meeussen