[Question]
  [
Given an integer ***n > 2***, print or return the smallest non-negative integer ***k*** such that ***a(n, k) = 9***, where ***a(n, k)*** is defined by:
* ***a(n, 0) = n***
* ***a(n, k+1) =***
	+ ***a(n, k) / 2 + 1*** if ***a(n, k)*** is even
	+ the sum of the digits of ***a(n, k)²*** (in base 10) if ***a(n, k)*** is odd
## Examples
For ***n = 5***, the expected output is ***k = 4***:
```
a(5, 0) = 5
a(5, 1) = 7  (5² = 25 and 2 + 5 = 7)
a(5, 2) = 13 (7² = 49 and 4 + 9 = 13)
a(5, 3) = 16 (13² = 169 and 1 + 6 + 9 = 16)
a(5, 4) = 9  (16 / 2 + 1)
```
For ***n = 40***, the expected output is ***k = 2***:
```
a(40, 0) = 40
a(40, 1) = 21 (40 / 2 + 1)
a(40, 2) = 9  (21² = 441 and 4 + 4 + 1 = 9)
```
## Clarifications and rules
* The input is guaranteed to be greater than 2.
* Your program should theoretically work for any value of ***n***. (In practice, it may be limited by the maximum integer size supported by your language.)
* ***k*** may be either 0-indexed or 1-indexed. Please state it in your answer.
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest answer in bytes wins!
## First values
Below are the first values from ***n = 3*** to ***n = 422***, with ***k*** 0-indexed. (For 1-indexing, just add `1` to these values.)
```
 1  2  4  3  3  5  0  4  3  4  2  6  1  1  6  5  5  4  1  5  2  3  3  7  6  2  3  2  2  7
 6  6  5  6  6  5  1  2  2  6  6  3  1  4  3  4  4  8  1  7  6  3  5  4  6  3  2  3  3  8
 7  7  3  7  4  6  6  7  5  7  6  6  6  2  4  3  3  3  6  7  3  7  2  4  7  2  6  5  6  4
 7  5  2  5  6  9  6  2  3  8  2  7  1  4  6  6  6  5  1  7  4  4  3  3  7  4  3  4  2  9
 6  8  6  8  6  4  6  8  2  5  3  7  6  7  3  8  2  6  7  8  6  7  5  7  6  7  4  3  3  5
 6  4  3  4  4  4  6  7  6  8  3  4  6  8  7  3  6  5  6  8  3  3  2  7  6  6  5  7  6  5
 7  8  2  6  3  3  6  6  6  7  4 10  6  7  3  3  6  4  1  9  2  3  3  8  7  2  6  5  2  7
 7  7  6  7  3  6  7  2  4  8  3  5  6  5  6  4  2  4  6  8  3  5  6  4  7  5  2  3  6 10
 7  7  3  9  2  7  1  9  5  7  6  5  6  7  4  9  6  3  6  6  3  4  2  8  7  7  6  8  6  4
 7  9  4  3  3  7  7  8  3  9  4  7  6  8  3  6  6  8  7  7  7  8  6  5  7  4  6  4  2  6
 7  7  6  5  3  4  7  5  4  5  3  5  7  7  6  8  2  7  1  9  6  4  6  5  7  7  2  9  6  8
 7  4  3  7  4  6  6  7  6  9  3  4  6  4  2  3  3  8  1  7  6  7  2  6  7  8  3  7  5  6
 7  8  2  9  3  3  6  7  6  4  4  4  6  7  6  7  6  7  6  8  7  5  6 11  7  7  3  8  4  4
 7  4  6  7  3  5  6  2  2 10  6  3  6  4  3  4  4  9  7  8  3  3  6  7  7  6  4  3  6  8
```
  
[Answer]
# [Perl 6](https://perl6.org), 41 bytes (40 chars)
```
{+($_,{$_%2??[+] $_².comb!!$_/2+1}...9)}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJKmYKvwv1pbQyVep1olXtXI3j5aO1ZBJf7QJr3k/NwkRUWVeH0jbcNaPT09S83a/9ZcxYkgXRomBprW/wE "Perl 6 – Try It Online")
This uses 1-indexing of k's, so it gives 1 higher answers than the examples in OP. If this is not what the 1-indexing means, I'll have to add 1 byte more.
**Explanation**: It's an anonymous function. We just use the Perl 6's facility for generating lists using recursion :—). It looks like this: `(first element),(block that takes the previous element and gives the next)...(end condition)`. In this case, the first element is `$_` (argument of the main function) and the end condition is `9` (fulfilled when we generate a 9). In the middle block, we use `$_` to refer to its argument ( = the previous element of the sequence). The `?? !!` is the old ternary operator (better known as `? :`). Finally, we take the length of this list by forcing numerical context by `+(...)`.
The last weird thing here is the sum of digits. Numbers are `Cool` (behave both like strings and numbers), so we use a string method `.comb` on `$_²` (give list of characters = digits), then adding the characters up (that converts them back to numbers).
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 17 bytes
```
²DSµH‘$Ḃ?ßµ-n9$?‘
```
[Try it online!](https://tio.run/##y0rNyan8///QJpfgQ1s9HjXMUHm4o8n@8PxDW3XzLFXsgQL///83MQAA "Jelly – Try It Online")
Straight-forward approach. Uses 0-based indexing.
## Explanation
```
²DSµH‘$Ḃ?ßµ-n9$?‘  Input: n
               ?   If
            n9$      n != 9
          µ        Then
        ?            If
       Ḃ               n % 2 == 1
   µ                 Then
²                      Square
 D                     Decimal digits
  S                    Sum
      $              Else
    H                  Halve
     ‘                 Increment
         ß           Call recursively
                   Else
           -         The constant -1
                ‘  Increment
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~129~~ ~~126~~ ~~76~~ ~~68~~ ~~67~~ ~~64~~ ~~54~~ 53 bytes
*-3 bytes thanks to Jonathan Frech. -8 bytes thanks to Maltysen. -7 bytes thanks to Jonathan Allan. -1 byte thanks to Mr. Xcoder.*
```
f=lambda n:n-9and-~f(n%2*sum(map(int,`n*n`))or 1+n/2)
```
[Try it online!](https://tio.run/##VVBBboMwELzzihFSFQimKeaUSOm1v6hi6gUcYEG2aZVLv04NqpJ2Tzuzs7OrmW6@HVkucRxHb@aTGIxXSIHJGvYYLSz52TJ8S3CD6ntyHjxyztQoHzYQdNSQRQc3f7RBqDxUwgJdijOOAl8tWbpTxkFTbZg0qtspQqht9LKq@YG7rAjMhh9cigMkMhQw9V9HCp/fpdur84Cx3lptGuPdin4X3iUSw6iUIxTh7H@rUesopLHU514NlVbgE@dHxTr/rhN@kvtgnQxqChZeXHjPlzQNMRUZH2S6bLElO@yer6PhTee8FVibWsAqbigpBcoyXWv5AQ "Python 2 – Try It Online")
From somebody who probably doesn't know enough math, this seems completely arbitrary. :P
[Answer]
# [Husk](https://github.com/barbuz/Husk), 13 bytes
```
€9¡?o→½ȯΣd□¦2
```
This is 1-indexed. [Try it online!](https://tio.run/##ASMA3P9odXNr///igqw5wqE/b@KGksK9yK/Oo2TilqHCpjL///80MA "Husk – Try It Online")
## Explanation
Nothing too fancy here.
```
€9¡?o→½ȯΣd□¦2  Implicit input, say n = 5
  ¡            Iterate the following function:
   ?       ¦2   If divisible by 2,
    o→½         then halve and increment,
       ȯΣd□     else square, take digits and get their sum.
               This gives an infinite sequence: [5,7,13,16,9,9,9,9,9..
€9             1-based index of 9; print implicitly.
```
[Answer]
# Mathematica, 58 bytes
1-indexed
```
If[#!=9,#0@If[OddQ@#,Total@IntegerDigits[#^2],#/2+1]+1,0]&
```
[Try it online!](https://tio.run/##y00sychMLv6fZvvfMy1aWdHWUkfZwAHI9E9JCXRQ1gnJL0nMcfDMK0lNTy1yyUzPLCmOVo4zitVR1jfSNozVNtQxiFX7H1CUmVeioO@Qpu8QlJiXnhptrGNsEPv/PwA "Mathics – Try It Online") (in order to work on Mathics, `Tr` is replaced with `Total`)  
  
here is -1 byte version *by @JungHwanMin* (but it doesn't work on mathics so I kept both)
# Mathematica, 57 bytes
```
If[#!=9,#0@If[2∣#,#/2+1,Total@IntegerDigits[#^2]]+1,0]&
```
[Answer]
# JavaScript (ES6), ~~59~~ 50 bytes
0-indexed.
```
f=n=>n-9&&f(n%2?eval([...""+n*n].join`+`):n/2+1)+1
```
---
## Try it
```
o.innerText=(
f=n=>n-9&&f(n%2?eval([...""+n*n].join`+`):n/2+1)+1
)(i.value=5);oninput=_=>o.innerText=f(+i.value)
```
```
<input id=i min=3 type=number><pre id=o>
```
---
## Explanation
The first thing we do is calculate `n-9`. If `n==9` then that, obviously, gives `0` and things stop there. If `n!=9` then `n-9` will give a non-zero value which, being truthy, means we can continue on through the logical AND. We call the function again, passing a new `n` to it, calculated as follows:
```
n%2?
```
If `n` modulo `2` is truthy - i.e., `n` is odd.
```
[...""+n*n]
```
Multiply `n` by itself, convert it to a string and destructure that string to an array of individual characters (digits).
```
 .join`+`
```
Rejoin the characters to a string using `+`, giving us a mathematical expression.
```
eval(                   )
```
Evaluate that expression, giving us the sum of the digits of `n*n`.
```
:n/2+1
```
If `n%2` is falsey (i.e., `n` is even) then we simply divide `n` by `2` and add `1`.
To the result of calling the function again, we then add `1`. So, using an initial input of `5`, the process goes as follows:
```
f(5)
= -4&&f(7)+1
= -2&&(f(13)+1)+1
=  4&&((f(16)+1)+1)+1
=  7&&(((f(9)+1)+1)+1)+1
=     (((0+1)+1)+1)+1
= 4
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~16~~ 15 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
-1 byte thanks to [miles](https://codegolf.stackexchange.com/users/6710/miles) (use of ternary if)
```
²DSµH‘µḂ?_9$Ð¿L
```
A monadic link taking and returning numbers.  
**1-indexed**
**[Try it online!](https://tio.run/##ASUA2v9qZWxsef//wrJEU8K1SOKAmMK14biCP185JMOQwr9M////MTk0 "Jelly – Try It Online")** or see a [test-suite](https://tio.run/##ATIAzf9qZWxsef//wrJEU8K1SOKAmMK14biCP185JMOQwr9M/zNyNDIyw4figqzigJlzMzBH/w "Jelly – Try It Online") (coerces results to be 0-indexed and formats like OP code-block)
### How?
```
²DSµH‘µḂ?_9$Ð¿L - Link: number, n
            Ð¿  - collect results in a list while:
           $    -   last two links as a monad:
         _9     -     subtract nine
        ?       -   if:
       Ḃ        -     bit - current loop input modulo by 2 (1 if odd, 0 if even)
   µ            -   ...then:
²               -     square the current loop input
 D              -     cast to a list of its decimal digits
  S             -     sum
      µ         -   ...else:
    H           -     halve current loop input
     ‘          -     increment
              L - length (get the number of results collected
                -         - this includes the 9, so is 1-indexed w.r.t. k)
```
[Answer]
## Haskell, ~~62~~ 59 bytes
```
f 9=0
f a=1+f(cycle[div a 2+1,sum[read[d]|d<-show$a^2]]!!a)
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P03B0taAK00h0dZQO00juTI5JzU6JbNMIVHBSNtQp7g0N7ooNTElOiW2JsVGtzgjv1wlMc4oNlZRMVHzf25iZp6CrUJKPpeCgkJBUWZeiYKKQpqCKSrXxOA/AA "Haskell – Try It Online")
Edit: -3 bytes thanks to @Ørjan Johansen.
[Answer]
# [Perl 5](https://www.perl.org/), 56 + 1 (-n) = 57 bytes
```
$|++,$_=$_%2?eval$_**2=~s/./+$&/gr:1+$_/2while$_-9;say$|
```
[Try it online!](https://tio.run/##K0gtyjH9/1@lRltbRyXeViVe1cg@tSwxRyVeS8vItq5YX09fW0VNP73IylBbJV7fqDwjMydVJV7X0ro4sVKl5v9/y3/5BSWZ@XnF/3V9TfUMDA3@6@YBAA "Perl 5 – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 16 bytes
```
[Ð9Q#Èi2÷>ënSO]N
```
[Try it online!](https://tio.run/##MzBNTDJM/f8/@vAEy0Dlwx2ZRoe32x1enRfsH@v3/7@JkREA "05AB1E – Try It Online")
**Explanation**
```
[                  # start a loop
 Ð                 # triplicate current number
  9Q#              # if it equals 9, break
     Èi            # if even
       2÷>         # divide by 2 and increment
          ë        # else
           n       # square
            SO     # sum digits
              ]    # end loop
               N   # push the iteration counter N
```
[Answer]
# VB.NET (.NET 4.5.2), 107 + 20 (imports) = 117 bytes
Requires `Imports System.Linq`
```
Function A(n)
While n<>9
n=If(n Mod 2=0,n/2+1,CStr(n^2).Sum(Function(c)Val(c)))
A+=1
End While
End Function
```
Function which takes `n` as an integer input and returns a 0-based `k`.
Ungolfed:
```
Function A(n) ' input/output types are Object, but we will be casting to integer
    'A = 0 ' VB will create an implicit variable with the same name as the function
    ' loop until a(n, k) = 9
    ' using n as the variable to store a(n, k)
    While n <> 9
        n = If(n Mod 2 = 0, ' equivalent to c# ternary ?: operator
            n / 2 + 1, ' even case
            CStr(n ^ 2).Sum(Function(c) Val(c)))
            ' odd case
            ' cast number to string
            ' then convert each char to the number it represents
            ' and do a linq sum
        A += 1 ' Object + Integer will coerce to an integer
    End While
    ' Where's the return?
    ' That implicit variable with the matching name will get returned if there's no explicit return
End Function
```
[Answer]
# Golfscript, 34 bytes
[Try it online!](http://golfscript.apphb.com/?c=OyI0MCIKfns5LX17LjIley4qYHsrNDgtfSo0OC19ezIvKX1pZn0vLA%3D%3D)
I really need a better way than I have to add up the digits of a number.
```
~{9-}{.2%{.*`{+48-}*48-}{2/)}if}/,
```
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), ~~23~~ 22 bytes
For now, this is a recursive function ~~but I'll try to switch to `.W` (functional while) to save bytes instead~~.
```
L&-b9hy|*%b2sj^b2Th/b2
```
**[Try it here!](https://pyth.herokuapp.com/?code=L%26-b9hy%7C%2a%25b2sj%5Eb2Th%2Fb2%3B%2B%225+-%3E+%22%60y5%2B%2240+-%3E+%22%60y40%3B&input=%22Test%22%0A2&test_suite=1&debug=0)** (with additional code to call the function - use **`y`**`<your_number>` - without spaces)
[Answer]
# Java 8, ~~110~~ 98 bytes
```
n->{int k=0,s;for(;n!=9;k++){s=0;for(int c:(n*n+"").getBytes())s+=c-48;n=n%2<1?n/2+1:s;}return k;}
```
0-indexed
**Explanation:**
[Try it here.](https://tio.run/##dU/BasMwDL33K7TCwJ6XLC0dbPW8we7rpcfRg@e6xU2qBEsplJBvz5ys14Ek0HtC772Tvdisbjye9uXgKksEXzZgNwMIyD4erPOwGdcJACfGiVInpE@dithycLABBAMDZu/deFKa4pH0oY5C45151aVSsiNTTND0aS3wAdV8LvOj588rexJSkjIuW71oNHi/fFt84NNSLdak@@i5jQil7gc9S6pN@1Ml1Zv4pQ57OCfjYssx4PF7B1b@ud5eif05r1vOm0RxhQJzJ57llOFfflXIW8h@@AU)
```
 n->             // Method with integer as both input and return-type
   int k=0,      //  Result-integer `k` starting at 0
       s;        //  Sum-integer
   for(;n!=9;    //  Loop (1) as long as `n` is not 9
        k++){    //    And increase `k` by 1 after every iteration
     s=0;        //   Reset sum `s` to 0
     for(int c:(n*n+"").getBytes())
                 //   Do `n*n` and inner loop (2) over the digits as characters
       s+=c-48;  //    And increase the sum `s` with these digits
                 //   End of inner loop (2) (implicit / single-line body)
     n=n%2<1?    //   If `n` is even:
        n/2+1    //    Change `n` to `n/2+1`
       :         //   Else:
        s;       //    Change `n` to sum `s`
  }              //  End of loop (1)
  return k;      //  Return the result `k`
}                // End of separated method (2)
```
[Answer]
# [Clojure](https://clojure.org/) v1.8, ~~124~~ ~~113~~ 112 bytes
0-indexed
```
(fn[n](loop[a n k 0](if(= a 9)k(recur(if(even? a)(+(/ a 2)1)(apply +(map #(-(int %)48)(str(* a a)))))(inc k)))))
```
[Try it online!](https://repl.it/languages/clojure)
# Explanation
```
(loop[a n k 0](if(= a 9)...))  Loop until a=9
(if(even? a)(+(/ a 2)1)...)    If even, a(n, k) / 2 + 1 if a(n, k)
(if(even? a)...(apply +(map #(-(int %)48)(str(* a a)))))  If odd, calculate the sum of digits of a(n, k)²
#(-(int %)48)                  Convert character to number
```
[Answer]
# Pyth, 18 bytes
```
tl.u?%N2sj*NNTh/N2
```
Try it online: [Demonstration](http://pyth.herokuapp.com/?code=tl.u%3F%25N2sj%2aNNTh%2FN2&input=5&test_suite_input=3%0A4%0A5%0A6%0A7%0A8%0A9%0A10%0A11%0A12%0A13%0A14%0A15%0A16%0A17%0A18%0A19%0A20%0A21%0A22%0A23%0A24%0A25&debug=0)
### Explanation:
```
tl.u?%N2sj*NNTh/N2
  .u                 apply the following function to the input, 
                     until it runs into a fixed point
    ?%N2                if value % 2 == 1:
          *NN               value * value
         j   T              convert to digits
        s                   sum
                        else:
               /N2          value / 2
              h              + 1
 l                   get the length of all visited values
t                     - 1
```
[Answer]
# Japt, ~~22~~ 21 bytes
0-indexed.
```
NcUÆ=v ?U/2Ä:U²ìxÃ b9
```
[Try it](https://ethproductions.github.io/japt/?v=1.4.5&code=TmNVxj12ID9VLzLEOlWy7HjDIGI5&input=NDIy)
---
## Explanation
Implicit input of integer `U`.
```
UÆ             Ã
```
Generate an array of integers from `0` to `U-1` and pass each through a function.
```
=
```
Set the value of `U`.
```
v ?
```
If `U` is divisible by 2.
```
U/2Ä
```
`U` divided by 2, plus 1 (`Ä`).
```
:U²ìx
```
Else: `U` to the power of 2 (`²`), split to an array of digits (`ì`) and reduced by addition (`x`).
```
Nc
```
Append the resulting array to the array of inputs.
```
b9
```
Find the index of the first occurrence of `9` in the array. Implicitly output the result.
]