8
\$\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\$
  • \$\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 at 8:57
  • 2
    \$\begingroup\$ Do you have any test cases for N>4? \$\endgroup\$ – fireflame241 Jul 9 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 at 21:48
  • \$\begingroup\$ Such an operation can only exist when N is a power of 2. \$\endgroup\$ – att Jul 10 at 0:03
  • \$\begingroup\$ @att Why can it only exist for N a power of 2? \$\endgroup\$ – fireflame241 Jul 10 at 2:24
10
\$\begingroup\$

Python 2, 115 bytes

This assumes that a \$\star\$ exists iff \$N\$ is an integer power of 2, including 1. I don't have a proof for it, but it is evident from the first few cases (and @att noted it in comments).

N=input()
f=lambda p,q:f(f(p,q-1),(p+1)%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]

Try it online

188 bytes without assuming the power-of-2 condition.

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

Try it online! (N from 1 to 10, simulates STDIN)

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. This reveals a bit of a pattern (two 2s, two 4s, four 8s, four (?) 16s, etc.), but this needs confirmation before working into an answer.

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\$ (Rationalization to myself that the proof was necessary: It 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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 106 90 bytes

IntegerQ@Log2@#&&L[NestWhileList[r#0[r][[Mod[#+1,L@#0@r,1]]],#+1,#<0&]&[1-#]]&
L=Length

Try it online! or see a verbose version.

Returns the period if it exists, or False otherwise. Assumes that only integer powers of 2 are solutions, and filters for those accordingly.

Calculates the minimal cycles for rows -1,-2,...,2,1, before taking the length of the cycle for row 1. As each row recomputes the previous row at least twice, runtime balloons quickly, failing to compute for \$N=32\$ within 60s on TIO.

An ungolfed, memoized faster program with a slightly different structure, which computes \$N=2^{17}=131072\$ in ~30s on TIO: Try it online!

Computes rows of \$S:\mathbb Z^-\times\mathbb Z\to\mathbb Z\$, the function defined by:

  1. \$S(a,1)=a+1\$.

  2. \$S(a,S(b,c))=S(S(a,b),S(a,c))\$ if \$S(a,b)\le0\$.

  3. If \$S(a,b)=S(a,c)\$, then \$S(a,b+k)=S(a,c+k)\$ for all \$k\in\mathbb Z\$. *can this be shown with (1) and (2) alone?

    This is consistent with (1) and (2): \$S(a,b+1)=S(S(a,b),S(a,1))=S(S(a,c),S(a,1))=S(a,c+1)\$, which can be extended to positive \$k\$ by induction.

Then \$S(a,b)\bmod N=(a\bmod N)\star(b\bmod N)\$ iff \$N\$ is a consistent modulus for \$\star\$.


\$\star\$ exists for only \$N=2^k\$: WIP.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Is there supposed to be a nonprintable U+F4A1 in the middle of your answer? \$\endgroup\$ – Neil Jul 11 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 at 19:26
  • \$\begingroup\$ Well, its presence seems to completely confuse Firefox 77 for some reason... \$\endgroup\$ – Neil Jul 11 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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