Implemente essa relação de recorrência como uma função ou programa que insere e gera um número inteiro não negativo:

• F (0) = 0

• F (N) = o menor número inteiro maior que F (N-1), de modo que a soma e / ou produto de seus dígitos da base 10 seja N

N é a entrada do seu programa e F (N) é a sua saída.

Para ficar claro, a soma dos dígitos em um número como 913 é 9 + 1 + 3 = 13. O produto é 9 × 1 × 3 = 27. Para números de um dígito, a soma e o produto são o mesmo número. Os números que contêm um 0, obviamente, têm o produto 0.

Os resultados através de F (70) são:

N F(N)
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 19
11 29
12 34
13 49
14 59
15 69
16 79
17 89
18 92
19 199
20 225
21 317
22 499
23 599
24 614
25 799
26 899
27 913
28 1147
29 2999
30 3125
31 4999
32 5999
33 6999
34 7999
35 8999
36 9114
37 19999
38 29999
39 39999
40 41125
41 59999
42 61117
43 79999
44 89999
45 91115
46 199999
47 299999
48 311128
49 499999
50 511125
51 699999
52 799999
53 899999
54 911116
55 1999999
56 2111147
57 3999999
58 4999999
59 5999999
60 6111125
61 7999999
62 8999999
63 9111117
64 11111188
65 29999999
66 39999999
67 49999999
68 59999999
69 69999999
70 71111125

O código mais curto em bytes vence. Parabéns se você puder mostrar que seu código tira proveito de alguma eficiência.

05AB1E , 20 12 bytes

Economizou 8 bytes graças a Osable !

µNSDOsP‚¾>å½

Usa a codificação CP-1252 . Experimente online!

Mathematica, 71 bytes, 68 caracteres

±0=0;±n_:=(For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];x)

Por apenas mais 4 bytes, aqui está uma versão que armazena os valores de ±n:

±0=0;±n_:=(For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)

Com a última versão, antes de avaliar ±n, PlusMinusterá dois valores baixos:

In[2]:= DownValues@PlusMinus
Out[2]= {HoldPattern[±0] :> 0, HoldPattern[±n_] :> (For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)}

Agora, se avaliarmos ±20:

In[3]:= ±20
In[3]:= 225

In[4]:= DownValues@PlusMinus
Out[4]= {HoldPattern[±0] :> 0, HoldPattern[±1] :> 1, HoldPattern[±2] :> 2, HoldPattern[±3] :> 3, HoldPattern[±4] :> 4, HoldPattern[±5] :> 5, HoldPattern[±6] :> 6, HoldPattern[±7] :> 7, HoldPattern[±8] :> 8, HoldPattern[±9] :> 9, HoldPattern[±10] :> 19, HoldPattern[±11] :> 29, HoldPattern[±12] :> 34, HoldPattern[±13] :> 49, HoldPattern[±14] :> 59, HoldPattern[±15] :> 69, HoldPattern[±16] :> 79, HoldPattern[±17] :> 89, HoldPattern[±18] :> 92, HoldPattern[±19] :> 199, HoldPattern[±20] :> 225, HoldPattern[±n_] :> (For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)}

Isso acelera drasticamente os cálculos futuros, já que o Mathematica não calcula mais os valores entre 0e 20recursivamente. O tempo economizado é mais dramático à medida que naumenta:

In[5]:= Quit[]

In[1]:= ±0=0;±n_:=(For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)

In[2]:= AbsoluteTiming[±60]
Out[2]= {23.0563, 6111125}

In[3]:= AbsoluteTiming[±60]
Out[3]= {9.89694*10^-6, 6111125}

C #, 155 159 135 bytes

a=n=>{if(n<1)return 0;int i=n,s=0,p=1,N=a(n-1);for(;;){s=0;p=1;foreach(var c in++i+""){s+=c-48;p*=c-48;}if(i>N&(s==n|p==n))return i;}};

Super ineficiente, leva muito tempo para apenas N>=14. Vou tentar obter uma solução mais eficiente, mas mais longa.

