Introducción

Su objetivo es encontrar la menor cantidad de unidades que necesita sumar o multiplicar para obtener el valor de entrada, esto es A005245 .

Entrada

Un número entero positivo N .

Salida

El número más pequeño de los que hay que sumar / multiplica para obtener N .

Entrada de muestra

7 7

Salida de muestra

6 6

Explicación

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

Debido a que esto requiere 6unos, la salida es6

Casos de prueba

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

Como se trata de un desafío de código de golf , gana el menor número de bytes.

Python 2 , 74 70 bytes

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

Pruébalo en línea!

Versión alternativa, 59 bytes (sin verificar)

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

Esto funciona al menos hasta n = 1,000,000 , pero todavía tengo que demostrar que funciona para todos los n positivos .

Pruébalo en línea!

Jalea , 16 14 bytes

¡Gracias Dennis por guardar 2 bytes!

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

Pruébalo en línea!

Explicación lógica

Dado un número n :

• Si es así 1, la respuesta es 1. De otra manera:

La representación es a + bo a × b, where ay bson expresiones.

Considere todos los valores posibles de ay b:

• Si la representación es a + b, entonces ay bestán dentro del rango [1 .. n-1].
• Si la representación es a × b, ay bson divisores propios de nmayor que 1.

En ambos casos, [[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]se calcula la lista ( ÆḌḊ,Ṗ), asigna el enlace actual sobre cada número ߀€, agrega los pares correctos ( +U$) y obtén el valor mínimo ( FṂo).

Explicación del código

ÆḌḊ,Ṗ߀€+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 bytes

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))))

Muy ineficiente; Array(n>>1)lo acelera ligeramente a un costo de un byte. Explicación: n%++ino es cero si ino es un factor, también lo n%++i/0es Infinity(y, por lo tanto, es verdad, y definitivamente no es mínimo) si ino es un factor, pero NaN(y por lo tanto es falso) si ies un factor. Editar: guardado 12 bytes con inspiración de @ edc65.

Pari / GP , 66 bytes

Un puerto de la respuesta Python de Dennis :

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

Pruébalo en línea!

Pari / GP , 72 bytes

Más largo, pero más eficiente:

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

Pruébalo en línea!

Pari / GP , 213 bytes

Editar: He sido severamente golpeado .

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]]))))}

Pruébalo en línea!

Python 2 , 181 bytes

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)

Pruébalo en línea!

Wolfram Language (Mathematica) , 59 bytes

Guardado 3 bytes gracias a Martin Ender. Usando la codificación CP-1252, donde ±hay un byte.

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

Pruébalo en línea!

Perl 5 , -p 78 bytes

79 bytes en conteo de estilo antiguo ( +1para -p)

El hecho de que Perl deba usar un extra $para todo acceso escalar realmente perjudica la longitud de los campos de golf que hacen mucha aritmética ...

Este método es principalmente como los otros ya publicados (intente la multiplicación y la suma para construir un número objetivo, tome el más barato). Sin embargo, no se repite repetidamente, por lo que puede usarse para entradas relativamente grandes.

Tampoco trata de minimizar el costo de construir un número mediante la suma o la multiplicación porque perl 5 no tiene incorporado miny la ordenación numérica es muuuuuuy larga (como se ve en la ordenación aún en el código). En cambio, supongo que si un número es un factor del objetivo, usaré la multiplicación. Eso es seguro ya que si, por ejemplo, 3es un factor de 12(por lo tanto, suma el costo de 3y 12/3) más adelante en el ciclo, considerará 9=12-3cuál no será un factor, por lo que 9+3con el mismo costo que se 3+9probará de todos modos. Sin embargo, eso puede fallar para los objetivos <= 4(solo lo hace para 1y 2). Agregar $_a la lista para minimizar las correcciones que. Lo cual es lamentable ya que en realidad no lo necesito para los casos base porque ya lo inicializo@; con los valores iniciales adecuados, por lo que cuesta 3 bytes.

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

Pruébalo en línea!