[Question]
  [
We are all familiar with the [Fibonacci sequence](https://oeis.org/A000045):
```
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
```
However, instead of, `f(n) = f(n-1) + f(n-2)` we'll be taking [digital sum](https://en.wikipedia.org/wiki/Digit_sum) of the previous 2 entries. 
---
The sequence should still start with `0, 1`, after that the differences are rapidly apparent. This list is 0-indexed, you may use 1-indexed as well, state which you used.
```
f(0)  = 0
f(1)  = 1
f(2)  = 1   # 0 + 1
f(3)  = 2   # 1 + 1
f(4)  = 3   # 1 + 2
f(5)  = 5   # 2 + 3
f(6)  = 8   # 3 + 5
f(7)  = 13  # 8 + 5
f(8)  = 12  # 8 + 1 + 3
f(9)  = 7   # 1 + 3 + 1 + 2
f(10) = 10  # 1 + 2 + 7
f(11) = 8   # 7 + 1 + 0
f(12) = 9   # 1 + 0 + 8
f(13) = 17  # 8 + 9
f(14) = 17  # 9 + 1 + 7
f(15) = 16  # 1 + 7 + 1 + 7
f(16) = 15  # 1 + 7 + 1 + 6
f(17) = 13  # 1 + 6 + 1 + 5
f(18) = 10  # 1 + 5 + 1 + 3
f(19) = 5   # 1 + 3 + 1 + 0
f(20) = 6   # 1 + 0 + 5
f(21) = 11  # 5 + 6
f(22) = 8   # 6 + 1 + 1
f(23) = 10  # 1 + 1 + 8
f(24) = 9   # 8 + 1 + 0
f(25) = 10  # 1 + 0 + 9
f(26) = 10  # 9 + 1 + 0
f(27) = 2   # 1 + 0 + 1 + 0
(After this point it repeats at the 3rd term, 0-indexed)
```
*Note: I didn't notice the repetition until I posted the challenge itself, and here I was thinking it'd be impossible to write another novel Fibonacci challenge.*
---
Your task is, given a number `n`, output the nth digit of this sequence.
First 3 digits: `[0,1,1]`,
24-digit repeated pattern: `[2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]`
*Hint: You may be able to exploit this repetition to your advantage.*
---
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), lowest byte-count is the winner.
---
**BONUS:** If you use the repetition in your answer, I will award the lowest byte-count answer that takes advantage of the repetition in the sequence a bounty of 100 points. This should be submitted as part of your original answer, after your original answer. See this post as an example of what I am talking about: <https://codegolf.stackexchange.com/a/108972/59376>
To qualify for this bonus your code must run in constant time (`O(1)`) with an explanation.
***Bonus Winner: Dennis <https://codegolf.stackexchange.com/a/108967/59376>*** < Dennis won.
***Most Unique Implementation: <https://codegolf.stackexchange.com/a/108970/59376>  
(Also will receive 100 points, finalized after correct answer is chosen)***
  
[Answer]
## JavaScript (ES6), 45 bytes
```
f=(n,x=0,y=1)=>n?f(n-1,y,(x%9||x)+(y%9||y)):x
```
```
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>
```
`x` and `y` can't both be `9`, since that would require the previous number to be `0`, so their digital sum can't exceed `17`. This means that the digital root for numbers greater than `9` is the same as the remainder modulo `9`.
[Answer]
# Python 2, 53 bytes
```
f=lambda n:n>1and sum(map(int,`f(n-1)`+`f(n-2)`))or n
```
Recursive function. The base cases of `n=0` and `n=1` yield `n`, larger numbers calculate the value by calling `f(n-1)` and `f(n-2)` converting each to a string, concatenating the two strings, converting each character to an integer using a `map` with the `int` function, and then sums the resulting list.
---
Using the modulo-24 information I can currently get a 56 byte non-recursive unnamed function:
```
lambda n:int(('011'+'2358dc7a89hhgfda56b8a9aa'*n)[n],18)
```
[Answer]
# JavaScript (ES6), 34 bytes
```
f=n=>n<2?n:~-f(--n)%9+~-f(--n)%9+2
```
May freeze your browser for inputs above 27 or so, but it does work for all input values. This can be verified with a simple cache:
```
c=[];f=n=>n<2?n:c[n]=c[n]||~-f(--n)%9+~-f(--n)%9+2
```
```
<input type=number value=0 min=0 step=1 oninput="O.value=f(this.value)"> <input id=O value=0 disabled>
```
As pointed out in [Neil's brilliant answer](https://codegolf.stackexchange.com/a/108970/42545), the output can never exceed 17, so the digital sum of any output above 9 is equal to `n%9`. This also works with outputs below 9; we can make it work for 9 as well by subtracting 1 with `~-` before the modulus, then adding back in 1 after.
---
The best I could do with hardcoding is 50 bytes:
```
n=>"0x"+"7880136ba5867ffedb834968"[n%24]-(n<3)*9+2
```
[Answer]
# [Oasis](https://github.com/Adriandmen/Oasis), 5 bytes
Code:
```
ScS+T
```
[Try it online!](https://tio.run/nexus/oasis#@x@cHKwd8v//fyNDAA "Oasis – TIO Nexus")
Expanded version:
```
ScS+10
```
Explanation:
```
ScS+   = a(n)
     0 = a(0)
    1  = a(1)
S      # Sum of digits on a(n-1)
 c     # Compute a(n-2)
  S    # Sum of digits
   +   # Add together
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 bytes
```
;DFS
ç¡1
```
[Try it online!](https://tio.run/nexus/jelly#@2/t4hbMdXj5oYWG//8bmgIA "Jelly – TIO Nexus")
### How it works
```
ç¡1   Main link. No arguments. Implicit left argument: 0
  1   Set the right argument to 1.
ç¡    Repeatedly execute the helper link n times – where n is an integer read from
      STDIN – updating the left argument with the return value and the right
      argument with the previous value of the left argument. Yield the last result.
;DFS  Helper link. Arguments: a, b
;     Concatenate; yield [a, b].
 D    Decimal; convert both a and b to their base-10 digit arrays.
  F   Flatten the result.
   S  Compute the sum of the digits.
```
## Alternate solution, 19 bytes, constant time
```
;DFS
9⁵ç23Ð¡⁸ịµṠ>?2
```
[Try it online!](https://tio.run/nexus/jelly#ATAAz///O0RGUwo54oG1w6cyM8OQwqHigbjhu4vCteG5oD4/Mv8wcjI3wrXFvMOH4oKsR/8 "Jelly – TIO Nexus")
### How it works
```
9⁵ç23Ð¡⁸ịµṠ>?2  Main link. Argument: n
9               Set the return value to 9
 ⁵              Yield 10.
  ç23Ð¡         Execute the helper link 23 times, with initial left argument 10
                and initial right argument 9, updating the arguments as before.
                Yield all intermediate results, returning
                [10,10,2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9].
   ⁸ị           Extract the element at index n. Indexing is 1-based and modular.
     µ          Combine all links to the left into a chain.
       >?2      If n > 2, execute the chain.
      Ṡ         Else, yield the sign if n.
```
[Answer]
# JavaScript (ES6), ~~52 46~~ 45 bytes
```
_=$=>$<2?$:eval([..._(--$)+[_(--$)]].join`+`)
```
# Usage
```
_=$=>$<2?$:eval([..._(--$)+[_(--$)]].join`+`)
_(7)
```
## Output
```
13
```
# Explanation
This function checks if the input is smaller than 2, and if so, it returns the input. Otherwise, it creates an array of two values that are appended to each other as strings. Those two values are the result of calling the function with `input - 1` and `input - 2`.
The `...` operator splits this string into an array of characters, which then is converted to a string again, but now with `+`es between values. This string is then interpreted as code, so the sum is calculated, which is then returned.
This is a double-recursive algorithm, which makes it quite inefficient. It needs 2`n-2` function calls for input `n`. As such, here's a longer but faster solution. Thanks to ETHproductions for coming up with it.
```
f=($,p=1,c=0)=>$?f($-1,c,eval([...p+[c]].join`+`)):c
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 8 bytes
```
XÎF‚¤sSO
```
[Try it online!](https://tio.run/nexus/05ab1e#@x9xuM/tUcOsQ0uKg/3//zcyBwA "05AB1E – TIO Nexus")
**Explanation**
```
XÎ        # push 1,0,input
  F       # input_no times do:
   ‚      # pair the top 2 elements of the stack
    ¤     # push a copy of the 2nd element to the stack
     s    # swap the pair to the top of the stack
      S   # convert to list of digits
       O  # sum
```
[Answer]
# CJam, ~~22~~ 20 bytes
*Saved 2 bytes thanks to Martin Ender*
```
ri2,{(_(jAb\jAb+:+}j
```
Straightforward recursive algorithm, nothing fancy. 0-indexed.
[Try it online!](https://tio.run/nexus/cjam#@1@UaaRTrRGvkeWYFAPE2lbatVn//1sAAA) or [test for 0-50](https://tio.run/nexus/cjam#@29qUG2kU60Rr5HlmGSlHQMmtWuzalUL/v83BQA) (actually runs pretty fast).
**Explanation**
```
ri                    Read an integer from input
  2,                  Push the array [0 1]
    {             }j  Recursive block, let's call it j(n), using the input as n and [0 1] as base cases
     (                 Decrement (n-1)
      _(               Duplicate and decrement again (n-2)
        jAb            Get the list digits of j(n-2)
           \           Swap the top two elements
            jAb        Get the list of digits of j(n-1)
               +       Concatenate the lists of digits
                :+     Sum the digits
```
# CJam, 42 bytes
Solution using the repetition. Similar algorithm to Jonathan Allan's solution.
```
ri_2,1+"[2358DC7A89HHGFDA56B8A9AA]"S*~@*+=
```
[Try it online!](https://tio.run/nexus/cjam#@1@UGW@kY6itFG1kbGrh4mzuaGHp4eHu5uJoauZk4Wjp6BirFKxV56Clbfv/vxkA "CJam – TIO Nexus")
[Answer]
# [Perl 6](https://perl6.org), ~~41~~ 37 bytes
```
{(0,1,{[+] |$^a.comb,|$^b.comb}...*)[$_]}
```
[Try it](https://tio.run/nexus/perl6#Ky1OVSgz00u25sqtVFBLzk9JVbBV@F@tYaBjqFMdrR2rUKMSl6iXnJ@bpANkJYFZtXp6elqa0SrxsbX/ixMrFVLyFdLyixTijCwUqrkUFMCGqMRz1f7/mpevm5yYnJEKAA "Perl 6 – TIO Nexus")
```
{(0,1,*.comb.sum+*.comb.sum...*)[$_]}
```
[Try it](https://tio.run/nexus/perl6#Ky1OVSgz00u25sqtVFBLzk9JVbBV@F@tYaBjqKOll5yfm6RXXJqrjWDq6elpaUarxMfW/i9OrFRIyVdIyy9SiDOyUKjmUlAAG6ASz1X7/2tevm5yYnJGKgA "Perl 6 – TIO Nexus")
```
{ # bare block lambda with implicit parameter ｢$_｣
  (
    0, 1,           # first two values
    # WhateverCode lambda with two parameters ( the two ｢*｣ )
    *.comb.sum      # digital sum of first parameter
    +
    *.comb.sum      # digital sum of second parameter
    ...            # keep using that code object to generate new values until:
    *              # never stop
  )[ $_ ]          # index into the sequence
}
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 15 bytes
```
lOi:"yyhFYAss]&
```
[Try it online!](https://tio.run/nexus/matl#@5/jn2mlVFmZ4RbpWFwcq/b/v5E5AA "MATL – TIO Nexus")
```
lO       % Push 1, then 0. So the next generated terms will be 1, 1, 2,... 
i        % Input n
:"       % Repeat that many times
  yy     %   Duplicate top two elements in the stack
  h      %   Concatenate into length-2 horizontal vector
  FYA    %   Convert to decimal digits. Gives a 2-row matrix
  ss     %   Sum of all matrix entries
]        % End
&        % Specify that next function (display) will take only 1 input
         % Implicit display
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~54~~ 46 bytes
```
f=lambda n:n>2and~-f(n-1)%9+~-f(n-2)%9+2or n>0
```
Heavily inspired by [@ETHproductions' ES6 answer](https://codegolf.stackexchange.com/a/108977/12012).
[Try it online!](https://tio.run/nexus/python2#@59mm5OYm5SSqJBnlWdnlJiXUqebppGna6ipaqkNYRqBmEb5RQp5dgb/00C0QmaeQlFiXnqqhpGFphUXZ0FRZl6JgrqqUYqCrp0CkFJXUFXQyNNRAGrX1PwPAA "Python 2 – TIO Nexus")
[Answer]
# C, 96 bytes
*or 61 bytes counting escape codes as 1 byte each*
0 indexed. Similar to some of the other answers I am indexing a lookup table of values but I have compressed it into 4 byte chunks. I didn’t bother investigating the mod 24 version because I didn’t think it was as interesting since the others have done so already but let’s face it, C isn’t going to win anyway.
```
#define a(n) n<3?!!n:2+(15&"\x1\x36\xba\x58\x67\xff\xed\xb8\x34\x96\x87\x88"[(n-3)/2%12]>>n%2*4)
```
explanation:
```
#define a(n)                                                                                     // using a preprocessor macro is shorter than defining a function
             n<3?!!n:                                                                            // when n is less than 3 !!n will give the series 0,1,1,1..., otherwise..
                                                                             (n-3)/2%12          // condition the input to correctly index the string...
                           "\x1\x36\xba\x58\x67\xff\xed\xb8\x34\x96\x87\x88"                     // which has the repeating part of the series encoded into 4 bits each number
                                                                                                 // these are encoded 2 less than what we want as all numbers in the series after the third are 2 <= a(n>2) <= 17 which conforms to 0 <= a(n>2) - 2 <= 15
                                                                                        >>n%2*4  // ensure the data is in the lower 4 bits by shifting it down, n%2 will give either 0 or 1, which is then multiplied by 4
                        15&                                                                      // mask those bits off
                     2+                                                                          // finally, add 2 to correct the numbers pulled from the string
```
[Try it online!](https://tio.run/nexus/c-gcc#HY5BDoIwFET3nOKDwbQCkVLAKogH8bvAtE1Y8DUNJk2MZ8fqambeZJJZN9rYiQyMjDhQLy9xTKcqY6LZJugFetmiv4/oG4W@PaC3Fr3RgYUsa/TH0KvAlUqujArJ91UqqtswUFrtar5OtMA8TsQ4vCMAsA8H7A/hDGUXpAdR/kyWcXi6UFmWpBqKAVKNlOQw5@HezHn32zuzvByFZfRZvw)
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 27 25 bytes
```
U<2?U:~-ß´U %9+~-ß´U %9+2
```
[Try it online!](https://tio.run/nexus/japt#@x9qY2QfalWne3j@oS2hCqqW2khMo///DQE "Japt – TIO Nexus")
Saved 2 bytes thanks to ETHproductions.
[Answer]
# [Haskell](https://www.haskell.org/), 54 bytes
```
a!b=sum$read.pure<$>([a,b]>>=show)
g=0:scanl(!)1g
(g!!)
```
[Try it online!](https://tio.run/nexus/haskell#@5@omGRbXJqrUpSamKJXUFqUaqNipxGdqJMUa2dnW5yRX67JlW5rYFWcnJiXo6GoaZj@PzcxM0/BVgGkwSdPAahKoaAoM69EQU9BI11RUfO/oREA "Haskell – TIO Nexus") Usage: `(g!!) 12`
[Answer]
## Mathematica, 49 bytes
```
If[#<2,#,Tr[Join@@IntegerDigits[#0/@{#-1,#-2}]]]&
```
Straightforward recursive definition. Gets pretty slow after a while.
## Mathematica, ~~79~~ 71 bytes
```
If[#<3,Sign@#,(9@@LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ")[[#~Mod~24]]]&
```
Hardcoding the periodic pattern. Lightning fast and satisfyingly abusive to Mathematica :) *Thanks to JungHwan Min for saving 8 bytes!*
[Answer]
# [Python 2](https://docs.python.org/2/), 56 bytes
Simple iterative solution.
```
a,b=0,1
exec'a,b=b,(a%9or a)+(b%9or b);'*input()
print a
```
[Try it online!](https://tio.run/nexus/python2#@5@ok2RroGPIlVqRmqwO4iTpaCSqWuYXKSRqamskgVlJmtbqWpl5BaUlGppcBUWZeSUKif//GxkAAA "Python 2 – TIO Nexus")
Using `(a%9or a)+(b%9or b)` actually turned out to be shorter than `sum(map(int(`a`+`b`)))`!
[Answer]
# [PowerShell](https://github.com/PowerShell/PowerShell), 79 bytes
```
$b,$c=0,1;for($a=$args[0];$a;$a--){$z=[char[]]"$b$c"-join'+'|iex;$b=$c;$c=$z}$b
```
[Try it online!](https://tio.run/nexus/powershell#DcxLCoAgFAXQvcgFixSsUSBvJeJApY8NEmwSVms34YxPhRcIpMSo15Q7OILL22WU1XCNlP2DQibsLhtrGTwCk0eKJx/4G5dbwxOCbgfKB19rneYf "PowerShell – TIO Nexus")
Lengthy boring iterative solution that does direct digit-sum calculations each `for` loop. At the end of the loop, the number we want is in `$b`, so that's left on the pipeline and output is implicit. Note that if the input is `0`, then the loop won't enter since the conditional is false, so `$b` remains `0`.
[Answer]
## Batch, 85 bytes
```
@set/ax=0,y=1
@for /l %%i in (1,1,%1)do @set/az=x-x/10*9+y-y/10*9,x=y,y=z
@echo %x%
```
I was wondering how I was going to port my JavaScript answer to batch but the clue was in @Dennis's Python solution.
[Answer]
# Pyth, 20 bytes
```
J,01VQ=+JssjRT>2J)@J
```
A program that takes input of a zero-indexed integer and prints the result.
[Test suite](http://pyth.herokuapp.com/?code=pQp%22+-%3E+%22+J%2C01VQ%3D%2BJssjRT%3E2J%29%40J&test_suite=1&test_suite_input=0%0A1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A9%0A10%0A11%0A12%0A13%0A14%0A15%0A16%0A17%0A18%0A19%0A20%0A21%0A22%0A23%0A24%0A25%0A26%0A27&debug=0) (First part for formatting)
**How it works**
*[Explanation coming later]*
[Answer]
## Ruby, 58 bytes
```
->n{n<3?n<=>0:"9aa2358dc7a89hhgfda56b8a"[n%24].to_i(18)}
```
The simple hardcoded solution.
[Answer]
# [stacked](https://github.com/ConorOBrien-Foxx/stacked), 40 bytes
```
{!2:>[:$digitsflatmap sum\last\,]n*last}
```
This lambda is equivalent to the following lambda:
```
{n : 2:>[:$digitsflatmap sum\last\,]n*last}
```
[Try it online!](https://tio.run/nexus/stacked#@1@taGRlF22lkpKZnllSnJaTWJKbWKBQXJobk5NYXBKjE5unBWLU/newKkktLkkt4jJUMDJQqLFTUIHwFcDqM/LL/wMA "stacked – TIO Nexus")
[Answer]
# Octave, 148 bytes
```
function f = fib(n)
  if (n <= 1)
    f = n;
  else
    f = sum(int2str((fib(n - 1)))-48) + sum(int2str((fib(n - 2)))-48);
  endif
endfunction
```
[Answer]
## Haskell, 151 bytes
```
import Numeric
import Data.Char
s i=foldr(\c i->i+digitToInt c)0$showInt i""
d a b=a:d b(s a+s b)
f 0=0
f 1=1
f 2=1
f i=d 2 3!!fromIntegral(mod(i-3)24)
```
Invoke the function with `f 123456789012345678901234567890123456789012345678`, for example.
The code works also with very big indices. Because of the implemented modulo 24 functionality it is very fast.
The uncompressed code:
```
-- FibonacciDigital
-- Gerhard
-- 13 February 2017
module FibonacciDigital () where
import Numeric
import Data.Char
-- sum of digits
digitSum :: Int -> Int 
digitSum i = foldr (\c i -> i + digitToInt c) 0 $ showInt i ""
-- fibonacci digital sequence function with arbitrary starting values
fibonacciDigitals :: Int -> Int -> [Int]
fibonacciDigitals a b = a : fibonacciDigitals b (digitSum a + digitSum b)
-- index -> fibonacci digital value
f :: Integer -> Int 
f 0 = 0 
f 1 = 1 
f 2 = 1 
f i = fibonacciDigitals 2 3 !! fromIntegral (mod (i-3) 24) 
-- End
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal) `2`, 7 bytes
```
≬"Ṡ∑k≈Ḟ
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIyUCIsIiIsIuKJrFwi4bmg4oiRa+KJiOG4niIsIjMwMOG6jiIsIiJd)
[Answer]
# R, 90 bytes
A horribly long solution, but it's better than the 108 I originally had. I suspect that there is a lot better way to do this, but I can't see it at the moment.
```
function(n,x=0:1){repeat`if`(n,{x=c(x,sum(scan(t=gsub('',' ',x))))[-1];n=n-1},break);x[1]}
```
This is an unnamed function that uses `gsub` and `scan(t=` to split the numbers in the vector into digits. The sum of these is added to the vector while the first item is dropped. `repeat` is used to step through the sequence `n` times and the result is the first item of the vector.
[Answer]
# PHP, 80 Bytes
```
for($r=[0,1];$i<$argn;)$r[]=array_sum(str_split($r[$i].$r[++$i]));echo$r[$argn];
```
[Online Version](http://sandbox.onlinephpfunctions.com/code/1e93222a286864182c1c2eade6a1c2bb502b844b)
[Answer]
## Mathematica, 67 bytes
```
r=IntegerDigits;f@0=0;f@1=1;f[x_]:=f@x=Tr@r@f[x-1]+Tr@r@f[x-2];f@#&
```
[Answer]
# [Fig](https://github.com/Seggan/Fig), \$8\log\_{256}(96)\approx\$ 6.585 bytes
```
Gr2'+SxS
```
[Try it online!](https://fig.fly.dev/#WyJHcjInK1N4UyIsIiJd)
Beats Jelly for once.
```
Gr2'+SxS
G        # Generate an infinite list using the initial terms...
 r2      # [0, 1]
   '     # And the generating function...
     Sx  # Digit sum of first number
       S # Digit sum of second number
    +    # Add the sums
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 11 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
@Zo2 xì'x}g
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFpvMiB47Cd4fWc&input=OA)
]