[seqfan] Re: Is there a better way to find the terms of this sequence (other than trial and error)? Correction

Wed Nov 13 10:46:34 CET 2019

Yes, I suppose a sequence could be made of the numbers that don't have such multiples could be created, provided one can supply a reasonable number of initial terms. However, I've no real idea how much work that would involve - to establish whether 625 is its first term would involve either showing that all of 1-624 do have such multiples or that at least one of them doesn't.

I did find a few criteria for establishing that particular numbers do have such multiples during the train of thought that eventually led me to 625 - basically, I was trying to prove that a(n) does always exist, and seeing where my attempts ran out of steam, until I got a feel for what a problematic number is like. I'll describe a few of them:

I will use D(n) to denote the set of digits of n, e.g. D(625) = {2,5,6}, D(626) = {2,6}, D(627) = {2,6,7}. (Note that the fact that I call it a "set" and not a "multiset" implies that duplicate digits are eliminated.)

Define T(n) to be D(n+1) UNION D(n+2), i.e. the 'target set' of digits we want a multiple of n plus 1 to contain. Note that T(n) always contains at least one of the sets {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}, {7,8} or {8,9} as a subset, because:

* the least significant digits of n+1 and n+2 form such a subset unless they are 9 and 0;

* the second-least significant digits of n+1 and n+2 form such a subset if the least significant digits are 9 and 0, unless either the second-least significant digits don't both exist or they are 9 and 0;

* the third-least significant digits of n+1 and n+2 form such a subset if the two least significant digits are 99 and 00, unless either the third-least significant digits don't both exist or they also 9 and 0;

* the fourth-least significant digits of n+1 and n+2 form such a subset if the three least significant digits are 999 and 000, unless either the fourth-least significant digits don't both exist or they also 9 and 0;

* ...

Since a digit of n+2 can only fail to exist if the corresponding digit of n+1 also doesn't exist, this process only fails to find such a subset if all the digits of n+1 are 9s. But in that case, the digits of n+2 are a 1 followed by the same number of 0s, so {0,1} is such a subset. So such a subset exists in all circumstances, i.e. we know that d exists such that 0 <= d <= 8 and {d,d+1} is a subset of T(n).

The other important ingredient in my criteria is that any n has a multiple of the form 111...1000...0, and that if n is coprime to 10 (i.e. gcd(n,10)=1, or equivalently the last digit of n is one of 1, 3, 7 or 9), then it has a multiple of the form 111...1. To prove that, consider the sequence 1 MOD n, 11 MOD n, 111 MOD n, 1111 MOD n, 11111 MOD n, ... Its terms can only take the n values 0, 1, 2, 3, ..., n-1, and it has infinitely many terms, so by the pigeonhole principle, there is a pair of distinct terms of that sequence that are equal, say (string of r 1s) MOD n = (string of s 1s) MOD n with r > s, which implies that the difference (string of r 1s) - (string of s 1s) is congruent to 0 modulo n. So that difference, which is equal to (string of r-s 1s followed by string of s 0s), is a multiple of n, equal to say kn. If n is coprime to 10 and s > 0, then 10 divides kn, so each of the primes 2 and 5 divides kn, and since neither of those primes divides n, they must both divide k, i.e. 10 must divide k. But in that case (string of r 1s followed by string of s-1 0s) = (k/10)n is also a multiple of n, i.e. we can reduce the number of 0s by 1 and still have a multiple of n. We can do that repeatedly until we run out of 0s, so if n is coprime to 10, we can deduce that (string of r-s 1s) is a multiple of n.

Putting those ingredients together leads to my criteria:

Criterion 1: If n is coprime to 10, a(n) exists.

Proof: T(n) contains {d,d+1} as a subset for some digit d with d not equal to 9, and n has a multiple m of the form 111...1. Suppose that multiple contains k 1s. If T(n) is {r,s,t,...}, then

  i = m * (... + t*10^3k + s*10^2k + r*10^k + d)

is a multiple of n of the form ...ttt...tsss...srrr...rddd...d such that D(i) = T(n). And because both d and d+1 appear in the sequence ...ttt...tsss...srrr...r, changing the final digit d to d+1 won't alter the value of D(i). So D(i+1) = D(i) = T(n), making i a multiple of n of the desired type, and the existence of such a multiple suffices to prove that a(n) exists.

Criterion 2: If T(n) includes both 0 and 1, a(n) exists.

Proof: n has a multiple of the form 111...1000...0 with k 1s and j 0s. Multiply it by 10 if necessary to ensure that j > 0, then construct a multiple i of n of the form ...ttt...tsss...srrr...r000...0 with at least one 0 at the end similarly to above. Then i+1 is of the form ...ttt...tsss...srrr...r00...01, so D(i+1) = T(n), and the existence of such a multiple i of n again establishes that a(n) exists.

Another criterion that is a sort of hybrid of those is that if n is divisible by neither 4 nor 25 and T(n) includes 1, then a(n) exists. It is proved by showing that such an n has a multiple of the form 111...10 and then arguing as for criterion 2, but with just a single 0 at the end of i.

The existence of those criteria (especially criterion 1) led me to realise that factors of 2 and 5 were the main things that might cause difficulties in establishing that a(n) exists, and that eventually led me to investigate powers of 2 and 5, which eventually resulted in discovering that a(625) doesn't exist. But as well as that, those criteria also allow one to establish that a(n) does exist for quite a lot of smaller values of n without having to calculate it explicitly, so they should reduce the work required to establish whether 625 is the smallest value of n for which a(n) doesn't exist. It will still be a lot of work, but criterion 1 reduces it by 40% and the other criteria improve somewhat on that.

