# Fibonacci program lengths

Write a program with length n that outputs another program whose length is the next Fibonacci number after n. The new program must do the same thing - output another program whose length is the next Fibonacci number, etc.
n itself (the original program's length) does not have to be a Fibonacci number, although it would be nice if it is.

Shortest code wins.

No external resources, ASCII only, free compiler/interpreter required.
If your output ends in a newline, it is also counted.

• Does this need to continue on forever? (int or BigInteger) Commented Jun 10, 2014 at 21:39
• @Quincunx it's ok if it stops working at int's limit or compiler/interpreter's limit, whichever comes first. I expect it to get to 10000+ though. Commented Jun 10, 2014 at 21:41
• Are there restrictions on use of whitespace or comments or arbitrarily long variable/function/class names in either the original or subsequently produced programs? Commented Jun 10, 2014 at 21:45
• Can the program read its own source code, or are you looking for a true quasi-quine? Commented Jun 10, 2014 at 21:47
• @JonathanPullano no restrictions, they just need to be valid programs Commented Jun 10, 2014 at 21:53

# Python 2, 160 bytes

s='s=%s;c=s;l=len(s%%c)+4;a,b=1,1\nwhile b<l:a,b=b,a+b\nc+="1"*(b-l-1);print s%%c;a=1'
c=s
l=len(s%c)+4
a,b=1,1
while b<l:a,b=b,a+b
c+="1"*(b-l-1)
print s%c


This is a true quasi-quine; it doesn't read its own source, but it generates it. First output (has trailing newline):

s='s=%s;c=s;l=len(s%%c)+4;a,b=1,1\nwhile b<l:a,b=b,a+b\nc+="1"*(b-l-1);print s%%c;a=111111111111111111111111111111111111111111111111111111111111111111111';c=s;l=len(s%c)+4;a,b=1,1
while b<l:a,b=b,a+b
c+="1"*(b-l-1);print s%c;a=1


Second:

s='s=%s;c=s;l=len(s%%c)+4;a,b=1,1\nwhile b<l:a,b=b,a+b\nc+="1"*(b-l-1);print s%%c;a=1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111';c=s;l=len(s%c)+4;a,b=1,1
while b<l:a,b=b,a+b
c+="1"*(b-l-1);print s%c;a=111111111111111111111111111111111111111111111111111111111111111111111


Edit: Oops. Forgot to change the string when I changed from ;s to 1s, so the second output was outputting extra semicolons (which Python doesn't support). Fixed

• I'm afraid it stops working after about 3 iterations... Commented Jun 11, 2014 at 4:34
• @aditsu What? Python has a limit on the size of an integer?! (or is it that the count isn't a fibonacci / skips / something else?) Oh wait. Duh. I forgot to change the string XD Commented Jun 11, 2014 at 6:30

# CJam, 41 31 bytes

{1$+S@]_1=4+1$,-S*"2$~"}21D2$~


Try it online.

### Output

$cjam <(echo '{1$+S@]_1=4+1$,-S*"2$~"}21D2$~'); echo {1$+S@]_1=4+1$,-S*"2$~"}34 21 2$~$ cjam <(echo '{1$+S@]_1=4+1$,-S*"2$~"}21D2$~') | wc -c
34
$cjam <(cjam <(echo '{1$+S@]_1=4+1$,-S*"2$~"}21D2$~')); echo {1$+S@]_1=4+1$,-S*"2$~"}55 34                      2$~$ cjam <(cjam <(echo '{1$+S@]_1=4+1$,-S*"2$~"}21D2$~')) | wc -c
55
$cjam (cjam <(cjam <(echo '{1$+S@]_1=4+1$,-S*"2$~"}21D2$~'))); echo bash: syntax error near unexpected token cjam'$ cjam <(cjam <(cjam <(echo '{1$+S@]_1=4+1$,-S*"2$~"}21D2$~'))); echo
{1$+S@]_1=4+1$,-S*"2$~"}89 55 2$~
$cjam <(cjam <(cjam <(echo '{1$+S@]_1=4+1$,-S*"2$~"}21D2$~'))) | wc -c 89  ### How it works { " {…} 21 13 "; 1$+   " Duplicate the higher number and add.              {…} 21 34                     ";
S@    " Push a space and rotate the lower number on top.  {…} 34 ' ' 21                 ";
]     " Wrap the stack into an array.                     [ {…} 34 ' ' 21 ]             ";
_1=   " Push the second element of the array.             [ {…} 34 ' ' 21 ] 34          ";
4+    " Add 4 to it.                                      [ {…} 34 ' ' 21 ] 38          ";
1$, " Push the length of the stringified array. [ {…} 34 ' ' 21 ] 38 37 "; -S* " Subtract and push that many spaces. [ {…} 34 ' ' 21 ] ' ' "; "2$~" " Push the string '2$~'. [ {…} 34 ' ' 21 ] ' ' '2$~'   ";
}       "                                                   {…}                           ";

