Date: Fri, 02 Nov 2001 03:00:05 +0000
From: Don Reble
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