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
Improve this question
\$\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\$
    – Wheat Wizard ♦
    Aug 31, 2021 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\$
    – Dominic van Essen
    Aug 31, 2021 at 20:40
  • \$\begingroup\$ @DominicvanEssen That seems reasonable. Edited accordingly. \$\endgroup\$
    – Arnauld
    Aug 31, 2021 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, 2021 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, 2021 at 14:31

10 Answers 10

Reset to default
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
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -2 bytes by removing the S and changing the ++ to O. Nice answer, btw! \$\endgroup\$
    – Kevin Cruijssen
    Sep 2, 2021 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
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 15 bytes \$\endgroup\$
    – Razetime
    Sep 3, 2021 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\$
    – Dominic van Essen
    Sep 3, 2021 at 14:09
  • \$\begingroup\$ "An Husk".....?? \$\endgroup\$
    – user7467
    Sep 4, 2021 at 9:42
3
\$\begingroup\$

Charcoal, 45 bytes

Ｎθ≔¹η≔⁰ζＷ⁻θη¿‹ηθ≧⁺Σ⁺⌊Ｉη⌈Ｉηη«≧⁺Σ⁺⌊Ｉθ⌈Ｉθθ≦⊕ζ»Ｉζ

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

Ｎθ

Input x.

≔¹η

Start with a=1.

≔⁰ζ

Start with n=0.

Ｗ⁻θη

Repeat until x=a.

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

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

«≧⁺Σ⁺⌊Ｉθ⌈Ｉθθ

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

≦⊕ζ»

... and increment n.

Ｉζ

Output n.

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\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!

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ 85 by putting x+'' in a variable. \$\endgroup\$
    – emanresu A
    Aug 31, 2021 at 21:05
  • \$\begingroup\$ @emanresuA, 84 bytes ;) \$\endgroup\$
    – Shaggy
    Aug 31, 2021 at 21:24
  • \$\begingroup\$ @Shaggy Ooh, clever! \$\endgroup\$
    – Radvylf Programs
    Aug 31, 2021 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, 2021 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, 2021 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\$.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 111 since s doesn't need to be a list \$\endgroup\$
    – gsitcia
    Sep 1, 2021 at 0:04
  • \$\begingroup\$ Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 1, 2021 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Ḣ
Improve this answer
\$\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)
Improve this answer
\$\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.