24
\$\begingroup\$

Challenge

There are many numbers which can be expressed as the difference of two squares, or as the difference of two cubes, or maybe even higher powers. Talking about squares, there are various ways of writing a number, say 75, as the difference of 2 squares. You can write:

75 = (10)^2 - (5)^2 
   = (14)^2 - (11)^2 
   = (38)^2 - (37)^2         

So let's talk about the challenge. Firstly, the user enters a number and then he enters a value for n. You need to display all the ways in which that number can be written in the form of aⁿ - bⁿ.

Input and Output

The input will be the number and the value of n. Your output shall have all such pairs of 'a' and 'b' such that the above-stated condition is met. The first number in the pair must be larger than the second. Please note that a, b, n and the input number are all positive integers, and n > 1.

Examples

50, 2 -> (none)

32, 2 -> (9,7), (6, 2)

7, 3 -> (2,1)

665, 6 -> (3, 2)

81, 4 -> (none)

Scoring

This is , so the shortest code wins!

\$\endgroup\$

12 Answers 12

9
\$\begingroup\$

Jelly, 8 bytes

p*ƓIFẹ+d

This is a monadic link that takes the number as argument and reads n from STDIN.

Try it online!

How it works

p*ƓIFẹ+d  Main link. Argument: k

p         Cartesian product; yield all pairs [b, a] with b and a in [1, ..., k].
  Ɠ       Get; read an integer n from STDIN.
 *        Power; map each [b, a] to [b**n, a**n].
   I      Increments; map each [b**n, a**n] to [a**n-b**n].
    F     Flatten the resulting list of singleton arrays.
     ẹ    Every; find all indices of k in the list we built.
      +   Add k to the indices to correct the offset.
       d  Divmod; map each index j to [j/k, j%k].
\$\endgroup\$
6
\$\begingroup\$

Haskell, 42 bytes

k#n=[(a,b)|b<-[1..k],a<-[b..k],a^n-b^n==k]

Try it online!

Ungolfed with UniHaskell and -XUnicodeSyntax

import UniHaskell

f     ∷ Int → Int → [(Int, Int)]
f k n = [(a, b) | b ← 1 … k, a ← b … k, a^n - b^n ≡ k]

Can't change much else...

\$\endgroup\$
  • \$\begingroup\$ Actually, the equal sign == in UniHaskell is somewhat confusing, as it denotes congruence in mathematics. \$\endgroup\$ – user202729 Jan 16 '18 at 10:41
4
\$\begingroup\$

05AB1E, 9 bytes

Very inefficient for larger input values.

LãDImƹQÏ

Try it online!

Explanation

L           # range [1 ... input_1]
 ã          # cartesian product with itself
  D         # duplicate
   Im       # raise each to the power of input_2
     Æ      # reduce each pair by subtraction
      ¹QÏ   # keep only values in the first copy which are true in this copy
\$\endgroup\$
4
\$\begingroup\$

MATL, 11 bytes

t:i^&-!=&fh

Try it online! Or verify all test cases.

Explanation

t     % Implicit input: M. Duplicate
:     % Range [1 2 ... M]
i     % Input: n
^     % Power, element-wise. Gives [1^n 2^n ... M^n]
&-    % Matrix of pairwise differences (size n×n)
!     % Transpose. Needed so the two numbers in each pair are sorted as required
=     % Is equal? Element-wise. Gives true for entries of the matrix equal to M
&f    % Row and column indices of true entries
h     % Concatenate horizontally. Implicit display
\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog), 21 bytes

{o/⍨⍵=-/¨⍺*⍨¨o←,⍳2⍴⍵}

Try it online!

Left argument is n.

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

Python 2, 65 bytes

lambda k,n:[(j%k,j/k)for j in range(k,k*k)if(j%k)**n-(j/k)**n==k]

Try it online!

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

Jelly, 10 bytes

*Iċ³
ṗ2çÐf

A full program taking i, and n which prints out the pairs of [b,a] with an empty output when there are none.

Try it online!

How?

*Iċ³ - Link 1, isValid?: pair of +ve integers, [b,a]; +ve integer, n
*    - exponentiate             -> [b^n,a^n]
 I   - incremental differences  -> [a^n-b^n]
   ³ - program's third argument -> i
  ċ  - count occurrences        -> 1 if a^n-b^n == i, otherwise 0

ṗ2çÐf - Main link: +ve integer i, +ve integer n
ṗ2    - second Cartesian power = [[1,1],[1,2],...,[1,i],[2,1],...,[2,i],...,[i,i]]
   Ðf - filter keeping if:
  ç   -   call last link (1) as a dyad (left = one of the pairs, right = n)
      - implicit print of Jelly representation of the list
\$\endgroup\$
  • 1
    \$\begingroup\$ Okay fine. You can keep it as you wish. \$\endgroup\$ – Manish Kundu Jan 14 '18 at 16:41
2
\$\begingroup\$

JavaScript (ES7), 64 bytes

A recursive function taking input in currying syntax (n)(p). Returns a space-separated list of pairs of integers, or an empty string if no solution exists. Uses the same algorithm as user202729's Python answer.

n=>p=>(g=x=>x--?((y=(x**p+n)**(1/p))%1?[]:[y,x]+' ')+g(x):[])(n)

Or 60 bytes with 0-terminated, encapsulated arrays:

n=>p=>(g=x=>x--&&((y=(x**p+n)**(1/p))%1?g(x):[y,x,g(x)]))(n)

This would output [ 9, 7, [ 6, 2, 0 ] ] for f(32)(2).

Test cases

let f =

n=>p=>(g=x=>x--?((y=(x**p+n)**(1/p))%1?[]:[y,x]+' ')+g(x):[])(n)

console.log(f(50)(2))
console.log(f(32)(2))
console.log(f(7)(3))
console.log(f(665)(6))

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

Pyth, 14 bytes

f/.+^RvzTQ^SQ2

Try it here!, Alternative!

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

Python 3, 71 bytes

Thanks Mr.Xcoder for saving some bytes!

lambda x,n:[(a,b)for b in range(1,x)for a in[(b**n+x)**(1/n)]if a%1==0]

Try it online!


Python 3, 69 bytes

lambda x,n:[(a,b)for b in range(1,x)for a in range(x)if a**n-b**n==x]

Try it online!

Use totallyhuman's x^2 brute force approach actually saves bytes.

\$\endgroup\$
  • \$\begingroup\$ 77 bytes \$\endgroup\$ – Mr. Xcoder Jan 14 '18 at 15:18
  • 3
    \$\begingroup\$ Unfortunately, brute forcing is usually the shortest approach. :P \$\endgroup\$ – totallyhuman Jan 14 '18 at 15:34
  • \$\begingroup\$ 'b in range(x)' works on TIO. That makes 67 bytes. \$\endgroup\$ – Alix Eisenhardt Jan 15 '18 at 12:16
  • \$\begingroup\$ @AlixEisenhardt I don't think so. \$\endgroup\$ – user202729 Jan 15 '18 at 12:55
1
\$\begingroup\$

Octave, 80 bytes

function r=f(n,p)[X Y]=meshgrid(1:n,1:n);r=[X(:) Y(:)](X(:).^p-Y(:).^p==n,:);end

Try it online!

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

Perl 6, 45 bytes

->\k,\n{grep * **n-* **n==k,flat 1..k X 1..k}

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.