21D     " Push 21 and 13.                                   {…} 21 13                     ";
2$~ " Copy the code block an evaluate. [ {…} 34 ' ' 21 ] ' ' '2$~'   ";

• Nice, confirmed up to 1 million :) I think it's 37 instead of 39 though in the explanation. Commented Jun 11, 2014 at 4:48
• @aditsu: Didn't notice you edited your comment until right now. It should be 37 indeed, thanks. Commented Jun 11, 2014 at 22:34

# Python - 89

g="%(s,b,a+b);print o.ljust(b-1)";s,a,b="s,a,b=%r,%i,%i;o=s%"+g,89,144;exec("o=s"+g)#####


My perfect character count is gone. ;_; Thanks to TheRare for pointing out the newline thing and Quincunx for suggesting I use Python 2, shaving off 2 chars.

EDIT: Now just uses more #s instead of 1s; 12 chars shorter.

EDIT 2: 94 chars! Eliminated some repetition. >:3

EDIT 3: Shorter repr alternative for Python 2.

EDIT 4: Output is a character shorter now.

EDIT 5: The use of %r to shorten it was taken from an answer on another question by @primo.

EDIT 6: Shorter. :D

Here's a Python 3 version:

g="%(s,b,a+b);print(o.ljust(b-1))";s,a,b="s,a,b=%r,%i,%i;o=s%"+g,89,144;exec("o=s"+g)####


This answer is similar to the one by @Quincunx.

• print always adds a newline, unless you specify end='' argument. Commented Jun 11, 2014 at 7:55
• Why not use Python 2?: s,a,b="s,a,b=%s,%i,%i;o=s%%(s,b,a+b)+'#';print o+(b-len(o)-1)*'1'",89,144;o=s%(s,b,a+b)+'#';print o+(b-len(o)-1)*'1' Commented Jun 11, 2014 at 8:01
• @Quincunx I shall! Thanks :D Commented Jun 11, 2014 at 15:53
• Your 90-char program doesn't work with python 3, and has a 145-char output (not a Fibonacci number) Commented Jun 18, 2014 at 8:18
• @aditsu Fixed. :3 Commented Jun 18, 2014 at 15:43

# CJam, 26 23

I just had a try with your language.

