This is done in a very similar technique to that used in array look-up:
substitute each single cell with *width* cells. Now, create two
vectors, one where there is a running counter over the *width* elements,
the other that has repetitions of b[i]. Equality will happen only in the
b[i]'th element. This will transform each cell in the original vector to a
vector of size *width*, where all cells are zero except the b[i]'th
element, that equals one. Now, change the width of the cells to be 1. The
result is the desired vector.

Below is a step-by-step example using a vector b=[1,4,2] encoded with
*width*=5:

b[i] | [1,4,2] |

element-repeat b[i] | [1,1,1,1,1,4,4,4,4,4,2,2,2,2,2] |

repeated counter | [0,1,2,3,4,0,1,2,3,4,0,1,2,3,4] |

equality? | [0,1,0,0,0,0,0,0,0,1,0,0,1,0,0] |

This solution not only looks like array look-up, it can actually be
implemented as such. The function "1<<a[i]" can be described as a
look-up into the table [1<<0, 1<<1, 1<<2, ... ,
1<<(*width*-1)]
(with potentially zeros appended at the end). This table is encoded by the
integer Σ_{i=0}^{width-1}
2^{i}2^{i*width}, which equals
Σ_{i=0}^{width-1}
2^{i*(width+1)}, which is simply the all-ones vector
of length *width* and width *width*+1.

Also, note that x>>y equals (x<<z)>>(z+y) for any z. What
we do, therefore, is to first calculate the left-shift by *width*-b[i] of
the array elements, then right-shift all by *width*.

This assumes that all b[i] are smaller than or equal to *width*. If this
isn't true, any shift right that is by *width* or larger will always yield the
same result (zero), so we can simply left-shift by min(b[i],*width*).

Now, consider the *X*^{size} coefficient of this result.
It equals the sum of all s[*i*]*t[*size*-*i*]. All we need to
do is to create *S* and *T* such that
s[*i*]=a[*i*]*2^{i*width} and
t[*i*]=b[*size*-*i*], and then isolate this element, to reach the
desired result. Both s[*i*] and t[*i*] are vectors easily created
by width-change/folding operations.

We will utilize the parallelization properties of the computational model. Consider that the integer division answer can only be between 0 and a[i]. Let us first find the maximum of all a[i] (not a problem, as we already know how to perform an entire sort in O(1).) Next, let us create a counter running from 0 to max(a[i]), aligning a copy of each of the original a[i] and b[i] against each of the values of this counter. This is done by repeating either copies of the entire array or of each element inside it, both being functions we have shown to be tractable in O(1).

The 0 through max(a[i]) counter will serve as a series of "guesses" regarding
the division answer. We will check whether a guess is correct by use of the
inequality *guess**b[i]≤a[i]<(*guess*+1)*b[i]. Once the
positions of the correct guesses are found, we mask out everything else and
fold the results into the correct positions in the output vector.

**Note:** This month's riddle allows the convenience assumption
that all inputs are positive and that outputs do not cause overflows. Would
the question have become more difficult if these assumptions had been removed?
The answer is no, though, of course, some special-case handling would have had
to be inserted.
Consider, for example, the solution for division. Internally, the solution for
division uses multiplication. However, unlike in the answer to 1(c), the
internal multiplication used here cannot assume lack of overflows or positive
inputs. This means that in order to perform this internal multiplication we
need to have a generic solution to multiplication without mitigating
assumptions.
As a result, some allowances are made. In particular, all vectors have their
widths doubled prior to be sent to be multiplied. This is because the width
needed in order to store a multiplication result cannot be larger than the
sum of the widths of the operands.

Such logic works in every part and sub-part of this month's riddle. It is
always possible to find a suitable width for the output, even if such a
width were to be not given explicitly.

We leave to the reader the question of how to augment the solutions above to be able to handle vectors carrying values that are zero/negative.

So, we don't really need to answer the question for *any* vector, but
rather only for one specific vector, namely [0, 1, 2, ..., *n*].
Differently worded, we are considering the function

*f*(*n*)=Σ_{i=0}^{n}
*i*!2^{width*i}

and are asking whether this function has a closed form formula, for
sufficiently large values of *width*. (A closed form formula is a finite
combination of basic functions. Given that our atomic functions are to be
considered "basic", a "closed form formula" and an "O(1) calculation" both
mean exactly the same thing.)

The surprising answer is that not only is this possible, but that **every
function that is known to be calculable by a specific computer has a closed form
representation**, or, alternatively worded, **all functions that
can be calculated by any specific computer can be calculated in the described
computational model in O(1)**.

