In this challenge we try to solve two important problems at once. They are:

1. Given integers $$\a\$$ and $$\b\$$, tell if $$\a^b-1\$$ is a prime number.
2. Given integers $$\a\$$ and $$\b\$$, return $$\a\choose b\$$.

Specifically, you must write two programs, one that does the first task and one that does the other. As we want to solve both problems at once, it is encouraged to use a same piece of code in both programs.

## Scoring

The score of an answer is the Levenshtein distance between the two programs. Lower score is better. In case of a tie, the answer with the shortest combined code of the two programs wins. You can use this script to calculate the score of your solution.

## Rules

1. You must write two programs in the same language that solve the tasks described above. You can use any I/O methods you want. For task 1, you can return a truthy/falsy value or choose two values to mean true and false and return them accordingly. Eg. you can choose that "prime" means true and "not prime" means false.

2. The algorithms you use must work for all possible inputs, but it is OK if the code fails for large numbers due to limitations of the used number type. You can assume that the input is valid.

3. No subset of the program must solve the problem, ie. the code must not work if any character(s) are removed. For example, the following code is not valid, because it is possible to remove the unused else-block without breaking the program:

 if (1) { /* change to 0 to get the second program*/
...
} else {
...
}

4. Standard loopholes are not allowed.

## Test cases

### $$\a^b-1\$$ is prime?

a b
1 1 false
2 3 true
5 2 false
2 5 true
4 3 false
2 7 true


### $$\a\choose b\$$

a b nCr(a,b)
1 1 1
5 2 10
4 3 4
10 7 120
12 5 792

• This may be handy to compute Levenshtein distance Apr 2, 2017 at 16:08
• The idea is nice, but I think you'll still get solutions with Levenshtein distance 1 that manage to prevent modifications to unused parts one way or another and then effectively result in the structure you want to prohibit. Apr 2, 2017 at 16:13
• @LuisMendo The issue is that many of those solutions are really slow. You can use this Mathics script instead. Apr 2, 2017 at 16:31
• I think a better metric would have been the Levenshtein distance divided by the total length of the two programs. Apr 2, 2017 at 21:06
• @GregMartin Wouldn't that result in code bowling? It is possible to artificially make programs larger and still claim that they don't have any unnecessary code. Apr 3, 2017 at 6:12

# Ruby, Distance 1, Combined Length 194

Prime check:

->a,b{s='[(a**b-1).prime?,(1..b).inject(1){|m,i|(a+1-i)/i*m}]';require'math'<<s.size*2;eval s}


Try it online!

nCr:

->a,b{s='[(a**b-1).prime?,(1..b).inject(1){|m,i|(a+1-i)/i*m}]';require'math'<<s.size*2;eval s}


Try it online!

As predicted in the comments, some jerk always has to go against the spirit of the problem. It was fun finding a way to work around it, though! Here's how it works: We have two separate solutions to the problems. We run both, put them into an array, and then either choose the 0th element or the 1st, for an edit distance of 1. This would ordinarily be illegal, since you could just delete everything but the calculation you wanted and it would still work. However, each code snippet is written to rely on the loading of the same standard library, 'mathn':

• The first uses its builtin prime?
• The second relies on mathn changing how division works--before loading it, 3/4 evaluates to 0, while afterwards it evaluates to the fraction (3/4). Since the intermediate result of (a+1-i)/i is not always a whole number, the overall result is wrong without the library.

Now we just need to make loading the library contingent on the rest of the code being unmodified. We do this by generating the name mathn using the character length of the rest of the main code: the combined calculation has length 55, which doubled to 110 is the ASCII value of 'n'. So concatenating this onto the string 'math' gives the desired library.

As a bonus, introducing the library dependencies also makes the code run in a reasonable amount of time. In particular, the naive approach to nCr wouldn't generate fractional intermediate results.

# MATLAB, distance 10

Primality:

function x=f(a,b);x=isprime(a^b-1);


nCr:

function x=f(a,b);x=nchoosek(a,b);

• That's the built-in I was searching for! Apr 2, 2017 at 16:49

# PHP, distance 29

a^b-1 prints 0 for true and any integer value > 0 for false

[,$a,$b]=$argv;for($c=-$i=1;$i<=$d=$a**$b-1;$d%++$i?:$c++);echo$c;  nCr(a,b) [,$a,$b]=$argv;for($c=$i=1;$i<=$a;$c*=$i**(1-($i<=$a-$b)-($i<=$b)),$i++);echo$c;  ## PHP, distance 36 a^b-1 prints 1 for true nothing for false [,$a,$b]=$argv;for($c=-1,$i=1;$i<=$d=-1+$a**$b;)$d%++$i?:$c++;echo$c<1;


nCr(a,b)

