Recover the mutated source code

Question

In a very unusual accident involving a small sample of radium, an electrocuted whale, and three gummy bears, some of The Management™'s source code has been mutated. Little does The Management™'s boss know, it was actually the Cops© who had been responsible, in an attempt to thwart The Management™'s "evil" plans. So the Robbers® have been hired in an attempt to retrieve the original code, because who doesn't like being evil sometimes?

note: This challenge was heavily inspired by Unscramble the Source Code.

Description

This is a cops-and-robbers challenge.

• The cops will write a program (the mutated code) that performs Task #1 (and also write a program that performs Task #2, but is kept secret).
• The robbers will attempt to reverse the "mutation" and change this original code into code that performs Task #2.

In this challenge, Task #1 will be to output the nth prime number, and Task #2 will be to output the nth Fibonacci number (which is somehow evil, according to the Cops© anyway). The Fibonacci sequence is defined as (n=1 → 1; n=2 → 1; n=3 → 2; ...), and the prime numbers are defined as (n=1 → 2; n=2 → 3; n=3 → 5; ...).

The cops' goal is to minimize the difference between the programs that complete Task #1 and Task #2, while preventing the robbers from recreating the code that completes Task #2.

Cop Rules

The cops will write two programs (one that completes Task #1, and one that completes Task #2), and make the following information public:

• The first program (that outputs the nth prime number)
• The Levenshtein edit distance between the first program and the second program
• The programming language that both programs are written in (must be the same language for both programs)

The following restrictions apply to both programs:

• They must be 128 characters in length or less.
• They must only use printable ASCII (plus newlines, which are also allowed).
• They must take less than 10 seconds to run for n=45, and they are not required to produce the correct output for any n>45.
• They must not use any hashing or cryptographic functions.

Robber Rules

The robber will attempt to change the cop's program (which completes Task #1) into a program that completes Task #2 (not necessarily the original program written by the cop) in the edit distance specified by the cop.

An already-cracked submission cannot be cracked again (only the first robber who cracks a submission gets credit).

After cracking a submission, please do the following:

• Post an answer to this challenge's accompanying question (link), providing the language, your solution, and a link to the original answer.
• Leave a comment with the text "Cracked" that links to your posted answer.
• Edit the cop's answer if you have edit privileges (if you do not, either wait until someone else with the required privileges does so for you or suggest an edit).

Scoring

If a cop's program remains uncracked for 1 week, the cop can post the original code that completes Task #2 (in the specified edit distance), and the submission is from then on considered "safe." The safe submission that has the smallest edit distance will win. In the event of a tie, the shortest program (the original that completes Task #1) wins. If two submissions are still tied, the one posted earlier wins.

If a robber successfully cracks a cop's submission, the robber's score goes up by the edit distance of that submission. For example, a robber that cracks a submission with an edit distance of 3 and one with a distance of 5 earns 8 points. The robber with the highest score wins. In the event of a tie, the robber who earned the score first wins.

Leaderboard

1. Ruby, 6 (histocrat)

A small tool to compute the Levenshtein distance

var f=document.getElementById("f"),g=document.getElementById("s"); function h(){var a=f.value,e=g.value;if(128<a.length)a="<span style='color:red'>First program is too long!</span>";else if(128<e.length)a="<span style='color:red'>Second program is too long!</span>";else{if(0===a.length)a=e.length;else if(0===e.length)a=a.length;else{var d=[],b;for(b=0;b<=e.length;b++)d[b]=[b];var c;for(c=0;c<=a.length;c++)d[0][c]=c;for(b=1;b<=e.length;b++)for(c=1;c<=a.length;c++)d[b][c]=e.charAt(b-1)===a.charAt(c-1)?d[b-1][c-1]:Math.min(d[b-1][c-1]+1,Math.min(d[b][c-1]+1,d[b-1][c]+ 1));a=d[e.length][a.length]}a="Distance = <strong>"+a+"</strong>"}document.getElementById("d").innerHTML=a}f.onkeyup=h;g.onkeyup=h;

<h3 id=ft>First program</h3>
<textarea id=f rows=7 cols=80 style="width:100%"></textarea>
<h3 id=st>Second program</h3>
<textarea id=s rows=7 cols=80 style="width:100%"></textarea>
<p id=d></p>

Answer 1

Python 2, distance = 8 [cracked]

from fractions import*
n=input()
k,=P=[2]
while n>len(P):k+=1;z=reduce(lambda x,y:x*y,P,1);P+=[k]*(gcd(z,k)<2)
print P[-1]

Finally got this one under the char limit. Shouldn't be too hard, but I thought the idea was interesting.

---

Intended solution:

from fractions import* n=input() k,=P=[1] while n>len(P):k+=1;z=reduce(lambda x,y:x+y,P[:-1],1);P+=[z]*(gcd(z,k)<2) print P[-1]

The idea was to use that F(n+2) = 1 + (sum over F(k) from k = 1 to n), and the fact that consecutive Fibonacci numbers are coprime. The 1 in the reduce argument was supposed to provide the +1.

Looks like feersum found a different line of attack!

Answer 2

J, distance = 5 [Cracked]

f=:3 :'{.p:|.i.y'

Usage:

> f 45
197

Answer 3

Ruby, distance 6 [safe]

require'prime';p Prime.take(n=gets.to_i)[-1]
#p (((807462154311276410)**n/(5**0.5)).round)

Coming up with pairs of formulas with short edit distances is fun, but it seems like this approach might be more effective/annoying. You may understand exactly what I did, but that doesn't mean you can reverse it.

Solution:

require'prime';p=Prime.take(n=gets.to_i)[-1] p (((0742154311276/4e10)**n/(5**0.5)).round)

Explanation:

The code generates the Golden Ratio to 11 decimal places and uses it to directly calculate the Fibbonaci sequence. It's just enough precision to get the required number of terms right. That part wasn't obfuscated at all, if you happen to know the formula. To make it harder to brute-force reverse my mutations and recover the constant, I used octal notation (the leading 0) and scientific notation (4e10). Dividing by 4e10 rather than 1e11 makes it look more like I'm dividing by something .0 to force float division, when actually anything in scientific notation is for some reason always a Float in Ruby, even when a Bignum might seem to make more sense. I thought I was being clever with the p= stuff, but the way I wrote it you can just delete the p. I could've reduced the distance by 1 and forced the p= solution by using p&& instead of # on the second line, but I didn't think of it.

Answer 4

Python 2 - LD = 13 Cracked

n=1;j=input();
while j>0:
    n+=1;j-=1;
    while~-all(n%i for i in range(2,n)):n+=1;
print n

A nice, easy (hopefully not too easy) one to start things off :)

