Answer-Chaining Fibonacci

Question

(Inspired by ASCII's 95 Characters...95 Movie Quotes)

The Challenge

Given input n, output the nth Fibonacci number. You can use either 0 or 1 indexing, please state which in your submission. Simple, yeah? The catch is you must take the character set of the immediate previous answer, remove two characters from it, and add a separate character. The separate character must

• not be from the immediate previous answer's character set
• be from the set of (printable ASCII, space, newline, horizontal tab)

and thus your total character set size will be exactly one smaller than the immediate previous answer's set.

The initial answer

The first submission must contain a subset of (all printable ASCII, space, newline, and horizontal tab) with two characters removed. Every submission thereafter must restrict their answers to this original ASCII-only format (meaning you can't add a Unicode or extended-ASCII character ... sorry Jelly, APL, et al.).

Examples and Clarifications

• Suppose the first answer is in C and contains (almost all printable ASCII, newline, and horizontal tab), and omits the % and ^ from its character set. The second submission, then, must remove two characters from the previous (almost all printable ASCII, newline, and horizontal tab) character set and add in either the % or ^. Perhaps it's a one-liner PowerShell answer that omits the newline. And so on.
• If the previous answer had print(){}!*+ as its character set (12 characters), your submission could have print(){}! (10 characters) and one additional character, print(){!+ (10 characters) and one additional character, etc.
• If the previous answer had print(){}!*+ as its character set (12 characters), your submission could not have print() and & (8 characters) as its character set, since 12 - 8 > 1.
• If the previous answer had print(){}!*+ as its character set (12 characters), your submission could not have print(){}! (10 characters) plus additional character * as its character set, since even though that's 11 characters, the * is included in the previous set.
• Not every character in your character set must do something useful for your submission. For example, if the previous answer had print(){}!*+ as its character set, and your language has a built-in ! that calculates the Fibonacci sequence and # that starts a comment, your submission could be !#print(){} and still be valid.
• You can use the same character from your character set multiple times. For example, suppose your character set was !*#_, your answer could be !!!**#**#_!! and would be acceptable.
• In addition to your code (and an explanation is nice, too!) please also explicitly list your character set, to make it easier for future submissions.

Winning

The winner of the challenge will be the person who posted the second most-recent submission (i.e., not the person who posted last, since they broke the chain).

Final Rules

Usual answer-chaining rules apply:

• The same person can't post twice in a row
• If an answer is deemed invalid (for example, it used a forbidden character, or doesn't calculate correctly), it needs to be deleted (and any subsequent answers that chain off of it also)
• Two users who post "at the same time" will have to let the earlier submission stand
• The same language cannot be posted twice in a row. For the purposes of this rule, languages of the same family (e.g., Python 2 and Python 3) count as "the same language."

---

Final things:

• This post works best if you sort by "Oldest" so that the answers are in proper order.
• Kyle Gullion constructed a code checker in Python here to verify if you're missing or using wrong characters.

Answer 1

1. C

Contains no { or }.

#if 1
#define Q !"$&'",./=@[]^_\`|*
int WERTYUIOPASDFGHJKLZXCVBNM34567890(qwrtyuopasghjklzxcvbm)<%
	return qwrtyuopasghjklzxcvbm<2?1:WERTYUIOPASDFGHJKLZXCVBNM34567890(~-qwrtyuopasghjklzxcvbm)+WERTYUIOPASDFGHJKLZXCVBNM34567890(qwrtyuopasghjklzxcvbm-2);
%>
#endif

Try it online!

_{I hope I did this right.}

Answer 2

8. Octave

Added U and removed + and -. Solution contains no +-`01AEI or tab character.

% !"#$&\'*./256789:<>?BCDFGHJKLMNOPQRSTUVWXYZ\\_abceghijklnpqrstuvwyz{|}~
f=@(x)([mod(4,3) mod(4,3);mod(4,3) mod(4,4)]^x)(3)

Based on the Fibonacci Matrix.

Answer 3

33, MATL

Added -, removed (). Solution doesn't contain !&'()/\01?AEIKLMNPSTWZ`dmwz{}|~, tab, space, or newline.

5X^Hq+G^Hq5X^-G^-HG^5X^*Hqqq^*Yo%"#$,.2346789:;<=>@BCDFJOQRUV[]_abcefghijklnprstuvxy

Try it at MATL Online

Fixed mistake: 0, 1, and \ were accidentally left in the comment (after the %) at the end. Their removal does not break the functionality. Moved this answer from 32 to 33 in an attempt to keep it valid. If it needs to be deleted, please let me know and I'll do just that.

Answer 4

2. Mathematica

Contains no }, Z, or horizontal tab. (Reincluded {.)

(* !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXY
[\]^_`\abcdefghijklmnopqrstuvwxyz{|~ *)
Fibonacci

The two first lines are just a comment; the last line is the builtin function, using the Only True Super Cosmically Ordained Indexing where inputs 0 and 1 yield outputs 0 and 1 respectively (I have no idea whether to call this 0-indexed or 1-indexed).

Answer 5

36. Java

Added \. Removed qx. Doesn't use !&'()/1?AEIKLMNPSTWZ`dmnqtwxz{}|~[], tab, or space.

\u002f\u002f"#$%*:>@BCGHJOQRUVXY^_jk
class
Fibo\u006eacci\u007b
i\u006e\u0074
fib\u0028i\u006e\u0074
\u006e\u0029\u007b
i\u006e\u0074
lo\u0077=0,high=3-2,\u0074e\u006Dp;
for\u0028i\u006e\u0074
i=3-2;i<\u006e;i++\u0029\u007b
\u0074e\u006Dp=lo\u0077;
lo\u0077=high;
high=high+\u0074e\u006Dp;
\u007D
re\u0074ur\u006e
lo\u0077;
\u007D
public
s\u0074a\u0074ic
voi\u0064
\u006Dai\u006e\u0028\u0053\u0074ri\u006eg\u005b\u005Db\u0029\u007b
Fibo\u006eacci
a=\u006ee\u0077
Fibo\u006eacci\u0028\u0029;
for\u0028i\u006e\u0074
i=3-2;i<=20;i++\u0029\u007b
\u0053ys\u0074e\u006D.ou\u0074.pri\u006e\u0074l\u006e\u0028a.fib\u0028i\u0029\u0029;
\u007D
\u007D
\u007D

I know I probably could have waited longer but I wanted to make sure to get this out before it was too late. Not only does this class define a function which takes an integer n and return that Fibonacci number, but it also prints the first 20 for you just for fun. I tried to do my due diligence by writing this in plain old java with no sneaky golfing and then I removed illegal characters 1 by 1 until we got to the creature you see before you now.

Try it online!

Answer 6

37. Python 2

Readded x. Doesn't use !&'()/1?AEIMNPSTWZdmnqtwz{}|~[], space, tab or `. Removed K and L.

f=u"\u0074"
b=u"\u006D"
i=u"\u0028"
j=u"\u0029"
h=u"\u006e"
r=2.2360679775
s=u"\u002F"
exec"p="+i+"3-2+r"+j+s+"2"
exec"g=i"+h+"pu"+f+i+j
exec"pri"+h+f+i+"i"+h+f+i+i+"p**g-"+i+"-p"+j+"**-g"+j+s+"r"+j+j
#$%´:;<=>@BCGHJOQRUVXY^agklopvy

With comments:

f=u"\u0074" #t
b=u"\u006D" #m
i=u"\u0028" #(
j=u"\u0029" #)
h=u"\u006e" #n
r=2.2360679775 #sqrt(5)
s=u"\u002F" #/
exec"p="+i+"3-2+r"+j+s+"2" #p=(3-2+r)/2 = (1+sqrt(5))/2 = phi
exec"g=i"+h+"pu"+f+i+j #g=input()
exec"pri"+h+f+i+"i"+h+f+i+i+"p**g-"+i+"-p"+j+"**-g"+j+s+"r"+j+j #print(int((p**g-(-p)**-g)/r))

This approach uses the fibonacci series' general term.

Answer 7

3. Brain-Flak

Contains no Z, ~, A, or horizontal tab. (Re-included })

({}<(())>){({}<(({})<>)<>({}{}<<>({}<>)>)>[()])}{}{}
# !"$%&'*+,-./0123456789:;=?@BCDEFGHIJKLMNOPQRSTUVWXY\^_`abcdefghijklmnopqrstuvwxyz|

Try it online!

Answer 8

5, Haskell

Removed AEIOU and tab, added Z

-- #!"$%&'*./23456789;:<>?@BCDFGHJKLMNPQRSTVWXYZ[\]^`abcdeghijklmopqrstuvwxyz{|}~,_
f 0 = 1
f 1 = 1
f n = f (n-1) + f (n-2)

Try it online!

Answer 9

12. Python 3

added : removed {; doesn't contain {};`01AEIPQx or tab character.

#!"#$%&\',./23456789?@BCDFGHJKLMNORSTUVWXYZ[\]^_abcdgjkmopqrvwyz|~:
def fib(n,a=3-2,b=3-2):
 if n==2-2:
  return a
 a, b = b, a + b
 return fib(n-1,a,b)

Answer 10

6. Brain-Flak

({}<(())>){({}<(({})<>)<>({}{}<<>({}<>)>)>[()])}{}{}
# !"$%&'*+,-./0123456789:;=?@BCDFGHJKLMNOPQRSTVWXY\^bcdfghjklmnopqrstvwxyz|

Try it online! Doesn't use tabAEIU`_, and added back O

Answer 11

26. Prolog (SWI)

Added %. Removed NK. Doesn't use &*01AEIKLMNPSTWZ`dmrwz{}], tab or newline.

a(X,B):-X<3,B is 4-3;C is X-4-(-3),D is X-2,a(C,G),a(D,F),B is G-(-F).%!"#$'/56789=>?@HJOQRUVY[\^_bcefghjklnopqtuvxy|~

Try it online!

Answer 12

34. brainfuck

Added newline, removed n and t. Doesn't use !&'()/\01?AEIKLMNPSTWZ`dmntwz{}|~, tab, or space. (maybe we can get some 2D languages now)

0-indexed. Input/output is by byte values.

,[->]+>+<<[->>[->+<]<[->+<]>>[-<+<+>>]<<<]>>.
"#$%*23456789:;=@BCDFGHJOQRUVXY^_abcefghijklopqrsuvxy

Try it online!

Answer 13

4, Python 2

Removed AEIZ, tab added ~

# !"$%&'*-./23456789;<>?@BCDFGHJKLMNOPQRSTUVWXY[\]^`chjklmpqsvwxyz{|}

def f(x):
 a=0
 b=1
 for _ in range(x):
  a,b = a+b,a
 return a

Try it online!

Answer 14

11. Standard ML (mosml)

Added +. Removed :}. Doesn't contain :}0`1AEIPQx or tab character.

(* !"#$%&\',./23456789;<>?@BCDFGHJKLMNORSTUVWXYZ[\]^_abcdgjkmopqrvwyz{|~ *)
fun f s = if s = 2-2 then 2-2 else if s = 3-2 then 3-2 else f (s-4+2) + f (s-3+2)

SML isn't on TIO, and I used the moscow ml variety, but there's an online SMLNJ interpreter here.

Answer 15

10. C

Added m, removed PQ. Doesn't contain +`01AEIPQx or tab character.

Compiler flag: -lm

//!"#$%&'*346789:<=>?@BCDFGHJKLMNORSTUVWXYZ[\]^_acfghkmvyz|.

double fib(i){
    double j = -(-~-2-sqrt(5))/2;
    return floor((pow(j,i)-pow(-j,-i))/sqrt(5));
}

Try it online!

Answer 16

9. Python 2

Added -, removed m and x. Contains no +`01AEImx or tab character.

# --!"$%&'*./29;:<>?@[\]^345678BCDFGHJKLMNOPQRSTUVWXYZabcdeghijklopqrstuvwyz{|}~,_

def fibonacci(n):
    elif n==(2/2):
        return 2-2
    elif n==2:
        return 2/2
    else:
        return fibonacci(n-2/2)-(-(fibonacci(n-2)))

Recursive Python function! Adds all Fibonacci numbers backwards until n is 1.

Answer 17

18. Octave

Added ; and removed f and space. Solution contains no {}:`*%01AEIPQfrd, no tab, no newline, and no space characters.

g=@(x)([4-3,4-3;4-3,4-4]^x)(3)#!"$&'+./256789<>?BCDFGHJKLMNORSTUVWXYZ\_abcehijklmnopqstuvwyz|~

Identical to answer 8, just with more SML hate :P

Answer 18

23. Standard ML (mosml)

There we go again. Added Q, removed } and ]. Doesn't use %&*+01:AEILMPZ`dmrzM{}], tab, or linefeed

fun f x = #2("!#$\\',.23456789<>?@BCDFGHJKNOQRSTUVWXY[/;^_abcgjkopqvwxy|~", if x = 2-2 then 2-2 else if x = 3-2 then 3-2 else f (~(~(x-4)-2)) + f (x-(~3-2)))

Answer 19

25. CJam

Added + back, removed S and T. Doesn't use %&*01AEILMPSTZ`dmrz{}]Ww, tab, or linefeed.

Basically a port of my older answer, but this one uses some eval trickery to circumvent the lack of braces.

q~"XX"a:~'|("_(j\((j+"'|)'j+++~e# !$,-./23456789;<=>?@BCDFGHJKNOQRUVY[^bcfghiklnopstuvxy

0-indexed.

Try it online!

Answer 20

27. JavaScript

Added *, removed " and '. Doesn't use "&'01AEIKLMNPSTZ`dmrz{}]Ww, tab, or linefeed.

f=a=>a<2?3-2:f(a-3+2)+f(a-4+2)/* !#$,.56789;%@BCDFGHJOQRUVXY[\^_bceghijklnopqstuvxy|~*/

Answer 21

28. Haskell

f=length"":scanl(+)(length"f")f;g=const(f!!)"#$%*,./23456789<>?@BCDFGHJOQRUVXY[\\^_bijkpquvxy|~"

Try it online! Usage: g 3 gives 2.

Added ", removed <space> and -. Does not use &'-01AEIKLMNPSTZ`dmrz{}]Ww or any white spcae.

Answer 22

30. Standard ML

Added :, removed + and ?. Does not contain !&'+-01?AEIKLMNPSTWZ`dmrwz{} or any white space.

fun$(a,b,x)n=if(length(x)=n)then(length(a))else$(b,a@b,()::x)n;("#%*./23456789<>BCDFGHJOQRUVXY\\^_cjkopqvy|~";$([],[()],[]))

The first part fun$(a,b,x)n=if(length(x)=n)then(length(a))else$(b,a@b,()::x)n defines a function $ which computes the nth fibonacci number itereatively using an unary list encoding. The length of argument x indicates the current number and a and b are lists of length fib(length(x)-1) and fib(length(x)). If n equals length(x) we return length(b), otherwise recursively add a and b via list concatenation and increment x by adding an element () to it.

The second part ("#%*./23456789<>BCDFGHJOQRUVXY\\^_cjkopqvy|~";$([],[()],[])) is a sequence where the string is discarded and $([],[()],[]) is the initialisation of the function $ with a = 0, b = 1 and x = 0, resulting in an anonymous function which computes the nth fibonacci number.

Answer 23

32, Python 3

exec(chr(2**2+2**5+2**6)+chr((3^2)+2**2+2**5+2**6)+chr(2+2**2+2**5+2**6)+chr(2**5)+chr(2+2**2+2**5+2**6)+chr(2**3+2**5)+chr(2**3+2**4+2**5+2**6)+chr((3^2)+2**3+2**5)+chr(2+2**3+2**4+2**5)+chr(2+2**3)+chr(2**5)+chr((3^2)+2**5+2**6)+chr((3^2)+2**2+2**3+2**4+2**5)+chr(2**4+2**5)+chr(2+2**3)+chr(2**5)+chr(2+2**5+2**6)+chr((3^2)+2**2+2**3+2**4+2**5)+chr((3^2)+2**4+2**5)+chr(2+2**3)+chr(2**5)+chr(2+2**2+2**5+2**6)+chr((3^2)+2+2**2+2**3+2**5+2**6)+chr(2+2**4+2**5+2**6)+chr(2**5)+chr((3^2)+2+2**2+2**3+2**4+2**6)+chr(2**5)+chr((3^2)+2**3+2**5+2**6)+chr(2+2**2+2**3+2**5+2**6)+chr(2**5)+chr(2+2**4+2**5+2**6)+chr((3^2)+2**5+2**6)+chr(2+2**2+2**3+2**5+2**6)+chr((3^2)+2+2**2+2**5+2**6)+chr((3^2)+2**2+2**5+2**6)+chr(2**3+2**5)+chr(2**3+2**4+2**5+2**6)+chr((3^2)+2**3+2**5)+chr(2+2**3+2**4+2**5)+chr(2+2**3)+chr(2**5)+chr(2**5)+chr((3^2)+2**5+2**6)+chr(2**2+2**3+2**5)+chr(2+2**5+2**6)+chr(2**5)+chr((3^2)+2**2+2**3+2**4+2**5)+chr(2**5)+chr((3^2)+2**5+2**6)+chr((3^2)+2+2**3+2**5)+chr(2+2**5+2**6)+chr(2**2+2**3+2**5)+chr((3^2)+2**5+2**6)+chr(2+2**3)+chr(2**5)+chr(2+2**4+2**5+2**6)+chr((3^2)+2**2+2**5+2**6)+chr(2**2+2**4+2**5+2**6)+chr((3^2)+2**2+2**4+2**5+2**6)+chr(2+2**4+2**5+2**6)+chr(2+2**2+2**3+2**5+2**6)+chr(2**5)+chr((3^2)+2**5+2**6))#"$%,.789:;<=>@BCDFGHJOQRUVXY[]_abfgijklnopqstuvy

Added r and removed |~. Solution contains no !&'/\-01?AEIKLMNPSTWZ`dmrwz{}|~, no tab, no newline, and no space characters.

Answer 24

39. Python 2

Added 0. Removed @^. Doesn't use !^&'()/1?@AEIMNPSTWZdmntwz{}|~[] `, tab or newline.

C=u"f=la\u006Db\u0064a\u0020X:3-2if\u0020X<2else\u0020f\u0028X-3+2\u0029+f\u0028X-2\u0029";exec""+C#$%*,.57>BFGHJKLOQRUVY_ghjkopqrvy

Argument to exec without escape sequences:

f=lambda X:3-2if X<2else f(X-3+2)+f(X-2)

Try it online!

Answer 25

38. Matl

Added q. Removed 0 <newline>. Doesn't use !&'()/1?AEIKLM0NPSTW{Z`dmntwxz}|~[], tab, newline, or space.

5X^Hq+G^Hq5X^-G^-HG^5X^*Hqqq^*Yo%"#$,.2346789:;<=>@BCDFJORUV_abcefghijklprsuvy

Try it online

Answer 26

7, Python 2

Re-included _. Removed characters: tab and AEIU`, and (just to get a little nasty) 0 and 1. Otherwise, just a copy of Wheat Wizard's answer (hence the community wiki).

# !"$%&'*./456789;<>?@BCDFGHJKLMNOPQRSTVWXY[\]^chjklmpqsvwxyz{|}

def f(x):
 a=2-2
 b=3-2
 for _ in range(x):
  a,b = a+b,a
 return a

Try it online!

Answer 27

13. Standard ML (mosml)

Added x. Removed :r. Doesn't contain :;{}0`1AEIPQr or tab character.

(* !"#$%&\',./23456789<>?@BCDFGHJKLMNORSTUVWXYZ[\]^_abcdgjkmopqvwxyz|~ *)
fun f s = if s = 2-2 then 2-2 else if s = 3-2 then 3-2 else f (s-4+2) + f (s-3+2)

After we've pretty much excluded C-style languages, let's go after Python. This answer is pretty much identical to answer 11.

Answer 28

14. Octave

Added r and removed newline and space. Solution contains no {}:;`01AEIPQ, no tab, no newline, and no space characters.

f=@(n)round(((2/2+sqrt(5))/2)^n/sqrt(5))%!"#$&'*-,.346789<>?BCDFGHJKLMNORSTUVWXYZ[\]_abceghijklmpvwyz|~

Based on a closed form formula (7).

Answer 29

16. Octave

Added / and removed * and space. Solution contains no {}:;`*%01AEIPQ, no tab, no newline, and no space characters.

f=@(n)round(((2/2+sqrt(5))/2)^n/sqrt(5))#!"$&'-,.346789<>?BCDFGHJKLMNORSTUVWXYZ[\]_abceghijklmpvwyz|~

Identical to answer 14, just a straight up attack on SML and Python :P

Answer 30

15. Standard ML (mosml)

Added space and removed %/. Doesn't contain {}:;`01AEIPQ, tab, or newline.

fun f s = if s = 2-2 then 2-2 else if s = 3-2 then 3-2 else f (s-4+2) + f (s-3+2) (* !"#$&\',.23456789<>?@BCDFGHJKLMNORSTUVWXYZ[\]^_abcdgjkmopqrvwxyz|~ *)