introduction

Votre objectif est de trouver le moins de nombres dont vous avez besoin d'ajouter ou de multiplier ensemble pour obtenir la valeur d'entrée, c'est A005245 .

Contribution

Un nombre entier positif N .

Sortie

Le plus petit nombre de ceux qui doivent être ajoutés / multiplié pour obtenir N .

Exemple d'entrée

7

Exemple de sortie

6

Explication

( 1+ 1+ 1) * ( 1+ 1) + 1= 7

Parce que cela en nécessite 6, la sortie est6

Cas de test

 1  1
 2  2
 3  3
 5  5
10  7
20  9
50 12

Comme il s'agit d'un défi de code-golf , le plus petit nombre d'octets gagne.

Python 2 , 74 70 octets

f=lambda n:min([n]+[f(j)+min(n%j*n+f(n/j),f(n-j))for j in range(2,n)])

Essayez-le en ligne!

Version alternative, 59 octets (non vérifié)

f=lambda n:min([n]+[f(j)+f(n/j)+f(n%j)for j in range(2,n)])

Cela fonctionne au moins jusqu'à n = 1 000 000 , mais je dois encore prouver que cela fonctionne pour tous les n positifs .

Essayez-le en ligne!

Gelée , 16 14 octets

Merci Dennis d'avoir économisé 2 octets!

ÆḌḊ,Ṗ߀€+U$FṂo

Essayez-le en ligne!

Explication logique

Étant donné un nombre n :

• Si c'est le cas 1, la réponse est 1. Autrement:

La représentation est soit a + bou a × b, où aet bsont des expressions.

Tenez compte de toutes les valeurs possibles de aet b:

• Si la représentation est a + b, alors aet bsont dans la plage [1 .. n-1].
• Si la représentation est a × b, aet bsont des diviseurs propres nsupérieurs à 1.

Dans les deux cas, la liste [[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]est calculée ( ÆḌḊ,Ṗ), mappez le lien actuel sur chaque nombre ߀€, ajoutez les paires correctes ensemble ( +U$) et obtenez la valeur minimale ( FṂo).

Explication du code

ÆḌḊ,Ṗ߀€+U$FṂo   Main link. Assume n = 10.
ÆḌ       Proper divisors. [1,2,5]
  Ḋ      Ḋequeue, remove the first element. [2,5]
   ,Ṗ    Pair with Ṗop. Auto convert n = 10 to range 
         [1,2,3,4,5,6,7,8,9,10] and remove the last element
         10, get [1,2,3,4,5,6,7,8,9].

߀€      Apply this link over each element.
   +U$   Add with the Upend of itself.

FṂ       Flatten and get the Ṃinimum element.
  o      Logical or with n.
         If the list is empty, minimum returns 0 (falsy), so logical or
         convert it to n.

JavaScript (ES6), 108 96 octets

f=n=>n<6?n:Math.min(...[...Array(n-2)].map((_,i)=>Math.min(f(++i)+f(n-i),n%++i/0||f(i)+f(n/i))))

Très inefficace; Array(n>>1)l'accélère légèrement au prix d'un octet. Explication: n%++iest non nul si in'est pas un facteur, il en n%++i/0est de même Infinity(et donc véridique, et certainement pas minimal) si in'est pas un facteur, mais NaN(et donc falsifié) si iest un facteur. Edit: 12 octets enregistrés avec l'inspiration de @ edc65.

Pari / GP , 66 octets

Un port de la réponse Python de Dennis :

f(n)=vecmin(concat(n,[f(j)+min(n%j*j+f(n\j),f(n-j))|j<-[2..n-1]]))

Essayez-le en ligne!

Pari / GP , 72 octets

Plus long, mais plus efficace:

f(n)=if(n<6,n,vecmin([if(d>1,f(d)+f(n/d),1+f(n-1))|d<-divisors(n),d<n]))

Essayez-le en ligne!

Pari / GP , 213 octets

Edit: j'ai été sévèrement battu .

f(n)={d;n<6&return(n);if(n<=#a,a[n]&return(a[n]),a=vector(n));for(i=1,n-1,a[i]||a[i]=f(i));a[n]=min(vecmin(vector(n\2,k,a[k]+a[n-k])),if(isprime(n),n,vecmin(vector((-1+#d=divisors(n))\2,i,a[d[i+1]]+a[d[#d-i]]))))}

Essayez-le en ligne!

Python 2 , 181 octets

def F(N,n,s="",r=""):
 try:
	if n<1:return(eval(s)==N)*0**(`11`in s or"**"in s)*s
	for c in"()+*1":r=F(N,~-n,s+c)or r
 except:r
 return r
f=lambda N,n=1:F(N,n).count(`1`)or f(N,-~n)

Essayez-le en ligne!

Wolfram Language (Mathematica) , 59 octets

Enregistré 3 octets grâce à Martin Ender. Utilisation du codage CP-1252, où ±est un octet.

±1=1;±n_:=Min[1+±(n-1),±#+±(n/#)&/@Divisors[n][[2;;-2]]]

Essayez-le en ligne!

Perl 5 , -p 78 octets

79 octets en comptage à l'ancienne ( +1pour -p)

Le fait que perl doive utiliser un extra $pour tous les accès scalaires nuit vraiment à la longueur des golfs qui font beaucoup d'arithmétique ...

Cette méthode est principalement similaire aux autres déjà publiées (essayez la multiplication et l'ajout pour construire un nombre cible, prenez le moins cher). Cependant, il ne recuit pas de manière répétée, il peut donc être utilisé pour des entrées relativement importantes.

Il n'essaie pas non plus de minimiser le coût de construction d'un nombre par addition ou par multiplication, car perl 5 n'a pas de tri intégré minet numérique est looooooong (comme le montre le tri toujours dans le code). Au lieu de cela, je suppose simplement que si un nombre est un facteur de la cible, j'utiliserai la multiplication. C'est sûr car si par exemple 3est un facteur de 12(donc il résume le coût de 3et 12/3) plus tard dans la boucle, il considérera 9=12-3ce qui ne sera pas un facteur, donc 9+3avec le même coût que celui qui 3+9sera essayé de toute façon. Cependant, cela peut échouer pour les cibles <= 4(cela ne fonctionne que pour 1et 2). Ajout $_à la liste pour minimiser les correctifs. Ce qui est regrettable car je n'ai pas vraiment besoin de cela pour les cas de base car j'ai déjà initialisé@; avec les valeurs de départ appropriées, donc cela coûte 3 octets.

#!/usr/bin/perl -p
($_)=sort{$a-$b}$_,map{$;[$_]+$;[$'%$_?$'-$_:$'/$_]}//..$_ for@;=0..$_;$_=pop@

Essayez-le en ligne!