18
\$\begingroup\$

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.

\$\endgroup\$

16 Answers 16

4
\$\begingroup\$

05AB1E, 20 12 bytes

Saved 8 bytes thanks to Osable!

µNSDOsP‚¾>å½

Uses the CP-1252 encoding. Try it online!

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

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}
\$\endgroup\$
  • \$\begingroup\$ This starts at F(N - 1) instead of F(N - 1) + 1; the recurrence must be strictly increasing. \$\endgroup\$ – LegionMammal978 Dec 7 '16 at 2:17
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ -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. \$\endgroup\$ – milk Dec 6 '16 at 20:22
2
\$\begingroup\$

Pyth - 18 17 bytes

One byte saved thanks to @Jakube!

Uses reduce to do the recursive thing.

uf}HsM*FBjT;hGSQZ

Test Suite.

\$\endgroup\$
  • \$\begingroup\$ sM*FBjT; also generates the digit sum and product and is 1 byte shorter. \$\endgroup\$ – Jakube Dec 6 '16 at 20:26
  • \$\begingroup\$ @Jakube ooh nice trick \$\endgroup\$ – Maltysen Dec 6 '16 at 22:28
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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() \$\endgroup\$ – Billywob Dec 6 '16 at 12:22
  • \$\begingroup\$ Ooh, clever way of forcing x into a string :o \$\endgroup\$ – JAD Dec 6 '16 at 12:24
  • \$\begingroup\$ 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() \$\endgroup\$ – Billywob Dec 6 '16 at 12:26
  • \$\begingroup\$ @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. \$\endgroup\$ – JAD Dec 7 '16 at 9:10
  • \$\begingroup\$ @JarkoDubbeldam Whoops, misread it :P \$\endgroup\$ – LegionMammal978 Dec 7 '16 at 12:07
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Arnauld Dec 6 '16 at 17:55
  • \$\begingroup\$ @Arnauld I expect some problem with repeated floating point division \$\endgroup\$ – edc65 Dec 6 '16 at 18:50
  • \$\begingroup\$ 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. \$\endgroup\$ – Arnauld Dec 6 '16 at 19:25
  • \$\begingroup\$ @darrylyeo don't give suggestions you did not try yourself (try eval`1+1` ) (here's why codegolf.stackexchange.com/a/52204/21348 : read the first comment) \$\endgroup\$ – edc65 Dec 8 '16 at 9:19
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.