[seqfan] Re: Which of these two definitions is better?

[David Seal]

> ...  Maybe this definition would be more specific: "Least multiple of n
> that contains only the digits of n and n+1. Each digit should appear at
> least once."

It's on the right lines, but nitpicking about the wording, I would prefer "must" to "should", because "should" can be used either to say that something is obligatory, or that it is recommended. You want to say that each digit appearing once is obligatory, and "must" indicates that unambiguously. But I would also make it all one sentence, to make it completely clear that the additional requirement is within the 'scope' of "Least multiple of ...", and that can be done without either "must" or "should" by simply stating that it's the case. What I would end up with is "Least multiple of n that contains only the digits of n and n+1, with each of those digits appearing at least once." or something similar.

> I think that in this sequence we avoid the problem of powers of 2 and
> powers of 5, mentioned by David Seal. 
> For example, 128=2^7.  We can find a multiple of 128 that contains 9
> by repeating 128 until we reach the 8th digit, or higher, then we put
> 9.
> 98128128 is a multiple of 128. However, are we sure this method will
> give us the "least multiple"?

In this case, the least multiple of 128 that consists only of the digits 1, 2, 8 and 9 and contains at least one of each of those digits is 64*128 = 8192. So we can be sure that your method doesn't always give us the least multiple!

> Maybe we could add another sentence to make sure that we have values
> for all numbers. Something like "Add the least number of extra digits
> when necessary."

It isn't necessary for "Least multiple of n that contains only the digits of n and n+1, with each of those digits appearing at least once.", because it's fairly easy to prove that there is always such a multiple using the fact that n is always nonzero together with the result I proved earlier in the thread that any nonzero n has a multiple of the form 111...1000...0. Specifically, there are the following cases:

Case A) The least significant digit of n is not 9
=================================================

Let d be the least significant digit plus 1 (so d lies in the range 1 to 9). Then n+1 has the same distinct digits as n except that its least significant digit is d, and it might or might not have a digit equal to d-1. So using D(i) to denote the digit set of i, we want a multiple mn of n such that D(mn) = D(n) UNION D(n+1) = D(n) UNION {d}. To get one, form a multiple kn of n that is of the form 111...1000...0. Then dkn is of the form ddd...d000...0. Form another multiple jn of n by repeating n enough times to ensure that the number of digits of jn is greater than or equal to the number of zeros at the bottom of dkn. Then multiply dkn by p = 10^r, where r is the number of digits of jn minus the number of zeros at the bottom of dkn. We now know that pdkn is of the form ddd...d000...0, jn contains only the digits of n and each of them at least once, and the number of zeros at the bottom of pdkn is equal to the number of digits of jn. So pdkn and jn add 'cleanly' to form a number consisting of repeated d's followed by repeated copies of n, so D((pdk+j)n) = D(n) UNION {d}, i.e. (pdk+j)n is a multiple of n of the desired form.

Example: suppose n=592. Then d is its least significant digit plus 1, i.e. 3. A multiple of n that is of the form 111...1000...0 can be constructed by forming the sequence:

0 MOD 592 = 0 (in which 0 is essentially the number represented by the empty string, i.e. a string of no 1s) 
1 MOD 592 = 1
11 MOD 592 = 11
111 MOD 592 = 111
1111 MOD 592 = 519
11111 MOD 592 = 455
111111 MOD 592 = 407
1111111 MOD 592 = 519

until we get a repeated value, which happens when the 7th term is equal to the 4th in this case. Subtracting the smaller term from the larger, we get 1110000 MOD 592 = (1111111-1111) MOD 592 = (1111111 MOD 592) - (1111 MOD 592) = 519-519 = 0, so 1110000 is a multiple of n=592; doing the division, 1110000 = kn, where k = 1875.

