Robbers: The Hidden OEIS Substring

Question

This is a Cops and Robbers challenge. This is the robber's thread. The cop's thread is here.

The cops will pick any sequence from the OEIS, and write a program p that prints the first integer from that sequence. They will also find some string s. If you insert s somewhere into p, this program must print the second integer from the sequence. If you insert s + s into the same location in p, this program must print the third integer from the sequence. s + s + s in the same location will print the fourth, and so on and so forth. Here's an example:

Python 3, sequence A000027

print(1)

The hidden string is two bytes.

The string is +1, because the program print(1+1) will print the second integer in A000027, the program print(1+1+1) will print the third integer, etc.

Cops must reveal the sequence, the original program p, and the length of the hidden string s. Robbers crack a submission by finding any string up to that length and the location to insert it to create the sequence. The string does not need to match the intended solution to be a valid crack, nor does the location it's inserted at.

If you crack one of the cops answers, post your solution (with the hidden string and location revealed) and a link to the answer. Then comment on the cops answer with a link to your crack here.

Rules

• Your solution must work for any number in the sequence, or at least until a reasonable limit where it fails due to memory restrictions, integer/stack overflow, etc.

• The winning robber is the user who cracks the most submissions, with the tiebreaker being who reached that number of cracks first.

• The winning cop is the cop with the shortest string s that isn't cracked. Tiebreaker is the shortest p. If there are no uncracked submissions, the cop who had a solution uncracked for longest wins.

• To be declared safe, your solution must stay uncracked for 1 week and then have the hidden string (and location to insert it) revealed.

• s may not be nested, it must concatenated end to end. For example, if s was 10, each iteration would go 10, 1010, 101010, 10101010... rather than 10, 1100, 111000, 11110000...

• All cryptographic solutions (for example, checking the hash of the substring) are banned.

• If s contains any non-ASCII characters, you must also specify the encoding being used.

Answer 1

Python 2, sequence A138147 by xnor

Original:

print 10

Cracked:

print "1%s0"%10
      ^^^^^^^

Try it online!

Answer 2

Brain-Flak, A000984 by Nitrodon

({({}<>({}))<>}<>){({}<>)<>}<>

This is only 30 bytes, not sure what Nitrodon had in mind.

Try it online!

Explanation

I tried a lot of things but here is what worked. The terms of A000984 are the central elements of Pascal's triangle.

Now I figured out that I can get them by adding up the diagonals above them:

For example:

\$1+3+6+10 = 20\$

And since the final action in Nitrodon's program is to sum up everything these seemed like a good candidate (more like I tried a bunch of things but this one ended up working).

So we want a program that takes one partial sum and produces the next. Luckily there is a pretty neat way to get from one of these to the next. Each row is the deltas of the next row. That is the \$n\$th term in a row is the difference between the \$n\$th and \$n-1\$th terms in the next row.

The one problem is that we don't quite have enough of the last row to calculate the row we want. Since each row is one longer than the last if we have a row we can't get the last member of the next row with this method. However here we have another trick, the last member of each row is equal to all previous members of that row!

\$1+3+6=10\$

And if you are familiar with Brain-Flak that should stick out to you as something that is going to be really easy to do.

Now for the code:

To start we do the next row calculation where each new member is the sum of two adjacent old members. That can be done with:

{({}<>({}))<>}<>

Which basically moves an element over and adds (without deletion) what ever was already on top to it. However this reverses everything so for the next time we get a row we need to put it back.

{({}<>({}))<>}<>{({}<>)<>}<>

Now we need to calculate the last member of the row. As I said before this is super easy. Since we had a loop over all the elements of the row we can just take that sum and push it. We push it before the second loop so it ends up on the bottom.

({({}<>({}))<>}<>){({}<>)<>}<>

And that's it.

Answer 3

Brain-Flak, A000290, by Sriotchilism O'Zaic

Original:

((()))({}<>)

Cracked:

((()))({}([])[]<>)
         ^^^^^^

Try it online!

Alternatively:

((())([])[])({}<>)
     ^^^^^^

Try it online!

Answer 4

MATL, sequence A005206 by Luis Mendo

Original:

voOdoO

Try it online!

Cracked:

voOdoOdNq17L/k
      ^^^^^^^^

I am not a MATL expert, but from what I understand, the original voOdoO creates two empty arrays and an array [0] on the stack. this [0] is what gets printed without brackets as the first element of the sequence. The crack/solution then does the following:

