11
\$\begingroup\$

Given an initial \$n\$-tuple \$t_0=(t_{0,1},...,t_{0,n})\$, we can obtain its corresponding Ducci sequence \$\{t_0, t_1, ...\}\$ by the recurrence \$\displaystyle t_{i+1}=\left(\left|t_{i,1}-t_{i,2}\right|,\left|t_{i,2}-t_{i,3}\right|,...\left|t_{i,n}-t_{i,1}\right|\right)\$.

That is, to obtain the next term of the sequence, we take the absolute differences of successive terms of \$t_i\$, treating it as cyclic; by convention, the first element corresponds to the difference of the first two elements of \$t_i\$.

When the initial tuple \$t_0\$ consists of integers, such sequences are always eventually periodic. For example,
\$(3,1,4)\to(2,3,1)\to(1,2,1)\to\underline{(1,1,0)}\to(0,1,1)\to(1,0,1)\to\underline{(1,1,0)}\$
has a cycle of length 3.

Task

Given a length \$n\$, compute the maximum cycle length among all Ducci sequences on tuples of \$n\$ integers.

This is A038553 on OEIS.

Test cases

1       1
2       1
3       3
4       1
5       15
6       6
7       7
8       1
9       63
10      30
11      341
12      12
13      819
14      14
15      15
16      1
17      255
18      126
19      9709
20      60
21      63
22      682
23      2047
24      24
25      25575
37      3233097
51      255
\$\endgroup\$

6 Answers 6

8
\$\begingroup\$

JavaScript (ES6), 62 bytes

n=>eval(`for(m=1,o=j=[];!o[m^=m/2^m%2<<n-1];o[m]=j++);j-o[m]`)

Try it online!


54 bytes

A recursive version, failing earlier.

f=(n,m=1,j=o=[])=>++j-o[m]||f(n,m^m/2^m%2<<n-1,o[m]=j)

Try it online!


65 bytes (ES11)

A BigInt version. This one can process all test cases on TIO.

n=>eval(`for(m=1n,o=j=[];!o[m^=m/2n^m%2n<<~-n];o[m]=j++);j-o[m]`)

Try it online!


How?

The main observation here is that a necessary condition for a cycle to appear is that the only remaining elements in the tuple are \$0\$ and some \$v>0\$. And because we're only interested in the maximum cycle length, it doesn't matter what happens before we reach this state.

When all elements in the tuple are in \$\{0,v\}\$, we have:

$$\left|t_{i,j}-t_{i,j+1}\right| = t_{i,j} \operatorname{XOR} t_{i,j+1}$$

We can arbitrarily choose \$v=1\$ and turn the \$n\$-tuple representation into a bit mask \$m\$. This allows us to apply all updates at once by doing the following 'XOR rotation':

m ^= m / 2 ^ m % 2 << n - 1
\$\endgroup\$
6
  • 4
    \$\begingroup\$ This happens because \$f(s \operatorname{XOR} t) = f(s) \operatorname{XOR} f(t)\$, so if both \$s\$ and \$t\$ return to their original state after \$k\$ iterations, so does \$s \operatorname{XOR} t\$ \$\endgroup\$
    – Nitrodon
    Commented Jul 11, 2023 at 17:11
  • 1
    \$\begingroup\$ @Arnauld Indeed all cycles contain only 2 elements \$\{0,v\}\$, one proof of this can be found here \$\endgroup\$ Commented Jul 11, 2023 at 21:05
  • 1
    \$\begingroup\$ Thanks Nitrodon and CursorCoercer for your feedback. Just to clarify a little, my code is not testing all binary patterns of length \$n\$. It just starts with \$m=1\$ and stops when a cycle is found. So my main concern is whether this method always finds the maximum length cycle. \$\endgroup\$
    – Arnauld
    Commented Jul 11, 2023 at 21:27
  • 2
    \$\begingroup\$ @Arnauld Starting with \$m=1\$ does indeed work. As Nitrodon points out, the update step distributes over XOR, and it furthermore commutes with shifts. Together these imply that it commutes with XOR (carryless) multiplication by any value, where we wrap around positions in the circle. So, \$f(p \cdot q) \equiv p \cdot f(q)\$ and so \$f^k(p \cdot q) \equiv p \cdot f^k(q)\$. This implies if that if we reach a \$k\$-step cycle from 1, we also reach a cycle that's \$k\$ steps (or fewer) from any multiple of \$1\$, which is anything. \$\endgroup\$
    – xnor
    Commented Jul 11, 2023 at 22:27
  • 1
    \$\begingroup\$ Something that may be useful is a starting value that is guaranteed to lie on this cycle, so that we can just check that we've returned to it: \$2^{2^n} \thinspace \mathrm{XOR} \thinspace1\$, where we reduce the exponent \$2^n\$ modulo \$n\$ so the starting value fits in \$n\$ bits. \$\endgroup\$
    – xnor
    Commented Jul 11, 2023 at 22:32
