cp's OEIS Frontend

The machine has a cache which holds 1 integer and a memory which holds a list of integers.

The machine starts with a number 1 in cache and empty memory.

At every step, the machine can do one of three things:

(1) write the number from cache to a new position in memory;

(2) read any number from memory and put it in cache;

(3) add any number from memory to the number in cache.

a(n) is the minimum number of steps needed to get the number n in cache.

Conjecture: reading from memory (operation 2) is never needed to get to a number in the minimal number of steps.

Additional conjectures and comments by Glen Whitney, Oct 12 2021: (Start)

Conjecture II: For each n, there is a minimal-length program for n that stores numbers in memory in increasing order.

Conjecture III: For each n, there is a minimal-length program such that the difference between successive numbers stored in memory is strictly increasing.

All three conjectures are empirically verified for all programs of length 23 or less, and all values of n up to 2326. However, note that if you are allowed to specify the set of numbers that must be stored in memory, then the first conjecture fails for memory {1,3,9,27,30,54} and conjecture II fails for {1,3,9,27,30,54,60}. (These sequences of numbers in memory are similar to addition chains, see A003313.) Hence, a proof of the first conjecture might need to involve showing that every n has a "good" sequence of numbers that can be stored in memory to produce n, avoiding the need to invoke the read operation. Conjecture III supplies one speculative possibility of a property that might fill the role of "good." A proof of any of these conjectures would tremendously speed up computation of a(n) as compared to brute force. (End)

One can add a useless read instruction after the first operation of writing the initial one in cache to memory. Therefore, there is always a program one step longer than optimal that performs a read. Thus, in a numerical search, the first sign one might observe that read operations can be helpful is a tie for shortest between a program that does read and one that doesn't, for some value of n. However, no such ties occur for program length 21 or less. - Glen Whitney, Oct 23 2021

A sequence 1=a_0 < a_1 < a_2 < ... < a_l = n is an addition chain (of length l) for n if for each i, 0 < i <= l, there are j_i and k_i such that a_i = a_j_i + a_k_i. Such a chain is called a star-chain or Brauer chain if in addition each j_i = i-1. A number is a Brauer number if among its shortest addition chains there is a Brauer chain, and non-Brauer otherwise.

The length of a shortest Brauer chain for n is often denoted l^*(n). A003313(n) gives the length of a shortest addition chain for n. Thus n is in this sequence if and only if A003313(n) < l^*(n).

For entries at least through 41506, these numbers satisfy l^*(n) = A003313(n) + 1. It seems likely that larger differences between l^*(n) and A003313(n) occur for later entries in this sequence, but it is unclear whether any n with a larger difference have been found.

These differences between l^*(n) and A003313(n) are highlighted by the following formulation: consider a machine which starts with a 1 in "cache" and can then at each step execute one of two operations: (1) Add any number that has ever been in cache to the current contents of cache, or (2) Restore any number that has previously been in cache to the cache, replacing its prior contents. Then n is in this sequence if and only if there is a shortest program that results in n in cache that includes a "Restore" step. Note further that if there is an entry in this sequence such that l^*(n) > A003313(n)+1, then all shortest programs producing n in cache would contain a "Restore" operation. The definition of A293771 is based on a similar machine with a separate "Store" operation that puts the cache value into "memory," and one could formulate an analogous conjecture here that the "Restore" operation is never necessary for a shortest program. The existence or not of an n in this sequence such that l^*(n) > A003313(n)+1 would settle this question and provide mild evidence one way or the other on the conjecture in A293771.

There are multiple ways to get a shortest addition chain (A003313), this sequence is the smallest sum of the possible chains.

n appears in row a(n)+1 of A114622.

n appears A114623(n+1) times.

First differs from A003313 at n = 77.

This is an upper bound for both addition chains (A003313) and A117497. The first few values where A003313 is smaller are 23,43,46,47,59. The first few values where A117497 is smaller are 77,143,154,172,173. The first few values where both are smaller are 77,154,172,173,203.

For a function f from a finite set X to itself, let I(f) be the number of subsets A of X, which are f-stable in the sense that f(A) is contained in A. Then a(n) is the smallest positive integer m, such that a function f exists on a set with m elements, so that I(f) = n. The f-stable subsets form a finite topology on X, which implies that A137813 is a lower bound. The first index where A137813 is smaller is 23. - Qiaochu Yuan, Jun 27 2024