cp's OEIS Frontend

SNUSP is a programming language where each command is an individual letter. The four of concern here are +, -, @ and #. + increments the current data value, - decrements it, @ is a "subroutine call" and # is a "return". When an @ is encountered, a record of the location is put on a stack and execution continues. When a # is encountered, if there is a return point on the stack, the execution continues at that a single character beyond that return point. If there is no return point on the stack, execution terminates.

Thus "@@++#" would put the first two "@" return points on the stack, increment data twice, return from the second "@" to the last "+", increment the data once more, return from the first "@" to the first "+", increment the data two more times and finally terminate when it hits the "#" with no return points on the stack. The data is always initialized to zero so this effectively puts 5 into the data. In order to place a particular value into the data, there is a minimal string of these characters. The i-th element of the sequence gives the minimal number of characters (excluding the "#" which is always the last character) to produce an SNUSP program which sets the data to i. The string above is a minimal string to produce 5 and has four characters before the # so the 5th item in the sequence is 4.

Sequence A172005 is the same as this one but disallows the '-' command. Many values have smaller sequences by allowing the -. There are some sequences that can cut up to two characters off by using the -. I don't know if larger savings are possible or if the savings can become arbitrarily large.

SNUSP is a programming language where each command is an individual letter. The four of concern here are +, -, @ and #. + increments the current data value, - decrements it, @ is a "subroutine call" and # is a "return". When an @ is encountered, a record of the location is put on a stack and execution continues. When a # is encountered, if there is a return point on the stack, the execution continues at that a single character beyond that return point. If there is no return point on the stack, execution terminates.

Thus "@@++#" would put the first two "@" return points on the stack, increment data twice, return from the second "@" to the last "+", increment the data once more, return from the first "@" to the first "+", increment the data two more times and finally terminate when it hits the "#" with no return points on the stack. The data is always initialized to zero so this effectively puts 5 into the data. In order to place a particular value into the data, there is a minimal string of these characters. In some cases, allowing the '-' command can shorten this minimal string. This sequence is a list of numbers which require a - in their minimal sequence. All the numbers represented in the above sequence save at most 2 characters by allowing the -. Whether this is a maximum savings and whether the savings can be arbitrarily large is not known (at least not to me).

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

Shortest SNUSP representation of a number using only + and @ is in A172005.

SNUSP is a programming language where each command is an individual letter. The three of concern here are + and @ and #. + increments the current data value, @ is a "subroutine call" and # is a "return". When an @ is encountered, a record of the location is put on a stack and execution continues. When a # is encountered, if there is a return point on the stack, the execution continues at that a single character beyond that return point. If there is no return point on the stack, execution terminates.

Thus "@@++#" would put the first two "@" return points on the stack, increment data twice, return from the second "@" to the last "+", increment the data once more, return from the first "@" to the first "+", increment the data two more times and finally terminate when it hits the "#" with no return points on the stack. The data is always initialized to zero so this effectively puts 5 into the data. In order to place a particular value into the data, there are one or more minimal strings of these characters. The i-th term of the sequence gives the number of minimal SNUSP programs using only these characters. After 2, all sequences end in either +++ or @++, which are equivalent, so all values above a(2) are even.

SNUSP is a programming language where each command is an individual letter. The four of concern here are +, -, @ and #. + increments the current data value, - decrements it, @ is a "subroutine call" and # is a "return". When an @ is encountered, a record of the location is put on a stack and execution continues. When a # is encountered, if there is a return point on the stack, the execution continues at that a single character beyond that return point. If there is no return point on the stack, execution terminates.

Thus "@@++#" would put the first two "@" return points on the stack, increment data twice, return from the second "@" to the last "+", increment the data once more, return from the first "@" to the first "+", increment the data two more times and finally terminate when it hits the "#" with no return points on the stack. The data is always initialized to zero so this effectively puts 5 into the data. In order to place a particular value into the data, there are one or more minimal strings of these characters. The i-th term of the sequence is the number of minimal SNUSP programs using only these characters. After 2, all sequences end in either +++ or @++, which are equivalent, so all values above a(2) are even.