Multiples of 37
me13013
of 37?
1) choose an integer at random
2) multiply it by 37
3) reverse the order of the digits in the result of 2
4) insert a zero between every pair of digits in the result of 3
For example, in step 1 I happen to choose 293. Step 2 gives 10841.
Step 3 gives 14801. Step 4 gives the final result, 104080001, which
happens to be a multiple of 37. So the probability is not zero
(except perhaps in the limit). One might expect it to be 1/37, but is
it?
Bob H
me13013
> What is the probability that the following process produces a multiple
> of 37?
>
> 1) choose an integer at random
> 2) multiply it by 37
> 3) reverse the order of the digits in the result of 2
> 4) insert a zero between every pair of digits in the result of 3
>
and someone who wishes to remain anonymous sent me this response:
> 20 random numbers between 1 and 10^6
>
> Do[x=Random[Integer,{1,1000000}];
> xd=Reverse[IntegerDigits[37*x]];
> xr=FromDigits[Flatten[Transpose[{xd,Table[0,{Length[xd]}]}]]]/10;
> Print[37*x," ",xr," ",Mod[xr,37]],
> {20}
> ];
>
> 37*x 37*x reversed mod
> 21239110 1010903020102 0
> 4168938 8030908060104 0
> 26613804 400080301060602 0
> 16681376 607030108060601 0
> 29952869 906080205090902 0
> 10118390 9030801010001 0
> 18334018 801000403030801 0
> 27200957 705090000020702 0
> 15339386 608030903030501 0
> 12664545 504050406060201 0
> 26070607 700060007000602 0
> 7706767 7060706000707 0
> 8135597 7090505030108 0
> 19677673 307060707060901 0
> 28227078 807000702020802 0
> 10917109 900010701090001 0
> 16013822 202080301000601 0
> 29539616 601060903050902 0
> 28696386 608030609060802 0
> 30238398 809030803020003 0
>
> 20 out of 20 were divisible by 37.
> Either I made a mistake or it isn't P=1/37
You are correct, the probability is not 1/37. But what is it?
Bob H
ObPuzzle: which is easier to read, Mathematica or APL?
me13013
> ... the probability is not 1/37. But what is it?
and the same wishing-to-be-anonymous individual sent this response:
> 10^6 out of 10^6 were divisible by 37
> So again either I made a mistake OR likely P=1.
>
> My first thought was that every number with intervening
> zeros is divisible by 37. My first manually created number
> contradicts that so a trivially easy proof won't do.
Actually the probability is 1. Asking for this as a probability was a
red herring. The real question is, why does that procedure always
produce a multiple of 37? There is a proof that, while it is not
trivial, I believe it could be understood by your average high school
student (though admittedly it's been quite a while since I've been
near a high school).
What for it's worth the same process works with 27 instead of 37.
Bob H
me13013
>
> 1) choose an integer at random
> 2) multiply it by 37
> 3) reverse the order of the digits in the result of 2
> 4) insert a zero between every pair of digits in the result of 3
>
> There is a proof that, while it is not trivial, I believe it could be
OK, here's the proof. The key is that 10^3 == 1, modulo 37.
Let x and y be the results of steps 2 and 4, respectively. Let n be
the number of digits of x and its digits be x_(n-1) ... x_0.
We have
x = sum over i=0 to n-1 of x_i*10^i == 0 (modulo 37)
and we want to show that
y = sum over i=0 to n-1 of x_i*10^2(n-1-i) == 0 (modulo 37)
Let m=(1-n) mod 3 and consider y-x*10^m.
y-x*10^m = sum over i=0 to n-1 of [x_i*10^2(n-1-i) - x_i*10^(i+m)]
= sum over i=0 to n-1 of x_i*[10^(2n-2-2i) - 10^(i
+m)]
As we run over the sum, the left exponent of 10 is decreasing and the
right exponent is increasing. First suppose the left exponent is
larger, i.e. that
2n-2-2i > i+m
Then
10^(2n-2-2i) - 10^(i+m) = 10^(i+m) * [10^(2n-2-3i-m) - 1]
== 10^(i+m) * [10^(2n-2-3i-(1-n))
- 1]
In that step we replaced equals by congruence modulo 37.
Continuing...
10^(2n-2-2i) - 10^(i+m) == 10^(i+m) * [10^(3n-3-3i) - 1]
== 10^(i+m) * [(10^3)*(10^(n-1-
i)) - 1]
== 10^(i+m) * [1*10^(n-1-i) - 1]
== 10^(i+m) * [1 - 1]
== 0
If the right exponent is larger we also get zero (proof left to
reader). And of course if the exponents are equal we get zero.
Thus
y-x*10^m = sum over i=0 to n-1 of x_i*10^(i+m)*[10^(2n-2-2i-i-m)
- 1]
== sum over i=0 to n-1 of x_i*0
== 0
and since x*10^m == 0 (any multiple of x == 0), y == 0.
This is probably easier to see with an example. For x = 10841 we have
n=5 and m=2. Listing y and x*10^m one over the other we see that the
difference in exponents (for the same digit of x) is always a multiple
of 3. Thus the difference for that digit is always of the form 10^j*
[10^k*10^3 - 1] which is congruent to zero.
y = 1*10^0 + 0*10^2 + 8*10^4 + 4*10^6 + 1*10^8
x*10^2 = 1*10^6 + 0*10^5 + 8*10^4 + 4*10^3 + 1*10^2
The above proof also works if we replace 37 with 27, because 10^3 == 1
modulo 27 too.
Bob H
Macavity
Let the multiple of 37 obtained at step (2) be N, with m+1 digits -
each being d(k).
So N = Sum {d(k) 10^k; k = 0 to m}
For ease, let us write this as a "vector" dot product, i.e.
N = <d(0), d(1), ... d(m)> . <1, 10, ... 10^m>
Also note that:
10^0 mod 37 = 1
10^1 mod 37 = 10
10^2 mod 37 = 26
10^3 mod 37 = 1
10^4 mod 37 = 10
10^5 mod 37 = 26
10^6 mod 37 = 1
...
So N mod 37 can be written as
= <d(0), d(1), ... d(m)> . <1, 10, 26, 1, 10, 26, ... >
= < A, B, C> . < 1, 10, 26 >
where
A = d(0) + d(3) + ... d(3k) + ...
B = d(1) + d(4) + ... d(3k+1) + ...
C = d(2) + d(5) + ....d(3k+2) + ...
Thus, we have N = 0 mod 37
or < A, B, C > . < 1, 10, 26 > = 0 mod 37
Steps (3) and (4) on N [or the digits d(k)] can be considered as a
rearrangement on the corresponding 10^ks. In fact, it can be verified
that the steps have the combined effect of rearranging the < 1, 10, 26
> to
either < 10, 26, 1> or < 26, 1, 10 > or retaining the same order < 1,
10, 26 >, depending on m mod 3.
---
To illustrate consider following e.g.,
let us assume we selected 1234 in Step (1). Then the multiple is N =
45658
= <8, 5, 6, 5, 4> . <1, 10, 100, 1000, 10000>
= <8, 5, 6, 5, 4> . <1, 10, 26, 1, 10> mod 37
which can also be written as <13, 9, 6> . <1, 10, 26> mod 37
The digit reversal in step (3), can be represented as
<8, 5, 6, 5, 4> . <10000, 1000, 100, 10, 1>
and the insertion of the additional zeros by
<8, 5, 6, 5, 4> . <10^8, 10^6, 10^4, 100, 1>
= <8, 5, 6, 5, 4> . <10^8, 10^6, 10^4, 100, 1>
= <8, 5, 6, 5, 4> . <26, 1, 10, 26, 1> mod 37
= <13, 9, 6> . <26, 1, 10> mod 37
It can be seen that the effect of steps (3) and (4) have been to
cyclically rotate
<1, 10, 26> factor of N, to <26, 1, 10>
----
(The above assertion is easy enough to see, though isn't rigourous
proof)
Thus if we start with N = <A, B, C> . <1, 10, 26> mod 37
we have the final number as
< A, B, C > . <10, 26, 1> or
< A, B, C > . <26, 1, 10> or
the same original number N.
Now, 10 * <1, 10, 26> = <10, 26, 1> mod 37 and
100 * <1, 10, 26> = <26, 1, 10> mod 37, and as 10 is relatively prime
to 27,
the divisibility by 37 does not change through these steps.
Hence the final number is also divisible by 37.
As 27 also has a "three period" in base 10, <1, 10, 19>, and is also
relatively prime to 10, I expect the above steps will work for 27 as
well...
- Mac.
Macavity
> = <13, 9, 6> . <26, 1, 10> mod 37
>
> It can be seen that the effect of steps (3) and (4) have been to
> cyclically rotate
> <1, 10, 26> factor of N, to <26, 1, 10>
>
> ----
> (The above assertion is easy enough to see, though isn't rigourous
> proof)
>
Hi Bob,
Just read your proof, which is more direct. Also had an idea to fill
the gap in my own post, i.e, that the change from 10^k to 10^(2m - 2k)
has the effect of only cyclically shifting <1, 10, 26>
Given a finite repeating sequence (a, b, c, a, b, c, a, b, c, ... )
with m terms, the steps (3) and (4) result in reversing the order, and
skipping alternate terms. Digit reversal leads to (...., c, b, a, c,
b, a, c, b, a....), which also has reverse the order of a, b, c. Now
skipping alternate terms leads to "restoring" the order (...., c, a,
b, c, a, ....). Hence the net effect would be only to cyclically
shift <1, 10, 26>
Hope that is clearer!
- Mac.
> Thus if we start with N = <A, B, C> . <1, 10, 26> mod 37
> we have the final number as
> < A, B, C > . <10, 26, 1> or
> < A, B, C > . <26, 1, 10> or
> the same original number N.
>
> Now, 10 * <1, 10, 26> = <10, 26, 1> mod 37 and
> 100 * <1, 10, 26> = <26, 1, 10> mod 37, and as 10 is relatively prime
> to 27,
> the divisibility by 37 does not change through these steps.
>
> Hence the final number is also divisible by 37.
>
> As 27 also has a "three period" in base 10, <1, 10, 19>, and is also
> relatively prime to 10, I expect the above steps will work for 27 as
> well...
>
> - Mac.- Hide quoted text -
>
> - Show quoted text -
me13013
> Just read your proof, which is more direct. ...
I think your approach gets at the heart of the matter better than mine
does. My proof obscures the underlying property.
The general principle that led me to this multiple-of-37 trick is even
more interesting. Suppose we have integers p,q and w such that pq ==
1 modulo w. If we take any multiple of w in radix p, reverse the
digits, and interpret that as radix q, it will be a multiple of w. I
generously leave the proof as an exercise for the reader. ;)
For example, p=10, q=12, w=17. 31*17 is 527 in base 10. Reverse it
to 725 and treat it as base 12. If you know someone who does a lot of
work in base 16 you can show him this trick for bases 10 and 16 and
multiples of 53 (fifty-three in base 10 that is).
The multiple-of-37 trick uses p=10 and q=100 (and w=37). Insertion of
zeros between digit pairs is just a quick way to convert from base 100
back to base 10.
Bob H
Prai Jei
continuum:
> the divisibility by 37 does not change through these steps.
>
> Hence the final number is also divisible by 37.
>
> As 27 also has a "three period" in base 10, <1, 10, 19>, and is also
> relatively prime to 10, I expect the above steps will work for 27 as
> well...
I would think the fact that 27 x 37 = 999 is of some significance here.
--
ξ:) Proud to be curly
Interchange the alphabetic letter groups to reply
me13013
he waxed poetic about the following:
> Macavity set the following eddies spiralling through the space-time
> continuum:
> > the divisibility by 37 does not change through these steps.
>
> > Hence the final number is also divisible by 37.
>
> > As 27 also has a "three period" in base 10, <1, 10, 19>, and is also
> > relatively prime to 10, I expect the above steps will work for 27 as
> > well...
>
> I would think the fact that 27 x 37 = 999 is of some significance here.
It will work for any factor of 999. But 3 and 9 aren't very
impressive. 111 is not very impressive either, but I suppose it might
not be too obvious why 5493227*111 = 609748197 -> 70901080407090006 =
638748472135946*111. Maybe 333 or 999 would be interesting, but 37
seemed the most interesting to me.
Bob H
Macavity
> On Jan 7, 12:08 pm, Macavity <raj.r...@gmail.com> wrote:
>
> > Just read your proof, which is more direct. ...
>
> I think your approach gets at the heart of the matter better than mine
> does. My proof obscures the underlying property.
>
> The general principle that led me to this multiple-of-37 trick is even
> more interesting. Suppose we have integers p,q and w such that pq ==
> 1 modulo w. If we take any multiple of w in radix p, reverse the
> digits, and interpret that as radix q, it will be a multiple of w. I
> generously leave the proof as an exercise for the reader. ;)
>
OK, I will bite again, but will attempt proof along the approach /
notation as in the earlier post.
Rephrasing the problem...
Let "==" below denote == mod w.
Given
(1) pq == 1
and
(2) X = <A(0), A(1), A(2), ... A(m)> a vector,
s.t. X . P == 0 mod w, where kth element of P is p^k
To show X . Q == 0
where kth element of Q is q^(m-k)
------
From (1) we have
=> q^(-1) == p
Also q is relatively prime to w, hence multiplying by any power of q
is not going to affect divisbility by w.
But q^(m-k) == q^m p^k
Thus q^m P == Q
and X . P == 0
=> q^m (X . P) == 0
=> X . (q^m P) == 0
=> X . Q == 0.
If that's right, this more general case seems sweeter and simpler!
- Mac.
Macavity
> On Jan 7, 10:42 pm, me13013 <me13...@gmail.com> wrote:
>
> > On Jan 7, 12:08 pm, Macavity <raj.r...@gmail.com> wrote:
>
> > > Just read your proof, which is more direct. ...
>
> > I think your approach gets at the heart of the matter better than mine
> > does. My proof obscures the underlying property.
>
> > The general principle that led me to this multiple-of-37 trick is even
> > more interesting. Suppose we have integers p,q and w such that pq ==
> > 1 modulo w. If we take any multiple of w in radix p, reverse the
> > digits, and interpret that as radix q, it will be a multiple of w. I
> > generously leave the proof as an exercise for the reader. ;)
>
> OK, I will bite again, but will attempt proof along the approach /
> notation as in the earlier post.
>
> Rephrasing the problem...
>
> Let "==" below denote == mod w.
>
> Given
> (1) pq == 1
>
> and
> (2) X = <A(0), A(1), A(2), ... A(m)> a vector,
> s.t. X . P == 0 mod w, where kth element of P is p^k
>
> To show X . Q == 0
> where kth element of Q is q^(m-k)
>
> ------
>
q^m p^k = (pq)^(k) q^(m-k)
== 1 q^(m-k)
Thus q^m P == Q
X . P == 0
=> q^m (X . P) == 0
=> X . (q^m P) == 0
=> X . Q == 0.
Shorter and sweeter?
- Mac.
me13013
very nice