Escribir números como una diferencia de enésimas potencias

24

Reto

Hay muchos números que pueden expresarse como la diferencia de dos cuadrados, o como la diferencia de dos cubos, o tal vez incluso potencias más altas. Hablando de cuadrados, hay varias formas de escribir un número, digamos 75, como la diferencia de 2 cuadrados. Puedes escribir:

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

Entonces hablemos del desafío. En primer lugar, el usuario ingresa un número y luego ingresa un valor para n. Debe mostrar todas las formas en que se puede escribir ese número en forma de aⁿ - bⁿ.

Entrada y salida

La entrada será el número y el valor de n. Su salida tendrá todos esos pares de 'a' y 'b' de manera que se cumpla la condición mencionada anteriormente. El primer número del par debe ser mayor que el segundo. Tenga en cuenta que a, b, n y el número de entrada son todos enteros positivos yn> 1 .

Ejemplos

50, 2 -> (none)

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

7, 3 -> (2,1)

665, 6 -> (3, 2)

81, 4 -> (none)

Tanteo

Este es el , por lo que gana el código más corto.

Manish Kundu
fuente

Respuestas:

9

Jalea , 8 bytes

p*ƓIFẹ+d

Este es un enlace monádico que toma el número como argumento y lee n de STDIN.

Pruébalo en línea!

Cómo funciona

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].
Dennis
fuente
6

Haskell , 42 bytes

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

Pruébalo en línea!

Ungolfed con UniHaskell y-XUnicodeSyntax

import UniHaskell

f      Int  Int  [(Int, Int)]
f k n = [(a, b) | b  1  k, a  b  k, a^n - b^n  k]

No puedo cambiar mucho más ...

totalmente humano
fuente
En realidad, el signo igual ==en UniHaskell es algo confuso, ya que denota congruencia en matemáticas.
user202729
4

05AB1E , 9 bytes

Muy ineficiente para valores de entrada más grandes.

LãDImƹQÏ

Pruébalo en línea!

Explicación

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
Emigna
fuente
4

MATL , 11 bytes

t:i^&-!=&fh

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

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
Luis Mendo
fuente
2

Jalea , 10 bytes

*Iċ³
ṗ2çÐf

Un programa completo que toma i, y nque imprime los pares [b,a]con una salida vacía cuando no hay ninguno.

Pruébalo en línea!

¿Cómo?

*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
Jonathan Allan
fuente
1
Bien vale. Puedes mantenerlo como quieras.
Manish Kundu
2

JavaScript (ES7), 64 bytes

Una función recursiva que toma datos en la sintaxis de curry (n)(p). Devuelve una lista de pares de enteros separados por espacios, o una cadena vacía si no existe una solución. Utiliza el mismo algoritmo que la respuesta Python de user202729 .

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

O 60 bytes con matrices encapsuladas terminadas en 0:

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

Esto daría salida [ 9, 7, [ 6, 2, 0 ] ]para f (32) (2) .

Casos de prueba

Arnauld
fuente
2

Python 3 , 71 bytes

¡Gracias Mr.Xcoder por guardar algunos bytes!

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

Pruébalo en línea!


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]

Pruébalo en línea!

Usar el enfoque de fuerza bruta x ^ 2 de humanhuman realmente ahorra bytes.

usuario202729
fuente
77 bytes
Sr. Xcoder
3
Desafortunadamente, el forzamiento bruto suele ser el enfoque más corto. : P
totalmente humano
'b in range (x)' funciona en TIO. Eso hace 67 bytes.
Alix Eisenhardt
@AlixEisenhardt No lo creo .
user202729