22
\$\begingroup\$

Here's an interesting sequence discovered by Paul Loomis, a mathematician at Bloomsburg University. From his page on this sequence:

Define
f(n) = f(n-1) + (the product of the nonzero digits of f(n-1))
f(0) = x, with x as any positive integer, written in base 10.

So, starting with f(0)=1, you get the following sequence
1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, ...

So far, so standard. The interesting property comes into play when you take any other integer as the starting point, eventually the sequence converges into a point along the above x=1 sequence. For example, starting with x=3 yields
3, 6, 12, 14, 18, 26, 38, 62, 74, 102, ...

Here are some more sequences, each shown only until they reach 102:

5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, ...
7, 14, 18, 26, 38, 62, 74, 102, ...
9, 18, 26, 38, 62, 74, 102, ...
13, 16, 22, 26, 38, 62, 74, 102, ...
15, 20, 22, 26, 38, 62, 74, 102, ...
17, 24, 32, 38, 62, 74, 102, ...
19, 28, 44, 60, 66, 102, ...

He conjectured, and empirically proved up to x=1,000,000, that this property (i.e., that all input numbers converge to the same sequence) holds true.

The Challenge

Given a positive input integer 0 < x < 1,000,000, output the number where the f(x) sequence converges to the f(1) sequence. For example, for x=5, this would be 26, since that's the first number in common to both sequences.

 x output
 1 1
 5 26
19 102
63 150056

Rules

  • If applicable, you can assume that the input/output will fit in your language's native Integer type.
  • The input and output can be given by any convenient method.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$

11 Answers 11

5
\$\begingroup\$

JavaScript (ES6), 81 67 bytes

Saved 1 byte thanks to @l4m2

f=(n,x=1)=>x<n?f(x,n):x>n?f(+[...n+''].reduce((p,i)=>p*i||p)+n,x):n

Try it online!

Commented

f = (n,                   // n = current value for the 1st sequence, initialized to input
        x = 1) =>         // x = current value for the 2nd sequence, initialized to 1
  x < n ?                 // if x is less than n:
    f(x, n)               //   swap the sequences by doing a recursive call to f(x, n)
  :                       // else:
    x > n ?               //   if x is greater than n:
      f(                  //     do a recursive call with the next term of the 1st sequence:
        +[...n + '']      //       coerce n to a string and split it
        .reduce((p, i) => //       for each digit i in n:
          p * i || p      //         multiply p by i, or let p unchanged if i is zero
        ) + n,            //       end of reduce(); add n to the result
        x                 //       let x unchanged
      )                   //     end of recursive call
    :                     //   else:
      n                   //     return n
\$\endgroup\$
  • \$\begingroup\$ ```` f=(n,x=1)=>x<n?f(x,n):x>n?f(+[...n+''].reduce((p,i)=>p*i||p)+n,x):n ```` \$\endgroup\$ – l4m2 Apr 23 '18 at 19:31
4
\$\begingroup\$

Jelly, 18 14 bytes

ḊḢDo1P+Ʋ;µQƑ¿Ḣ

Input is a singleton array.

Try it online!

How it works

ḊḢDo1P+Ʋ;µQƑ¿Ḣ  Main link. Argument: [n]

            ¿   While...
          QƑ      all elements of the return value are unique...
         µ          execute the chain to the left.
Ḋ                     Dequeue; remove the first item.
 Ḣ                    Head; extract the first item.
                      This yields the second item of the return value if it has
                      at least two elements, 0 otherwise.
       Ʋ              Combine the links to the left into a chain.
  D                     Take the decimal digits of the second item.
   o1                   Perform logical OR with 1, replacing 0's with 1's.
     P                  Take the product.
      +                 Add the product with the second item.
        ;             Prepend the result to the previous return value.
             Ḣ  Head; extract the first item.
\$\endgroup\$
2
\$\begingroup\$

Python 2, 111 95 93 bytes

