cp's OEIS Frontend

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

%I A293771 #43 Oct 25 2021 11:00:15
%S A293771 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,
%T A293771 11,10,11,11,11,10,11,11,11,11,12,11,12,12,11,12,12,11,12,12,12,12,13,
%U A293771 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
%N A293771 Minimum number of steps needed to compute n using a machine that can read, write and add starting with the number 1.
%C A293771 The machine has a cache which holds 1 integer and a memory which holds a list of integers.
%C A293771 The machine starts with a number 1 in cache and empty memory.
%C A293771 At every step, the machine can do one of three things:
%C A293771   (1) write the number from cache to a new position in memory;
%C A293771   (2) read any number from memory and put it in cache;
%C A293771   (3) add any number from memory to the number in cache.
%C A293771 a(n) is the minimum number of steps needed to get the number n in cache.
%C A293771 Conjecture: reading from memory (operation 2) is never needed to get to a number in the minimal number of steps.
%C A293771 Additional conjectures and comments by _Glen Whitney_, Oct 12 2021: (Start)
%C A293771 Conjecture II: For each n, there is a minimal-length program for n that stores numbers in memory in increasing order.
%C A293771 Conjecture III: For each n, there is a minimal-length program such that the difference between successive numbers stored in memory is strictly increasing.
%C A293771 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)
%C A293771 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
%H A293771 Glen Whitney, <a href="/A293771/b293771.txt">Table of n, a(n) for n = 1..2326</a> (Terms 1..340 from Robert G. Wilson v)
%H A293771 Glen Whitney, <a href="/A293771/a293771.c.txt">C program to compute a(n) for small values of a(n)</a>
%H A293771 Glen Whitney, <a href="/A293771/a293771_1.c.txt">Somewhat more efficient C program to compute a(n)</a>
%H A293771 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A293771 For n = 23 we need 10 steps to get 23 in cache:
%e A293771    1. Write 1 to memory
%e A293771    2. Add 1 to cache (cache contains 2)
%e A293771    3. Write 2 to memory
%e A293771    4. Add 2 to cache (cache contains 4)
%e A293771    5. Add 2 to cache (cache contains 6)
%e A293771    6. Add 1 to cache (cache contains 7)
%e A293771    7. Write 7 to memory
%e A293771    8. Add 7 to cache (cache contains 14)
%e A293771    9. Add 7 to cache (cache contains 21)
%e A293771   10. Add 2 to cache (cache contains 23)
%e A293771 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:
%e A293771 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.
%e A293771 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.
%t A293771 PossibleNextStates[{n_, l_}] :=
%t A293771 Join[{#, l} & /@ l,
%t A293771   If[! MemberQ[l, n], {{n, Sort@Append[l, n]}}, {}], {n + #, l} & /@ l]
%t A293771 states = {{1, {}}}; i = 0; c[1] = 0;
%t A293771 Do[states = Union @@ PossibleNextSteps /@ states; i++;
%t A293771   If[! IntegerQ[c[#[[1]]]], c[#[[1]]] = i] & /@ states, {14}];
%t A293771 c /@ Range[88]
%Y A293771 Cf. A005245, A091333, A172005.
%Y A293771 Cf. A003313 (addition chains; similar except read/write are "free").
%K A293771 nonn
%O A293771 1,2
%A A293771 _Floris P. van Doorn_, Oct 15 2017