• d takes an elements off the stack and (assuming it's a number or an array of size 1) turns it into an empty array. These empty arrays don't get printed, but contribute to the stack size
• Nq counts the size of the stack and subtracts one. This is the n+1 term when evaluating the function (since it starts at 2 and increases by one every iteration because of the d adding invisible stuff to the stack)
• 17L this is the constant Phi = (1+sqrt(5))/2
• /k this performs floor((n+1)/Phi) which is one of the formulas that computes the elements of the sequence. This formula is listed on OEIS as a(n) = floor(sigma*(n+1)) where sigma = (sqrt(5)-1)/2 except we use the identity (sqrt(5)-1)/2 = 1/Phi

Answer 5

Python 3 -- A__

print(100+-1)

Try it online!

100 bottles of beer, add -1 to get the next number, 99, etc.

Answer 6

Keg, sequence A000045, by A__

Original:

0.

Cracked:

01":&+.
 ^^^^^

Note that the challenge was finding a substring of length <=6, but the found string has length 5.

Definition of the commands for those who are too lazy to look up the Keg specification: 0 and 1 push the respective number to the stack; " moves the stack top to the stack bottom (roll); & pops the stack top into the register if it's empty, otherwise empties the register onto the stack; + adds the top two stack values.

The initial 1" just inserts a 1 at the bottom of the stack. This growing list of 1's only plays a role in the first iteration, where it allows us to assume the stack starts as 1 0 rather than just 0. Indeed, the program 10:&+., where the :&+ part is repeated, has the exact same behaviour as the solution above, except that it doesn't have a growing list of 1's at the bottom.

Since & is used only once in the repeating part and has alternating behaviour, the behaviour of 1":&+ depends on the parity of the iteration.

Now, this program doesn't really print the sequence Fibonacci sequence starting with 0, 1 from the start; it actually prints the 1, 0 Fibonacci sequence from the second place, i.e. from the 0. (This results in the same sequence.) Knowing this, the program is easily analysed:

• In the first, third, ... iteration, the state starts as [a, b] and ends as a+b (&=b).
• In the second, fourth, ... iteration, the state starts as [b] (&=a) and ends as [b, b+a].

This indeed computes the sequence as required.

Answer 7

Pyret, sequence A083420, by MLavrentyev

fold({(b,e):(2 * b) + 1},1,[list: 0,0,])
                                  ^^^^

You can run it here, but I've not figured out how to link to the code. You'll have to copy-paste.

The function provided ignores its second argument. It doubles its first and adds one, which will generate the necessary 2^n - 1 sequence needed here—all I need do is tell it how many times to perform that operation, done by changing the length of the folded list. Fortunately, Pyret doesn't complain about that trailing comma.

Answer 8

Java 8+, sequence A010686 by Benjamin Urquhart

()->System.out.println(1^4);
                        ^^

Answer 9

Brain-Flak, A000578 by Sriotchilism O'Zaic

Original:

((())<>)

Try it online!

Cracked:

((())(({})([][][]){})<>)
    ^^^^^^^^^^^^^^^^

Try it online!

Answer 10

AsciiDots, sequence A019523 by Alion

\+++/
//\/\

Once!

Twice!

Ten times!

While trying to figure out how the code/language works, I learned that the first two lines of the existing code does all the work of outputting the Fibonacci sequence infinitely. The code terminates when any dot hits the &, so I merely needed to add further delay in the remaining lines to allow for the appropriate number of entries to output.

After some trial, error, and observation, I discovered that the correct delay interval is 16 time units per number. Fitting enough characters in a single row seemed infeasible, so I would need to put the delay in 2 rows, leaving 10 characters for the actual delay. In order for the pattern to match up with itself, both rows had to have 5 characters, and since the middle three characters in a row can be traversed twice, this gives 16 time units as desired.

The requirement to match this up to the & in the eighth column seemed to make this impossible, until I realized that I could start with a newline in the interior of the third row. This makes the penultimate row the right length, and removes the now-redundant end of the third line.

Answer 11

Python 3, sequence A268575 by NieDzejkob

Original:

from itertools import product
S,F,D=lambda*x:tuple(map(sum,zip(*x))),lambda f,s:(v for x in s for v in f(x)),lambda s:{(c-48>>4,c&15)for c in map(ord,s)}
W=D("6@AQUVW")
print(len(W))

Cracked (100 bytes):

from itertools import product
S,F,D=lambda*x:tuple(map(sum,zip(*x))),lambda f,s:(v for x in s for v in f(x)),lambda s:{(c-48>>4,c&15)for c in map(ord,s)}
W=D("6@AQUVW");A=-1,1,0;*X,=F(lambda a:(S(a,x)for x in product(A,A)),W);W={p for p in X if 2<X.count(p)<4+({p}<W)}
print(len(W))

Try it online!

From what I can gather, the original code is setting up definitions to make the hidden string as abbreviated as possible and then defining the initial Game of Life pattern. The hidden string is then equivalent to writing an iteration of Conway's Game of Life in 102 bytes.

For the purposes of this crack, S is a function that sums the elements within its arguments (which are iterables) and F applies a function returning an iterable to every element of a list and smashes all the results together.

• ;A=-1,1,0; ends the preceding statement and abbreviates the tuple (-1,1,0) with A, which is used as product(A,A) which gives all the neighbors relative to a given cell as well as the cell itself.
• *X,=F(lambda a:(S(a,x)for x in product(A,A)),W); creates a new list X holding all the neighbors of cells in W and the cells in W themselves by adding the relative positions of the neighbors to each cell and smashing them together into a list.
• W={p for p in X if 2<X.count(p)<4+({p}<W)} goes through this list X and determines whether each cell in X belongs in the set of cells in the next iteration. This was taken almost verbatim from this Game of Life golf.

Answer 12

Unefunge-98 (PyFunge), sequence A000108, by NieDzejkob

1# 2g1+:2p4*6-*2g/.@
 ^^^^^^^^^^^^^^^^^

Try it online!

Repeated six times

Two bytes to spare of the nineteen allowed! What appears to be a space there is actually a 0x01 Start Of Header character.

Explanation:

This challenge is all about generating a(n) from a(n-1) and perhaps n. OEIS provides the explicit formula a(n) = (2n)!/(n!(n+1)!), which is easily enough converted to a(n) = a(n-1) * (4n-6) / n. Now to implement this in Funge.

I must be inserting code between the 1 and the .. That's half the puzzle done already. All that remains is what code to insert? Funge is notably lacking in stack manipulation tools, so the bottom of the stack is off-limits; I need to track both n and a(n) without growing the stack. And how better to do that than with Funge space?

That 0x01 character is my counter n. I keep a(n) on the stack, as it must be on the stack after my bit finishes executing.

1# 2g1+:2p4*6-*2g/.@
1                       Push 1. This is a(0).
 #                        Skip the next instruction. Without this, I believe the instruction pointer will reverse direction upon encountering 0x01.
   2g                     Push the third character in the source, which starts out as 1.
     1+                   Increment it...
       :                  ...copy it...
        2p                ...and put it back. One copy remains atop the stack.
          4*6-            Multiply by four. Subtract six.
              *           Multiply by a(n), leaving the result alone on the stack.
               2g         Push n again...
                 /        ...and divide our intermediate result by it. Ta-da!
                          At this point, the stack is the same as at the start of the indented block, except the one item has been advanced one place in the sequence.
                          The source of the program has changed; the third character holds the number of times this indented block has run.
                  .@    Print and terminate.

Answer 13

Haskell, A014675 by Khuldraeseth na'Barya

Original code

main=print$uncurry(!!)([2],0)

With substring

main=print$uncurry(!!)                                   ([2],0)
                      $(\(a,n)->(a>>= \e->2:[1|e>1],n+1))

Try it online!

Answer 14

Haskell, A000045 (Fibonacci), by Rin's Fourier transform

f = head $(flip(:)<*>sum.take 2)[0, 1]
         ^^^^^^^^^^^^^^^^^^^^^^^

Try it online!

23 bytes exactly.

This one was fun and a bit tricky. The reversed 0 and 1 threw me off for a little bit before I realized that wasn't an issue. The lack of $ in the original had me trying sketchy stuff like $...$id (one byte too long) before it dawned on me that I could just wrap it all in parentheses. All in all, a nice little puzzle.

H.PWiz points out that pattern matching could have saved me at least five bytes: $(\[x,y]->[y,x+y]). That darn pointfree challenge has me thinking pointfree everywhere.

Answer 15

Desktop Calculator, A006125, by A__

Original:

1n

Cracked:

1 2lx1+dsx^*n
 ^^^^^^^^^^^

Try it online!

Straightforward implementation.

Answer 16

cQuents, sequence A003617 by Stephen

=10#2:pZ
  ^

Try it online!

Begin with the lowest n+1-digit number, a one followed by n zeroes. The #2 specifies that only the second term of the sequence, which is the sequence definition applied once to the seed, will be printed; this sequence definition simply finds and returns the next prime.

Answer 17

Python 3 -- agtoever

from sympy import isprime, primerange
from itertools import count
r=1
r+=1
while isprime(r-2)or r&1<1and r>3:r+=1
print(r)

Try it online!

Answer 18

MATL, sequence A000796 by Luis Mendo

Original:

'pi'td1_&:_1)Y$J)

