A269631 - OEIS

%I #38 May 11 2021 05:55:34

%S 0,1,10,2,11,12,20,21,22,23,24,25,26,27,28,29,32,42,52,62,72,82,92,

%T 102,3,13,112,30,120,31,121,33,122,34,123,35,124,36,125,37,126,38,127,

%U 39,128,43,129,53,132,63,142,73,152,83,162,93,172,103,113,130,131,133,134,135

%N a(1) = 0; a(n+1) is the smallest integer not yet used that contains the number of decimal digits of a(n) as a substring.

%C Conjecture: a(n) is a permutation of the nonnegative integers.

%C The following table shows:

%C C = number of terms calculated

%C F = number of terms less than C

%C +------------+----------+-----------+

%C | C          | F        | %         |

%C +------------+----------+------------

%C | 10         | 2        | 20.0      |

%C | 100        | 39       | 39.0      |

%C | 1000       | 532      | 53.2      |

%C | 10000      | 6379     | 63.79     |

%C | 100000     | 71609    | 71.609    |

%C | 1000000    | 765630   | 76.563    |

%C | 10000000   | 7907944  | 79.07944  |

%C | 100000000  | 81251152 | 81.251152 |

%C .

%C and the growth of percentage seems to support the conjecture.

%H Francesco Di Matteo, <a href="/A269631/b269631.txt">Table of n, a(n) for n = 1..1000</a>

%e a(2) = 1 because a(1) = 0 and 0 has 1 decimal digit;

%e a(3) = 10 because a(2) = 1, so 1 has 1 digit, and 10 is the first integer not yet used that contains "1";

%e a(4) = 2 because a(3) = 10 and 10 has 2 digits;

%e a(5) = 11 because a(4) = 2, so 2 has 1 digit, and 11 is the first integer not yet used that contains "1"; ...

%t a = {0, 1}; Do[AppendTo[a, SelectFirst[Range[10^3], And[! MemberQ[a, #], MemberQ[IntegerDigits@ #, IntegerLength@ a[[n - 1]]]] &]], {n, 3, 64}]; a (* _Michael De Vlieger_, Apr 01 2016 *)

%o (Python)

%o # This routine is a little bit more complex compared to the same with

%o # the a(n) terms 'storage' (now we memorize only the highest number

%o # for every k-digits) but is very much faster.

%o print("0", end=',')

%o lista = [-1,0,0,0,0,0,0,0,0,0]

%o a = 1

%o for g in range (1,100):

%o     b = len(str(a))

%o     val = lista[b] + 1

%o     flag = 0

%o     while flag == 0:

%o         sval = str(val)

%o         while str(b) not in sval:

%o             val += 1

%o             sval = str(val)

%o         k = len(sval)

%o         comp = k

%o         for s in range(k):

%o             if lista[int(sval[s])] < val:

%o                 comp -= 1

%o         if comp == 0:

%o             flag = 1

%o         else:

%o             val +=1

%o     print(val, end=',')

%o     lista[b] = val

%o     a = val

%o # _Francesco Di Matteo_, Mar 02 2016

%o (PARI) findnew(nbd, vsa) = {k=0; while (vecsearch(vsa, k) || !vecsearch(vecsort(digits(k)), nbd), k++); k;}

%o listd(nn) = {va = vector(nn); print1(va[1], ", "); vsa = vecsort(va,,8); for (n=2, nn, nbd = #Str(va[n-1]); na = findnew(nbd, vsa); print1(na, ", "); va[n] = na; vsa = vecsort(va,,8););} \\ _Michel Marcus_, Mar 08 2016

%K nonn,base

%O 1,3

%A _Francesco Di Matteo_, Mar 01 2016