17
\$\begingroup\$

Let's define a function \$f\$ which, given a positive integer \$x\$, returns the sum of:

  • \$x\$
  • the smallest digit in the decimal representation of \$x\$
  • the highest digit in the decimal representation of \$x\$ (which may be the same as the smallest one)

For instance:

  • \$f(1)=1+1+1=3\$
  • \$f(135)=135+1+5=141\$
  • \$f(209)=209+0+9=218\$

We now define the sequence \$a_k = f^k(1)\$. That is to say:

  • \$a_1=1\$
  • \$a_k=f(a_{k-1})\$ for \$k>1\$

The first few terms are:

1, 3, 9, 27, 36, 45, 54, 63, 72, 81, 90, 99, 117, 125, 131, 135, 141, 146, ...

Challenge

Given a positive integer \$x\$, you must return the smallest \$n\$ such that \$f^n(x)\$ belongs to the sequence. Or in other words: how many times \$f\$ should be applied consecutively to turn \$x\$ into a term of the sequence.

You can assume that you'll never be given an input for which no solution exists. (Although I suspect that this can't happen, I didn't attempt to prove it.)

You may also use 1-based indices (returning \$n+1\$ instead of \$n\$). Please make it clear in your answer if you do so.

Standard rules apply.

Examples

  • Given \$x=45\$, the answer is \$0\$ because \$x\$ is already a term of the sequence (\$a_6=45\$).
  • Given \$x=2\$, the answer is \$3\$ because 3 iterations are required: \$f(2)=2+2+2=6\$, \$f(6)=6+6+6=18\$, \$f(18)=18+1+8=27=a_4\$. Or more concisely: \$f^3(2)=27\$.

(These are the 0-based results. The answers would be \$1\$ and \$4\$ respectively if 1-based indices are used.)

Test cases

Input : 0-based output

1     : 0
2     : 3
4     : 15
14    : 16
18    : 1
45    : 0
270   : 0
465   : 67
1497  : 33
\$\endgroup\$
7
  • 3
    \$\begingroup\$ If you are going to use the \$f^n\$ notation you might as well just define the sequence in terms of it in the first place. \$a_n=f^n(1)\$. I think it lowers the overhead to only do things one way. \$\endgroup\$
    – Grain Ghost
    Aug 31 at 20:34
  • \$\begingroup\$ Can we output '1-based' instead of '0-based' indices: that is, output for 1,3,9, and so on is 1, and output for 18 is 2, etc.? \$\endgroup\$ Aug 31 at 20:40
  • \$\begingroup\$ @DominicvanEssen That seems reasonable. Edited accordingly. \$\endgroup\$
    – Arnauld
    Aug 31 at 21:12
  • 3
    \$\begingroup\$ @WheatWizard I've added the alternate notation. Not everyone may be familiar with functional powers however, so I think it's better to keep the verbose version as well. \$\endgroup\$
    – Arnauld
    Aug 31 at 21:18
  • 1
    \$\begingroup\$ Since every number in the range 100-117 eventually reaches the number 159 by repeated iteration, the same is true if you add arbitrarily many 1s at the beginning of each number. Hence, the sequences starting at any two points must eventually meet. \$\endgroup\$
    – Nitrodon
    Sep 1 at 14:31

10 Answers 10

7
\$\begingroup\$

05AB1E, 15 bytes

-2 bytes thanks to Kevin Cruijssen!

$‚€λDZsßO}`.i1k

Try it online!

$‚            # pair 1 and the input
  €           # for each k of those two values
   λDZsß++}   # calculate the infinite sequence given by f^n(k):
    D         # duplicate the previous value
     Z        # take the maximum digit of the copy without removing it from the stack
      sß      # swap to the copy and get the minimum digit
        O     # sum previous value, maximum digit and minimum digit

`             # push both infinite sequences seperately on the stack
 .i           # for each value in the sequence starting with the input:
              #  is it contained in the other (non-decreasing) sequence?
   1k         # print the index of the first 1
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -2 bytes by removing the S and changing the ++ to O. Nice answer, btw! \$\endgroup\$ Sep 2 at 14:15
6
\$\begingroup\$

Husk, 21 20 15 bytes

Edit: -5 bytes thanks to Razetime

V£₁1₁
¡S+o§+▲▼d

Try it online!

1-based output.

¡S+o§+▲▼d       # helper function ₁:
¡               # generate infinite sequence by repeatedly applying:
 S+o§+▲▼d       # function f:
 S+             # add the input to  
    §+▲▼        # sum of the max and the min of
   o    d       # the digits of the input
   
V£₁1₁           # main program:
V               # index of first truthy result of ...
 £              # getting the index (or zero if absent) of 
  ₁1            # the infinite sequence of helper function starting with 1
    ₁           # in the infinite sequence of helper function ₁ starting with the program input
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 15 bytes \$\endgroup\$
    – Razetime
    Sep 3 at 13:55
  • 1
    \$\begingroup\$ @Razetime - Thanks a LOT! I'd always glossed-over £ without really understanding what 'list is supposed to be sorted' meant or was good for... now I finally understand! \$\endgroup\$ Sep 3 at 14:09
  • \$\begingroup\$ "An Husk".....?? \$\endgroup\$
    – user7467
    Sep 4 at 9:42
3
\$\begingroup\$

Charcoal, 45 bytes

