Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
Does this need to continue on forever? (int or BigInteger) –  Quincunx Jun 10 at 21:39
1  
@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 Jun 10 at 21:41
1  
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 at 21:45
1  
Can the program read its own source code, or are you looking for a true quasi-quine? –  histocrat Jun 10 at 21:47
    
@JonathanPullano no restrictions, they just need to be valid programs –  aditsu Jun 10 at 21:53
show 1 more comment

6 Answers 6

up vote 2 down vote accepted

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.

share|improve this answer
    
Very impressive! –  Dennis Jun 18 at 22:26
    
I think we have a new winner :) –  aditsu Jun 22 at 19:04
add comment

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

share|improve this answer
    
I'm afraid it stops working after about 3 iterations... –  aditsu Jun 11 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 –  Quincunx Jun 11 at 6:30
add comment

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$~'   ";
share|improve this answer
2  
Nice, confirmed up to 1 million :) I think it's 37 instead of 39 though in the explanation. –  aditsu Jun 11 at 4:48
    
@aditsu: Didn't notice you edited your comment until right now. It should be 37 indeed, thanks. –  Dennis Jun 11 at 22:34
add comment

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.

share|improve this answer
    
print always adds a newline, unless you specify end='' argument. –  TheRare Jun 11 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' –  Quincunx Jun 11 at 8:01
    
@TheRare Ah. Thanks :) –  Trimsty Jun 11 at 15:52
    
@Quincunx I shall! Thanks :D –  Trimsty Jun 11 at 15:53
    
Your 90-char program doesn't work with python 3, and has a 145-char output (not a Fibonacci number) –  aditsu Jun 18 at 8:18
show 5 more comments

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".

share|improve this answer
    
It doesn't seem to work correctly when it passes 1000 –  aditsu Jun 18 at 8:15
    
1000 what? Iterations? –  Jacob Jun 18 at 9:54
    
No, program length –  aditsu Jun 18 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 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 Jun 18 at 12:45
show 2 more comments

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 :).

share|improve this answer
    
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 Jun 18 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 at 16:54
    
Oh, I see. Just leave it then, no need to delete. –  aditsu Jun 18 at 17:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.