cp's OEIS Frontend

Records occur at indices 0, 1, 2, 3, 5, 7, 11, 22, 23, 46, 47, 94, ... (see A297026).

Theorem: S_n contains Fibonacci(n+2) elements.

Proof from Adam P. Goucher, Jan 12 2022 (Start)

Let 'D' and 'I' be the 'double' and 'increment' operators, acting on 0 from the right. Then every element of S_n can be written as a length-n word over {D,I}. E.g., S_4 contains

0: DDDD

1: DDDI

2: DDID

3: DIDI

4: DIDD

5: IDDI

6: IDID

8: IDDD

We can avoid having two adjacent 'I's (because we can transform it into an equivalent word by prepending a 'D' -- which has no effect -- and then replacing the first 'DII' with 'ID').

Subject to the constraint that there are no two adjacent 'I's, these 'II'-less words all represent distinct integers (because of the uniqueness of binary expansions).

So we're left with the problem of enumerating length-n words over the alphabet {I, D} which do not contain 'II' as a substring. These are easily seen to be the Fibonacci numbers because we can check n=0 and n=1 and verify that the recurrence relation holds since a length-n word is either a length-(n-1) word followed by 'D' or a length-(n-2) word followed by 'DI'. QED (End)

From Rémy Sigrist, Jan 12 2022: (Start)

For any m >= 0, the value m first appears on row A056792(m).

For any n > 0: row n minus row n-1 corresponds to row n of A243571.

(End)

This is initially the same as A056792, and in fact a(n) is less than or equal to A056792(n) for all n, since adding one and doubling correspond to precisely the zeroth and first functions in the fast-growing hierarchy (regardless of which assignment of fundamental sequences is used).

This function is slow-growing, satisfying a(n) <= n for all n. Also, values of a(n) at odd numbers n can be computed from those at even numbers, since, if n is even, the only way to get from 0 to n+1 is to get from 0 to n and then add one. In particular, a(2n+1) = a(2n)+1 for all n. Additionally, if n is odd, then similarly the shortest way to get from 0 to 2n is to get from 0 to n and then double, and therefore a(4n+2) = a(2n+1)+1 = a(2n)+2.

In general, a(2n) <= a(n)+1, a(2^k*n) <= a(n)+k, and a(2^n*n) <= a(n)+1 (as opposed to a(n)+n). This is because 2^n*n is the second function in the fast-growing hierarchy, obtained by applying the first function (doubling) n times.

Let a_b(n), for an ordinal b > 0, denote a(x) but only considering the functions in the fast-growing hierarchy arising strictly before stage b. Then a_1(n) = n, a_2(n) = A056792(n), and a(n) <= a_b(n) for all b, providing slower and closer approximations to a (since, straightforwardly, a_b(x) <= a_c(x) for all x whenever c < b). Since the "limit" of the Wainer hierarchy is e_0, one has a(x) = a_e_0(x). One last remark regarding these minor modifications is that, if b is a limit ordinal, then a_b = a_(b+1), since any application of f_b, where f_b denotes the b-th function in the fast-growing hierarchy, can be converted into an application of f_c for c < b without changing the input. The first "obligatory" usage of f_(w+1), i.e., the first point of difference between a_(w+2) and a_w, occurs at n = f_(w+1)(2) = f_8(8). This is smaller than Graham's number but far larger than any reasonable power tower.

The n with a(n) < 3 are precisely 0, f_b(0) and f_b(1) for b < e_0. Using transfinite induction and case classification, one sees that if b is zero or successor then f_b(0) is 0 or 1 and f_b(1) is 2, and if b is a limit then one can apply fundamental sequences iteratively until one reaches a non-limit index to get that f_b(0) is, again, either 0, 1 or 2. Therefore, there are finitely many n so that a(n) < 3, but infinitely many n so that a(n) = 3, and therefore the limit infimum of this sequence is precisely 3. This is another sense in which it may be considered slow-growing.

The values of a(n) for n < 91 were first manually computed by Jayde Massmann and Umut Tahiroğlu in personal correspondence. Adrian Kwon wrote a program to automatically compute a(n), which lended to computing the values of a(n) for 91 <= n < 101.

Records are a(0) = 0, a(1) = 1, a(2) = 2, a(4) = 3, a(5) = 4, a(11) = 5, a(14) = 6, a(32) = 7, a(41) = 8, a(95) = 9, a(122) = 10, a(284) = 11, a(365) = 12, a(851) = 13, a(1094) = 14, a(2552) = 15, a(3281) = 16, a(7655) = 17, a(9842) = 18, a(22964) = 19, .... - Charles R Greathouse IV, Jan 03 2017