Nθ≔¹η≔⁰ζW⁻θη¿‹ηθ≧⁺Σ⁺⌊Iη⌈Iηη«≧⁺Σ⁺⌊Iθ⌈Iθθ≦⊕ζ»Iζ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input x.

≔¹η

Start with a=1.

≔⁰ζ

Start with n=0.

W⁻θη

Repeat until x=a.

¿‹ηθ≧⁺Σ⁺⌊Iη⌈Iηη

If a<x then calculate a=f(a).

«≧⁺Σ⁺⌊Iθ⌈Iθθ

Otherwise calculate x=f(x), ...

≦⊕ζ»

... and increment n.

Iζ

Output n.

\$\endgroup\$
3
\$\begingroup\$

R, 109 bytes

(or R>=4.1, 95 bytes replacing both function appearances with \)

function(x,`!`=function(n)n+sum(range(n%/%10^(0:log10(n))%%10))){while({F=F+1;i=1;while(i<x)i=!i;i-x})x=!x;F}

Try it online!

Returns 1-based result.

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

Scala, 100 bytes

a(_)indexWhere(? =>a(1)takeWhile?.>=toSet?)
val a=Stream.iterate(_:Int)(x=>x+s"$x".min+s"$x".max-96)

Try it in Scastie!

Pretty simple solution. a is a function that makes an infinite list of the sequence, given a starting number. We make a sequence starting at x using that, and find the first index where an item is inside the sequence starting at 1. Since the sequence can only be added to, it's monotonic and therefore safe to only check the elements which are less than or equal to x.

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

C (gcc), 114 bytes

d;s;m;x;f(n){for(s=m=n,x=0;n;n/=10)d=n%10,m=d<m?d:m,x=d>x?d:x;s+=m+x;}g(n){for(s=1;n>s;s=f(s));s=n<s?1+g(f(n)):0;}

Try it online!

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

JavaScript (ES6), 104 86 82 bytes

-2 thanks to @emanresuA and @Shaggy, and another -2 from @tsh (with an honorable mention for @m90 :p)

r=x=>(f=x=>x+Math.min(...x+="")+Math.max(...x),g=y=>y<x?g(f(y)):y>x)(1)&&r(f(x))+1

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ 85 by putting x+'' in a variable. \$\endgroup\$
    – emanresu A
    Aug 31 at 21:05
  • \$\begingroup\$ @emanresuA, 84 bytes ;) \$\endgroup\$
    – Shaggy
    Aug 31 at 21:24
  • \$\begingroup\$ @Shaggy Ooh, clever! \$\endgroup\$ Aug 31 at 22:41
  • \$\begingroup\$ r=x=>(f=x=>x+Math.min(...x+="")+Math.max(...x),g=y=>y<x?g(f(y)):y>x)(1)&&r(f(x))+1 \$\endgroup\$
    – tsh
    Sep 1 at 7:52
  • \$\begingroup\$ Also 82: f=x=>x+Math.min(...x+="")+Math.max(...x),r=(n,a=1)=>a>n?r(f(n),a)+1:a<n&&r(n,f(a)) \$\endgroup\$
    – m90
    Sep 1 at 8:47
1
\$\begingroup\$

Python 2, 128 \$\cdots\$ 98 94 bytes

f=lambda n:n+int(min(`n`))+int(max(`n`))
g=lambda n,s=1:n>s and g(n,f(s))or n<s and-~g(f(n),s)

Try it online!

Saved 17 bytes thanks to gsitcia!!!

\$0\$-based return value and returns False for \$0\$.

\$\endgroup\$
2
  • \$\begingroup\$ 111 since s doesn't need to be a list \$\endgroup\$
    – gsitcia
    Sep 1 at 0:04
  • \$\begingroup\$ Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 1 at 0:06
1
\$\begingroup\$

Jelly, 21 bytes

;1DṀ+ṂƊ+Ɗ€</¦⁻/пḢ€QL

A monadic Link that accepts a positive integer and yields a positive integer (using the 1-indexed option).

Try it online!

How?

Perhaps there is a more terse approach, but I have not thought of one yet.

Starts with the input and \$1\$ and applies \$f\$ to the minimum of the two while they are unequal, then counts the number of values visited from the input to the final value.

;1DṀ+ṂƊ+Ɗ€</¦⁻/пḢ€QL - Link: integer, x
;1                    - concatenate a one
               п     - collect while...
             ⁻/       - ...condition: reduce by not-equal
         €  ¦         - ...do: sparse application...
          </          -       ...to indices: reduce by less-than
        Ɗ             -       ...action: last three links as a monad, f(v)
  D                   -         decimal digits
   Ṁ+ṂƊ               -         minimum plus maximum
       +              -         add (v)
                 Ḣ€   - head each (all the values we got from x's side)
                   Q  - deduplicate
                    L - length

0-indexed alternative

Also 21 bytes:

;1DṀ+ṂƊ+Ɗ€</¦⁻/пnƝSḢ
\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 62 bytes

!a=a+sum(extrema(digits(a)))
>(x,a=1)=x<a ? 1+(!x>a) : a!=x>!a

Try it online!

Explanation

  • ! is the function f
  • a is fⁿ(1) (we don't care about n)
  • 1+(!x>a): if x<a, we compute f(x) and add 1 to the result
  • a!=x>!a is parsed a!=x && x>!a
    • returns false if a==x (false is equivalent to 0) and doesn't evaluate the second part
    • if a!=x, computes x>!a, which means we compute f(a) and return x>f(a)
\$\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.