Ok, muito melhor agora, mas com 4 bytes a mais. Oh, bem, eu posso fazer N<=50muito rapidamente agora. Obrigado @milk por salvar 24 bytes!

Pitão - 18 17 bytes

Um byte salvo graças ao @Jakube!

Usa reduzir para fazer a coisa recursiva.

uf}HsM*FBjT;hGSQZ

Conjunto de Teste .

R, 124 bytes 112

f=function(N){y=x=`if`(N-1,f(N-1),0);while(N!=prod(y)&N!=sum(y)){x=x+1;y=as.double(el(strsplit(c(x,""),"")))};x}

Falha em N = 45 porque R insiste em escrever 10.000 como 1e + 05, o que não é apreciado por as.numeric(), isso é corrigível usando as.integer()o custo de 12 bytes:

f=function(N){y=x=`if`(N-1,f(N-1),0);while(N!=prod(y)&N!=sum(y)){x=x+1;y=as.double(el(strsplit(c(as.integer(x),""),"")))};x}

Como linguagem de programação estatística, R tem maneiras irritantemente prolixo de dividir números em um vetor de dígitos. Especialmente porque tudo precisa ser convertido de volta de seqüências para valores numéricos explicitamente.

12 bytes salvos graças ao billywob.

JavaScript (ES6) 109 107 105 91 89 Bytes

f=n=>n&&eval(`for(i=f(n-1);++i,${x="[...i+''].reduce((r,v)=>"}+r+ +v)-n&&${x}r*v)-n;);i`)



console.log(f.toString().length + 2); 
console.log(f(25));
console.log(f(13));
console.log(f(8));                                  

JavaScript (ES6), 84 86

Editar: 2 bytes salvos thx @Arnauld

f=n=>eval("for(v=n&&f(n-1),p=s=n+1;s&&p-1;)[...++v+''].map(d=>(p/=d,s-=d),p=s=n);v")

Nota de teste acima de 50, ele usará muito de sua CPU, clique em 'Ocultar resultados' para parar antes que seja tarde demais

f=n=>eval("for(v=n&&f(n-1),p=s=n+1;s&&p-1;)[...++v+''].map(d=>(p/=d,s-=d),p=s=n);v")

out=x=>O.textContent=x+'\n'+O.textContent

i=0
step=_=>out(i+' '+f(i),++i,setTimeout(step,i*10))

step()

<pre id=O></pre>

Mathematica, 67 bytes

a@0=0;a@b_:=NestWhile[#+1&,a[b-1]+1,+##!=b&&1##!=b&@*IntegerDigits]

Função, nomeada a. Pega um número como entrada e retorna um número como saída. Inspirado na solução anterior do Mathematica, mas usa um mecanismo de loop diferente.

C, 240 bytes

int f(char n){int q[19],i=19,r=n%9,j=9,*p=q,c=n/9;while(i)q[--i]=0;if(c){if(!r){r=9;c--;}q[9]=c;if(!(n%r)){n/=r;while((j-1)*(n-1)*c){if(n%j)j--;else{c--;q[9+j]++;n/=j;}}q[10]=c;if(1==n)p+=9;}while(++i<10){while(p[i]--)r=r*10+i;}}return(r);}

Tentando explorar algumas propriedades matemáticas da sequência.

PowerShell v3 +, 114 bytes

param($n)$i=,0;$l=1;1..$n|%{for(;$_-notin((($b=[char[]]"$l")-join'+'|iex)),(($b-join'*'|iex))){$l++}$i+=$l};$i[$n]

Solução iterativa, sem uma maneira fácil de transformar um número na soma / produto de seus dígitos, por isso é um pouco mais do que as respostas do JavaScript.

Pega entrada $n, define $ipara uma matriz com just 0(esta é a coleção de F()e define $ligual a 1(esta é a mais recente F). Em seguida, fazemos um loop ascendente de 1para $n, cada iteração executando um forloop.

O forcondicional do loop pega o $lnúmero do atest, em uma string "$l", depois o projeta como uma charmatriz e armazena esse array na variável temp $b. Nós, então, -joinesses dígitos juntos +e o canalizamos iex(abreviado Invoke-Expressione semelhante a eval). Além disso, também fazemos o mesmo com *. Esses dois números são encapsulados em parênteses e tratados como o argumento do array para o -notinoperador em relação ao número atual $_do loop externo (ou seja, o forloop é executado desde que +e *seja diferente de $_). O corpo do forloop apenas aumenta$l++ .

Quando saímos desse forloop interno , adicionamos nosso $lon como um novo elemento de $i. Depois de concluirmos completamente o loop de intervalo, colocamos apenas$i[$n] no pipeline e a saída é implícita.

Nota: fica muito lento para executar acima 20, simplesmente por causa da estrutura do loop. Por exemplo, N=40leva cerca de dois minutos na minha máquina e eu nem me incomodei em testar N>50.

Pyke, 17 bytes

t.fY'Bs]~ohR{Io(e

Experimente aqui!

Ou 13 bytes não competitivos

first_nagora coloca a quantidade de itens já encontrados mais um, ise usado.

Q.fY'Bs]iR{)e

Experimente aqui!

Q.f        )  -  first_n(input, start=1)
   Y          -   digits(^)
    'Bs]      -   [sum(^), product(^)]
         R}   -   V in ^
        i     -    len(results)+1
            e - ^[-1]