a(n) is the shortest number of commands, excluding the output command, to write the number n in the esoteric programming language Deadfish (see link Deadfish programming language specification for more information), ignoring the rule of setting n to zero if n ever equals 256.

a(n) <= n, since applying the incrementation operation n times trivially yields n.

a(n+1) <= a(n)+1, a(n-1) <= a(n)+1, and a(n^2) <= a(n)+1. This is because it is always possible to apply some valid operation to a series of valid operations that yields n in order to yield n+1, n-1, or n^2, respectively.

These also imply that |a(n+1)-a(n)| <= 1, since a(n-1) <= a(n)+1 implies a(n) <= a(n+1)+1 implies -a(n+1) <= 1-a(n) implies a(n+1) >= a(n)-1. Therefore the first differences of this sequence will always be -1, 0, or 1.

For n >= 4, at least one squaring operation must be used in the sequence of length a(n) yielding n. This is because using only incrementation or decermentation yields a sequence at least as long as n, but a(4) < 4, and because a(n+1) <= a(n)+1, thus a(n) < n for n >= 4, which leads to a contradiction.

Binary tree that contains odd numbers. Predecessors to numbers of Collatz sequences are determined.

The variables u and d are used here to distinguish between one and two consecutive even numbers in a Collatz sequence: If there is one even number between two odd numbers in the Collatz sequence, then this is a u-evolution; if there are two even numbers, then this is a d-evolution: 3 is a u-predecessor of 5, 17 is a d-predecessor of 13.

Each integer is assigned to a mod residue class from A000079. The offset 5 receives the modulo 8. Later the u-number gets the doubled modulo, the d-number gets the quadrupled modulo. These attached modulo are used to increase the base in the design for predecessors if necessary. The exponent results from the sequence A119476 starting with the second term.

Two predecessors are determined for every integer backwards to the procedure for the Collatz problem: a u-predecessor and a d-predecessor.

The main rule is that we calculate u = (m*2-1)/3 and d = (m*4-1)/3. If this calculation does not result in an integer, we add to m its associated modulus n: m' = m + n.

First step: 5*2 = 10, next: 10-1 = 9, next: 9/3 = 3. As described above, 3 is a u-predecessor of 5. To determine the d-predecessor, 5 is already used, so we have to add the modulus 8: 5+8 = 13. The d-predecessor to 13 has to use the factor 4. So 13*4 = 52 and 52-1 = 51 and 51/3 is 17. 17 is the d-predecessor of 5.

So 5 has the two generating predecessors 3 and 17. As described above, the following attached modulo now result: 3 mod 16 and 17 mod 32.

For numbers m divisible by 3, the predecessor is formed with the next element of the residue class. In the same way - as described above - if (m*2-1)/3 or (m*4-1)/3 doesn't work, the predecessor is formed with the next element m' of the residue class.

Example: u-predecessor of 3: 3 has no predecessor. 19 (3+16) does not work for u-formation, because 2*19-1 = 37 is not divisible by 3. So the predecessor of 35 (3+16+16) is formed. It is 23, because 35*2-1 = 69 and 69/3 = 23.

Example: d-predecessor of 3: 19 (3+16): 19*2*2-1 = 75. 75/3 = 25.

Example: u-predecessor of 17: (17*2-1)/3 = 11.

Example: d-predecessor: 17+32 = 49 is taken. 49*4-1 = 195. 195/3 = 65.

Note: There is a canonical u-predecessor and a d-predecessor for every odd number.

Sketch of a proof of this:

If we look for an odd Collatz predecessor for an odd number m > 1, there are only three cases:

1) m is divisible by 3;

2) m has a u-predecessor, so m*2-1 is divisible by 3;

3) m has a d-predecessor, so m*4-1 is divisible by 3.

The addition (m' = m + 2^n) of m to a power of 2 forces these cases to alternate, so there is no other possibility at all. This follows from modular arithmetic.

Note: If we start the corresponding Collatz sequence with a number T(n, k), then there are at least n odd numbers in this Collatz sequence.

Conjecture: With the associated residue classes, this sequence forms a complete decomposition of the odd integers. In other words: If we form the complete residue classes to each number from this sequence, then all odd numbers > 1 occur once.

Remark: Even if it can be shown that every odd integer can be transformed by a Collatz sequence into a number equivalent to 5 mod 8, this does not mean that the sequence already ends immediately in the 4-2-1 cycle. For example, T(4, 2) = 73 is transformed into 125, but then jumps up again to T(14, k) = 47.