The full proof of this claim is given below in the section
How to Solve the Halting Problem in O(1). Before going to
show this general result, however, let's solve the specific case of
the factorial calculation. This is done by use of a method very similar to
that of the solution to division. In division, we had a finite number of
guesses for the correct solution. All we had to do is to parallelize the
test that checks which of the guesses is the correct one. Here, we will do the
same, but instead of just guessing the final *n*! answer, we will guess
the entire value of *f*(*n*). This value, too, has only a finite
number of possibilities, because it is known to be representable by only
*width**(*n*+1) bits. All we have to do is to produce a vector
including all such numbers (this is simply a counter going from 0 to
2^{width*(n+1)}.

To complete the solution we need to show that we
can check, in O(1), whether a guess is correct. This is easy to do, as
*f*(*n*) is the only vector of length *n*+1 to satisfy the
induction assumptions

*f*(0)=1

For all 0<*x*≤*n*,
*f*(*x*)=*f*(*x*-1)**x*

The former can be checked in O(1) easily (and, in fact, we can even go so far as to only generate guesses that have this property). The latter condition can be worded for the entire vector together as

f(n) element-wise multiplied by (counter(n+1)>>width) = f(n) >> width

To exemplify, if *n*=5:

f(n) | [1, 1, 2, 6, 24, 120] |

counter(n+1) | [0, 1, 2, 3, 4, 5] |

counter(n+1)>>width | [1, 2, 3, 4, 5] |

multiplication | [1*1, 1*2, 2*3, 6*4, 24*5] |

= f(n) >> width | [1, 2, 6, 24, 120] |

We leave the reader with the follow-up riddle of how to solve the same question, but using an algorithm that requires an amount of memory that is no more than exponential in the length of the output.

This may sound like a magical solution to the halting problem, but there's one
small problem with it: recall the note at the end of part 1. It indicated that
for all questions asked in both parts of this month's riddle it is possible to
know in advance what a good *width* parameter is going to be. This is not
true for Turing machine simulations.

So, the solution above *is* an O(1) solution to the halting problem, but
not to the halting problem of generic Turing machines but rather to the much
simpler case of Turing machines that use a *bounded length tape*
(as well as for non-deterministic Turing machines that use a bounded length
tape). These are computationally equivalent to actual computers, where the
bounded
length of the tape acts like the bounded memory/hard-disk of the computer. They
are also equivalent to finite state machines (or to non-deterministic finite
state machines).

As the total number of possible states for such a machine is known, it's possible to know in advance how many steps one needs to simulate before one is guaranteed to either reach a halting state or to get stuck in an infinite loop. The fact that for Turing machines with bounded length tape the halting problem can be solved is well known, but this month's riddle innovates over this fact by adding that the entire calculation needed for this can be performed in O(1) in the described computational model. Alternatively worded, the calculation has a closed form formula.

Furthermore, not only do all functions that can be calculated using any
specific computer
have closed-form formulae, but also, because anything calculated by any specific
computer
can be computed by a *universal* Turing machine with bounded length
tape, all functions that can be calculated using any computer can actually be
computed using *the same* closed form formula, with the difference only
being the input parameters used. (The formula will need, at its input,
information equivalent to the size of the tape and its initial contents. The
former is equivalent to knowing the memory capabilities of the computer and the
latter equivalent to knowing the function being calculated.)

The discussion above may have left the reader with the impression that
everything can be tackled by our model in O(1), but this is not the case.
What *can't* be calculated in O(1) in this model? One easy example is
functions
that are just too large. Consider a state of our computational model where all
stored integers are smaller (in absolute value) than some *n*_{0}.
In the next computational step, for *n*_{0}≠0, the
largest value that any of the integers can have is
*n*_{1}=*n*_{0}<<*n*_{0}.
Let us define a corresponding *n*_{k} sequence, where each
*n*_{k} is calculated as
*n*_{k-1}<<*n*_{k-1}.
The value *n*_{k} cannot be calculated in less than
*k* steps, meaning O(*k*) time, not O(1).

However, all we need to do to circumvent this is to add to the input a number
that is known to be larger than the final result (and, more generally, a number
known to be larger than any intermediate result required in the process of
calculation). So, computing
*A*(*n*,*n*) from *n* is not possible in this model in O(1)
(where *A* is the Ackermann function, a function that rises much more
rapidly than
*n*_{k}). However, supposing that in some untold way we
happen to obtain a number, *M*, that is known to satisfy the rather
common property
*M*>*A*(*n*,*n*) -- it doesn't need to satisfy any other
requirement! -- then suddenly calculating *A*(*n*,*n*) as a
function of both *n* and *M* is something that can be accomplished
in the described computational model in O(1). All we needed to do is to add
to the input a number, *M*, that satisfies a property that, mathematically
speaking, is satisfied by almost every natural in the world.

One last word, before we leave this computational model entirely. Clearly, now
that we're solving halting problems in O(1), this computational model has
ceased to be an interesting computational model to ask complexity questions
about. Nevertheless, in future "Using your Head is Permitted" questions where
we will return to the subject of complexity, we will, once again, need a
computational model with specific, explicitly mentioned assumptions, to work on.
In all such future cases, unless explicitly stated otherwise, we will be working
with a somewhat more tame computational model, which I call "The Usual
Complexity Assumptions", described in full
here. You will note that this model still
includes O(1) addition, subtraction and bit shifts, so it's still possible to
sort in it *n* integers in O(*n*), but such small quirks aside it
behaves more or less as you'd expect.

I'm afraid I don't have an equivalently mathematically-neat formulation for what I mean in questions where I will ask for a "closed form solution", but readers should use their best judgment on this, and if your closed form solution is more than, say, two hundred symbols long, it probably isn't the closed form solution I had in mind when I wrote the question.

Lastly, but perhaps most importantly: I initially neglected to provide full
credit for this riddle. I will correct this omission now. This riddle came to
me following a conversation with my good friend Shachar Shemesh, during which
he pointed out to me the casualness in which we use terms like
O(*n*^{2})-time when we really mean
O(*n*^{2}) comparisons, where in truth the two mean different
things. The same conversation yielded the December and the January
riddles as well. Thanks Shachar!