Escreva números como a diferença de enésimas potências

24

Desafio

Existem muitos números que podem ser expressos como a diferença de dois quadrados, ou a diferença de dois cubos, ou talvez potências ainda mais altas. Falando em quadrados, existem várias maneiras de escrever um número, digamos 75, como a diferença de 2 quadrados. Você pode escrever:

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

Então, vamos falar sobre o desafio. Primeiro, o usuário digita um número e, em seguida, ele insere um valor para n. Você precisa exibir todas as maneiras pelas quais esse número pode ser escrito na forma de aⁿ - bⁿ.

Entrada e saída

A entrada será o número e o valor de n. Sua saída deve ter todos esses pares de 'a' e 'b', de modo que a condição acima indicada seja atendida. O primeiro número no par deve ser maior que o segundo. Observe que a, b, n e o número de entrada são números inteiros positivos e n> 1 .

Exemplos

50, 2 -> (none)

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

7, 3 -> (2,1)

665, 6 -> (3, 2)

81, 4 -> (none)

Pontuação

Isso é , então o código mais curto vence!

Manish Kundu
fonte

Respostas:

9

Geléia , 8 bytes

p*ƓIFẹ+d

Este é um link monádico que pega o número como argumento e lê n de STDIN.

Experimente online!

Como 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
fonte
6

Haskell , 42 bytes

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

Experimente 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]

Não pode mudar muito mais ...

totalmente humano
fonte
Na verdade, o sinal de igual ==no UniHaskell é um pouco confuso, pois denota congruência na matemática.
usar o seguinte comando
4

05AB1E , 9 bytes

Muito ineficiente para valores de entrada maiores.

LãDImƹQÏ

Experimente online!

Explicação

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
fonte
4

MATL , 11 bytes

t:i^&-!=&fh

Experimente online! Ou verifique todos os casos de teste .

Explicação

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
fonte
4

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]

Experimente online!

Dennis
fonte
2

Gelatina , 10 bytes

*Iċ³
ṗ2çÐf

Uma captura de programa completa ie nque imprime os pares de [b,a]com uma saída vazia quando não há nenhuma.

Experimente online!

Quão?

*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
fonte
11
Certo, tudo bem. Você pode mantê-lo como quiser.
Manish Kundu
2

JavaScript (ES7), 64 bytes

Função recursiva que recebe entradas na sintaxe de currying (n)(p). Retorna uma lista separada por espaços de pares de números inteiros ou uma sequência vazia, se não houver solução. Usa o mesmo algoritmo da resposta Python do user202729 .

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

Ou 60 bytes com matrizes encapsuladas terminadas em 0:

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

Isso produziria [ 9, 7, [ 6, 2, 0 ] ]para f (32) (2) .

Casos de teste

Arnauld
fonte
2

Python 3 , 71 bytes

Obrigado Mr.Xcoder por salvar alguns bytes!

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

Experimente 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]

Experimente online!

O uso da abordagem de força bruta x ^ 2 de totallyhuman realmente salva bytes.

user202729
fonte
77 bytes
Sr. Xcoder
3
Infelizmente, a força bruta é geralmente a abordagem mais curta. : P
totallyhuman 14/01
'b in range (x)' funciona no TIO. Isso gera 67 bytes.
Alix Eisenhardt
@AlixEisenhardt Acho que não .
usar o seguinte comando