A009994 Numbers with digits in nondecreasing order.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• base
• look

Comments

Record values and occurrences of A004185. - Reinhard Zumkeller, Dec 05 2009

A193581(a(n)) = 0. - Reinhard Zumkeller, Aug 10 2011

This sequence was used by the U.S. Bureau of the Census in the mid-1950s to numerically code the alphabetical list of counties within a state (with some modifications for Texas). The 3-digit code has a "self-policing element" built into it and "was fairly effective in detecting the transposition of 2 digits." (Hanna 1959). - Randy A. Becker, Dec 11 2017

References

• Amarnath Murthy and Robert J. Clarke, Some Properties of Staircase sequence, Mathematics & Informatics Quarterly, Volume 11, No. 4, November 2001.
• Frank A. Hanna, The Compilation of Manufacturing Statistics. U.S. Department of Commerce, Bureau of the Census, 1959.

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Reinhard Zumkeller)
• David Applegate, Marc LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
• David Radcliffe and Brendan McKay, Re: A009994, SeqFan list, Jul 29 2019
• Eric Weisstein's World of Mathematics, Digit.
• Index entries for 10-automatic sequences.

Crossrefs

Apart from the first term, a subsequence of A052382. A254143 is a subsequence.

Cf. A152054, A036839.

Programs

Haskell

import Data.Set (fromList, deleteFindMin, insert)
a009994 n = a009994_list !! n
a009994_list = 0 : f (fromList [1..9]) where
   f s = m : f (foldl (flip insert) s' $ map (10*m +) [m `mod` 10 ..9])
         where (m,s') = deleteFindMin s
-- Reinhard Zumkeller, Aug 10 2011

Magma

[k:k in [0..122]|Sort(Intseq(k)) eq Reverse(Intseq(k))]; // Marius A. Burtea, Jul 28 2019

Maple

A[0]:= [0]: A[1]:= [$1..9]:
for d from 2 to 4 do
  A[d]:= map(t -> seq(10*t+i,i=(t mod 10) .. 9), A[d-1]):
od:
seq(op(A[d]),d=0..4); # Robert Israel, Jul 28 2019

Mathematica

Select[Range[0, 125], LessEqual@@IntegerDigits[#] &] (* Ray Chandler, Oct 25 2011 *)

PARI

is(n)=n=digits(n);n==vecsort(n) \\ Charles R Greathouse IV, Dec 03 2013

Python

from itertools import combinations_with_replacement
def A009994generator():
    yield 0
    l = 1
    while True:
        for i in combinations_with_replacement('123456789',l):
            yield int(''.join(i))
        l += 1 # Chai Wah Wu, Nov 11 2015

Scala

def hasDigitsSorted(n: Int): Boolean = {
  val digSort = Integer.parseInt(n.toString.toCharArray.sorted.mkString)
  n == digSort
}
(0 to 200).filter(hasDigitsSorted()) // _Alonso del Arte, Apr 20 2020

Formula

a(n) >> exp(n^(1/10)). - Charles R Greathouse IV, Mar 15 2014

a(n) ~ 10^((9! n)^(1/9) - 5), since 10^(d - 1) <= a(n) < 10^d for binomial(d + 8, 9) < n <= binomial(d + 9, 9) = (d + 5 - epsilon)^9 / 9!. Using epsilon = 10/(3n) + o(1/n) gives more precise estimate. [Following Radcliffe and McKay, cf. SeqFan list.] - M. F. Hasler, Jul 30 2019