Plus and Times, Ones and Nines

Question

Implement this recurrence relation as a function or program that inputs and outputs a non-negative integer:

• F(0) = 0

• F(N) = the smallest integer greater than F(N-1) such that the sum and/or product of its base-10 digits is N

N is your program's input and F(N) its output.

To be clear, the sum of the digits in a number like 913 is 9+1+3=13. The product is 9×1×3=27. For single-digit numbers, the sum and product is the same number. Numbers that contain a 0 of course have product 0.

The results through F(70) are:

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

The shortest code in bytes wins. Kudos if you can show that your code takes advantage of some efficiency.

Answer 1

05AB1E, 20 12 bytes

Saved 8 bytes thanks to Osable!

µNSDOsP‚¾>å½

Uses the CP-1252 encoding. Try it online!

Answer 2

Mathematica, 71 bytes, 68 characters

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

For just 4 more bytes, here's a version that stores the values of ±n:

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

With the latter version, before you evaluate ±n, PlusMinus will have two down values:

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

Now if we evaluate ±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)}

This dramatically speeds up future calculations since Mathematica will no longer calculate the values between 0 and 20 recursively. The time saved is more dramatic as n increases:

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}

Answer 3

Pyth - 18 17 bytes

One byte saved thanks to @Jakube!

Uses reduce to do the recursive thing.

uf}HsM*FBjT;hGSQZ

Test Suite.

Answer 4

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 inefficient, takes a long time for just N>=14. Gonna try to get a more efficient, but longer solution.

Okay, much better now, but 4 bytes longer. Oh well, I can do N<=50 pretty quickly now. Thank you @milk for saving 24 bytes!

Answer 5

R, 124 112 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(x,""),"")))};x}

Fails at N=45 because R insists on writing 10.000 as 1e+05, which isnt appreciated by as.numeric(), this is fixable by using as.integer() at the cost of 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}

As a statistical programming language R has annoyingly wordy ways of splitting numbers into a vector of digits. Especially because everything has to be converted back from strings to numerical values explicitly.

12 bytes saved thanks to billywob.

Answer 6

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

Answer 7

JavaScript (ES6), 84 86

Edit: 2 bytes saved 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 above 50 it will use too much of your CPU, click 'Hide results' to stop before it's too late

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>

Answer 8

Mathematica, 67 bytes

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

Function, named a. Takes a number as input and returns a number as output. Inspired by the previous Mathematica solution, but uses a different looping mechanism.

Answer 9

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

Trying to exploit some math properties of the sequence.

Answer 10

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]

Iterative solution, with no easy way to turn a number into the sum/product of its digits, so it's quite a bit longer than the JavaScript answers.

Takes input $n, sets $i to an array with just 0 (this is the collection of F(), and sets $l equal to 1 (this is the latest F). We then loop upward from 1 to $n, each iteration executing a for loop.

The for loop's conditional takes the $latest number, in a string "$l", then casts that as a char-array, and stores that array into temp variable $b. We then -join those digits together with + and pipe that to iex (short for Invoke-Expression and similar to eval). Additionally, we also do similar with *. Those two numbers are encapsulated in parens and treated as the array argument for the -notin operator against the current number $_ of the outer loop (i.e., the for loop runs so long as either + and * are different than $_). The body of the for loop just increments $l++.

Once we're out of that inner for loop, we add our $l on as a new element of $i. Once we've fully completed the range loop, we just place $i[$n] on the pipeline, and output is implicit.

NB -- Gets pretty slow to execute above about 20, simply because of the loop structure. For example, N=40 takes about two minutes on my machine, and I've not even bothered testing N>50.

Answer 11

Pyke, 17 bytes

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

Try it here!

Or 13 bytes noncompetitive

first_n now puts the amount of items already found plus one in i if used.

Q.fY'Bs]iR{)e

Try it here!

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

Answer 12

Wonder, 49 bytes

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

Pattern matching ftw! Usage:

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

More readable:

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

This is basically just a word-for-word implementation of the specs.

Answer 13

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)

Try it online!

Answer 14

BASH, 107 bytes

with fold + paste + bc

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

Answer 15

Befunge, 101 bytes

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

Try it online! But note that it's going to get really slow once you get into the high forties. If you want to test the full range, you really need to be using a Befunge compiler.

Explanation

&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.

Answer 16

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

Try it online!