12
\$\begingroup\$

This is the cops' thread. See the robbers' thread here.

In this cops and robbers challenge, the cops will be tasked with writing an algorithm that computes some function of their choice, while the robbers will try to come up with their algorithm. The catch is, the 'algorithm' must be a single closed-form mathematical expression. Remarkably, a function that determines whether a number is prime has been shown to be possible using only Python operators.

Cops

This is the cops' thread. To compete, first choose any infinite OEIS sequence (e.g. A000027). Then, write a single closed-form expression that takes an integer n, and provably computes the nth term of this sequence. You only need to handle n for which the sequence is defined.

In addition, pay attention to the offset of your chosen OEIS sequence. If the offset is 0, the first term should be evaluated at n=0. If the offset is 1, it should be evaluated at n=1.

The specification for the closed-form expression is as such:

  • The expression must consist of the following arithmetic/bitwise operators: **, %, *, /, +, -, <<, >>, &, ^, | (note that / represents floor division). Unary negation -, bitwise negation ~, and parentheses () are also allowed.
  • The expression may also contain n, as well as any positive or negative integer literals. Only decimal (base 10) literals are permitted.
  • To avoid ambiguity, the behavior of the expression will explicitly be defined as its result when evaluated as Python 2 code. Take extra note of how Python handles / and %, especially when used with negative numbers.
  • a**b may result in a floating-point number, if b is negative. Your expression must not have this occur.

Once you have chosen an OEIS sequence with an accompanying expression, submit an answer containing the OEIS sequence, and the number of bytes in your expression. It is also recommended to include a brief description of the OEIS sequence itself. Don't reveal your actual expression, as this is what the robbers will try to crack!

The robbers will have one week to crack your submission by trying to figure out your expression. Their expression must be at most twice the length of your expression to be considered a crack. This is to ensure that the robber can't crack your submission with an overly long expression.

Additional Information

  • Optionally, you may choose to disallow a subset of the allowed operators. If you do so, mention the restricted set in the body of your submission. Both your expression and the robber's expression must then adhere to this restriction.

  • Make sure to specify the offset if you use a different one than on the OEIS.

  • If your solution has not been cracked and you find a shorter solution after posting, you may update your byte count accordingly.

Scoring

If your submission is not cracked within one week of its initial post, you can mark it as safe and reveal your solution. After this point, it can no longer be cracked.

Your score is the length of your expression in bytes, with a lower score being better.

Example Submission

A000225, 6 bytes

a(n) = 2^n - 1. Sometimes called the Mersenne numbers.

Solution (keep this hidden until you are cracked or safe!):

2**n-1
\$\endgroup\$
15
  • \$\begingroup\$ Is 0**n a valid expression (which takes \$1\$ for \$n=0\$ and \$0\$ otherwise)? \$\endgroup\$ Aug 12, 2023 at 8:08
  • 1
    \$\begingroup\$ I think this challenge would've been better if you could use variables, because otherwise the equations blow up in size due to the need to use values in multiple places. Perhaps you could allow new cop submissions to decide whether to allow variables? \$\endgroup\$ Aug 12, 2023 at 9:43
  • 1
    \$\begingroup\$ @CommandMaster This is ELEMENTARY, weaker than PR but still strong enough \$\endgroup\$
    – l4m2
    Aug 12, 2023 at 11:37
  • 1
    \$\begingroup\$ @CommandMaster Yes there's paper about it \$\endgroup\$
    – l4m2
    Aug 12, 2023 at 12:06
  • 2
    \$\begingroup\$ @CommandMaster It seems some answers are already using a different offset, so sure. Also, I thought about allowing variables, but it kind of gets rid of the "elegance" of a one-line expression I think. For now, try to find a way to get around it :) \$\endgroup\$ Aug 12, 2023 at 19:26

9 Answers 9

5
\$\begingroup\$

A002193, 82 bytes

Cracked by @loopy walt. The brownie points are still open.

