# 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) – Justin Jun 10 '14 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. – aditsu quit because SE is EVIL Jun 10 '14 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? – Jonathan Pullano Jun 10 '14 at 21:45
• Can the program read its own source code, or are you looking for a true quasi-quine? – histocrat Jun 10 '14 at 21:47
• @JonathanPullano no restrictions, they just need to be valid programs – aditsu quit because SE is EVIL Jun 10 '14 at 21:53

# CJam, 26 23

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! – Dennis Jun 18 '14 at 22:26
• I think we have a new winner :) – aditsu quit because SE is EVIL Jun 22 '14 at 19:04

# 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... – aditsu quit because SE is EVIL Jun 11 '14 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 – Justin Jun 11 '14 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. – aditsu quit because SE is EVIL Jun 11 '14 at 4:48
• @aditsu: Didn't notice you edited your comment until right now. It should be 37 indeed, thanks. – Dennis Jun 11 '14 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. – seequ Jun 11 '14 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' – Justin Jun 11 '14 at 8:01
• @Quincunx I shall! Thanks :D – cjfaure Jun 11 '14 at 15:53
• Your 90-char program doesn't work with python 3, and has a 145-char output (not a Fibonacci number) – aditsu quit because SE is EVIL Jun 18 '14 at 8:18
• @aditsu Fixed. :3 – cjfaure Jun 18 '14 at 15:43

# 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 – aditsu quit because SE is EVIL Jun 18 '14 at 8:15
• 1000 what? Iterations? – Jacob Jun 18 '14 at 9:54
• No, program length – aditsu quit because SE is EVIL Jun 18 '14 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. – Jacob Jun 18 '14 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. – aditsu quit because SE is EVIL Jun 18 '14 at 12:45

## 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. – aditsu quit because SE is EVIL Jun 18 '14 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. – Szabolcs Jun 18 '14 at 16:54
• Oh, I see. Just leave it then, no need to delete. – aditsu quit because SE is EVIL Jun 18 '14 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!