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