Numbers avoiding certain digits

This page is about numbers not having one or some given digits in their decimal or maybe some other base B expansion.

Introduction

Although focusing on decimal digits of numbers (the so-called "base" sequences in the OEIS) is sometimes frowned upon, some considerations in that sense have recently regained big interest:

• In 2016 the EMS (Europ. Math. Soc.) has given their prestigious prize to James Maynard for "Primes with restricted digits"
• Also in 2016, work from RJL Oliver and K Soundararajan about the frequency of consecutive primes with given final digits, has made big international "buzz".

Related sequences

Basic sequences

Depending on which digit is to be avoided, we have the following sequences, and subset of primes:

   avoided digit       0        1        2        3        4        5        6        7        8        9
 numbers without    A052382  A052383  A052404  A052405  A052406  A052412  A052413  A052419  A052421  A007095
subset of primes    A038618  A038603  A038604  A038611  A038612  A038613  A038614  A038615  A038616  A038617

Special cases:

• The list of numbers with no decimal digit 9 is the same as the list of all numbers but written in base 9. This yields an efficient method to compute the n-th term of all of this and also the other digit-avoiding sequences, see #Programs section.
• The numbers/primes without digit '0' are commonly called "zeroless numbers"/primes. (Primes with a digit 0 or "nought" are sometimes jokingly called "naughty primes". So zeroless primes would be non-naughty primes.)
• For other digits, sometimes the (fun) terminology of "ban-X" sequences (e.g., ban-2 or "Banto") is used, similar to "Eban numbers", "Uban numbers", ... (which however refers to the English name of the numbers, which must not have the letter E or U etc...)

All these sequences are 10-automatic (see the index here).

Generalizations

• 2 digits excluded: for excluded digits X = {8, 9}, this is A007094: numbers in base 8
• 3 digits excluded: for excluded digits X = {7, 8, 9}, this is A007093: numbers in base 7
• 4 digits excluded: for excluded digits X = {6, 7, 8, 9}, this is A007092: numbers in base 6

  for X = {2, 3, 5, 7}: Prime digits are excluded, so we get numbers having only non-prime digits

  For X = { 0, (4?), 6, 8, 9}: Complement of the "holy" numbers Axxx (having a "hole" in one of the digits).

• 5 digits excluded: for excluded digits X = {5, ..., 9}, this is A007091: numbers in base 5

  For X = {0, 2, 4, 6, 8}: numbers with only odd digits

  For X = {1, 3, 5, 7, 9}: numbers with only even digits

• 6 digits excluded: for excluded digits X = {4, ..., 9}, this is A007090: numbers in base 4

  For X = {0, 1, 4, 6, 8, 9}, non-prime digits are excluded, so we get Annn: numbers having only prime digits {2, 3, 5, 7}

  for X = {0, 1, 2, 3, 5, 7}: Prime digits and 0 and 1 are excluded, so we get numbers having only composite digits {4, 6, 8, 9}

• 7 digits excluded: for excluded digits X = {3, ..., 9}, this is A007089: numbers in base 3
  • There are many sequences of "squares having only digits {a, b, c}, a.k.a. "sporadic three-digital solutions" and variations:

    see OEIS index for squares having only given digits

• 8 excluded digits, i.e., only 2 digits allowed: (All of these sequences follow in an obvious way from the first one, the binary numbers.)

  Cf. A007088 (digits 0 & 1), A007931 (digits 1 & 2), A032810 (digits 2 & 3), A032834 (digits 3 & 4), A256290 (digits 4 & 5) - A256292 (digits 6 & 7), A256340 (digits 7 & 8), A256341 (digits 8 & 9).

  [more? to be completed...]

• 9 digits excluded: for excluded digits X = {0, 2, ..., 9} (only 1 is allowed) these are the repunits A000042, R(n) = (10^n-1)/9 (a.k.a. numbers in base 1).

Programs

Algorithms

For the basic sequences, it is quite easy to implement the complete set of functions:

• Axxx: directly compute the n-th term.

To do so, use the base (b-1) expansion of n and replace all digits >= the excluded one with the next larger digit. (The zeroless numbers require a slightly different treatment, and for the 9-less numbers there is no need for the "replace..." step.)

This method also generalizes to sets of numbers avoiding more than one given digit:

if only m digits are allowed, use base m expansion and replace the digits 0, ..., m-1 by the corresponding allowed digits d(1), ..., d(m), respectively.

• isAxxx or AxxxQ: check for membership in Axxx.

The straightforward method is to compute the base b expansion and check whether the given digit is present. In principle, we don't need the whole expansion: as soon as the first forbidden digit is computed, we may return false. If all digits are computed, we can scan from the beginning and stop once a forbidden digit is found. The worst one can do in terms of efficiency is to count the number of times the digit is there and return false if > 0.

However, often built-in functions that compute the whole expansion will give faster code than a custom implementation computing one digit after the other. Even checking for membership of forbidden digit(s) within the set of digits (in increasing order and with duplicates removed) will be faster.