David

> On 11 November 2019 at 18:54 Ali Sada via SeqFan <seqfan at list.seqfan.eu> wrote:
> 
> 
>  Thank you David. This answered the question. I put +1 in the original definition because of 5, however, now I have the same problem with 5^4! Adding an optional 0 digit to the definition would solve the problem of 625 (70625/625=113), but that might not help with other numbers. 
> 
> In this case, can we make a sequence for the numbers that don't have such multiples? Is 625 the first number in this new sequence? 
> 
> Best,
> Ali
> 
> 
> 
> 
>  
> 
>     On Monday, November 11, 2019, 11:26:57 AM EST, David Seal <david.j.seal at gwynmop.com> wrote:  
>  
>  > I guess an obvious question about this sequence is: Can we
> > prove that this sequence has values for all natural numbers?
> 
> No, we cannot prove that, because for n = 625, your requirement is that the digits comprising 625i+1 include at least one 2, at least one 6 and at least one 7 (the distinct digits of n+1 = 626 and n+2 = 627) and no digits other than 2, 6 and 7. But 625i+1 is 1 if i=0 and 626 if i=1, neither of which contains a 7, and is otherwise a >=4-digit number ending with one of:
> 
> 0001 0626 1251 1876 2501 3126 3751 4376 5001 5626 6251 6876 7501 8126 8751 9376
> 
> none of which contain only 2s, 6s and 7s.
> 
> So a(625) doesn't have a value.
> 
> David
> 
> 
> > On 10 November 2019 at 19:07 Ali Sada via SeqFan <seqfan at list.seqfan.eu> wrote:
> > 
> > 
> >  Thank you very much Dr. Hasler for your response. I really appreciate it. 
> > 
> > First, I am sorry for the huge blunder at a(9.) Sometimes I automatically exclude n+1. 
> > I used the word "all" so that we include the all the distinct digits of n+1 And n+2. Otherwise, we could use only the digits of n+1 (and that would be just the natural numbers.) For example, for n=34, the digits of a(n) should include 3,5, and 6. We can repeat any digit as many times as we like.
> > For a(18)=1122229, we can argue that there is a digit 0 at the far left of the number. However, if we insist on having it "inside" the number then a(18)=10122229.
> > What I meant in my question was to have an analytical way to find the terms of the sequence. For example, between n=x and n=y the values of a(n) could be found by the function f(x,y.)  
> > 
> > I guess an obvious question about this sequence is: Can we prove that this sequence has values for all natural numbers?
> > Best,
> > Ali
> > 
> > 
> > 
> >    On Sunday, November 10, 2019, 10:57:45 AM EST, M. F. Hasler <oeis at hasler.fr> wrote:  
> >  
> >  On Sun, Nov 10, 2019 at 2:54 AM Ali Sada wrote:
> > 
> > > a(n)=m+1, where m is the least multiple of n such that a(n) digits consist
> > > only of all the distinct digits of n+1 and n+2.
> > >
> > 
> > It depends what you call "better" and what you call "trial and error".
> > You can indeed write a program the avoids testing "all" multiples.
> > For example, if the first digit is not in the allowed set, you can skip
> > increasingly many multiples.
> > 
> > There are certainly "even more intelligent" (lol) approaches.
> > But most probably the programs get much longer. I think that testing
> > leading digits and skipping contiguous ranges where a given digit excludes
> > success will maybe a good length/efficiency compromise.
> > 
> > For example, 209 is the least multiple of 19 where m (209+1=210) consists
> > > only of the distinct digits of 20 and 21.
> > 
> > 23, 43, 445,65, 76, 787, 988, 1009, 1111111111, 21, 1321, 11413, 4551, 561,
> > > 11176, 8817, 9181,1122229, 210, 221, 232, 243, 254, 265, 276, 287, 298,
> > > 22093, 1103, 3211, 32, 34433,3334
> > 
> > 
> > I get different values.
> > I notice that you say "only all the digits of n+1 and n+2",
> > but on one hand, 445 has twice the digit of 4, idem for 1009,
> > so I am not sure whether you really don't want to allow a(9) = 10 = 9+1
> > which has all and only digits of 10 and 11 -- or maybe that would be OK ?
> > Also, your a(18) does not contain the 0 of 20, several other following
> > values are smaller than yours:
> > 
> > apply(
> > {a(n,d=eval(Set(Vec(Str(n+1,n+2)))))=forstep(m=n,oo,n,Set(digits(m+1))==d&&return(m+1))},
> > [1..20])
> > % = [23, 43, 445, 65, 76, 787, 988, 1009, 10, 21, 1123, 11341, 1145, 561,
> > 11176, 817, 9181, 10122229, 210, 21]
> > 
> > For a(9) and a(20), I'm not sure whether you mean "multiple of n larger
> > than n":
> > If so, "m=n" must be replaced by "m=2*n" in my code which then gives
> > a(9) = 100 = 9*11 + 1 (still much smaller than 11...11), and
> > a(20) = 121 = 20*6 + 1, having only and all digits of 21 and 22, but
> > also smaller than your 221.
> > 
> > - Maximilian
> > 
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >  
> > 
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>   
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/