Using unpacking in replace(*'01') as in @Rod answer
-18 bytes thanks to @Lynn

l=[1,input()]
while cmp(*l):l[0]+=eval('*'.join(`l[0]`.replace(*'01')));l.sort()
print l[0]  

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Ah, and the loop condition can be while cmp(*l), also! \$\endgroup\$ – Lynn Apr 23 '18 at 15:46
  • \$\begingroup\$ @Lynn Yes! Thanks again \$\endgroup\$ – Dead Possum Apr 23 '18 at 15:50
2
\$\begingroup\$

Haskell, 65 bytes

(!1)
a!b|a>b=b!a|a<b=(a+product[read[d]|d<-show a,d>'0'])!b|1<2=a

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 78 bytes

f=lambda a,b=1:a*(a==b)or f(*sorted([a+eval('*'.join(`a`.replace(*'01'))),b]))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I was working on solution with lambda, but got stuck with shortcircuting for couple minutes, good job! \$\endgroup\$ – Dead Possum Apr 23 '18 at 15:59
2
\$\begingroup\$

Husk, 13 bytes

→UΞm¡S+ȯΠf±dΘ

Takes input as a singleton list.

Try it online!

Explanation

                 Implicit input, e.g 5
            Θ    Prepend a zero to get  [0,5]
   m             Map the following over [0,5]
    ¡              Iteratatively apply the following function, collecting the return values in a list
           d         Convert to a list of digits
         f±          keep only the truthy ones
       ȯΠ            then take the product
     S+              add that to the original number
                After this map, we have [[0,1,2,4,8,16,22,26,38,62...],[5,10,11,12,14,18,26,38,62,74...]]
  Ξ             Merge the sorted lists:  [0,1,2,4,5,8,10,11,12,14,16,18,22,26,26,38,38,62,62,74...]
 U              Take the longest unique prefix: [0,1,2,4,5,8,10,11,12,14,16,18,22,26]
→               Get the last element and implicitely output: 26
\$\endgroup\$
1
\$\begingroup\$

Python 3, 126 125 bytes

m=[1]
n=[int(input())]
while not{*m}&{*n}:
 for l in m,n:l+=l[-1]+eval('*'.join(str(l[-1]).replace(*'01'))),
print({*m}&{*n})

Try it online!

Take the input as string

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

Java (JDK 10), 99 bytes

n->{for(int x=1;x!=n;n+=(""+n).chars().reduce(1,(a,b)->a*(b>48?b-48:1)))x^=x<n?n^(n=x):0;return n;}

Try it online!

Mostly an iterative port of Arnauld's JavaScript answer, so go upvote him!

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

Jelly, 23 bytes

ð⁹1,Dḟ0P+Ʋ⁸С€f/©µ1#ṛ®Ḣ

Try it online!

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

J, 50 bytes

tacit style function definition

[:{.@(e.~#])/[:(+[:*/@(*#])(#~10)&#:)^:(<453)"0,&1

if the argument (say 63) were pasted into a REPL expression it could be 45 e.g.

{.(e.~#])/(+[:*/@(*#])(#~10)&#:)^:(<453)"0]1,63
  • ,&1 append 1 to generate search sequence as well as argument's sequence
  • ^:(<453)"0 iterates each until 1mio is reached in 1's sequence
  • + [: */@(*#]) (#~10)&#: fork adds to hook which does the product of digits
  • (e.~ # ])/ uses repeat item if exists to get intersection of lists
  • {. return only the first common value

Try it online!

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

R, 110 86 bytes

o=c(1,1:9);o=o%o%o%o%o;o=c(o%o%o)
x=c(1,n);while((x=sort(x))<x[2])x[1]=(x+o[x+1])[1]
x

TIO

previous version 110:

f=function(x){if((x[1]=x[1]+(c((y=(y=c(1,1:9))%o%y%o%y)%o%y))[x[1]+1])==x[2]){x[1]}else{f(sort(x))}}
f(c(1,n))

TIO

\$\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.