When X is a string (of some radix) of numerical value Σ(X[k]*radix

^{k})

_{∀k∈0..X.length-1⊆Z}, then (int)X ≡ 0 mod Y

**iff**: Σ(X[k] * cycle[k])

_{∀k∈0..X.length⊆Z}≡ 0 mod Y, where cycle is the repeating series { radix

^{k}mod Y }.

Let's pick a radix we all know and love, base10:

Let Dn = { 10

^{0}, 10

^{1}, 10

^{2}, ... }

Dn mod 3 = { 1, 1, 1, ... } = Cycle (1). Since cycle[k] = 1, we get the age-old mantra "X is divisible by 3 iff the sum of digits is divisible by 3".

But let's look beyond 3,

Dn mod 7 = cycle ( 1, 3, 3*3≡9≡2, 2*3≡6≡-1 ..) = cycle (1, 3, 2, -1, -3, -2)

Dn mod 11 = cycle (1, 10≡-1 ..) = cycle (1,-1)

Interestingly, but with less power than an

*iff*relationship, since lcm(2,6) = 6 and both Dn mod 7 and Dn mod 11 have half-cycles (-1 as an element), then X ≡ 0 mod 77

**if**X in decimal form can be grouped into 3digit strings, where every other 3digit string is marked red and those in between are marked blue, and the { reds } minus { blues } = Null.

For exampe, let red = { 123, 444, 812, 912, 083, 948, 020, 436 }

Thus, blue = { 123, 444, 812, 912, 083, 948, 020, 436 }

Let shuffle(blue) = { 444, 948, 912, 436, 083, 812, 123, 020 }

Then interlace(red, shuffle(blue)) = 123444 444948 812912 912436 083083 948812 020123 436020. This now yields a base10 string which is divisible by 77 (and obviously also by 2, 5, 7, 11 and all the other factors of their multiple 770): 123444444948812912912436083083948812020123436020

Too big a number to verify with a pocket-calculator? Here's an easy multiple of 77 to generate: 001001 = 1,001. A pocket calculator can verify it is 13*77.

But then, what's the ratio of densities between these simple multiples and the full set of multiples? In the case of 77, cardinality of the full set of multiples for base10 string X is (1/77) * (10

^{X.length}). Cardinality for the parlor-trick partial set is:

Let red

_{i}= ∪(X[6*i+0..6*i+2])

Let blue

_{i}= ∪(X[6*i+3..6*i+5])

Let g = X.length/6

(

*φ*(∃unique j s.t. blue

_{i}= red

_{j}))

_{∀i∈0..g-1⊆Z}) * (10

^{X.length})

= (Π(1 - ((10

^{3}-1)/10

^{3})

^{k})

_{∀k∈1..g⊆Z}) * (10

^{X.length})

= (Π(1 - 0.999

^{k})

_{∀k∈1..g⊆Z}) * (10

^{X.length})

lim

_{X.length→∞}( Π(1 - 0.999

^{k})

_{∀k∈1..g⊆Z}) ≈ 7.4210E-713

Thus, the ratio of the two is (1/77) : 7.4210E-713 ⇒ 1 : 5.7142E-711. In other words, the parlor trick while being a very good way to

*generate*multiples is a rather improbable way to test for divisibility by 77. The only rigorous divisibility test is the one where

*iff*is ensured instead of the comparatively impotent

*if*.

## No comments:

Post a Comment