Date: Fri, 02 Nov 2001 03:00:05 +0000
From: Don Reble <djr(AT)nk.ca>

Subject: Extending A062885

John Layman writes:

> The interesting problem when extending A062885 is in proving that
> no such multiple exists, i.e.  that a(n) is indeed -1.
> A proof for n=25 is given in the comment to the sequence
> and is also easy for n=40. It would be of some interest to see
> proofs for n=31, 33, 37, 39, 41, etc. Some of these may be easy but,
> who knows, some may be rather challenging.
>
> John Layman


-----

Theorem: A062885[N] exists if and only if
    N divides 420864, or
    N is not divisible by 25, 40, nor 256.

Proof:
For any number N which is not a multiple of 2 nor 5, (1/N) has an
infinite periodic decimal representation which repeats from the start.

Suppose 1/N has M digits in its period. Then 10^M/N has the same
fractional part, and (10^M/N - 1/N) is an integer; that is, N divides
10^M-1.

Now, 10^M-1 is just a string of M nines, and it divides the string of
nines with length 5M: 10^M-1 divides 10^(5M)-1. Also, the number
99999 divides 10^(5M)-1. Let Q(N) = ((10^(5M)-1) / 99999). Q(N) looks
like this:
    100001000010000100001...100001
There are M ones, separated by quadruples of zeros.

-----

Let S be 8642, 20864, 42086, 64208, or 86420.

For any N not divisible by 2 nor 5, and for any S, S*Q(N) is a DED
(descending even digits) number. There are M groups of the quadruple.

So, N divides 10^M-1, which divides 10^(5M)-1, which equals
Q(N)*99999. So N divides Q(N)*99999.

-----

The prime factorization of 99999 is 3*3*41*271. If N (already not a
multiple of 2 nor 5) is also not a multiple of 3, 41, nor 271, then N
divides Q(N), and also S*Q(N).

Therefore, if N is not a multiple of 2, 3, 5, 41, nor 271, then N
divides some DED number, and A062885[N] exists.

(Note: S*Q(N) needn't be equal to A062885[N]. But it is an upper bound,
 and establishes existence.)

---

Now, suppose that N is not a multiple of 2 nor 5. Let P=99999*N.
Then P divides 99999*Q(P) (because P is not a multiple of 2 nor 5).
So (99999*Q(P))/(99999*N) is an integer, and so is Q(P)/N.
And N divides S*Q(P), which is a DED.

Therefore, if N is not a multiple of 2 nor 5, then N divides some DED
number, and A062885[N] exists.

---

The prime factorizations of S numbers are:
     8642 = 2*29*149
    20864 = 2*2*2*2*2*2*2*163
    42086 = 2*11*1913
    64208 = 2*2*2*2*4013
    86420 = 2*2*5*29*149.

For any N, one factorization of N is (2^A)*(5^B)*C, where C is not a
multiple of 2 nor 5. S*Q(99999*C) is:
    a DED number,
    a multiple of C (because of the previous argument).
If some S is also a multiple of (2^A)*(5^B), then S*Q(99999*C) is:
    a multiple of N (because C is coprime its cofactor).
And therefore N divides S*Q(99999*C).

Therefore if N=(2^A)*(5^B)*C (where C isn't a multiple of 2 nor 5), and
    A<8 and B=0 (because of 20864), or
    A<3 and B<2 (because of 86420),
then N divides some DED (either 20864*Q(99999*C) or 86420*Q(99999*C))
and A062885[N] exists.

So "C" multiples of 128 are ok, but multiples of 256 and 640 might not be.
And "C" multiples of 20 are ok, but multiples of 40 and 100 might not be.

----

We already know that 25 and 40 do not divide DED numbers; neither do
their multiples. Only multiples of 256=2^8 remain unknown.

A number is divisible by 2^K if and only if its last K digits are
divisible by 2^K. There are 32 possible eight-digit endings of
a DED number:
    2, 20, 208, ..., 4, 42, 420, ..., 86420864.
Of these, only the 420864 ending is a multiple of 256. And the only DED
number with that ending is 420864 itself.

Therefore: N divides a DED (and A062885[N] exists) if and only if
    N divides 420864, or
    N is not divisible by 25, 40, nor 256.

--
Don Reble       djr(AT)nk.ca