10
\$\begingroup\$

Background

We all know about distributivity, i.e. \$a(b+c) = ab + ac\$. This is a property on 2 different operations, namely addition and multiplication. But indeed, nothing can stop us from studying distributivity of 1 operation. In this challenge, you will be studying a kind of left-distributive operation.

Task

Given a positive integer \$N\$. Consider an operation \$p \star q\$ where \$p, q\in\{0, 1,\dots, N-1\}\$, such that \$ p \star 1 \equiv p + 1 \pmod N\$ and \$p \star (q \star r) = (p \star q) \star (p \star r)\$. In essence, you are making an \$N\times N\$ table. For instance, if \$N = 4\$, a possible \$\star\$ is:

⋆ q 0 1 2 3
p-+---------
0 | 0 1 2 3
1 | 0 2 0 2 ←
2 | 0 3 0 3
3 | 0 0 0 0
      ↑

Note that the marked column satisfies \$ p \star 1 \equiv p + 1 \pmod N\$. In this challenge, we are interested in the marked row. It seems to be periodic, and the challenge is to find its period. The smallest positive period for a sequence \$a_0, \dots , a_{N-1}\$, is defined to be the smallest positive integer \$k\$, such that \$k\$ divides \$N\$, and \$a_i = a_{i + k}\$, for \$i=0..(N-k-1)\$.

However, there may be many possible \$\star\$'s for a given \$N\$, or there may be none. So you need to compute the (smallest positive) periods for all of them.

Task: given a positive integer N, compute all the possible smallest positive periods of 1 ⋆ q. This is .

Details and clarifications

In the case N = 4, the given table turns out to be the only possible one, so you should output a list (or a set, etc.) consisting only of the number 2. But for N = 3, no operation satisfies all the requirements, so you can output an empty list, or 0, or some falsy value.

The smallest positive period will always be between 1 and \$N\$, if the sequence 1 ⋆ q (0 <= q < N) doesn't repeat at all, it is of period \$N\$.

N will range from 1 to \$2^{32}-1\$. So it is almost . But note that a formula or recurrence relation of this is unknown.

Test cases

In : N = 1
Out: [1]

In : N = 2
Out: [1]

In : N = 3
Out: []

In : N = 4
Out: [2]
\$\endgroup\$
7
  • \$\begingroup\$ @Arnauld Yeah, I originally planned to require the output each period seperated by spaces for each N=1..1024, seperated by newlines. Later I decided to take input, and enlarge the upper limit. Forgot to change the tag. \$\endgroup\$
    – Trebor
    Jul 9, 2020 at 8:57
  • 3
    \$\begingroup\$ Do you have any test cases for N>4? \$\endgroup\$ Jul 9, 2020 at 17:32
  • 1
    \$\begingroup\$ Shouldn't the output for n=2 be [1]? The only possible operation has the table 0 1 \\ 0 0, and 0 0 has period 1. \$\endgroup\$
    – att
    Jul 9, 2020 at 21:48
  • \$\begingroup\$ Such an operation can only exist when N is a power of 2. \$\endgroup\$
    – att
    Jul 10, 2020 at 0:03
  • \$\begingroup\$ @att Why can it only exist for N a power of 2? \$\endgroup\$ Jul 10, 2020 at 2:24

2 Answers 2

11
\$\begingroup\$

Python 2, 113 bytes

N=input()
f=lambda p,q:f(f(p,q-1),-~p%N)if p*q else q
print([i for i in range(1,N)if N%i+f(1,i)<1]+[N])[:N&N-1<1]

-2 bytes thanks to @Jakque

Try it online!

The short, recursive approach is slow since it repeats computation of many entries, so I've made an iterative, memoized approach which is much faster (quadratic in N) and can compute up to N=4096 within 60 seconds on TIO.

How it Works

The algorithm assumes that \$\star\$ is unique, if it exists (proof below). It uses recursion, setting

\$p\star q=\begin{cases} q, &p=0 \\ p+1 \mod n, &q=1 \\ (p \star (q-1 \mod n))\star (p+1 \mod n), &\text{otherwise} \end{cases}\$

The first case (\$p=0\$) is Lemma 1 in the uniqueness proof: \$0\star q=q\$.

The second case (\$q=1\$) is given.