Offset: 1 (that is, \$f(1) = 1, f(2) = 4, f(3)=1, ...\$)

The decimal expansion of \$\sqrt 2\$.

Six brownie points if your solution can finish for \$n = 1000\$ before the end of the universe.

My solution:

We can approximate \$\sqrt{2}\$ using the Pell numbers. To know how much accuracy we need, we need to bound \$|\sqrt{2} - \frac{p}{10^n}|\$. According to Carmichael's theorem, 1, 2 and 5 are the only Pell numbers which divide a power of ten, and if \$\frac{a}{b}\$ isn't a convergent of \$x\$ it's known that \$|x - \frac{a}{b}| > \frac{1}{2b^2}\$, so in particular \$|\sqrt{2} - \frac{p}{10^n}| > \min(\frac{1}{2\cdot 10^{2n}}, |\sqrt{2} - \frac{7}{5}|)\$, but it can be easily calculated that for any \$n \geq 1\$, \$\frac{1}{2\cdot 10^{2n}} < |\sqrt{2} - \frac{7}{5}|\$, so \$|\sqrt{2} - \frac{p}{10^n}| > \frac{1}{2\cdot 10^{2n}}\$. This means if we have an approximation with error of at most \$\frac{1}{2 \cdot 10^{2n}}\$ the n-th digit must be correct. We will show that \$|\sqrt{2} - \frac{H_{4n}}{P_{4n}}| \leq \frac{1}{2 \cdot 10^{2n}}\$ for \$n \geq 1\$. Since \$\frac{H_{4n}}{P_{4n}}\$ is a convergent to \$\sqrt{2}\$, it's known that \$|\sqrt{2} - \frac{H_{4n}}{P_{4n}}| \leq \frac{1}{P_{4n} P_{4n+1}} \leq \frac{1}{P_{4n}^2}\$. It can be seen that \$P_n \geq \frac{(1+\sqrt{2})^n}3\$, so \$\frac{1}{P_{4n}^2} \leq \frac{9}{(1+\sqrt{2})^{8n}} = \frac{9}{10^{\log_{10}(1 + \sqrt2)8n}} \leq \frac{9}{10^{3 n}}\$ and since \$n \geq 1\$, \$\frac{9}{10^{3 n}} \leq \frac{1}{10^{2n}}\$.
Now we just need to calculate \$H_n\$ and \$P_n\$. We will use \$(1 + x)^n \equiv H_n + x P_n \pmod {x^2 - 2}\$. Since \$H_n, P_n < 3^n\$, we can use \$x = 3^n\$, and \$(1 + 3^n)^n \equiv H_n + 3^n P_n \pmod {9^n - 2}\$. We actually need to calculate it for \$4n\$, so we use \$(1+81^n)^{4n} \equiv H_{4n} + 81^{n} P_{4n} \pmod {6561^n - 2}\$. Then we can calculate \$\lfloor \frac{H_{4n} 10^{n-1}}{P_{4n}} \rfloor \mod 10 \$. In code:
(1+81**n)**(4*n)%(6561**n-2)%81**n*10**~-n/((1+81**n)**(4*n)%(6561**n-2)/81**n)%10

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

A000796, 105 bytes

Offset: 1 (that is, \$f(1) = 3, f(2) = 1, ...\$)

The digits of \$\pi\$, in base 10.

Your formula must be provably correct, and can't relay on any unproven assumptions/conjectures. Note that if you approximate \$\pi\$, it is possible there are a bunch of \$9\$s in that position, and then the \$n\$th digit of the approximation could be wrong.

My solution:

