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!

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?

• Olga says:

Thank you!

• Try to solve the Geometric problem. It’s devious.

3. > va onfr o (jurer o vf ng yrnfg gjb), qvtvg q ercerfragf gur bcrengvba “zhygvcyl ol q naq nqq o”

It doesn’t work.