Particionamiento recíproco

21

Dado un número n> 77 , escriba un programa o función que encuentre un conjunto de enteros positivos distintos de modo que la suma del conjunto sea igual a n , y la suma de los recíprocos del conjunto sea igual a 1.

Ejemplo para 80:

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

Su programa o función debe (teóricamente) funcionar para cualquier n <2 32 , y no está justificado por errores de redondeo de coma flotante. Tenga en cuenta que existen soluciones para todos n> 77 .


El código más corto en bytes gana.

Hay un incentivo adicional: otorgaré una recompensa a la solución más pequeña que funcione para cualquier ny ejecute log (n) . Para pequeños n debe ser rápido (determinado a mi discreción). Si, esto es posible.

orlp
fuente
3
¿Se garantiza siempre que existe tal descomposición? ¿Algún teorema de teoría de números que lo asegure?
Luis Mendo
Parece que hay para todos n> 77. (No el registro de cada detalle.) Que debería haber sido en la descripción de su reto ...
flawr
1
@flawr, supongo que no incluyó esa referencia porque regala el O(log n)algoritmo.
Peter Taylor
1
Aún así, debería haber mencionado que este conjunto existe para el n dado. (Y me encontré con que el papel en la primera página cuando buscando en Google el título.)
flawr
1
@flawr, me llevó unos 10 minutos encontrarlo. Llegué a él a través de una página sobre fracciones egipcias, y tú me ninja por 10 segundos.
Peter Taylor

Respuestas:

3

Mathematica, 54 bytes

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

Casi tan ineficiente como parece, pero se resuelve n = 78en unos 9 segundos.

El resultado se devuelve como una lista envuelta en una lista única, por ejemplo:

{{45, 12, 9, 5, 4, 3}}
Martin Ender
fuente
Me pregunto si funciona para n muy grande.
njpipeorgan
@njpipeorgan Dado suficiente memoria y tiempo, sí.
Martin Ender
Encontré una estimación de la longitud de IntegerPartition [n], que está en el orden de exp (sqrt (n)), ~ 10 ^ 10 ^ 4.5 para n = 2 ^ 30. Realmente no creo que Mathica (o incluso cualquier arquitectura) pueda mantener la matriz.
njpipeorgan
@njpipeorgan El desafío establece explícitamente que el algoritmo debe funcionar hasta 2 ^ 32 teóricamente , no prácticamente (como se supone generalmente para el golf de código, a menos que el desafío requiera explícitamente que el programa realmente finalice para todas las entradas en una cantidad razonable de tiempo y memoria )
Martin Ender
4

Python 3, 7306 1995 Bytes

Esta solución se ejecuta en complejidad log (n) (por lo que puedo decir).

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]

Puedes probar que se f(2**32 - 1)ejecuta casi al instante

Usé este documento sobre un método para calcularlo. Con este método hay una gran cantidad de datos para los valores predeterminados para n de 78 a 334 sin los números pares después de 168. Quería convertir estos datos en algo pequeño y no conocía ningún buen algoritmo de compresión, así que hecho el mío

La forma en que lo comprimí fue tener una lista de reglas de reemplazo de cadenas. Creé un método que encontró la regla de reemplazo de cadena que reduciría la mayor parte del contenido teniendo en cuenta la definición de la regla. Luego lo apliqué recursivamente hasta que no pude crear más reglas (usé los caracteres gz y AZ). La cadena que hice para reemplazar era una lista separada por comas de los valores hexadecimales para cada uno de los números. En retrospectiva, convertirlos a sus valores hexadecimales puede no haber sido la mejor opción, probablemente sería más corto dejarlos en decimal, ya que tener hexadecimal solo ahorraría para los números de 3 dígitos pero agregaría un 0 para los números de un solo dígito.

La línea donde configuré c puede ver la lista de reglas de reemplazo y el texto en el que se ejecuta. Las reglas también deben aplicarse a la inversa porque algunas reglas incluyen caracteres creados a partir de otras reglas.

También hay numerosos lugares en este código donde probablemente podría reducir la sintaxis, como convertir la lista de listas en una sola lista y luego usar un método diferente para acceder a las reglas para reemplazar el texto con

Cameron Aavik
fuente
1
n=218salidas [2]es lo esperado ??
officialaimm
1
No, veré por qué sucede eso un poco más tarde. Mis disculpas. Podría ser un error en los datos que comprimí inicialmente.
Cameron Aavik
1

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

Horriblemente lento 1 pero se ejecuta en memoria constante. Solución trivial: verifique todas las subsecuencias de [2..n]para suma y suma de recíprocos.

Devolver todas las soluciones en lugar de una es 3 bytes más corto: simplemente elimine el !!0(cuidado: el tiempo de ejecución siempre estará fuera de los gráficos).


1 El tiempo de ejecución depende de qué tan temprano aparezca el resultado en la lista de subsecuencias. La pereza de Haskell detiene la búsqueda si se encuentra la primera coincidencia. Cuando se compila, p 89(result:) se [3,4,6,9,18,21,28]ejecuta en mi computadora portátil (de 4 años) en 35s. Otros valores, incluso los más pequeños, pueden llevar horas.

nimi
fuente
0

Julia, 77 bytes

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

Esta es una función lambda ineficiente que acepta un entero y devuelve una matriz de enteros. Para llamarlo, asígnelo a una variable.

Obtenemos las particiones del entero usando partitions. Luego filtramos el conjunto de particiones solo para aquellos con elementos únicos cuyos recíprocos suman 1. Para asegurar que no ocurra ningún error de redondeo, usamos el Rationaltipo de Julia para construir los recíprocos. filterdevuelve un iterador, por lo que tenemos que collecthacerlo en una matriz. Esto nos da una matriz de matrices (con un solo elemento), por lo que podemos obtener el primer uso [1].

Ahora, cuando digo ineficiente, lo digo en serio. Ejecutar esto para n = 80 toma 39.113 segundos en mi computadora y asigna 13.759 GB de memoria.

Alex A.
fuente