Is has been proven (by Kurt Mahler, I couldn't find the paper online) that for any integers \$q \geq 2\$ and \$p\$, \$|\pi - \frac{p}{q}| \geq \frac{1}{q^{42}}\$. In particular, if \$\frac{a}{10^{n-1}} < \pi < \frac{a+1}{10^{n-1}}\$, any value \$r\$ such that \$|\pi - r| \leq \frac{1}{10^{42(n-1)+1}}\$ will be entirely contained within that interval, and so its \$n\$-th digit will be correct. To approximate \$\pi\$, we can use the asymptotics for the centeral binomial coefficients: \$\binom{2n}{n} \approx \frac{4^n}{\sqrt{\pi n}}\$. We can use the nonasymptotic bounds \$\frac{1}{\sqrt{\pi (n+1)}} < \binom{2n}{n} 4^{-n} < \frac{1}{\sqrt{\pi n}}\$ to derive \$\frac{16^n}{\binom{2n}{n}^2 (n+1)} < \pi < \frac{16^n}{\binom{2n}{n}^2 n}\$, and it isn't hard to see that the error in any of these bounds is at most \$\frac{16^n}{\binom{2n}{n}^2} (\frac{1}{n} - \frac{1}{n+1}) = \frac{16^n}{\binom{2n}{n}^2} \frac{1}{n(n+1)}\$ but as stated earlier \$\frac{16^n}{\binom{2n}{n}^2 (n+1)} < \pi\$ and thus the error is at most \$\frac{\pi}{n} < \frac{4}{n}\$. If we set \$n = 10^{42 m}\$ there, where \$m\$ is the digit we're trying to calculate, we can see we get enough accuracy. In code:
16**10**(42*n)*10**~-n/(((1+4**10**(42*n))**(2*10**(42*n))/4**10**(84*n)%4**10**(42*n))**2*10**(42*n))%10

\$\endgroup\$
1
  • \$\begingroup\$ Cracked I believe. \$\endgroup\$
    – loopy walt
    Aug 16, 2023 at 11:47
2
\$\begingroup\$

A000120, 50 bytes

Cracked by @Command Master

Offset: 1

Here's one to get started: the Hamming weight of n, the number of 1's in the binary representation of n. You don't need to handle n=0.

\$\endgroup\$
3
  • \$\begingroup\$ Cracked \$\endgroup\$ Aug 12, 2023 at 7:39
  • \$\begingroup\$ My guess is your 50 looks something like this? \$\endgroup\$ Aug 12, 2023 at 23:57
  • \$\begingroup\$ @dingledooper Yes, that's exactly it. \$\endgroup\$
    – xnor
    Aug 13, 2023 at 0:17
2
\$\begingroup\$

A000005, 242 bytes

Cracked by @l4m2

Offset: 1

The number of divisors of \$n\$.

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

A000244, 23 bytes

Cracked by loopy walt

Compute 3**n, but ** is banned. Offset 1, so n>0.

\$\endgroup\$
1
  • \$\begingroup\$ cracked with 33. \$\endgroup\$
    – loopy walt
    Aug 12, 2023 at 20:22
2
\$\begingroup\$

A000045, 45 bytes

Cracked by xnor

Offset: 0

The Fibonacci numbers. / isn't allowed.

\$\endgroup\$
1
  • \$\begingroup\$ Cracked with 29 bytes \$\endgroup\$
    – xnor
    Aug 12, 2023 at 19:18
2
\$\begingroup\$

A007953, 93 bytes

Cracked by @Command Master

The nth term is the sum of digits of n (e.g. a(1234) = 1+2+3+4 = 10).

A step up from counting bits. You do not need to handle n=0.

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

A000012, 6 bytes, cracked in 8 minutes 🤯

Offset: Doesn't matter

Every term in the sequence is 1.

Of course, since this would be too trivial without this, you can only use bit-shifts (which are >> and <<) and the digit 9.

Intended solution

Exactly what the cracker posted, 999>>9.

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

A160155, 125 bytes

Offset: 1 (that is, \$f(1) = 1, f(2) = 1, f(3)=6, ...\$)

The decimal expansion of the single real root of \$x^5 - x-1\$, \$1.1673...\$.

Using & or | is forbidden.

\$\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.