if 0 {Richard Suchenwirth 2004-07-10 - When you do integer division, a non-zero remainder may occur, which the modulo operator % gives us:
10/7 = 1 10%7 = 3
In manual division, the remainder is multiplied by 10 and again integer-divided by the divisor, until a zero remainder is reached (or the person calculating is exhausted). Periodic decimal fractions are known to never terminate, because no zero remainder ever comes:
10/7. = 1.42857142857...
The "142857" part will repeat as long as you wish (you'd stop before "forever"), like a circular graph of digits, a ring. Such remainder rings (not sure whether that's the correct term, but searching Mathworld brought me no better one) ...
Lars H interrupts: What you are describing in the rest of this page is rather remainder orbits (they are technically the orbits of the multiply-by-10-modulo-b map). A ring is an algebraic structure which (at least) supports the three operations + (addition), - (subtraction), and * (multiplication).
... have ever again fascinated me a bit, and today I wanted to play with them in Tcl.}
proc rem-orbit {a b} {
set res {}
while 1 {
set rem [expr {$a % $b}]
if {$rem==0} {error "aperiodic $b"}
if [in $res $rem] {return $res}
lappend res $rem
set a ${rem}0 ;# fancy multiplication by 10 :-)
}
}
proc in {list element} {expr [lsearch -exact $list $element]>=0}if 0 {
Lars H again: Reaching $rem==0 does not (as the above procedure claims) mean that the sequence of remainders is aperiodic, but simply that the period length is 1. Compare with decimal fractions: a number has an aperiodic decimal fraction if and only if it is irrational.
Some tests:
% rem-orbit 1 7 1 3 2 6 4 5 % rem-orbit 2 7 2 6 4 5 1 3
The orbits look different - and yet are the same: if you just rotate the second one so that the smallest element comes first, it equals the first. This normalization can be easily coded:}
proc normalize ring {
set pos [lsearch $ring [min $ring]]
if $pos {
concat [lrange $ring $pos end] [lrange $ring 0 [expr $pos-1]]
} else {set ring} ;# return it unchanged
}
#-- numeric minimum of a list
proc min list {lindex [lsort -integer $list] 0}if 0 {Test:
% normalize [rem-orbit 2 7] 1 3 2 6 4 5
How many distinct remainder orbits does a natural number have? Depends on the number, of course. Here's a routine that for a number n, tries all remainders of dividing from 1 to n-1 by n; normalizes the resulting rings, and keeps only the distinct ones: }
proc rem-orbits n {
set res {}
for {set i 1} {$i<$n} {incr i} {
ladd res [normalize [rem-orbit $i $n]]
}
set res
}
#-- add an element to a list, if not contained yet
proc ladd {listVar element} {
upvar 1 $listVar list
if ![in $list $element] {lappend list $element}
}if 0 {Here's how to get the period (the sequence of repeating digits) from a remainder orbit:}
proc period {remorbit n} {
set res ""
foreach i $remorbit {append res [expr {(10*$i)/$n}]}
set res
}if 0 {Test again:
% period [rem-orbit 1 17] 17 0588235294117647 % period [rem-orbit 2 17] 17 1176470588235294 % period [rem-orbit 3 17] 17 1764705882352941
And now, let's just look at various numbers and their rem-orbit sets. The most interesting and regular results come from prime numbers. I made the following observations:
p=2,q=6) where p*q+1=n
% rem-orbits 3
1 2
% rem-orbits 5
aperiodic 5 ;# because it divides 10 without remainder
% rem-orbits 7
{1 3 2 6 4 5}
% rem-orbits 9
1 2 3 4 5 6 7 8 ;# eight tiny one-element orbits...
% rem-orbits 11
{1 10} {2 9} {3 8} {4 7} {5 6} ;# five two-orbits, that all add up to 11
% rem-orbits 13
{1 10 9 12 3 4} {2 7 5 11 6 8} ;# two six-orbits
% rem-orbits 17
{1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12}
% rem-orbits 19
{1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2}
% rem-orbits 21 ;# this is funny - you see the heritage of factors 7 and 3
{1 10 16 13 4 19} {2 20 11 5 8 17} {3 9 6 18 12 15} 7 14
% rem-orbits 23
{1 10 8 11 18 19 6 14 2 20 16 22 13 15 12 5 4 17 9 21 3 7}
% rem-orbits 29
{1 10 13 14 24 8 22 17 25 18 6 2 20 26 28 19 16 15 5 21 7 12 4 11 23 27 9 3}
% rem-orbits 31 ;# two 15-orbits
{1 10 7 8 18 25 2 20 14 16 5 19 4 9 28} {3 30 21 24 23 13 6 29 11 17 15 26 12 27 22}
% rem-orbits 37 ;# twelve 3-orbits
{1 10 26} {2 20 15} {3 30 4} {5 13 19} {6 23 8} {7 33 34}
{9 16 12} {11 36 27} {14 29 31} {17 22 35} {18 32 24} {21 25 28}
% rem-orbits 39
{1 10 22 25 16 4} {2 20 5 11 32 8} {3 30 27 36 9 12} {6 21 15 33 18 24}
{7 31 37 19 34 28} 13 {14 23 35 38 29 17} 26 ;# see? not prime!
% rem-orbits 41
{1 10 18 16 37} {2 20 36 32 33} {3 30 13 7 29} {4 40 31 23 25}
{5 9 8 39 21} {6 19 26 14 17} {11 28 34 12 38} {15 27 24 35 22}
% rem-orbits 43 ;# two 21-orbits
{1 10 14 11 24 25 35 6 17 41 23 15 21 38 36 16 31 9 4 40 13}
{2 20 28 22 5 7 27 12 34 39 3 30 42 33 29 32 19 18 8 37 26}
% rem-orbits 47 ;# one long orbit
{1 10 6 13 36 31 28 45 27 35 21 22 32 38 4 40 24 5 3 30 18 39 14
46 37 41 34 11 16 19 2 20 12 26 25 15 9 43 7 23 42 44 17 29 8 33}
% rem-orbits 51
{1 10 49 31 4 40 43 22 16 7 19 37 13 28 25 46}
{2 20 47 11 8 29 35 44 32 14 38 23 26 5 50 41}
{3 30 45 42 12 18 27 15 48 21 6 9 39 33 24 36} 17 34 ;# not prime!
% rem-orbits 53 ;# four 13-orbits
{1 10 47 46 36 42 49 13 24 28 15 44 16}
{2 20 41 39 19 31 45 26 48 3 30 35 32}
{4 40 29 25 38 9 37 52 43 6 7 17 11}
{5 50 23 18 21 51 33 12 14 34 22 8 27}}
Lars H: The second of your observations above isn't too hard to prove. What happens is that when n is a prime then the nonzero elements, in the ring Z_n of integers modulo n, form a group under multiplication. The element 10 generates a subgroup of this group, which shows up as the "rem-ring" containing the element 1 in your lists above. The other "rem-rings" are the remaining cosets of this subgroup. It is a fairly basic theorem in group theory that all cosets of a subgroup have the same size. One way to prove it is to observe that multiplication by a suitable group element gives rise to a bijection between the elements of the cosets. q is simply the size of the subgroup generated by 10 and p is the number of its cosets.