mathematics

Quine Number Problem

I have promised, long ago, that I will devise some math problems. Here is one.

Say that we have a number 8 written in binary (base 2) as 1000.

Now, we have two basic operations: INC and SHL.

INC increases a number by 1, SHL shifts a number left by 1 binary digit. It’s the same as the multiplication by 2.

We will code SHL as 0 and INC as 1. So the sequence 1000 means:

INC A; SHL A; SHL A; SHL A

At the beginning A=0, and it is A=8 (or 1000 in binary) at the end. We want to begin with zero and end up with whatever number is calculated.

The number 8 reproduces itself (in base 2) using those two operations, therefore it’s called a Quine number. 3 (or 11 in binary, or INC A; INC A) – makes 2 out of initial zero. So it’s not a Quine, for 2 not equal 3.

The problem: Which two, if any at all, operations makes any number a Quine number in base 2?

You may take ternary numeral system (base 3) and three basic instructions, such that every number is a Quine. Or base N, with N basic (not necessary different) operations/instructions as well.

(For N=1, for the unary numeral system, the solution is rather trivial. 7 decimal or 0000000 in base 1 – and INC coded as 0 – 7 gives you 7. X gives you X for every natural.)

Is there any nontrivial solution; above this base 1 with the INC operation?

Smaller values of base are better!

Advertisements
Standard

6 thoughts on “Quine Number Problem

  1. > Wait, are we supposed to make up arbitrary operations for higher bases?

    Yes. You can use any well defined function. EXP, LOG, SQRT .. or even LOG(A+1/A). Even something much more complicated.

  2. Olga says:

    Are we to assume that the obvious one doesn’t count?

    Whfg sbe pbzcyrrgarff: Va onfr $n$ gur bcrengbe gung fuvsgf n ahzore bar fgrc gb yrsg naq pbapngragrf gur qvtvg $i$ vf $$f_n_i(x) = n * x + i$$

    Also, that is the first sentence I have written in rot13. Was it readable?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s