The membership problem, or is 1001 in $\cal{S}$?

Before discussing the membership problem, the teacher may want to take advantage of this opportunity to introduce another concept from algorithmics, the concept of decision problems. Decision problems are the algorithmic problems that do not produce any ``real" outputs, but only a ``yes" or a ``no". In the world of algorithmic problems there are many well known problems that belong to the category of decision problems. The teacher is advised to point out such algorithmic problems, and to encourage the students to find more problems of this kind.

The problem presented here is a decision problem, as can easily be observed. The answer we are looking for is a ``yes" or ``no". How to produce this one-word answer is a different story and not necessarily a short one. In Engel's book two different algorithms are given, both of which produce a table of a subset of the first $n$ elements of the set $\cal{S}$. We can change these algorithms to produce a table of say, 1200 elements, and then look up the table to see if 1001 is included.

The first algorithm given in Engel's book, $inset$, is a recursive algorithm. It is assumed that the students are familiar with the concept of recursion, and that they have written recursive algorithms before. However, if this is not the case, the teacher has to devote time and effort to teach the problematic topic of recursion. The teacher may not be interested in doing so at this point, and may therefore skip the presentation of this algorithm. This is not a problem and the teacher can proceed to the next algorithm.

The algorithm we present here as a Pascal function, which determines if a given non-negative integer $x$ is in $\cal{S}$, differs only slightly from the one given by Engel. The algorithm is based on the following claim - Claim 3, which is a straightforward result of Claim 2.

Claim 3:
Let $x$ be a non-negative integer, $x \in \cal{S}$ iff
$x=0$ or
$x-1$ can be divided by $2$ and $(x-1) div 2 \in \cal{S}$ or
$x-1$ can be divided by $3$ and $(x-1) div 3 \in \cal{S}$.

function  InS(x: integer): boolean;

var y: integer;

begin

if   $x=0$ then InS:=true

else begin


y:=x-1;

if (y mod 2$<>$0) and (y mod3$<>$0)

then inS:=false

else if y mod 2$<>$0 

then inS:=inS(y div 3)

else if y mod 3$<>$0

then inS:=inS(y div 2)

else inS:=inS(y div 2) or  inS(y div 3)

end

end{InS}

The proof of Claim 3 paves the way to proving the correctness of the algorithm, which the teacher may want to emphasize. It is recommended that the students solve a few membership problems with the aid of the algorithm, either in the laboratory or in class.