3
$\begingroup$

Let a counting function inc for inputs of N bits be defined as:

inc(b0 | b1 ... | bN) = F0(b0) | F1(b0,b1) ... | FN(b0,b1,...bN)

Where FN is a function from N bits to a bit, and such that the period of inc is 2^N. Notice that, here, we have a special restriction: the nth bit of the output of inc must only depend on bits that come before the n+1th bit of the input. This is obviously the case for the traditional counting function. How many unique inc functions there are for a given N?

Example

For n = 3, there are at least two unique functions:

# Example 0

F(b0 | b1 | b2) 
   = not(b0)
   | xor(b0, b1) 
   | if b2 then and(b0,b1) else or(b0,b1)

Produces the usual counting: 000, 100, 010, 110, 001, 101, 011, 111, 000...

# Example 1

F(b0 | b1 | b2)
    = not b0
    | xnor(b0,b1)
    | if b2 then and(b0,b1) else or(b0,b1)

Produces the sequence: 000, 110, 011, 101, 001, 111, 010, 100, 000...
$\endgroup$
2
  • $\begingroup$ A useful step would be to try counting the number for $n=1$, $n=2$, $n=3$, $n=4$, $n=5$, show those numbers in the question, and try plugging into the OEIS to see if you spot anything useful? $\endgroup$
    – D.W.
    Commented Aug 28, 2018 at 21:42
  • $\begingroup$ @D.W. Ha, amazing idea. Sadly, it seems that the number is simply 2^(N-1). I'm trying to further investigate. $\endgroup$
    – MaiaVictor
    Commented Aug 28, 2018 at 23:47

2 Answers 2

1
$\begingroup$

Suppose that a set of functions $F_0,\ldots,F_{N-1}$ satisfies the constraints, generating the sequence $x_0 = 0^N, x_1, \ldots, x_{2^{N-1}-1}$. When does a function $F_N$ satisfy the constraints?

If $F_N$ works, then it generates a sequence of the form $$ x_0\alpha_0, \ldots, x_{2^N-1}\alpha_{2^N-1}, \\x_0\alpha_{2^N}, \ldots, x_{2^N-1} \alpha_{2^{N+1}-1}. $$ The $\alpha_i$'s are given by the following rules: $\alpha_0 = 0$, and for $0 \leq i \leq 2^N-1$, $$ \alpha_{i+1} = F_N(x_i\alpha_i), \\ \alpha_{2^N+i+1} = F_N(x_i\alpha_{2^N+i}). $$ In order for the period to be $2^{N+1}$, we must have $\alpha_{i+1} \neq \alpha_{2^N+i+1}$. This means that there is a function $G_N\colon \{0,1\}^{N-1} \to \{0,1\}$ such that $$ F_N(x\alpha) = G_N(x) \oplus \alpha. $$ It follows that for $0 \leq i \leq 2^N-1$, we have $$ \alpha_{i+1} = F_N(x_i \alpha_i) = G_N(x_i) \oplus \alpha_i, \\ \alpha_{2^N+i+1} = F_N(x_i \alpha_{2^N+i}) = G_N(x_i) \oplus \alpha_{2^N+i}. $$ In particular, this implies that $$ \alpha_{2^N} = G_N(x_0) \oplus \cdots \oplus G_N(x_{2^N-1}). $$ We must have $\alpha_{2^N} = 1$ in order to have a period of $2^{N+1}$, and this gives one constraint on $G_N$. One can check that there are no other constraints, and so the number of possibilities for $F_N$ is $2^{2^N-1}$. In total, the number of possibilities is $$ 2^{2^0-1 + \cdots + 2^N-1} = 2^{2^{N+1}-N-2}. $$ When $N=0,1,2$, this works out to be $2^0,2^1,2^4$. The corresponding sequences are:

For $N=0$, we have one sequence, $0, 1$.

For $N=1$, we have two sequences, $00, 10, 01, 11$ and $00, 11, 01, 10$.

For $N=2$, we have 16 sequences: $$ 000, 100, 010, 110, 001, 101, 011, 111 \\ 000, 100, 010, 111, 001, 101, 011, 110 \\ 000, 100, 011, 110, 001, 101, 010, 111 \\ 000, 100, 011, 111, 001, 101, 010, 110 \\ 000, 101, 010, 110, 001, 100, 011, 111 \\ 000, 101, 010, 111, 001, 100, 011, 110 \\ 000, 101, 011, 110, 001, 100, 010, 111 \\ 000, 101, 011, 111, 001, 100, 010, 110 \\ 000, 110, 010, 100, 001, 111, 011, 101 \\ 000, 110, 010, 101, 001, 111, 011, 100 \\ 000, 110, 011, 100, 001, 111, 010, 101 \\ 000, 110, 011, 101, 001, 111, 010, 100 \\ 000, 111, 010, 100, 001, 110, 011, 101 \\ 000, 111, 010, 101, 001, 110, 011, 100 \\ 000, 111, 011, 100, 001, 110, 010, 101 \\ 000, 111, 011, 101, 001, 110, 010, 100 $$

$\endgroup$
1
  • $\begingroup$ That makes a lot of sense, thanks for this explanation. Turned out to be much more than I expected. $\endgroup$
    – MaiaVictor
    Commented Aug 29, 2018 at 1:50
0
$\begingroup$

This answer is wrong, but OP asked me not to delete it.

There are $|B|^{|A|}$ different functions from set $A$ to set $B$ (every element in $A$ has $|B|$ possible elements to be mapped to).

All your functions Fi are maps to $B = \{0,1\}$ so we have

  • $2^2$ functions for F0 because its domain is $A = \{0,1\}$ and $|A|=2$
  • $2^{2^2}$ functions for F1 because its domain is $A = \{00,01,10,11\}$ and $|A|=4=2^2$
    $\vdots$
  • $2^{2^{N+1}}$ functions for FN because its domain $A$ is all possible combinations of $N+1$ bits and we have $2^{N+1}$ of those.

(the argumentation is the same for every Fi as the argument for FN, I just wrote it differently at smaller $i$s for clarification)

Because every Fi can be chosen independently, we multiply all the combinations and get $$\prod_{i=0}^N 2^{2^{i+1}} = 2^{\sum_{i=0}^{N} 2^{i+1}} = 2^{2^{N+2}-2}$$ possible functions for inc.

$\endgroup$
3
  • 1
    $\begingroup$ Oh, surely there are 2^(2^(N+1)) unique definitions for FN, but note that incN must have a cycle length of 2^N (i.e., it must be a counting function; a function like inc(a,b,c) = a | b | c would be excluded because it doesn't do anything and thus has a cycle length of 1). That's what complicates the matter a little bit! (Please do not delete this answer though!) $\endgroup$
    – MaiaVictor
    Commented Aug 28, 2018 at 21:37
  • $\begingroup$ This answer is not correct. The questions asks us to count the number of such functions that have a period of $2^n$. This answer doesn't take that restriction into account. $\endgroup$
    – D.W.
    Commented Aug 28, 2018 at 21:41
  • $\begingroup$ Oh, I see. It was a little bit suspicious to me that the solution is this "easy". Hope someone gets it soon. $\endgroup$ Commented Aug 28, 2018 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.