A308539 - OEIS

%I #23 May 18 2023 23:49:13

%S 1,2,4,8,16,3,6,12,5,10,7,14,9,18,11,13,15,17,19,20,22,24,26,28,30,21,

%T 32,27,34,33,36,39,42,40,44,48,52,25,38,45,56,35,51,50,55,60,54,65,66,

%U 72,49,64,78,63,84,80,88,96,81,104,23,46,68,90,99,108,29

%N Lexicographically earliest sequence of distinct positive terms such that for any n > 0, the initial digit of a(n) divides a(n+1).

%C This sequence is a permutation of the natural numbers (with inverse A308541):

%C - for any nonzero digit d, there are infinitely many multiples of d, hence we can always extend the sequence,

%C - by the pigeonhole principle, for some nonzero digit t, there are infinitely many terms with initial digit t,

%C - so eventually every multiple of t will appear in the sequence,

%C - after a term with initial digit 1, we can always extend the sequence with the least natural number not yet in the sequence,

%C - as there are infinitely many multiples of t with initial digit 1, so infinitely many terms with initial digit 1, every natural number will eventually appear, QED.

%H Rémy Sigrist, <a href="/A308539/b308539.txt">Table of n, a(n) for n = 1..10000</a>

%H Rémy Sigrist, <a href="/A308539/a308539.png">Colored scatterplot of the first 100000 terms</a> (where the color is function of the initial digits of a(n-1))

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e a(1) = 1.

%e a(2) = 2 as it is the first multiple of 1 not yet in the sequence.

%e a(3) = 4 as it is the first multiple of 2 not yet in the sequence.

%e a(4) = 8 as it is the first multiple of 4 not yet in the sequence.

%e a(5) = 16 as it is the first multiple of 8 not yet in the sequence.

%e a(6) = 3 as it is the first multiple of 1 not yet in the sequence.

%t a[1] = 1; a[n_] := a[n] = Block[{k = 2}, While[Mod[k, First@IntegerDigits[a[n - 1]]] != 0 || MemberQ[Array[a, n - 1], k], k++]; k]; Array[a, 67] (* _Giorgos Kalogeropoulos_, May 12 2023 *)

%o (PARI) { s=0; v=1; u=1; for (n=1, 67, print1 (v ", "); s+=2^v; while (bittest(s,u), u++); forstep (w=ceil(u/d=digits(v)[1])*d, oo, d, if (!bittest(s,w), v=w; break))) }

%Y See A248024 for a similar sequence.

%Y Cf. A000030, A308541 (inverse).

%K nonn,base

%O 1,2

%A _Rémy Sigrist_, Jun 06 2019