7{9\@5mq)2/*')*\"_~"}_~


9 is (22*0.618 + 0.5 - 1)/1.618 + 1.

It computes its own length*1.618 instead of repeatedly adding the two numbers. In the first version, it will fill the output before { like 1))))))))), which counts those characters themselves. Say the result n. The total length is n+22, and the new length before { should be (n+22)*1.618-22, rounded. Decrease it by one to count the number of )'s. Then it will be approximately equal to (n+8)*1.618.

Older version:

-3{1\@5mq)2/*E+')*\"_~"}_~


The number 14 is 24*0.618 + 0.5 - 1.

• Very impressive! Commented Jun 18, 2014 at 22:26
• I think we have a new winner :) Commented Jun 22, 2014 at 19:04

# JavaScript, 94

(function q(w,e){return ('('+q+')('+e+','+(s=w+e)+')'+Array(s).join('/')).substr(0,s)})(55,89)


Based on a well-known JavaScript Quine, this returns almost the same function, only followed by amount of slashes, such that it sums up to 144 which is the next Fibonacci number after N. And so on...

N is not a Fibonacci number, but it was only "nice to have".

• It doesn't seem to work correctly when it passes 1000 Commented Jun 18, 2014 at 8:15
• 1000 what? Iterations? Commented Jun 18, 2014 at 9:54
• No, program length Commented Jun 18, 2014 at 10:04
• Hmm... I was testing it in Chrome's Console, using p = (my answer) and then p = eval(p) a couple of times, and got until 196418... after that processing time was > 1sec so I quit testing :P But I guess it can continue even more. Commented Jun 18, 2014 at 10:11
• You don't understand.. I didn't say it stops working or it's too slow. I said it doesn't work correctly. Don't just do p=eval(p), also check p.length. After it gets to 987, I get length 1598, not a Fibonacci number. Commented Jun 18, 2014 at 12:45

# Python 3.8 (pre-release), 65 bytes

a,b=55,89;exec(s:="print((f'a,b={b,a+b};exec(s:=%r)#'%s*b)[:b])")


Try it online!

# Pari/GP, 63 bytes

(f(a,b)=print1(s=Str("(f="f")("b","a+b");")10^(b-#s-1)))(55,89)


Try it online!

## Mathematica

({0};
With[{n = Ceiling[ InverseFunction[Fibonacci]@LeafCount@#0 ], l = Length[#0[[1, 1]]]},
#0 /. {0..} -> ConstantArray[0, Fibonacci[n+1] - LeafCount[#0] + l]
]) &


This is a very straightforward implementation (i.e. no obfuscation here). It is an anonymous function that returns itself with a bit of padding to achieve the correct length. Mathematica is homoiconic: code and data are both represented as Mathematica expressions, which makes it realtively easy to modify/generate code on the fly. This also means that character counts are not a natural measure of code length. Epxression size ("leaf count") is. This version is based on leaf counts as code length measure.

If we assign this anonymous function to a variable f (so I can show what happens in a readable manner), and keep calling it 1, 2, 3, ... times, each time measuring the length of the return value, this is what we get:

In[]:= f // LeafCount
Out[]= 42

In[]:= f[] // LeafCount
Out[]= 89

In[]:= f[][] // LeafCount
Out[]= 144

In[]:= f[][][] // LeafCount
Out[]= 233


Regarding the free interpreter requirement: Mathematica is free for the Raspberry Pi. Otherwise this code should be straightforward to port to Mathics (open source). The only thing missing from Mathics is InverseFunction, which can be replaced as here (but I'm lazy :).

• Wow, I didn't know Mathematica was free for the Pi, I should check it out. However, the program is supposed to print characters to the standard output, and that's what should be counted. Commented Jun 18, 2014 at 8:22
• @aditsu Actually I did this more for fun than to compete in the challenge, and using LeafCount seemed much more interesting than using character counts (which would imply boring code-manipulation as string-manipulation). :-) I'm not going to change it to use character counts, but I can delete it without any bad feelings if you wish. Commented Jun 18, 2014 at 16:54
• Oh, I see. Just leave it then, no need to delete. Commented Jun 18, 2014 at 17:16

# Python 3.8 (pre-release), 78 bytes

p,c=55,89;exec(s:="print((a:=f'p,c={c},{p+c};exec(s:=%r)'%s)+'#'*(c-len(a)))")


Try it online!

# Python 2, 79 bytes

p,c,s=55,89,"a='p,c,s=%d,%d,%r;exec s'%(c,p+c,s);print a+'#'*(c-len(a))";exec s
`

Try it online!