[,$a,$b]=$argv;for($c=$d=$i=1;$i<=$a;$c*=$i++)$d*=$i**(($i<=$a-$b)+($i<=$b));echo$c/$d;  # 05AB1E, distance 3 nCr sc  Try it online! isPrime(a^b-1) m<p  Try it online! # Stacked, distance 13 [([@.!]$/{%y!x y-!*})fork!]
[^#-:([]1/$%{!n 1-!})fork!=]  Try it online! The first calculates nCr, the second primality, using Wilson's theorem. (f g h) fork! pops N args from the stack (call them a0 ... aN) and applies a0 ... aN f a0 ... aN h g. For the first program: [([@.!]$/{%y!x y-!*})fork!]
[(                  )fork!]  apply the fork of:
[@.!]                      equiv. { x y : x ! } => x!
$/ divided by {% } two-arg function y! y! x y- (x - y)! * *  And for the second: [^#-:([]1/$%{!n 1-!})fork!=]
[^                         ]  exponentiate  (a^b)
#-                          decrement     (a^b-1)
:                         duplicate     (a^b-1 a^b-1)
(              )fork!    apply the fork to:
[]1/                    1-arg identity function
$% modulus by {! } 1-arg with n: n 1- (n-1) ! ! = check for equality  # Python 2, distance 15, length 172 ### Task 1 D=lambda k:max(k-1,1) P=lambda n,k=0:n<k or P(n-1,k)*n/k lambda a,b:P(a**b-2)**2%D(a**b)  ### Task 2 D=lambda k:max(k-1,1) P=lambda n,k=1:n<k or P(n-1,D(k))*n/k lambda a,b:P(a,b)/P(a-b)  Try it online! # Mathematica, distance 10 Task 1: PrimeQ[#2^#-1]& Task 2: Binomial[#2,#]& Both functions take the inputs in the order b,a. # Javascript ES7, distance 14 Thanks @Conor O'Brien for reducing the distance by 7 Primality: f=x=>y=>{t=x**y-1;s=1;for(i=2;i<t;i++){if(!t%i)s=i-i}return s}  Returns 1 if prime returns 0 if not prime. Incredibly inefficient prime check, checks the number modulo every number smaller than it and greater than 1... nCr: f=x=>y=>{t=x+1;s=1;for(i=1;i<t;i++){if(y<i)s*=i/(i-y)}return s}  Multiplies 1 by each number from y+1 to x and divides by each number from 1 to x-y (x!/y!)/(x-y)! • Changing the second program to f=x=>y=>{t=x+1;s=1;for(i=1;i<t;i++){if(y<i)s*=i/(i-y)}return s} gives edit distance 14. Try it online! Apr 3, 2017 at 14:27 # Octave, distance 1716 15 ### nCr a=input("");b=input("");f=@(x)factorial(x);printf("%d",f(a)/f(b)/f(a-b))  Try it online! ### isprime(a^b-1) a=input("");b=input("");f=@(x)isprime(x);printf("%d",f(a^b-f(8-6)))  Try it online! I am not very fluent in Octave, so I don't know if there is a builtin to calculate nCr. # MATL, distance 4, length 6 ### Tell if a^b-1 is prime: ^qZq  Try it online! ### Compute nCr(a,b): Xn  Try it online! ## How it works ### Tell if a^b-1 is prime: ^ % Power with implicit inputs q % Subtract 1 Zq % Is prime? Implicit display  ### Compute nCr(a,b): Xn % nchoosek with implicit inputs. Implicit display  # Pyth, distance 4, total length 8 ## Primality of a^b-1 P_t^F  Try it online! ## nCr(a, b) .cF  Try it online! Both take input as tuples/lists of integers (e.g. (1,2)). # PHP, distance 14 Writing a program with two functions and only calling one of them would lead to a distance of 1, but it´d be too lame. Prime Test, 100 bytes: [,$a,$b]=$argv;function f($n){for($i=$n;--$i>0&&$n%$i;);return$i==1;}echo f($a**$b*-1)*(1|f($a-$b));  nCr, 98 bytes: [,$a,$b]=$argv;function f($n){for($i=$n;--$i>0&&$n*=$i;);return$n*=1;}echo f($a)/(f($b)*f($a-\$b));


# Jelly, distance 4, length 5

*’ÆP


c


Try it online!

## How it works

*’ÆP  Main link. Argument: a, b

*     Yield a**b.
’    Decrement; yield a**b-1.
ÆP  Test the result for primality.


c     nCr atom


# JavaScript, Score:1, Length:144142126 117

function(a,b){s="a=Math.pow(a,b)-t;for(b=2;a%b++;);b>a1for(;b;)t=t*a--/b--";t=s.length-56;return eval(s.split(1))}


function(a,b){s="a=Math.pow(a,b)-s.length+79;for(b=2;a%b++;);b>a1for(t=s.length-79;b;)t=t*a--/b--";return eval(s.split(1))}

function A(a,b){a=Math.pow(a,b)-(B+0).length+63;for(b=2;a%b++;);return b>a;}
function B(a,b){for(t=(A+0).length-76;b;)t=t*a--/b--;return t;}
F=A


Both subroutines use the other one's length to calculate its own constant, so no char can be removed