Partitions réciproques

21

Étant donné un nombre n> 77 , écrivez un programme ou une fonction qui trouve un ensemble d' entiers positifs distincts tels que la somme de l'ensemble est égale à n et la somme des inverses de l'ensemble est égale à 1.

Exemple pour 80:

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

Votre programme ou fonction doit (théoriquement) fonctionner pour tout n <2 32 et n'est pas excusé pour les erreurs d'arrondi à virgule flottante. Notez que des solutions existent pour tous les n> 77 .


Le code le plus court en octets gagne.

Il y a un bonus incitatif: je vais attribuer une prime à la plus petite solution qui fonctionne pour n et exécute log (n) . Pour les petits n il doit être rapide (déterminé à ma discrétion). Oui, c'est possible.

orlp
la source
3
Une telle décomposition est-elle toujours garantie d'exister? Un théorème de théorie des nombres qui assure cela?
Luis Mendo
Il semble qu'il y ait pour tout n> 77. (Je n'ai pas vérifié tous les détails.) Cela aurait dû être dans la description de votre défi ...
flawr
1
@flawr, je suppose qu'il n'a pas inclus cette référence, car cela donne l' O(log n)algorithme.
Peter Taylor
1
Il aurait quand même dû mentionner que cet ensemble existe pour le n donné. (Et j'ai trouvé ce papier sur la première page lors de la recherche sur le titre.)
flawr
1
@flawr, il m'a fallu environ 10 minutes pour le trouver. Je suis arrivé via une page sur les fractions égyptiennes, et vous m'avez ninja de 10 secondes.
Peter Taylor

Réponses:

3

Mathematica, 54 octets

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

À peu près aussi inefficace que possible, mais il se résout n = 78en environ 9 secondes.

Le résultat est renvoyé sous forme de liste enveloppée dans une liste singleton, par exemple:

{{45, 12, 9, 5, 4, 3}}
Martin Ender
la source
Je me demande si cela fonctionne pour un très grand n.
njpipeorgan
@njpipeorgan Avec suffisamment de mémoire et de temps, oui.
Martin Ender
J'ai trouvé une estimation de la longueur de IntegerPartition [n], qui est de l'ordre de exp (sqrt (n)), ~ 10 ^ 10 ^ 4,5 pour n = 2 ^ 30. Je ne crois vraiment pas que mathématique (ou même n'importe quelle architecture) soit capable de contenir le tableau.
njpipeorgan
@njpipeorgan Le défi indique explicitement que l'algorithme doit fonctionner jusqu'à 2 ^ 32 théoriquement , pas pratiquement (comme on le suppose généralement pour le golf de code, à moins que le défi n'exige explicitement que le programme se termine réellement pour toutes les entrées dans une quantité raisonnable de temps et de mémoire ).
Martin Ender
4

Python 3, 7306 1995 octets

Cette solution fonctionne en complexité log (n) (pour autant que je sache).

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]

Vous pouvez tester qui f(2**32 - 1)s'exécute presque instantanément

J'ai utilisé cet article sur une méthode de calcul. Avec cette méthode, il y a une énorme quantité de données pour les valeurs prédéterminées pour n de 78 à 334 sans les nombres pairs après 168. Je voulais transformer ces données en quelque chose de petit et je ne connaissais pas de bons algorithmes de compression, donc j'ai fait le mien.

La façon dont je l'ai compressé était d'avoir une liste de règles de remplacement de chaîne. J'ai créé une méthode qui a trouvé la règle de remplacement de chaîne qui réduirait le plus de contenu en tenant compte de la définition de la règle. J'ai ensuite appliqué récursivement ceci jusqu'à ce que je ne puisse plus créer de règles (j'ai utilisé les caractères gz et AZ). La chaîne que j'ai créée pour remplacer était une liste séparée par des virgules des valeurs hexadécimales pour chacun des nombres. Rétrospectivement, les convertir en leurs valeurs hexadécimales n'a peut-être pas été le choix le plus sage, il serait probablement plus court de les laisser en décimal, car avoir hex ne sauverait que pour les nombres à 3 chiffres mais ajouterait un 0 pour les nombres à un chiffre.

La ligne où je mets c, vous pouvez voir la liste des règles de remplacement et le texte sur lequel il s'exécute. Les règles doivent également être appliquées en sens inverse, car certaines règles incluent des caractères créés à partir d'autres règles.

Il y a aussi de nombreux endroits dans ce code où je pourrais probablement réduire la syntaxe, comme transformer la liste des listes en une seule liste puis utiliser une méthode différente pour accéder aux règles pour remplacer le texte par

Cameron Aavik
la source
1
n=218les sorties [2]sont-elles attendues ??
officialaimm
1
Non, je verrai pourquoi cela se produit un peu plus tard. Mes excuses. Cela pourrait être une erreur dans les données que j'ai compressées initialement.
Cameron Aavik
1

Haskell, 93 octets

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

Horriblement lent 1 mais il fonctionne en mémoire constante. Solution triviale: vérifiez toutes les sous-séquences de [2..n]pour la somme et la somme des inverses.

Renvoyer toutes les solutions au lieu d'une est 3 octets plus court: il suffit de supprimer le !!0(attention: le temps d'exécution sera toujours hors des graphiques).


1 Le temps d'exécution dépend de la précocité du résultat dans la liste des sous-séquences. La paresse de Haskell arrête la recherche si la première correspondance est trouvée. Une fois compilé, p 89(résultat:) [3,4,6,9,18,21,28]fonctionne sur mon ordinateur portable (âgé de 4 ans) en 35s. D'autres valeurs, même plus petites, peuvent prendre des heures.

nimi
la source
0

Julia, 77 octets

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

Il s'agit d'une fonction lambda inefficace qui accepte un entier et renvoie un tableau d'entiers. Pour l'appeler, affectez-le à une variable.

Nous obtenons les partitions de l'entier en utilisant partitions. Nous filtrons ensuite l'ensemble des partitions uniquement pour celles avec des éléments uniques dont les réciproques sont égales à 1. Pour garantir qu'aucune erreur d'arrondi ne se produit, nous utilisons le Rationaltype de Julia pour construire les réciproques. filterrenvoie un itérateur, nous devons donc le placer collectdans un tableau. Cela nous donne un tableau de tableaux (avec un seul élément), afin que nous puissions obtenir la première utilisation [1].

Maintenant, quand je dis inefficace, je le pense. L'exécution de ceci pour n = 80 prend 39,113 secondes sur mon ordinateur et alloue 13,759 Go de mémoire.

Alex A.
la source