Then dkn = 5625n = 3330000. That has 4 zeros at its bottom, and n=592 has only 3 digits, so repeat n enough times to get a multiple of jn of n with at least 4 digits and D(jn) = D(n). That requires two copies of n: jn = 1001n = 592592. Now jn has two more digits than the number of zeros at the bottom of dkn, so set p = 10^2 = 100 to get pdkn = 562500n = 333000000. Finally add jn and pdkn to get 333592592, a multiple of n that contains only the digits of n=592 and n+1=593, with each of those digits appearing just once. Specifically, 563501n = 592500n + 1001n = 333000000 + 592592 = 333592592.

Case B) The least significant digit of n is 9, but n is not all 9s
==================================================================

In this case, n will have a string of 9s at its bottom that is terminated by a non-9 digit immediately above it. Let that digit plus 1 be d, which lies in the range 1 to 9. Then the digits of n+1 differ from the digits of n only in that the string of 9s is replaced by a same-length string of 0s, and the digit d-1 that lies immediately above it is replaced by a digit d. So the set of digits of n+1 is the set of digits of n with 0 and d added if they're not already there, and 9 and d-1 possibly removed. We therefore want a multiple mn of n such that D(mn) = D(n) UNION D(n+1) = D(n) UNION {0,d}.

As in case A), we know that there is a multiple dkn of n of the form ddd...d000...0. Multiply it by p = 10^r, where r is 1 more than the number of digits of n, and we then know that pdkn is of the form ddd...d000...0 with more zeros at its bottom than n has digits. So pdkn and n add 'cleanly' to form a multiple of n of the form ddd...d000...0???...? in which there is at least one d, at least one 0 and the digits of ???...? are precisely the digits of n. So (pdk+1)n is a multiple of n of the desired type.

Example: if n=259, then d=6. We want a multiple of n of the form 111...1000...0 - let's suppose we find 11111100 = 42900n (it's not the smallest such number - that's 429n = 111111 - but it is one we could find). Multiplying by d, we get 257400n = 66666600. Since n has three digits, multiply that by 10^4 = 10000, and then add n: we get 2574000001n = 666666000259, which is a multiple of n whose digit set is D(259) UNION D(260) = {0,2,5,6,9}. (And we could have got the smaller 25740001n = 6666660259 if we'd used 111111 instead of 11111100.) 


Case C) n is all 9s
===================

In this case, n+1 is a 1 followed by a string of as many 0s as there are 9s in n, and we want a multiple mn of n with D(mn) = {0,1,9}. We can show that one exists by setting d=1 and then arguing as in case B).

Example: if d=999, then a multiple of n of the form 111...1000...0 is 111222333444555666777889n = 111111111111111111111111111. Multiply by p = 10^4 = 10000 and add n to get 1112223334445556667778890001n = 1111111111111111111111111110999.

So in all three cases, we can construct a multiple mn of n such that D(mn) = D(n) UNION D(n+1). Note that this is only an existence proof that such multiples exist and therefore the least such multiple exists, not a construction of the least such multiple. It often constructs such a multiple that is greater than the least such multiple, sometimes rather ludicrously so. For instance, if applied to n=211, case A) applies and following its recipe constructs 526592943654555028962611901n = 111111111111111111111111111111, then 1053185887309110057925223802n = 222222222222222222222222222222, then 1053185887309110057925223802001n = 222222222222222222222222222222211.  The actual least such multiple is 1n = 211!

But that existence proof means that nothing needs to be added to "Least multiple of n that contains only the digits of n and n+1, with each of those digits appearing at least once." to cover the case that no such multiple exists, because that case doesn't happen.

When it is possible that a sequence term doesn't exist, the usual policy is to add a clause to the definition to set it to a constant value that cannot occur normally, to make it as easy as possible to see the cases where the normal definition doesn't apply. If 0 cannot occur normally, I believe it's usual to make that constant 0; if it can, the next preferred choice is -1. (If both 0 and -1 can occur normally, one may need to get more inventive...)

So the definition I would choose for your earlier sequence is "Least multiple of n that contains only the digits of n+1 and n+2, with each of those digits appearing at least once, or 0 if there is no such multiple.", since it's impossible for the digits of either n+1 or n+2 to contain only 0. That way, my earlier observation is basically a proof that a(625) = 0.

David