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

Author

Rémy Sigrist, Jun 06 2019

Keywords

• nonn
• base

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.

Examples

			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.
		

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

Crossrefs

See A248024 for a similar sequence.

Cf. A000030, A308541 (inverse).

Programs

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

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

Python

from itertools import count, islice
def agen(): # generator of terms
    an, aset, m = 1, {1}, 1
    while True:
        yield an
        an1 = int(str(an)[0])
        an = next(k for k in count(m) if k not in aset and k%an1 == 0)
        aset.add(an)
        while m in aset: m += 1
print(list(islice(agen(), 67))) # Michael S. Branicky, Jan 27 2025