Python 2 , 77 bytes

f=lambda n,k=0,r=0:-(k>n)or-~f(n,k+(k in[eval(c.join(`r`))for c in'+*']),r+1)

Experimente online!

Maravilha , 49 bytes

f\.{0\0@(:>@(| =#1sum#0)=#1prod#0)(dp +1f -#0 1)N

Ftw de correspondência de padrão! Uso:

f\.{0\0@(:>@(| =#1sum#0)=#1prod#0)(dp +1f -#0 1)N}; f 10

Mais legível:

f\.{
  0\0
  @(
    find @(or = #1 sum #0) = #1 prod #0
  ) (dp + 1 (f -#0 1)) N
}

Isso é basicamente apenas uma implementação palavra por palavra das especificações.

BASH, 107 bytes

com dobra + colar + bc

for ((;n<=$1;z++)){
p(){ fold -1<<<$z|paste -sd$1|bc;}
[ `p +` = $n -o `p \*` = $n ]&&((z-->n++))
}
echo $z

Befunge, 101 bytes

&20p>:000pv
>\1+^vp011<
| >.@>:55+%:00g+00p10g*v>10g-*
::\$_^#!:/+55p01*!`"~":<^\-g00
< |!-g02
+1< v\

Experimente online! Mas observe que as coisas ficarão muito lentas quando você chegar aos quarenta. Se você deseja testar toda a gama, você realmente precisa usar um compilador Befunge.

Explicação

&20p           Read N and save for later.

>              Start of main loop; current target and test number on stack, initially 0.
:              Duplicate the test number so we can manipulate it.
000p           Initialise the sum to 0.
110p           Initialise the product to 1.

>              Start of inner loop.
:55+%:         Modulo 10 of the test number to get the first digit.
00g+00p        Add to the sum.
10g*           Multiply by the product.
:"~"`!*        If greater than 126, set to 0 to prevent overflows - it'll never match.
10p            Update the product variable.
55+/           Divide the test number by 10 to get the next digit.
:!_            If not zero, repeat the inner loop

$              Drop the zero left over from the loop.
\::00g-\10g-   Compare the sum and product with the current target.
*|             Multiply the two diffs and branch; up if no match, down if either match.
\1+^           On no match, we increment the test number and repeat the main loop.
:>20g-!|       With a match, we compare the current target with the saved N.
1+\v           If that doesn't match, increment the current target and restart main loop.
\>.@           If it does match, we've got our result; output it and exit.

PHP , 110 bytes

for(;$c<=$a=$argn;$c=count($r))array_product($s=str_split($n++))!=$c&&array_sum($s)!=$c?:$r[]=~-$n;echo$r[$a];

Experimente online!