8
\$\begingroup\$

This is the robbers' thread. See the cops' 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.

Robbers

Your goal as the robber is to crack the cops' submissions. To begin, pick any submission from the cops' thread that isn't marked as safe and is less than a week old. The submission should contain an OEIS sequence and a byte count representing the length of the intended expression. To submit a crack, 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 the 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 described in detail in the cops' thread.

Your expression must be at most twice the length of their expression to be considered a crack. This is to ensure that you can't crack their submission with an overly long expression. Bonus points if you are able to match or reduce their byte count.

Scoring

Your score is the number of answers you have cracked, with more cracks being better.

Example Crack

A000225, 6 bytes, cracks @user's answer

2**n-1
Improve this question
\$\endgroup\$

8 Answers 8

Reset to default
4
\$\begingroup\$

A000120, 86 bytes, cracks @xnor's answer

4**n**2*2**n/(2*4**n-1)*(4**n**2*2**n/(2*4**n-1)&4**n**2/(4**n-1)*n)>>2*n*n-n-1&2**n-1

Try it online!

I was hoping I could do something with \$v_2(\binom{2n}{n})\$, but it was too long because I needed to copy the expression for \$\binom{2n}{n}\$ multiple times, so I just used bitwise operators to separate the bits of \$n\$, and then using multiplication we can count the number of \$1\$s.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I also looked at choose(2n,n) initially and ran into needing to duplicate it to do x&-x, and found separating 1-bits was shorter. I did find a 63 with a modified binomial-based approach based on counting odd entries in rows of Pascal's triangle. \$\endgroup\$
    – xnor
    Aug 12 at 7:55
4
\$\begingroup\$

Python 2, 161 bytes

(((8**n**2/(8**n-1)**2*(8**n**4/(8**n**2-1)**2)+8**n**4/(8**n-1)*(8**n/2-1-n)&~(8**n**4/(8**n-1)*(8**n/2)))+8**n**4/(8**n-1)>>n*3-1)&8**n**4/(8**n-1))%(8**n-1)+1

Try it online!

https://codegolf.stackexchange.com/a/264066/76323

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python 2, 29 bytes

4**(n*-~n)%(16**n+~4**n)%4**n

Try it online!

Cracks Command Master's Fibonacci numbers A00045 with / banned.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python 2, 25 bytes

(1<<2*n*n-2)%((4<<2*n)-3)

Attempt This Online!

cracks @xnor's powers of 3.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I had pretty much this: (1<<3*n*n)%((1<<3*n)-3). By offset 1, I just meant that you don't need to handle n=0 . \$\endgroup\$
    – xnor
    Aug 12 at 23:56
2
\$\begingroup\$

A007953, 151 bytes, cracks @dingledooper's answer

10*n+((10**n*16**n**3/(10*16**n**2-1)*((n*16**n+~n)*16**n**2+1)/(16**n-1)**2+16**n**3/(16**n-1)*(16**n/2+~n)>>4*n-1&16**n**3/(16**n-1))%(4**n-1)-n*n)*9

Try it online!

Uses the formula (for \$d=10\$) $$s_{d}(n) = d n-(d-1)\sum_{k=0}^\infty {\left\lfloor \frac{n}{d^k} \right\rfloor}$$ calculating the sum by counting the numbers which can be formed as \$a 10^b\$ with \$1 \leq a \leq n\$ and \$0 \leq b \leq n\$ and are less than \$n\$ (for each particular \$b\$, there will be \$\left\lfloor \frac{n}{10^b} \right\rfloor\$ such numbers).

At first I tried to calculate it with a smarter approach, by looking at \$\sum_{i=0}^n {(10^{2n-1})^i n}\$ and then reinterpreting it as a base \$10^{n}\$ number, but while the even digits sum to the number you want, the odd digits have junk and you can't use bitwise operators to get rid of it since the base isn't a power of two.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Nice. The way I did it was by implementing "vector division" with the old trick of multiplying then shifting by a constant. \$\endgroup\$
    – dingledooper
    Aug 14 at 7:53
2
\$\begingroup\$

Python 2, 206 bytes

(((~16**k)**2-(((8**(4*k<<8*k)/~-8**(4*k<<4*k)*(8**(4*k*(16**k+2))/(~-4096**k)**3)+8**(4*k<<4*k)/~-4096**k*(8**(4*k<<8*k)/~-8**(4*k<<4*k))**3>>8*k-1)&(8**(4*k<<8*k)/~-4096**k))%~-4096**k))*5**~-k>>7*k-1)%10

Attempt This Online!

cracks @Command Master's decimals of pi (I think)

Times out at k=3, so I couldn't really test it that much.

It makes an ortho grid and counts points outside a circle of radius R=16**k with centre just between grid points.

I have no proof but as the error is O(1/R) this should converge faster than 1 digit per step.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ While heuristically this is enough accuracy, I did specify that it must be provably correct, and if there's an unlikely bunch of 9s or 0s in the digits it's theoretically possible for this formula to be wrong \$\endgroup\$
    – Command Master
    Aug 16 at 12:34
  • 1
    \$\begingroup\$ @CommandMaster It may well be provable. Not necessarily by me, though. \$\endgroup\$
    – loopy walt
    Aug 16 at 12:49
  • 1
    \$\begingroup\$ I would think the burden is on you to prove that your answer is valid before submitting it. \$\endgroup\$
    – The Fifth Marshal
    Sep 21 at 0:53
1
\$\begingroup\$

Python 2, 6 bytes, cracks @The Empty String Photographer's answer

999>>9

tio

Improve this answer
\$\endgroup\$
1
1
\$\begingroup\$

Python 2, 157 bytes

((128**(N*~-(2*10**~-N))/~-128**N*2*(16*128**~-N-100**~-N)+128**(N*-~(2*10**~-N))/(~-128**N)**3*-~128**N)>>7*N-3&128**(N*~-(2*10**~-N))/~-128**N)%~-128**N%10

Attempt This Online! cracks @CommandMaster's decimals of \$\sqrt 2\$

Updated using a suggestion by @CommandMaster.

Works by counting integer squares below 2,200,20000,2000000,...

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Couldn't you count squares less than \$2 \cdot 100^n\$ modulo 10? I don't get what that \$19...98\$ is useful for \$\endgroup\$
    – Command Master
    Aug 22 at 5:28
  • \$\begingroup\$ @CommandMaster I'm fairly new to this kind of problem. So far the only way of counting stuff I've figured out is creating an indicator set and then reducing modulo spacing - 1. Getting the indicator set requires masking so we need to work in a power of two base. And the easiest way I could think of to translate greater or smaller than 200 into a specific bit position was multiplying by a bitshifted inverse of 200. I'll certainly have a look at your reference solution once it is disclosed. \$\endgroup\$
    – loopy walt
    Aug 22 at 6:08
  • 1
    \$\begingroup\$ You can actually add the bit inversion of the number, and then it's less than or equal to your number if it didn't overflow. I'm going to wait a day with posting my solution to give people a crack at solving it efficiently \$\endgroup\$
    – Command Master
    Aug 22 at 6:40
  • 1
    \$\begingroup\$ @CommandMaster Adding! That would also get rid of some residual accuracy concerns. Did I mention I'm new to this? \$\endgroup\$
    – loopy walt
    Aug 22 at 6:51

Your Answer

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

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