• nextAxxx: given n, compute the smallest term > n of Axxx. [=> Iterators in languages providing such structure.]

Rather than checking all successors of n with isAxxx, one should find the first forbidden digit in n+1, increase it by one and set the subsequent digits to the smallest possible value. (Some additional considerations are needed when the forbidden digit is 0 or b-1 in base b.)

• Axxx_vec: the vector of the first n initial values. Typically, ( x_i; i=1..n ) with x_i = nextAxxx(x_{i-1}) for i > 1.
• Axxx_upto: the vector of the terms not exceeding a given limit.

Easily implemented as select( isAxxx, [0..n]), but it may be more efficient to a while loop with nextAxxx

PARI code

(Concerning the style below: the function definitions {isAnnn(n)=...}, Axxx_vec()=... etc. are "wrapped" into a code that not only defines them but also applies them to small values providing an example of use and check of correctness. The whole line can be copy-pasted into the PARI command line or [online interpreter], it will display the result of applying the function to some value(s), but the main purpose is to have the function defined thereafter.)

apply( {A007095(n)=fromdigits(digits(n-1,9))}, [1..99])   # n-th number avoiding digit 9: write n-1 in base 9!
# for numbers avoiding a digit < 9 we also write n in base 9 but increment digits >= the one we want to avoid
apply( {A052414(n)=fromdigits(apply(d->d+(d>=6), digits(n-1,9)))}, [1..99])   # n-th number avoiding digit 6
# for zeroless numbers, slightly different: subtract sum 9^k, then write in base 9, then add repunit 1...1 
apply( {A052382(n, L=logint(n, 9))=fromdigits(digits(n-9^L>>3, 9))+10^L\9}, [1..100]) # n-th zeroless number

Next larger term of the sequence: (here: numbers with no digit 6)

next_A052414(n, d=digits(n+=1))={for(i=1,#d, d[i]==6&&return((1+n\d=10^(#d-i))*d)); n}  # least a(k) > n

Example of use: first n terms >= M (if given)

( {A052414_vec(n,M=0)=M--;vector(n, i, M=next_A052414(M))} )(10, 1000)

Characteristic function:

select( {is_A052414(n)=!setsearch(Set(digits(n)),6)}, [0..99])

Naïve application: (better use next_Annn() above: there may be a big range with the forbidden digit near to the left.

( {A052414_upto(N,M=0)=select( is_A052414, [M..N])} )(99)   \\ the function is within {...}, outside the "check & demo wrapper"

Subset of primes:

select( {is_A038614(n)=is_A052414(n)&&isprime(n)}, [1..350]) \\ is_A052414 from above 
( {A038614_upto(N,M=2)=select( is_A052414, primes([M,N]))} )(350) \\ compute terms <= N (and >= M if given)

next_A038611(n)={until((n=nextprime(n+1))==n=next_A052405(n-1), ); n} \\ more efficient

Example of use: compute list of the first n terms >= M (if given):

( {A038611_vec(n, M=2)=M--; vector(n, i, M=next_A038611(M))} )(20, 1000)

Less efficient variants: (explain why!)

next_A038614(n)={until(isprime(n), n=next_A052414(nextprime(n+1)-1));n} # or: until(is_A052414(n), n=nextprime(next_A052414(n)));n

Python code

Here is example code for a class which comprises a generator function.

Project: define classes IntSeq & subclasses NumbersAvoidingDigit ... which allow to say A052404=NumbersAvoidingDigit('2') which should provide A052404.term(n), A052404.has(n), A052404.next(n), A052404.range([start,]stop), ...

class A052404:
   """ numbers with no digit '2', a.k.a. Bantu / banto / bantwo / ban2 numbers
       Use with one, two or zero arguments, corresponding to starting/ending values (not indices!), e.g.:
       list(A052404.range(50))
       [x for x in A052404.range(1, 1000) if isprime(x)] # this yields the "Banto primes" A...
       for x in A052404(): ...; if ... break;      # (infinite generator)
   """
   def range(self, *limits): # default limits: [[start = 0,] stop = math.inf]
       lim = limits[-1] if limits else math.inf
       n = limits[0] if len(limits)>1 else 0
       while n < lim:
           s=str(n); t = s.find('2')
           if t<0: yield n; n+=1
           else: t = 10**(len(s)-1-t); n += t - n % t

For 'fun', the following 1-lines:

def A052413(n): n-=1; return sum(n//9**e%9*6//5*10**e for e in range(math.ceil(math.log(n+1,9))))
def next_A052413(n): n+=1; s=str(n); s=10**(len(s)-1-s.find('5')); return n if s>n else n+s-n%s # compute least a(k) > n
def A052413_upto(N=math.inf, a=0): while a < N: yield a; a=next_A052413(a)
def A052413_list(n): A=A052413_upto(); return [next(A) for i in range(n)] # for illustration - maybe [A052413(i) for i in range(1,n+1)] is better!

See also

• Index entries for 10-automatic sequences

Authorship

M. F. Hasler, Numbers avoiding certain digits.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Numbers_avoiding_certain_digits] initial version: Jan 12 2020