3
\$\begingroup\$

Jelly, 11 10 8 bytes

Ṭṙ1ạƊÐḶL

Try it online!

-2 thanks to Bubbler

Just another port of Arnauld's approach. Now very straightforward, but check the edit history for a good laugh.

Ṭ           Create a list with a 1 at index n and 0s elsewhere.
    ƊÐḶ     Repeat while unique, collecting only the cycle:
 ṙ1         rotate once
   ạ        and take element-wise absolute differences with unrotated elements.
       L    How long is the cycle?

Jelly, 11 bytes

&NṬnṬṙ1nƊƬL

Try it online!

It's longer, but worth showing off how to apparently guarantee starting within a cycle. Namely, when starting with the single-1 tuple as in the approach above, the state that begins the cycle appears to always be the XOR of two single-1 states, rotated relative to each other by the largest power of 2 that divides the length.

&N             Bitwise AND n with its two's complement.
&N             This gives the largest power of 2 which divides it.
  Ṭ            Create a list with a 1 at that index and 0s elsewhere.
    Ṭ          Create a list with a 1 at index n and 0s elsewhere.
   n           For each element, are they not equal?
        ƊƬ     Repeat while unique:
       n       elementwise inequality with
     ṙ1        the current tuple rotated once.
          L    How many distinct tuples did this produce?
\$\endgroup\$
2
\$\begingroup\$

Python3, 145 bytes:

def f(n):
 m=[];v=[I==0for I in range(n)]
 while v not in m:m+=[v];v=[abs(v[I]-v[I+1if I+1<n else 0])for I in range(n)]
 return len(m)-m.index(v)

Times out on \$n = 37\$.

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 138 bytes \$\endgroup\$
    – The Thonnu
    Commented Jul 11, 2023 at 15:34
  • \$\begingroup\$ @TheThonnu v[-~I%n]? \$\endgroup\$
    – Neil
    Commented Jul 11, 2023 at 21:15
2
\$\begingroup\$

Pyth, 17 bytes

LaVb.<b1l.uyNuyGU

Try it online!

Relies on the same as yet unproven assumption that @Arnauld makes, being that the maximum cycle can always be found by starting with [1, 0, 0, 0, ...].

Explanation

LaVb.<b1l.uyNuyGUQ    # implicitly add Q
                      # implicitly assign Q = eval(input())
L                     # define y(b)
 aV                   #   absolute difference, vectorized of
   b.<b1              #   b and b shifted one left (cyclically)
                UQ    # list(range(Q))
             uyG      # repeatedly apply y until a result that has been seen occurs
         .uyN         # repeatedly apply y until a result that has been seen occurs and accumulate all intermediate results
        l             # take the length of this list
\$\endgroup\$
1
\$\begingroup\$

Python 2, 58 bytes

f=lambda n,k=1:~-2**2**n*k%~-2**n<1or-~f(n,k^1^k*2%~-2**n)

Try it online!

A recursive function, outputting True for 1. This will fail on large outputs due to exceeding the maximum recursion depth, which is around 1000 by default. Here's a longer iterative version, though it times out for larger inputs thanks to its double-decker power \$2^{2^n}\$.

62 bytes

N=2**input()
k=i=1
while~-2**N*k%~-N:k^=1^k*2%~-N;i+=1
print i

Try it online!

Here's the above but more optimized for speed.

70 bytes

n=input()
N=2**n
k=i=1
while~-2**(N%n)*k%~-N:k^=1^k*2%~-N;i+=1
print i

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 33 bytes

≔EN∧ι¹θW¬№υθ«⊞υθ≔Eθ⁼κ§θ⊕λθ»I⊕⌕⮌υθ

Try it online! Link is to verbose version of code. Explanation: Port of @Ajax1234's Python answer, but with inverted logic.

≔EN∧ι¹θ

Start with an array of length n whose first entry is 0 and remaining entries are 1.

W¬№υθ«

Repeat until a cycle is detected.

⊞υθ

Save the current state.

≔Eθ⁼κ§θ⊕λθ

Update the state by comparing each value to the next.

»I⊕⌕⮌υθ

Output the length of the cycle.

A more efficient version using a dictionary and bit twiddling weighs in at 48 bytes, but can handle n=29 on ATO:

≔⊖X²Nθ≔¹η≔⦃⦄ζW¬§ζ竧≔ζηLζ≔﹪⊗ηθε≔⁻|ηε&ηεη»I⁻Lζ§ζη

Attempt This Online! Link is to verbose version of code.

\$\endgroup\$

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.