A331440 Let S = smallest missing positive number, adjoin S, 2*S, 4*S, 8*S, 16*S, ... to the sequence until reaching a term that has S as a substring; reset S to the smallest missing positive number, repeat.

1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 96, 192, 384, 5, 10, 20, 40, 80, 160, 320, 640, 1280, 2560, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 9, 18, 36, 72, 144, 288, 576, 1152, 2304, 4608, 9216, 11, 22, 44, 88, 176, 352, 704, 1408, 2816, 5632, 11264, 13, 26, 52, 104, 208, 416

Offset

1,2

Comments

Theorem 1: Every positive numbers appears at least once.

Proof from Keith F. Lynch, Jan 04 2020:

Since no nonzero power of 2 equals a power of 10, i.e., log(10)/log(2) is irrational, any sequence in which each term is the double of the previous term will start with every decimal number infinitely many times. So any S will terminate after a finite number of steps, and the next missing number will be used as S. QED

Theorem 2: No term is repeated.

Proof:

Suppose N is repeated, so there are a pair of chains

{S, 2*S, 4*S, ..., N = 2^i*S, ...},

{T, 2*T, 4*T, ..., N = 2^j*T, ...},

where T occurs after S. There are two cases. If i>=j then T = 2^(i-j)*S, so T was not a missing number. If i<j then S = 2^(j-i)*T, and T would have been a smaller choice for S. QED

So this is a permutation of the positive integers.

From Rémy Sigrist, Jan 23 2020: (Start)

The sequence can naturally be seen as an irregular table where:

- the n-th row has A331442(n) = 1 + A331619(T(n, 1)) terms, and

- T(n, k+1) = 2*T(n, k) for k = 1..A331442(n)-1.

(End)

References

Eric Angelini, Posting to Math Fun Mailing List, Jan 04 2020.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10103 (first 168 chains)

Rémy Sigrist, PARI program for A331440

Example

The process begins like this:
Initially S = 1 is the smallest missing number, so we have:
S = 1, 2, 4, 8, 16, stop (because 16 contains S), S = 3, 6, 12, 24, 48, 96, 192, 384, stop, S = 5, 10, 20, 40, 80, 60, 320, 640, 1280, 2560, stop, S = 7, 14, 28, 56, 112, 224, 448, 896, 1792, stop, S = 9, 18, 36, 72, ...

Prog

(PARI) See Links section.

Crossrefs

The inverse permutation is A331441. The lengths of the chains are given in A331442.

Cf. A331619.

Sequence in context: A036122 A050124 A101943 * A247243 A341819 A352387

Adjacent sequences: A331437 A331438 A331439 * A331441 A331442 A331443

Keyword

nonn,base,tabf

Author

N. J. A. Sloane, Jan 21 2020

Status

approved