Short Normal Numbers in base 10

Question

Normal numbers in base 10 are those for which, in the base 10 decimal expansion, you can find every natural number. Champernowne's number is a very simple example of this where it is simply written as:

0.12345678910111213...etc.

I thought that it might be interesting to see if one could write a much shorter Normal Number but using a similar procedure to Champernowne. I haven't seen this done anywhere.

For example, in the above expression, you don't need to include the 12 explicitly as it's already there at the beginning. You could write

0.12345678910113 which now includes 11, 12 and 13.

I wanted to write some Mathematica code which generated such a Normal Number in as short a way as possible. This is what I've come up with, but I wonder if there may be a better way.

isitthere[seq_, n_] := SequencePosition[seq, IntegerDigits[n]]
addtoseq[seq_, n_] := Module[{},
   id = IntegerDigits[n];
   len = Length[id];
   For[i = 1, i < len, i++,
     If[seq[[i - len ;;]] == id[[;; -i - 1]], 
       Return[ Join[seq, id[[-i ;;]]]]]
   ];
   Return[ Join[seq, id]]
]
start = {1};
For[m = 1, m <= 200, m++,
   If[isitthere[start, m] === {}, start = addtoseq[start, m]]
]
N[FromDigits[start]/10^Length[start], Length[start]]

It gives the right answer:

0.12345678910113141516171819202122425262728293032335363738394043446474\
8495054557585960656686970767798087889099100102103104105106107108109110

but it feels a little clunky. Is there a purely functional way to do this?

Answer 1

I'm not sure this is much of an improvement, but it does yield the same result as the OP.

num = {};
If[SequenceCases[num, m = IntegerDigits[#]] == {},
    {Do[
      If[num[[-i ;;]] == m[[1 ;; i]],
       {m = m[[i + 1 ;;]], Break[]}],
      {i, Length[m] - 1, 1, -1}];
     num = Join[num, m]}
    ] & /@ Range[200];

N[FromDigits[num]/10^Length[num], Length[num]]

0.12345678910113141516171819202122425262728293032335363738394043446474\ 8495054557585960656686970767798087889099100102103104105106107108109110\ 1111211411511611711811912012412512612712812913013213313413513613713813\ 9140142143144145146147148149150152153154155156157158159160162163164165\ 1661671681691701721731741751761771781791801821831841851861871881891901\ 93194195196197198199200

Answer 2

This doesn't produce the same number as your approach (I'll explain why in a moment) and it works wholly with integers but it seems to produce numbers which satisfy your criteria for normal numbers and might appeal as being a bit more functional.

First define a function to add the digits of a number only if they don't already exist within the number we're building

appendIfNotFound[num_Integer, cand_Integer] := 
 If[SequencePosition[IntegerDigits[num], IntegerDigits[cand]] == {}, 
  FromDigits[Join[IntegerDigits[num], IntegerDigits[cand]]], num]

then apply this by folding

Fold[appendIfNotFound, 1, Range[2, 250]]

The principal difference is that this approach generates the number 222 earlier in the sequence (and also many of the other numbers with 3 or more identical digits). When it comes to test the presence of 24 in the existing sequence (which at that point is 123456789101113141516171819202122) it doesn't find it, and appends 24 giving 12345678910111314151617181920212224.

I look forward to the solutions some of the smart people around here might come up with.

Weasily defence in response to OP's comments ...

My approach works just fine for normal normal numbers, ie those with an infinite number of digits. It doesn't incorrectly include 1113 and fail to recognise that it could be shortened to 113, it inserts the 4-digit number 1113 earlier than OP's approach. As I raise the number of digits to find, though, it does correctly produce the right distribution of digits.

I've run both my function and OP's up to 10^5 (his is much faster), and the histograms for 1- and 2-digit numbers in the sequence are just about flat.

I suppose what you really want is a method to generate short normal numbers, ie a method which, given the input n finds a 'finite' normal number whose digit string contains the digit strings of all numbers up to n ?