A293771 Minimum number of steps needed to compute n using a machine that can read, write and add starting with the number 1.

0, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, 9, 9, 9, 10, 10, 9, 10, 10, 9, 10, 11, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 12, 12, 11, 12, 12, 11, 12, 12, 12, 12, 13, 11, 12, 12, 12, 13, 13, 12, 13, 13, 12, 12, 13, 13, 14, 13, 13, 13, 14, 12, 13, 13, 13, 13, 14, 13, 14, 13, 12, 13, 14, 13, 14, 14, 14, 14, 15

Offset: 1

Author

Floris P. van Doorn, Oct 15 2017

Keywords

• nonn

Comments

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

Examples

			For n = 23 we need 10 steps to get 23 in cache:
   1. Write 1 to memory
   2. Add 1 to cache (cache contains 2)
   3. Write 2 to memory
   4. Add 2 to cache (cache contains 4)
   5. Add 2 to cache (cache contains 6)
   6. Add 1 to cache (cache contains 7)
   7. Write 7 to memory
   8. Add 7 to cache (cache contains 14)
   9. Add 7 to cache (cache contains 21)
  10. Add 2 to cache (cache contains 23)
There are several other essentially different 10-step programs that result in 23 in cache, but no 9-step programs. (If a program differs just by the order of a sequence of successive additions, it's not considered essentially different.) Note that for all n < 2326, all of the numbers that have an essentially unique minimal program that puts a maximal set of numbers in memory are of the form 2^k, 1+2^k, 3^k, or 1+3^k, except for 5, 809 and 1609:
For n = 809 we need 21 steps: (1) W1; (2) A1 => 2; (3) A1 => 3; (4) W3; (5) A3 => 6; (6) A3 => 9; (7) A1 => 10; (8) W10; (9) A10 => 20; (10) W20; (11) A20 => 40; (12) W40; (13) A40 => 80; (14) W80; (15) A80 => 160; (16) A80 => 240; (17) A3 => 243; (18) W243; (19) A243 => 486; (20) A243 => 729; (21) A80 => 809.
n = 1609 can be computed most efficiently in 23 steps. The contents of memory when 1609 is reached are {1,3,10,20,40,80,160,483}; the precise steps can be inferred from these memory contents.
		

Links

• Glen Whitney, Table of n, a(n) for n = 1..2326 (Terms 1..340 from Robert G. Wilson v)
• Glen Whitney, C program to compute a(n) for small values of a(n)
• Glen Whitney, Somewhat more efficient C program to compute a(n)
• Index to sequences related to the complexity of n

Crossrefs

Cf. A005245, A091333, A172005.

Cf. A003313 (addition chains; similar except read/write are "free").

Programs

Mathematica

PossibleNextStates[{n_, l_}] :=
Join[{#, l} & /@ l,
  If[! MemberQ[l, n], {{n, Sort@Append[l, n]}}, {}], {n + #, l} & /@ l]
states = {{1, {}}}; i = 0; c[1] = 0;
Do[states = Union @@ PossibleNextSteps /@ states; i++;
  If[! IntegerQ[c[#[[1]]]], c[#[[1]]] = i] & /@ states, {14}];
c /@ Range[88]