12
\$\begingroup\$

This is a challenge. The Cops' thread to this challenge is here

An interesting question to think about is the following:

If I have a sequence of numbers how many of them do I have to provide before it is clear what sequence I am talking about?

For example if I want to talk about the positive integers in order starting from \$1\$, I could say \$1,2,3, \dots\$, but is that really enough?

I have one way of answering this question, and being a code-golfer It involves code-golf. You have provided enough terms of a sequence if the shortest code that produces those terms produces all the terms of the sequence. If we think about this in terms of code-golf, this would mean you have provided enough test cases such that the shortest code that passes the test-cases does the desired task.

Challenge

This challenge is a challenge. In which cops will be presenting test-cases and robbers will have to find a shorter way to spoof the test-cases other than the intended sequence. Cops will present the following things:

  • A piece of code that takes a positive integer as input and produces an integer as output. This code can be either zero or one indexed but it should be clear what the indexing is. This code will define your sequence.

  • Any relevant platform or language requirements that might effect the output, for example the size of longint.

  • A number \$n\$, along with the first \$n\$ terms of the sequence as calculated by the code. These will act as "test-cases".

Robbers will be finding a program in the same language that is shorter than the one presented and passes all the test cases (produces the same output for the first \$n\$ inputs as the cop's code). The robber's code must also differ in output from the cop's program for some number larger than \$n\$.

Scoring

Robbers will be scored in the number of cracks they find with more cracks being better. An answer can be cracked again by finding a valid answer shorter than the original crack. If an answer is cracked a second time the point is given to the second cracker rather than the first.

\$\endgroup\$
  • 2
    \$\begingroup\$ Are we not letting robbers beat each other for cracking an answer (ie shortest crack in the language winning) \$\endgroup\$ – fəˈnɛtɪk Jun 29 '18 at 15:52
  • \$\begingroup\$ @fəˈnɛtɪk Sounds, good I added that. \$\endgroup\$ – Wheat Wizard Jun 29 '18 at 16:06

14 Answers 14

6
\$\begingroup\$

cQuents, Stephen's answer, 3 bytes

z~$

Try it online!

How it works

z     Last item in the sequence
 ~    Concat
  $   Current index

Looks like the sequences should be identical, but this gives 12345678910 for n = 10 while "::$ gives 1234567891.

\$\endgroup\$
5
\$\begingroup\$

JavaScript, fəˈnɛtɪk's answer (17 bytes)

x=>"11237"[x]||22

Well it was easy to hardcode to obtain a much lower score... Differs from the reference implementation for any entry \$x\ge 6\$, 0-indexed. This uses a very well-known JS golfing trick: indexing into a sequence with an integer that exceeds the bounds of it returns a falsy value (undefined), so it can simply be coerced to a default value by using logical OR (||), in this case 22, handling the last term of the sequence but also those to follow.

Testing

let f=x=>"11237"[x]||22

for (x of [1,2,3,4,5,6,7]) {
  console.log(x + ' -> ' + f(x))
}

Alternatively, Try it online!

\$\endgroup\$
4
\$\begingroup\$

Haskell, Laikoni's answer, 15 bytes

b n=n*div(n+1)2

Try it online!

I would usually point something like this out in a comment, but then I thought, cops and robbers are a bit more cut-throat.

This is just BMO's answer minus the special case for b 42. Because Laikoni's original goes via floating point, it's not necessary: just find a number large enough to give rounding errors in that but not in exact Integer arithmetic. For example:

a 100000000000000000000000 = 4999999999999999580569600000000000000000000000
b 100000000000000000000000 = 5000000000000000000000000000000000000000000000
\$\endgroup\$
  • \$\begingroup\$ I thought that this might be possible (hence I wrote that it can be rewritten for the required terms) but didn't find a value for which it works.. Nicely done! \$\endgroup\$ – ბიმო Jul 2 '18 at 12:30
4
\$\begingroup\$

Python 2, xnor's answer, 43 bytes

The first difference occurs for \$n = 69\$:

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

Try it online!

Credits

A great deal of the credit for this crack must go to @Mr.Xcoder who first posted a comment about a possible attack using this method, and to @PoonLevi who found a 44-byte solution.

How?

Theory

The crack is based on Fermat's little theorem which states that if \$p\$ is prime and \$a\$ and \$p\$ are relatively prime, then:

$$a^{p-1}\equiv 1 \pmod p\tag{1}$$

In particular, for \$a=2\$:

$$2^{p-1}\equiv 1 \pmod p$$

So there exists some positive integer \$k\$ such that:

$$2^{p-1}=kp+1$$

Which leads to:

$$2^p=2kp+2$$ $$2^p-1=2kp+1$$ $$2^p-1\equiv 1 \pmod p\tag{2}$$

This last formula is the one the Python code is derived from and now holds for \$p=2\$, even though \$2\$ is not relatively prime with itself.

Now, for the most important part: the converse of Fermat's little theorem is not true. We may have \$a^{n-1}\equiv 1 \pmod n\$ for some composite number \$n\$. Such numbers are called Fermat pseudoprimes to base \$a\$. Fermat pseudoprimes to base 2 are also known as Poulet numbers.

The first Fermat pseudoprime to base \$2\$ (or first Poulet number) is \$n = 341=11\times 31\$, for which we do have:

$$2^{341-1}\equiv 1 \pmod{341}$$ $$2^{341}-1\equiv 1 \pmod{341}$$

This means that our algorithm is going to return \$341\$ instead of the expected 69th prime \$347\$.

Implementation

@PoonLevi found the following 44-byte solution, which is directly based on \$(2)\$:

f=lambda n,p=1:n and-~f(n-(~-2**p%p==1),p+1)

By using <2 instead of ==1, we save 1 byte but we introduce \$1\$ into the sequence, because \$2^1-1\equiv 0 \pmod 1\$:

f=lambda n,p=1:n and-~f(n-(~-2**p%p<2),p+1)

Try it online!

By starting with \$p=2\$, we get the expected terms off by 1 because we do one iteration less:

f=lambda n,p=2:n and-~f(n-(~-2**p%p<2),p+1)

Try it online!

The last trick is to use n<1or instead of n and. This is just as long but makes the last iteration return True instead of 0, hence adding the missing offset to each term.

\$\endgroup\$
  • \$\begingroup\$ Congrats to all of you! This is the solution I had in mind. I think it's funny that, from the challenge motivation "If I have a sequence of numbers how many of them do I have to provide before it is clear what sequence I am talking about?", the first 50 primes are apparently not enough -- a Python-golfing alien would assume you're talking about a different sequence. \$\endgroup\$ – xnor Jul 5 '18 at 23:56
  • \$\begingroup\$ @xnor I love the idea of a "Python-golfing alien" \$\endgroup\$ – dylnan Jul 6 '18 at 0:35
3
\$\begingroup\$

Python 3, crashoz, 45 bytes

lambda n:int(60*math.sin(n/10-2))
import math

Try it online!

The expression x*60-x**3*10+x**5/2-x**7/84 is the Taylor series for \$sin(x)\$ up to the \$x^7\$ term, multiplied by 60. This is accurate enough on the inputs used, but for higher values, the two will diverge as the truncated terms become more relevant.

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

JavaScript (ES6), Arnauld's answer (10 bytes)

n=>8*n*n|n

Try it online!

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

Haskell, Laikoni's answer, 26 22 bytes

-4 bytes by not using infix div, thanks to Laikoni!

b 42=0;b n=n*div(n+1)2

Try it online!

Explanation

For \$0 \leq n \leq 20\$ the term ceiling(realToFrac n/2) can be rewritten as div(n+1)2 which gives us enough bytes to pattern match on an \$n > 20\$ that leads to a crack within 28 bytes:

b 42=0
\$\endgroup\$
  • \$\begingroup\$ Ah, I didn't think of that. I have a different approach which leads to a 20 bytes crack in case you want to puzzle a bit more. Also ((n+1)`div`2) -> div(n+1)2. \$\endgroup\$ – Laikoni Jun 30 '18 at 14:59
  • \$\begingroup\$ @Laikoni: Yeah don't reveal it just yet! Oopsies, yeah it's been quite a while since I did some golfing, I'll update it. \$\endgroup\$ – ბიმო Jun 30 '18 at 15:07
2
\$\begingroup\$

><>, crashoz's answer 203 bytes

:l2-$g:0=?;n:





M
-
B
"
BM
",
7M
!"
BBM
!",
7CM
!"-
BBBM
!!",
7BBMM
!!,,
7BBBMM
!!,,
7BBBMM
!!!,,
7BBBBMM
!!!,,
7BBBBMM
!!!!,,
7BBBBBMM
!!!!,,
7BBBBBMM
!!!!!,,
7BBBBBBMM

Try it online!

I was going to do something clever with the fact that odd/even numbers above n=20 were the same except for a repeated element in the center, but it was easier to just hard code every element.

Input is via the -v flag. Prints nothing for elements above 34.

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

Pascal (FPC), AlexRacer's answer, 80 bytes

var n,m:word;begin read(n);while n<>0 do begin n:=n div 2;m:=m+n;end;write(m)end.

Try it online!

When \$0\le n\le 120\$ the outputs are identical, but when \$n=128\$ the above code outputs \$127\$, while AlexRacer's code outputs \$126\$.

This seems a late answer, but anyway thanks @AlexRacer for a good puzzle!

\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, this is even shorter than what I had. Welcome to PPCG! \$\endgroup\$ – AlexRacer Aug 18 '18 at 14:44
1
\$\begingroup\$

JavaScript, fəˈnɛtɪk's answer (12 bytes)

This works for the given values but fails for many other values (e.g. \$x=6\$) due to precision errors.

x=>2.72**x|0

Testing

g=
x=>2.72**x|0

tmp=[0,1,2,3,4]
console.log(tmp.map(g).join(','))

Alternatively, Try it online!

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

JavaScript, fəˈnɛtɪk's answer (17 bytes)

You can see in the TIO link or in the Stack Snippet result that it fails for entries higher than \$15\$.

x=>2.7182819**x|1

If accuracy would only be required for \$n\le 14\$ (the first \$15\$ values), then x=>Math.exp(x)|1 would work as well for 16 bytes.

Testing

f=x=>2.7182819**x|1
g=x=>(3-(5/63)**.5)**x|1

tmp=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
console.log(tmp.map(f).join(","))
console.log(tmp.map(g).join(","))

Alternatively, Try it online!

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

Husk, cracking BMO's 5 byter with  3  2 bytes

-1 thanks to BMO (LdΣ -> since, when given a Tnum, L performs "length of string representation")

Try it online!

The digital length of the triangular numbers* matches \$a(0)\cdots a(23)\$ then differs at \$a(24)\$
...when yields \$3\$ while ←d+16 yields \$4\$.

* Where \$T(0)=0\$ has a digital length of \$1\$ (not \$0\$)

\$\endgroup\$
  • \$\begingroup\$ Congratulations, that was my exact solution! However I just noted that for TNums L and Ld are equivalent saving you a byte ;) \$\endgroup\$ – ბიმო Jun 30 '18 at 16:42
  • \$\begingroup\$ Ah, I searched for "digit" in the wiki to try to find digital-length, but didn't spot that L overrides as "length of string representation" for Tnum. \$\endgroup\$ – Jonathan Allan Jun 30 '18 at 16:49
  • \$\begingroup\$ (Note that they are only equivalent for non-negative integers - good enough for this.) \$\endgroup\$ – Jonathan Allan Jun 30 '18 at 16:56
1
\$\begingroup\$

><>, Aiden F. Pierce's answer, 36 bytes

v101786
i5844
419902
%
>l{:}g:0=?;o:

Try it online!

Another solution with each value hardcoded per line. Since the original answer was also mostly hard-coded, I don't feel too guilty about this.

\$\endgroup\$
0
\$\begingroup\$

JavaScript, fəˈnɛtɪk's answer, 23 bytes

Returns \$0\$ for \$n\ge 14\$.

x=>14-`${73211e9}`[x]|0

Try it online!

How?

The expression `${73211e9}` expands to the string "73211000000000", providing a lookup table of 14 values that are subtracted from 14, which gives the expected sequence.

For \$n\ge 14\$, the result is:

(14 - undefined) | 0
=== NaN | 0
=== 0

21 bytes

Returns NaN for \$n\ge 14\$, which may or may not be considered a valid output.

x=>14-`${73211e9}`[x]

Try it online!

\$\endgroup\$

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.