cp's OEIS Frontend

A276633 a(n) = smallest integer not yet in the sequence with no digits in common with a(n-1) and a(n-2); a(0)=0, a(1)=1.

%I A276633 #49 Jul 01 2022 05:34:01
%S A276633 0,1,2,3,4,5,6,7,8,9,10,22,33,11,20,34,15,26,30,14,25,36,17,24,35,16,
%T A276633 27,38,19,40,23,18,44,29,13,45,28,31,46,50,12,37,48,21,39,47,51,32,49,
%U A276633 55,60,41,52,63,70,42,53,61,72,43,56,71,80,54,62,73,58,64,77,59,66,74,81,65,79
%N A276633 a(n) = smallest integer not yet in the sequence with no digits in common with a(n-1) and a(n-2); a(0)=0, a(1)=1.
%C A276633 The sequence is not a permutation of the positive integers. E.g., 123456789 and 1023456789 (the smallest pandigital number) are not members.
%C A276633 Numbers n such that a(n)=n: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 52, 147, 1619, 6140, ...
%C A276633 The sequence is infinite, since all digits in a(n-3) are allowed in a(n). - _Robert Israel_, Sep 20 2016
%H A276633 Zak Seidov and David A. Corneth, <a href="/A276633/b276633.txt">Table of n, a(n) for n = 0..19999</a> (First 2001 terms from Zak Seidov).
%e A276633 From _David A. Corneth_, Sep 22 2016: (Start)
%e A276633 Each number can consist of 2^10-1 sets of distinct digits, i.e., classes. For example, 21132 is in the class {1, 2, 3}. We don't include a number without digits. For this sequence, we can also exclude numbers with only the digit 0. This leaves 1022 classes. We create a list with a place for each class containing the least number from that class not already in the sequence.
%e A276633 To illustrate the algorithm used to create the current b-file, we'll (for brevity) assume we've already calculated all terms for n = 1 to 100 and that we already know which classes will be used to compute the next 10 terms, for n = 101 to 110.
%e A276633 These classes are:  {0, 1}, {2, 3}, {5, 9}, {7, 9}, {8, 9}, {0, 1, 6}, {0, 1, 7}, {2, 2, 2} and {2, 2, 4} having the values 110, 223, 95, 97, 89, 106, 107, 222 and 224. a(99) = 104 and a(100) = 88, so from those values we may only choose from {223, 95, 97 and 222}. The least value in the list is 95. Therefore, a(101) = 95. The number for the class is now replaced with the next larger number having digits {5, 9} (=A276769(95)), being 559.
%e A276633 (One may see that in the example I only listed 9 classes. Class {8, 9} occurs twice in the example; a(104) = 89 and a(107) = 98.)
%e A276633 From a list of computed values up to some n, the values for classes may be updated to compute further. E.g., to compute a(20000), one may use the b-file to find the least number not already in the sequence for each class and then proceed from a(19998) and a(19999), etc. (End)
%p A276633 N:= 10^3: # to get all terms before the first > N
%p A276633 for R in combinat:-powerset({$0..9}) minus {{},{$0..9}} do
%p A276633   Lastused[R]:= [];
%p A276633   MR[R]:= Array[0..9];
%p A276633   for i from 1 to nops(R) do MR[R][R[i]]:= i od:
%p A276633 od:
%p A276633 A[0]:= 0: A[1]:= 1:
%p A276633 S:= {0,1}:
%p A276633 for n from 2 to N do
%p A276633   R:= {$0..9} minus (convert(convert(A[n-1],base,10),set) union convert(convert(A[n-2],base,10),set));
%p A276633   L:= Lastused[R];
%p A276633   x:= 0;
%p A276633   while member(x,S) do
%p A276633     for d from 1 do
%p A276633       if d > nops(L) then
%p A276633         if R[1] = 0 then L:= [op(L),R[2]] else L:= [op(L),R[1]] fi;
%p A276633         break
%p A276633       elif L[d] < R[-1] then
%p A276633         L[d]:= R[MR[R][L[d]]+1]; break
%p A276633       else
%p A276633         L[d]:= R[1];
%p A276633       fi
%p A276633     od;
%p A276633     x:= add(L[j]*10^(j-1),j=1..nops(L));
%p A276633   od;
%p A276633   A[n]:= x;
%p A276633   S:= S union {x};
%p A276633   Lastused[R] := L;
%p A276633 od:
%p A276633 seq(A[i],i=0..N); # _Robert Israel_, Sep 20 2016
%t A276633 s={0,1};Do[a=s[[-2]];b=s[[-1]];n=2;idab=Union[IntegerDigits[a],IntegerDigits[b]]; While[MemberQ[s,n]|| Intersection[idab,IntegerDigits[n]]!={},n++];AppendTo[s, n],{100}];s
%o A276633 (Python)
%o A276633 from itertools import count, islice, product as P
%o A276633 def only(s, D=1): # numbers with >= D digits only from s
%o A276633     yield from (int("".join(p)) for d in count(D) for p in P(s, repeat=d))
%o A276633 def agen(): # generator of terms
%o A276633     aset, an1, an, minan = {0, 1}, 0, 1, 2
%o A276633     yield from [0, 1]
%o A276633     while True:
%o A276633         an1, an, s = an, minan, set(str(an) + str(an1))
%o A276633         use = "".join(c for c in "0123456789" if c not in s)
%o A276633         for an in only(use, D=len(str(minan))):
%o A276633             if an not in aset: break
%o A276633         aset.add(an)
%o A276633         yield an
%o A276633         while minan in aset: minan += 1
%o A276633 print(list(islice(agen(), 75))) # _Michael S. Branicky_, Jun 30 2022
%Y A276633 Cf. A067581, A086066, A276512, A276769.
%K A276633 nonn,base,easy
%O A276633 0,3
%A A276633 _Zak Seidov_ and _Eric Angelini_, Sep 08 2016