The third case has a simple proof despite its complex self (assuming addition and subtraction are mod \$N\$:

\begin{align*} &p \star q\\ =&p \star ((q-1)+1) \\ =&p \star ((q-1)\star 1) \\ =&(p \star (q-1))\star(p\star 1) \\ =&(p \star (q-1))\star(p+1) \end{align*}

This is enough to determine the unique \$\star\$ (The proof shows that the third case will not recurse indefinitely).

The period is the minimum \$i\$ such that \$1\star (i+1) = 1\star 1 = 2\$. If this \$i\$ doesn't divide \$N\$, then it is not a period.

Ungolfed code:

# f(p,q,N) = p⋆q
def f(p,q,N):
    if p==0:
        return q
    if q==1:
        return (p+1)%N
    return f(f(p,(q-1)%N,N),(p+1)%N, N)

def period(N):
    if any(f(p,f(q,r,N),N) != f(f(p,q,N),f(p,r,N),N) for p in range(N) for q in range(N) for r in range(N)):
        # The f does not exist
        return []
    for i in range(1, N):
        # period is i if f(1,i+1)=f(1,1)=2
        if f(1,i+1,N) == 2:
            # might not be divisible, in which case it is not the period
            if N%i:
                return [N]
            return [i]

This could be sped up immensely by memoization utilizing \$ a \star 2 = a \star (1 \star 1) = (a\star 1)\star (a\star 1) = (a+1)\star(a+1) \$ and \$1 \star a = (1\star (a-1))\star 2\$.

Proof of Uniqueness of \$\star\$

For this section, we assume all addition/subtraction is mod \$N\$.

Lemma 1: For all \$a\$, \$0 \star a = a\$

Proof: Induction

Base case: \$a=1\$. Given since \$0\star 1=1\$.

Step: Assume this lemma holds for \$a=k\$. Then \begin{align*} &0 \star (k + 1)\\ =& 0\star (k\star 1) \\ =& (0\star k)\star (0\star 1) \\ =& k \star 1 \\ =& k+1, \end{align*} so this holds for \$a=k+1\$. Since this addition is mod \$N\$, this will "wrap around" back to \$0\$, so it applies for \$a=0\$ too, not just \$a\geq 1\$

Theorem: If an operation \$\star\$ is valid for a given \$N\$, then it the unique \$\star\$ that is valid for that \$N\$.

Proof: We use strong induction to show that, for all \$0\leq a,b\leq N-1\$, \$a\star b\$ is uniquely determined by \$N\$. In addition, for each \$a\$ and \$b\$ in the same set, either (1) \$a\star b=0\$ or (2) \$a<a\star b<N\$

  1. Base case: \$a\star b\$ is uniquely determined and equal to \$0\$ for \$a=N-1\$ and for all \$b\$.

    We prove this base case with induction too.

    1. Base case: \$b=1\$. We are given \$a\star 1=a+1\$, so \$(N-1)\star 1=0\$, uniquely determined.
    2. Step: Given \$(N-1)\star b=0\$ for \$b=k\$, then \begin{align*} &(N-1)\star (b+1)\\ =&(N-1)\star (b\star 1)\\ =&((N-1)\star b)\star((N-1)\star 1)\\ =&0\star0 \\ =&0, \end{align*} where we use Lemma 1 to show \$0\star 0=0\$, so \$(N-1)\star b\$ is uniquely determiend to be \$0\$.
  2. Assume \$a\star b\$ is uniquely determined and either (1) or (2) hold for all \$k<a\leq N-1\$ and for all \$b\$. Then for \$a=k\$, we will show \$a\star b\$ is uniquely determined and either (1) or (2) hold for all \$b\$, again with induction.

    1. Base case: \$k\star b\$ is uniquely determined and either (1) or (2) hold for \$b=1\$. This is trivial since \$k\star 1=k+1>k\$, so \$k\star 1\$ is unique and (2) holds

    2. Step: Assume \$k\star b\$ is uniquely determined and either (1) or (2) hold for \$b=j\$. Then: \begin{align*} &k\star (b+1)\\ =&k\star (b\star 1)\\ =&(k\star b)\star(k\star 1)\\ =&(k\star b)\star(k+1) \end{align*} If (1) holds, then \$k\star b=0\$, so \$k\star(b+1)=k+1>k\$ by Lemma 1. Thus \$k\star(b+1)\$ is uniquely determined and satisfies (2).

      If (2) holds, then \$k<k\star b\leq N-1\$,so by the outer inductive assumption, \$k\star(b+1)=(k\star b)\star (k+1)\$ is uniquely determined and either (1) or (2) holds for it.

      In either case, \$k\star(b+1)\$ is uniquely determined and either (1) or (2) hold for it, completing the inductive step.

\$\endgroup\$
2
  • \$\begingroup\$ (p+1)%n => -~p%n for -2 bytes \$\endgroup\$
    – Jakque
    Jun 25, 2021 at 7:55
  • \$\begingroup\$ @Jakque updated \$\endgroup\$ Jun 25, 2021 at 8:41
3
\$\begingroup\$

Wolfram Language (Mathematica), 106 90 42 bytes

AtomQ@#&&2^Tr@UnitStep[#-{2,3,5,9}]&@*Log2

Try it online!

Returns the period if it exists, or False otherwise.

Laver Tables exist iff \$N\$ is a power of 2. The sequence of periods is A098820 on the OEIS.

Assuming the l3 rank-into-rank cardinal exists, it's been shown that the first \$N\$ for which the period is greater than 16 is at least \$2^{A(9,A(8,A(8,255)))}\ggg2^{31}-1\$, where \$A\$ is the Ackermann function. John Baez has a relatively accessible layman's explanation here.

\$\endgroup\$
3
  • \$\begingroup\$ Is there supposed to be a nonprintable U+F4A1 in the middle of your answer? \$\endgroup\$
    – Neil
    Jul 11, 2020 at 14:01
  • \$\begingroup\$ @Neil yes: Mathematica uses it for \[Function]; it's used here to enable recursion on the row-computing function with #0 (this is the function called on1-#). The function on r computes (a*(b+1))=((a*b)*(a+1)) from r=a*b. \$\endgroup\$
    – att
    Jul 11, 2020 at 19:26
  • \$\begingroup\$ Well, its presence seems to completely confuse Firefox 77 for some reason... \$\endgroup\$
    – Neil
    Jul 11, 2020 at 20:03

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.