Dado um número n> 77 , escreva um programa ou função que encontre um conjunto de números inteiros positivos distintos, de modo que a soma do conjunto seja igual a n e a soma dos recíprocos do conjunto seja igual a 1.

Exemplo para 80:

80 = 2 + 4 + 10 + 15 + 21 + 28 ⟶ 1/2 + 1/4 + 1/10 + 1/15 + 1/21 + 1/28 = 1

Seu programa ou função deve (teoricamente) funcionar para qualquer n <2 ³² e não é desculpa para erros de arredondamento de ponto flutuante. Observe que existem soluções para todos os n> 77 .

O menor código em bytes vence.

Há um incentivo de bônus: concederei uma recompensa à menor solução que funcione para qualquer n e execute log (n) . Para n pequeno , deve ser rápido (determinado a meu critério). Sim, isso é possível.

Mathematica, 54 bytes

Select[IntegerPartitions@#,Unequal@@#&&Tr[1/#]==1&,1]&

Tão ineficiente quanto possível, mas resolve n = 78em cerca de 9 segundos.

O resultado é retornado como uma lista agrupada em uma lista singleton, por exemplo:

{{45, 12, 9, 5, 4, 3}}

Python 3, 7306 1995 Bytes

Esta solução é executada com complexidade de log (n) (até onde eu sei).

def i(s,t):
 for n in s[::-1]:t=t.replace(*n)
 return [[]]*78+[list(bytearray.fromhex(a))for a in t.split(",")]
def f(n):
 g,h=lambda c,n:c+[[[2],[3,7,78,91]][n[len(c)]%2]+[i*2for i in c[-1]]],lambda n:[]if n<78 else h((n-[2,179][n%2])//2)+[n]
 v=h(n);c=[i([['g',',03040'],['h',',,0306080'],['i',',020'],['j','b0c1'],['k','21'],['l','60'],['m','30'],['n','141'],['o','k24'],['p',',g'],['q','618'],['r','0c0'],['s','1e'],['t',',0ml'],['u','283c'],['v','e0f1'],['w','2a38'],['x','80'],['y','a0'],['z','01'],['A','50'],['B','24'],['C','i40'],['D','plb1'],['E','gl'],['F','48'],['G','bre1'],['H','28'],['I','6k'],['J','416s'],['K',',040Al'],['L','90'],['M','2a'],['N','54'],['O','k6o'],['P','3c'],['Q','il'],['R','18'],['S','px'],['T','im'],['U','70'],['V','b1'],['W','23'],['X','pj'],['Y','hj'],['Z','0n']],'020lxycHTaRHCyf1517CyfneC91k51cCLdneQU912MCyf0dBiALyf2dClfPEyfneT9s2dELdneEjIgmLydHg5rd14BKLardsE3n8sQ9rd1517Q9rdneplmdRBgUmcRMC5sPEyf102bgA6sPE91z2miAj41IQmc0dRBQUen7spl31z82bT9RFT3wE7neMgmyf0dRBgUmaHMELc1b36EUdBMQLyfs2d,C710M2bgLardRHT3BFQ9rf0dPQ7rdBMQm9Rs2d,0mAl9100d142bE710M2bQmc0fRPtxarfn8sEc1k4sBTfnePExcwtxarf1k8BExcuT3kkT91663C51964,0mAl71k4BMELe12NTcRwQjOT820ltmarf1z8mExeRNCqBFtmyjIHKLa100ds2bQU91bM36garf1k4sBTcRBFgxarfwE91keB2dtUxcn8sME9nbs36gm9rduC5R78,0mAUyf0d14BME91kbB36QLc12AB2dgyjqkHEUeMNT9157eQU9RMFT8s78C8neuixLc1zk4AtUxc1z8Mmt8re0fn8sWhLyc1bH36pl8neu,Kxycsw,iAxc1420l,K8ren8NS9n81bs36hc0vz8WmYzqkmhyv2WBHhyVOHXkJoSjIwSjIuSvz4WASVZIAXZ6skmSj6oFXzOmplvcsW46D61csk46plv8WBFDqoF,tarvk8WBH,tyjkqoHhGqkN,tmvZ8sWmhVZqskmpc0vZ8WAXZqkAplbnImASbn6skwSbn6skuSVOwSVOupGONSbn6soFpyVkJk5aSj6sk78YJkuDkIP5aYOuhvzk4WBAhVzk416oA,tyjkJ265a,,0mxyjk41q53sYzIHmPXkqowXkqouhyVqoHFYz6omFhb0e1zqkmNSyVIP78YJ20klpyVOHwYk620olpc0vz8WBmFXzqomFpG61ckH38PhyjIP78Yz620kmlDkImLDzINUhGIuNDzIA78hb0e1ZIANYkqk366chG6oFNXkJkP5ahVZ6somFSb0e1620kNlhVk41qomADzIFLXkqso78pGqoFNXzkImP5a,tyjk620oHlhG620kNlXzqskm78,tjZqskHmPYqouFD6sku78YzqkNU,tjZqsomF')[v[0]]]
 for o in range(len(v)-1):c=g(c,v)
 return c[-1]

Você pode testar a f(2**32 - 1)execução quase instantânea

eu usei este artigo em um método para calculá-lo. Com esse método, há uma grande quantidade de dados para os valores predeterminados para n de 78 a 334 sem os números pares depois de 168. Eu queria transformar esses dados em algo pequeno e não conhecia nenhum bom algoritmo de compactação. fez o meu.

A maneira como eu o compactava era ter uma lista de regras de substituição de string. Eu criei um método que encontrou a regra de substituição de string que reduziria o máximo de conteúdo, levando em consideração a definição da regra. Apliquei isso recursivamente até não poder mais criar regras (usei os caracteres gz e AZ). A sequência que fiz para substituir foi uma lista separada por vírgula dos valores hexadecimais para cada um dos números. Em retrospecto, convertê-los em seus valores hexadecimais pode não ter sido a escolha mais sábia, provavelmente seria mais curto deixá-los em decimal, pois o hexadecimal salvaria apenas os números de 3 dígitos, mas adicionaria 0 para os números de um dígito.

Na linha em que defino c, você pode ver a lista de regras de substituição e o texto em que é executado. As regras também precisam ser aplicadas ao contrário, porque algumas regras incluem caracteres criados a partir de outras regras.

Existem também vários lugares nesse código em que eu provavelmente poderia reduzir a sintaxe, como transformar a lista de listas em uma única lista e, em seguida, usar um método diferente para acessar as regras para substituir o texto por

Haskell, 93 bytes

import Data.List
import Data.Ratio
p n=[x|x<-subsequences[2..n],sum x==n,1==sum(map(1%)x)]!!0

Horrivelmente lento ^1, mas roda em memória constante. Solução trivial: verifique todas as subsequências de [2..n]soma e soma de recíprocos.

Retornar todas as soluções em vez de uma é 3 bytes mais curto: basta remover o !!0(cuidado: o tempo de execução estará sempre fora dos gráficos).

¹ O tempo de execução depende de quão cedo o resultado aparece na lista de subsequências. A preguiça de Haskell interrompe a busca se a primeira correspondência for encontrada. Quando compilado, p 89(resultado [3,4,6,9,18,21,28]:) é executado no meu laptop (de 4 anos) aos 35 anos. Outros valores, ainda menores, podem levar horas.

Julia, 77 bytes

n->collect(filter(i->i==∪(i)&&sum(j->Rational(1,j),i)==1,partitions(n)))[1]

Esta é uma função lambda ineficiente que aceita um número inteiro e retorna um array inteiro. Para chamá-lo, atribua-o a uma variável.

Nós obtemos as partições do número inteiro usando partitions. Em seguida, filtramos o conjunto de partições apenas para aqueles com elementos exclusivos cujas recíprocas somam 1. Para garantir que nenhum erro de arredondamento ocorra, usamos o Rationaltipo de Julia para construir as recíprocas. filterretorna um iterador, portanto, temos que fazê- collectlo em uma matriz. Isso nos fornece uma matriz de matrizes (com apenas um único elemento), para que possamos obter o primeiro uso [1].

Agora, quando digo ineficiente, quero dizer isso. A execução disso para n = 80 leva 39,113 segundos no meu computador e aloca 13,759 GB de memória.