Try it online!

Cracked:

'pi'td1_&:|SQ_1)Y$J)
          ^^^

The original author sneakily created the array [-7:-1] and then extracted and negated the first element of it to get 7. He then used that to get the rounded 7'th digit of pi (which is 3) and presented it as the first digit of pi. Adding in |SQ makes the original array all positive, sorts it, and adds one to everything. This means that after everything instead of getting the index 7 it gets the index -2 after one application, -3 after two applications, and so on. The - is important because it tells the Y$ function to not round the digits.

Answer 19

Forth (gforth), A000042, by NieDzejkob

.( 1)1 .
^^^^^

Try it online!

The trivial 1-byter is simply extending the literal. Problem is, that overflows 64 bits as early as the ninteenth digit. Easy fix is to print the single digit repeatedly, right? Yep, but it's not quite that easy. Though tacking 1 . onto the end will indeed print the additional digits we require, they'll be separated by spaces. That ain't gonna work.

Now, according to Wikipedia, ".( (dot-paren) is an immediate word that parses a parenthesis-delimited string and displays it." Fortunately, that displaying has no other weird characters, so using .( to print a single 1 should suffice. And it does. No space is needed after the close-paren, so these five characters (there's a space after the open-paren) can be repeated to our hearts' content. To demonstrate, I've included in TIO an example that would have overflowed a 64-bit int several times over. Works like a charm.

Answer 20

Python 3, A008574 by tsh

print(1*2+2)
       ^^^^

Try it online!

Answer 21

V, A000290, by DJMcMayhem

é*Ä2é*Ø.
  ^^^^

yields the squares from 1.

Try it online!

The base é* inserts * and Ø. counts the number of non-newline characters in the entire buffer. The insertion Ä duplicates the top line to its own line, on which 2é* inserts **. Concatenations of the insertions yield successive odd numbers with the largest at the top. The final Ø. in effect sums the first n odd numbers, hence yielding the n-th square .

Answer 22

Brachylog, sequence A114018 by Unrelated String

Original program:

≜ṗ↔ṗb&w

String to insert:

≜ṗ↔ṗẹbb&w
    ^^

Try it online!

Explanation

Here is first the explanation of the original program (knowing that the sequence used is "least n-digit prime whose digit reversal is also prime")

≜         Assign an integer value to a variable named ? 
            (try 0, then 1, then -1, then 2, etc.)
 ṗ        ? must be prime
  ↔ṗ      The reverse of ? must be prime
    b     Remove the first element of ?
     &    Ignore that we removed that element
      w   Write ? to STDOUT

As you can see, the program is fairly straightforward except for one thing: there is a completely useless b - behead predicate call, that removes the first element of the reverse of our number, with which we don't do anything.

This is a definite clue as to how we can find the string. The idea is that, since we want to increase the length of the number by 1 digit each time we add the string, we need a string that "evaluates" the length of that number somehow, using that useless b.

The solution is to use ẹb: first, ẹ - elements will transform the number into a list of digits; then, b - behead will remove its first element. The trick is that b will fail if the list of digits is empty. So everytime we append a b, we will increase the length of the required number by 1 (because it will fail until the assigned value of ? is high enough to contain sufficiently many digits so that the last b is applied on a list of one digit).

Re-appyling ẹ each time has no effect because it's already a list of digits. We only need it once at the beginning because if we behead a number like 9001 instead of the list of its digits, we will get 001 = 1 which loses information about the number of digits.

Answer 23

VDM-SL, A000312, by Expired Data

let m={1|->{0}}in hd reverse[let x=x+1 in x**x|x in set m(1)&x<card m(1)]
                             ^^^^^^^^^^^^^

Since VDM-SL's let-expressions can re-bind variables which are already bound in an enclosing scope, x**x can be evaluated arbitrarily deeply nested in scopes in which x is one more than in the previous scope, while the original x is still less than the cardinality of m(1).

Answer 24

Haskell, A083318 by xnor

f=length     [2]
        $show

Try it online!

Answer 25

Pure Bash, sequence A010888 by nrgmsbki4spot1

Adds 17 bytes (1 fewer than OP). The added portion is the two lines in the middle, including two newlines.

x=
((x%9))||x=
x+=1
echo ${#x}

Try it online! or check out first 20 iterations.

x+=1 appends 1 to x as a string. Before adding it, x is reset to empty if x modulo 9 is zero.

Answer 26

1+, sequence A000079, by HighlyRadioactive

1"+:
 ^^

" duplicates the (only) number on the stack, and + adds the two numbers on the stack, thus doubling repeatedly to give the powers of 2.

Answer 27

1+, sequence A058891 by HighlyRadioactive

1"*"+:
 ^^^^

"* duplicates the stack and multiplies, thus squaring. "+ duplicates the stack and adds, thus doubling.