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

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, 32, 27, 34, 33, 36, 39, 42, 40, 44, 48, 52, 25, 38, 45, 56, 35, 51, 50, 55, 60, 54, 65, 66, 72, 49, 64, 78, 63, 84, 80, 88, 96, 81, 104, 23, 46, 68, 90, 99, 108, 29

Offset

1,2

Comments

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

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

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

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

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

- 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.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Rémy Sigrist, Colored scatterplot of the first 100000 terms (where the color is function of the initial digits of a(n-1))

Index entries for sequences that are permutations of the natural numbers

Example

a(1) = 1.
a(2) = 2 as it is the first multiple of 1 not yet in the sequence.
a(3) = 4 as it is the first multiple of 2 not yet in the sequence.
a(4) = 8 as it is the first multiple of 4 not yet in the sequence.
a(5) = 16 as it is the first multiple of 8 not yet in the sequence.
a(6) = 3 as it is the first multiple of 1 not yet in the sequence.

Mathematica

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 *)

Prog

(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))) }

Crossrefs

See A248024 for a similar sequence.

Cf. A000030, A308541 (inverse).

Sequence in context: A373944 A218338 A218468 * A036122 A050124 A101943

Adjacent sequences: A308536 A308537 A308538 * A308540 A308541 A308542

Keyword

nonn,base

Author

Rémy Sigrist, Jun 06 2019

Status

approved