# Plus and Times, Ones and Nines

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.

• OEIS sequence Dec 6, 2016 at 18:43
• Not quite right sequence. Dec 6, 2016 at 19:30

# 05AB1E, 20 12 bytes

Saved 8 bytes thanks to Osable!

µNSDOsP‚¾>å½


Uses the CP-1252 encoding. Try it online!

• Is the length test required? I came up with µNSDOsP‚¾>å½. It seems to work for randomly chosen numbers. Dec 6, 2016 at 13:08
• @Osable Ahh of course, you're a genius! I don't even know why I included that. Dec 6, 2016 at 13:17
• Amazing how you can suddenly reduce a 20 bytes program by 40%... Dec 22, 2016 at 22:26

## 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:= DownValues@PlusMinus
Out= {HoldPattern[±0] :> 0, HoldPattern[±n_] :> (For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)}


Now if we evaluate ±20:

In:= ±20
In:= 225

In:= DownValues@PlusMinus
Out= {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:= Quit[]

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

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

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

• This starts at F(N - 1) instead of F(N - 1) + 1; the recurrence must be strictly increasing. Dec 7, 2016 at 2:17

# C#, 155159 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!

• -2 bytes to replace the for with for(;;) and the foreach with foreach(var c in++i+""). -22 bytes to replace int.Parse(c+"") with c-48.
– milk
Dec 6, 2016 at 20:22

# Pyth - 18 17 bytes

One byte saved thanks to @Jakube!

Uses reduce to do the recursive thing.

uf}HsM*FBjT;hGSQZ

• sM*FBjT; also generates the digit sum and product and is 1 byte shorter. Dec 6, 2016 at 20:26
• @Jakube ooh nice trick Dec 6, 2016 at 22:28

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

• You can use as.double(el(strsplit(c(x,""),""))) to split an integer into a vector of its digits. However, you still run into the formatting issue but that can as in your answer be solved by as.integer() Dec 6, 2016 at 12:22
• Ooh, clever way of forcing x into a string :o
Dec 6, 2016 at 12:24
• You can also use sprintf() instead to format the integer into a string with no trailing zeros directly: as.double(el(strsplit(sprintf("%1.f",x),""))) and skip the use of as.integer() Dec 6, 2016 at 12:26
• @LegionMammal978 The first thing it does in the while loop is x=x+1 and this is guaranteed to be evaluated once, because at the start y=F(N-1) which is definitely not equal to N.
Dec 7, 2016 at 9:10
• @JarkoDubbeldam Whoops, misread it :P Dec 7, 2016 at 12:07

# JavaScript (ES6) 10910710591 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

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>

• I think for(v=n&&f(n-1),p=s=n+1;s&&p-1;)[...++v+''].map(d=>(p/=d,s-=d),p=s=n);v should save 2 bytes. I suspect it can be shortened some more, but I couldn't figure it out so far. Dec 6, 2016 at 17:55
• @Arnauld I expect some problem with repeated floating point division Dec 6, 2016 at 18:50
• Our only requirement is that p /= d produces an exact result when d is actually a divisor of p. Unless I'm mistaken, this is true for any d <= p <= Number.MAX_SAFE_INTEGER. We'll get floating point rounding errors when p % d != 0, but that should be safe. Dec 6, 2016 at 19:25
• @darrylyeo don't give suggestions you did not try yourself (try eval1+1 ) (here's why codegolf.stackexchange.com/a/52204/21348 : read the first comment) Dec 8, 2016 at 9:19

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

# C, 240 bytes

int f(char n){int q,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=c;if(!(n%r)){n/=r;while((j-1)*(n-1)*c){if(n%j)j--;else{c--;q[9+j]++;n/=j;}}q=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.

## 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. ## 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]  # 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! # 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. # 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  # 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.
$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];