Digital Sum Fibonacci
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
.
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)
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, 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