cp's OEIS Frontend

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.

%I A331440 #39 Jan 08 2021 20:51:46
%S A331440 1,2,4,8,16,3,6,12,24,48,96,192,384,5,10,20,40,80,160,320,640,1280,
%T A331440 2560,7,14,28,56,112,224,448,896,1792,9,18,36,72,144,288,576,1152,
%U A331440 2304,4608,9216,11,22,44,88,176,352,704,1408,2816,5632,11264,13,26,52,104,208,416
%N 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.
%C A331440 Theorem 1: Every positive numbers appears at least once.
%C A331440 Proof from _Keith F. Lynch_, Jan 04 2020:
%C A331440 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
%C A331440 Theorem 2: No term is repeated.
%C A331440 Proof:
%C A331440 Suppose N is repeated, so there are a pair of chains
%C A331440 {S, 2*S, 4*S, ..., N = 2^i*S, ...},
%C A331440 {T, 2*T, 4*T, ..., N = 2^j*T, ...},
%C A331440 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
%C A331440 So this is a permutation of the positive integers.
%C A331440 From _Rémy Sigrist_, Jan 23 2020: (Start)
%C A331440 The sequence can naturally be seen as an irregular table where:
%C A331440 - the n-th row has A331442(n) = 1 + A331619(T(n, 1)) terms, and
%C A331440 - T(n, k+1) = 2*T(n, k) for k = 1..A331442(n)-1.
%C A331440 (End)
%D A331440 Eric Angelini, Posting to Math Fun Mailing List, Jan 04 2020.
%H A331440 Rémy Sigrist, <a href="/A331440/b331440.txt">Table of n, a(n) for n = 1..10103</a> (first 168 chains)
%H A331440 Rémy Sigrist, <a href="/A331440/a331440.gp.txt">PARI program for A331440</a>
%e A331440 The process begins like this:
%e A331440 Initially S = 1 is the smallest missing number, so we have:
%e A331440 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, ...
%o A331440 (PARI) See Links section.
%Y A331440 The inverse permutation is A331441. The lengths of the chains are given in A331442.
%Y A331440 Cf. A331619.
%K A331440 nonn,base,tabf
%O A331440 1,2
%A A331440 _N. J. A. Sloane_, Jan 21 2020