Reuse your code!

Question

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

Given integers \$a\$ and \$b\$, tell if \$a^b-1\$ is a prime number.
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

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.
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.
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 {
     ...
 }
```
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

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. — Martin Ender, 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. — Martin Ender, 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. — Greg Martin, 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. — fergusq, Apr 3, 2017 at 6:12

histocrat · Accepted Answer · 2017-04-29 14:32:23Z

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}][0]';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}][1]';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.

Steadybox · Accepted Answer · 2017-04-02 16:55:14Z

7

MATLAB, distance 10

Primality:

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

nCr:

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

edited Apr 2, 2017 at 16:55

answered Apr 2, 2017 at 16:45

Steadybox

16.5k5 gold badges40 silver badges84 bronze badges

6

\$\begingroup\$ That's the built-in I was searching for! \$\endgroup\$
– user41805
Apr 2, 2017 at 16:49

Add a comment |

Jörg Hülsermann · Accepted Answer · 2017-04-02 22:07:03Z

7

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;

edited Apr 2, 2017 at 22:07

answered Apr 2, 2017 at 18:42

Jörg Hülsermann

13.3k3 gold badges14 silver badges36 bronze badges

Add a comment |

Emigna · Accepted Answer · 2017-04-02 17:00:35Z

5

05AB1E, distance 3

nCr

sc

Try it online!

isPrime(a^b-1)

m<p

Try it online!

answered Apr 2, 2017 at 17:00

Emigna

52.9k5 gold badges42 silver badges162 bronze badges

Add a comment |

Conor O'Brien · Accepted Answer · 2017-04-03 16:00:25Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

4

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 3, 2017 at 20:19

Dennis

210k41 gold badges368 silver badges819 bronze badges

Add a comment |

Greg Martin · Accepted Answer · 2017-04-03 08:35:14Z

3

Mathematica, distance 10

Task 1: PrimeQ[#2^#-1]&

Task 2: Binomial[#2,#]&

Both functions take the inputs in the order b,a.

edited Apr 3, 2017 at 8:35

answered Apr 2, 2017 at 21:09

Greg Martin

15.4k4 gold badges19 silver badges69 bronze badges

Add a comment |

fəˈnɛtɪk · Accepted Answer · 2017-04-04 19:28:51Z

3

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)!

edited Apr 4, 2017 at 19:28

answered Apr 3, 2017 at 13:52

fəˈnɛtɪk

4,2042 gold badges13 silver badges40 bronze badges

\$\begingroup\$ 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! \$\endgroup\$
– Conor O'Brien
Apr 3, 2017 at 14:27

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Octave, distance 17 16 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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 2, 2017 at 16:41

user41805

13.1k6 gold badges40 silver badges87 bronze badges

Add a comment |

Luis Mendo · Accepted Answer · 2017-04-03 12:10:40Z

1

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

edited Apr 3, 2017 at 12:10

answered Apr 2, 2017 at 16:12

Luis Mendo

104k9 gold badges132 silver badges365 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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)).

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 3, 2017 at 19:01

notjagan

4,2018 silver badges27 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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));

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Nov 29, 2017 at 9:03

Titus

14.6k1 gold badge23 silver badges41 bronze badges

Add a comment |

Dennis · Accepted Answer · 2017-04-02 20:30:23Z

0

Jelly, distance 4, length 5

Task 1

*’ÆP

Task 2

Try it online!

How it works

Task 1

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

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

Task 2

c     nCr atom

edited Apr 2, 2017 at 20:30

answered Apr 2, 2017 at 20:20

Dennis

210k41 gold badges368 silver badges819 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2017-11-29 08:19:37Z

JavaScript, Score:1, Length:144 142 126 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)[0])}

~~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)[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~~

Reuse your code!

Scoring

Rules

Test cases

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

\$a\choose b\$

14 Answers 14

Ruby, Distance 1, Combined Length 194

MATLAB, distance 10

PHP, distance 29

PHP, distance 36

05AB1E, distance 3

Stacked, distance 13

Python 2, distance 15, length 172

Task 1

Task 2

Mathematica, distance 10

Javascript ES7, distance 14

Octave, distance 17 16 15

nCr

isprime(a^b-1)

MATL, distance 4, length 6

Tell if a^b-1 is prime:

Compute nCr(a,b):

How it works

Tell if a^b-1 is prime:

Compute nCr(a,b):

Pyth, distance 4, total length 8

Primality of a^b-1

nCr(a, b)

PHP, distance 14

Jelly, distance 4, length 5

Task 1

Task 2

How it works

Task 1

Task 2

JavaScript, Score:1, Length:144 142 126 117

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-challengenumber-theoryprimescombinatoricssource-layout or ask your own question.

Linked

Related

Hot Network Questions

`isprime(a^b-1)`

Tell if `a^b-1` is prime:

Compute `nCr(a,b)`:

Tell if `a^b-1` is prime:

Compute `nCr(a,b)`:

Primality of `a^b-1`

Not the answer you're looking for? Browse other questions tagged
code-challenge
number-theory
primes
combinatorics
source-layout
or ask your own question.