Review: A069554

[David Wilson]

----- Original Message -----
From: "Don Reble" <djr at nk.ca>
To: "Number Sequence Mailing List" <seqfan at ext.jussieu.fr>
Sent: Friday, May 31, 2002 6:41 AM
Subject: Re: Review: A069554


> > The questionable elements are:
> > a(37) = 0.  Empirical evidence indicates that
> > 37 | gcf(k, rev(k)) ==> 111 | gcf(k, rev(k)),
> > in which case gcf(k, rev(k)) = 37 has no solution.
>
>     Questionable indeed! For k=1009009009009, gcd(k,rev(k))=37.
>     So we just have to find the smallest one.
> --
> Don Reble       djr at nk.ca

With your inspiration, I have proved that 1009009009009 is the least k with
gcd(k, rev(k)) = 37.  A sketch of the proof:

We can assume k > 0.  Let the decimal expansion of k be

   k = SUM(j = 0 to n; d(j)*10^j)

where each d(j) is a digit and d(n) > 0.  So, written out in decimal, we
have

  k = d(n) d(n-1) ... d(2) d(1) d(0)

Now, break the three groups:

  P = { d(2), d(5), d(8), ... }
  Q = { d(1), d(4), d(7), ... }
  R = { d(0), d(3), d(6), ... }

Given 10^3 == 1 (mod 37), you can show that

  k == 100*sum(P) + 10*sum(Q) + sum(R) (mod 37)

where sum(S) = sum of elements of S.

You can also show that one of the following is true:

  rev(k) == 100*sum(R) + 10*sum(Q) + sum(P) (mod 37)
  rev(k) == 100*sum(Q) + 10*sum(P) + sum(R) (mod 37)
  rev(k) == 100*sum(P) + 10*sum(R) + sum(Q) (mod 37)

according to whether k has 3n, 3n+1, or 3n+2 digits.

In each of these three cases, we can show

  rev(k) == 0 (mod 37)  <=>  100*sum(P) + 10*sum(R) + sum(Q) == 0 (mod 37)

Given that gcd(k, rev(k)) = 37, we must have k == 0 (mod 37) and rev(k) == 0
(mod 37).
These are equivalent to

  100*sum(P) + 10*sum(Q) + sum(R) == 0 (mod 37)
  100*sum(P) + 10*sum(R) + sum(Q) == 0 (mod 37)

With a little work, these two congruences imply

  sum(P) == sum(Q) == sum(R)  (mod 37).

Obviously each of sum(P), sum(Q) and sum(R) is >= 0.  Suppose each were <
37.  The
congruence would then force sum(P) = sum(Q) = sum(R).  The sum of all the
digits of k
would then be sum(P) + sum(Q) + sum(R) = 3 sum(P), implying 3 | k.  rev(k)
has the
same digital sum as k, so 3 | rev(k) as well.  Hence 3 | gcd(k, rev(k)),
contradicting
gcd(k, rev(k)) = 37.  We must conclude that one of sum(P), sum(Q), or sum(R)
>= 37.

Now

   sum(P) >= 37  ==>  k >= 100900900900900
   sum(Q) >= 37  ==>  k >= 10090090090090
   sum(R) >= 37  ==>  k >= 1009009009009

so k >= 1009009009009.  Happily k = 1009009009009 satisfies gcd(k, rev(k)) =
37, and
we know it is the least value that can do so.  Therefore:

%S A069554
1,2,3,4,5,6,7,8,9,0,11,48,1495,2072,510,2192,1156,234,2489,0,168,22,3358,
%T A069554
840,5200,2678,2889,4256,5017,0,1178,21920,33,20774,5075,216,1009009009009,
%U A069554
2318,1677,0,1066,2436,15523,44,540,20516,30644,8400,18718,0,1479,21788