Looks like it was too easy ;) I feel rather silly that I forgot you could use comments :/

Answer 5

Haskell, distance = 13

import Data.List
x=id=<<snd(mapAccumL(\m n->(,)=<<(++m)$[n|and[n`mod`m1/=0|m1<-m]])[1+1][3..])
main=print.(!!)(0:2:x)=<<readLn

This could be more readable, but the import ate too many bytes, so I had to golf it a bit.

Answer 6

Ruby, distance 14 (Cracked)

p [x=2,y=1,*(1..200).map{|i|y==(y*x**(i-1)+x%2).divmod(i)[x-1]?i:1}].-([x-1])[gets.to_i-1]

Answer 7

CJam, distance 10 (Cracked)

1l~{{)_mp!}g}*

Just put n on STDIN. Test it here.

For reference, the original solution used the rare j.

Original:

T1]l~\{(_j\(j+}j

Answer 8

J, distance = 4 [safe]

f =: 3 :  '{. (p:) (+) / 0 , y - 1x'

Solution:

f =: 3 : '{. 2(x:) (+%) / 0 , y $ 1x'

Method:

Denominator {. 2(x:) of the continued fraction (+%) 1+1/(...(1+1/(1+1/(1+1/(1))))).

Answer 9

Python 3, distance = 14 [cracked]

n = int(input())
P = [2]
k = 2
while n > len(P):
 k += 1
 for x in P:
  if k%x == 0: break
 else: P += [k]
print(k)

I had some spare chars so I put some whitespace in for clarity :)

Answer 10

JAGL Alpha 1.2 - Distance = 16 [Cracked]

T~2S]{]S1{D[dmn}wDS}wSP

Shouldn't be too hard, We will see what happens...

Answer 11

TI-BASIC, distance 38

Input N:{2>L1:For(A,3,E99:If min(1=gcd(A,seq(A,A,2,$(A:A>L1(1+dim(L1:End:L1(N

> represents the STO→ key and $ represents the square root symbol.

Answer 12

Python 2 – distance = 12 [Cracked]

I'm kinda happy with how this turned out.

f=lambda p,i:p if p[45:]else f(p+[i]if all(i%q for q in p[1:])else p,-~i)
print f([1,2,3],2)[input()]

Let's see how long it takes... I assume it'll still be cracked.

Edit: shortened code a tiny bit, no effect on operation/distance.

Intended solution

I tried to go for no comments or newline changes.

f=lambda p,i:p if p[45:]else f(p+[p[i]+p[-2]]if all(i|q for q in p[1:])else p,-~i) print f([1,1,1],2)[input()]

Answer 13

Python 3 - Distance = 14 [Cracked]

---

a,c,n=1,2,int(input())
while n-1:
 c+=1
 while 1!=list(map(c.__mod__,range(2,46))).count(0):
  c,a=a+c,a
 n-=1
print(c)

We'll see how long this lasts...