Реализуйте это рекуррентное отношение как функцию или программу, которая вводит и выводит неотрицательное целое число:

• F (0) = 0

• F (N) = наименьшее целое число больше, чем F (N-1), так что сумма и / или произведение его десятизначных цифр составляет N

N - это вход вашей программы, а F (N) - ее выход.

Для ясности, сумма цифр в числе, подобном 913, равна 9 + 1 + 3 = 13. Произведение 9 × 1 × 3 = 27. Для однозначных чисел сумма и произведение совпадают. Числа, которые содержат 0, конечно, имеют продукт 0.

Результаты через F (70):

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

Самый короткий код в байтах побеждает. Престижность, если вы можете показать, что ваш код использует некоторые преимущества.

05AB1E , 20 12 байтов

Сохранено 8 байтов благодаря Osable !

µNSDOsP‚¾>å½

Использует кодировку CP-1252 . Попробуйте онлайн!

Mathematica, 71 байт, 68 символов

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

Еще 4 байта, вот версия, в которой хранятся значения ±n:

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

С последней версией, прежде чем оценить ±n, PlusMinusбудет иметь два вниз значения:

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

Теперь, если мы оценим ±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)}

Это значительно ускоряет будущие вычисления, поскольку Mathematica больше не будет вычислять значения между 0и 20рекурсивно. Сэкономленное время становится более драматичным по мере nувеличения:

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 байтов

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;}};

Супер неэффективно, занимает много времени просто N>=14. Собираюсь найти более эффективное, но более длительное решение.

Хорошо, теперь намного лучше, но на 4 байта длиннее. О, хорошо, я могу сделать N<=50довольно быстро сейчас. Спасибо @milk за сохранение 24 байта!

Pyth - 18 17 байт

Один байт сохранен благодаря @Jakube!

Использует сокращение, чтобы сделать рекурсивную вещь.

uf}HsM*FBjT;hGSQZ

Тестовый пакет .

R, 124 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}

Сбой при N = 45, потому что R настаивает на записи 10.000 как 1e + 05, что не оценивается as.numeric(), это можно исправить, используя as.integer()по стоимости 12 байтов:

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}

В качестве языка статистического программирования R имеет раздражающие многословные способы разбиения чисел на вектор цифр. Тем более, что все должно быть преобразовано обратно из строк в числовые значения явно.

12 байтов сохранено благодаря billywob.

JavaScript (ES6) 109 107 105 91 89 байт

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

Редактировать: 2 байта сохранены 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")

Test Note выше 50, он будет использовать слишком много вашего процессора, нажмите «Скрыть результаты», чтобы остановить, пока не стало слишком поздно

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 байт

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

Функция, названная a. Принимает число в качестве ввода и возвращает число в качестве вывода. Вдохновленный предыдущим решением Mathematica, но использует другой механизм зацикливания.

C 240 байт

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

Попытка использовать некоторые математические свойства последовательности.

PowerShell v3 +, 114 байт

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

Итеративное решение, в котором нет простого способа превратить число в сумму / произведение его цифр, поэтому оно немного длиннее, чем ответы JavaScript.

Принимает ввод $n, устанавливает $iмассив только0 (это коллекция F(), и устанавливает значение $lравно 1(это самое последнее F). Затем мы выполняем цикл вверх от 1к $n, каждая итерация выполняет forцикл.

В forусловной Loop принимает на $lATEST числа, в строке "$l", а затем отбрасывает , что в качестве char-array, и сохраняет этот массив в переменный темпе $b. Затем мы получим -joinэти цифры вместе +и передадим их iex(сокращение от Invoke-Expressionи аналогично eval). Кроме того, мы также делаем подобное с *. Эти два числа заключены в скобки и рассматриваются как аргумент массива для-notin оператора против текущего номера $_внешнего цикла (т. forЕ. Цикл выполняется до тех пор, пока любой из них +и *отличается от него $_). Тело forцикла просто увеличивается $l++.

Как только мы выходим из этого внутреннего forцикла, мы добавляем наш $lновый элемент $i. Как только мы полностью завершили цикл диапазона, мы просто помещаем его $i[$n]в конвейер, и вывод неявен.

NB - становится довольно медленным для выполнения выше 20, просто из-за структуры цикла. Например, N=40на моей машине это занимает около двух минут, и я даже не потрудился на тестировании N>50.

Пайк, 17 байт

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

Попробуй это здесь!

Или 13 байт неконкурентоспособны

first_nтеперь помещает количество уже найденных предметов плюс один, iесли используется.

Q.fY'Bs]iR{)e

Попробуй это здесь!

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

Python 2 , 77 байт

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

Попробуйте онлайн!

Чудо , 49 байт

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

Образец соответствия ftw! Использование:

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

Более читабельно:

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

Это в основном просто дословная реализация спецификаций.

BASH, 107 байт

со сгибом + паста + до н.

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

Befunge, 101 байт

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

Попробуйте онлайн! Но учтите, что когда вы достигнете сороковых, будет очень медленно. Если вы хотите протестировать полный диапазон, вам действительно нужно использовать компилятор Befunge.

объяснение

&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 байт

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

Попробуйте онлайн!