8
\$\begingroup\$

As we know, a quine is a program that outputs its own source code. However, it's also possible to write a program that outputs another, different program, that outputs the first program again. For example, the Python 2 program

x = '''x = {}
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3'''
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3

will, when run, output the following text:

print """x = '''x = {}
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3'''
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3"""

When run as a Python program, this will output the original code again. This is called an iterating quine. Because you have to run it twice to get the original code back, we say it has period 2. But of course, much higher periods are possible.

Your challenge is to write an iterating quine with as long a period as you can, in 100 bytes or less, in the language of your choice. (Note that my example above doesn't fit this spec, as it's 119 bytes, including the trailing newline.)

Please note the following rules and clarifications:

  • The usual quine rules apply, i.e. your program can't use language features that would let it access its own source code directly.
  • The iterated outputs have to eventually loop back to exactly your original code, and you have to include a demonstration or proof that it will.
  • You must also include an explanation of why the cycle is as long as you say it is. This doesn't have to be at the level of a mathematical proof, but it should be convincing to someone familiar with your language. (This rule is here because I expect some of the answers to involve very, very large numbers.)
  • It's fine to say something like "at least 1,000,000 iterations" rather than giving the exact number, as long as you can prove that it is at least that long. In this case, your score would be 1,000,000. Otherwise, your score is the period of your quine.
  • The 100 byte limit only applies to your initial program - the programs it outputs can be longer, though of course they'll eventually have to get back down to 100 bytes in order to output your original code.
  • You can assume your machine has infinite RAM and infinite runtime, but you can't assume unlimited precision data types (such as integers) if your language doesn't have them. You can assume there is no limit to the length of input your parser can handle.
  • The highest score wins.

Please note: there is an existing challenge called Quit Whining; Start Quining that also involves iterating quines. However, aside from being based on the same concept, these are completely different types of challenge. The other one is straight up code golf, whereas this one is (intentionally!) really a busy beaver problem in disguise. The techniques needed to produce a good answer to this question are likely to be very different from what's needed to answer the other question, and this is very much by design.

\$\endgroup\$
  • 1
    \$\begingroup\$ @LeakyNun I don't know if it was you or a mod that deleted your answer, but perhaps if I explain what was wrong with it you will understand why this isn't a duplicate. This question specifies a 100 byte limit on the source length, so you actually can't go "as high as you want" using that method. That's the whole point of this question. To answer it, what you would have to do is post the longest version that fits into 100 characters, and say what its period is. What you posted would be a good first attempt but is very unlikely to be the winner. \$\endgroup\$ – Nathaniel Aug 27 '16 at 9:55
  • 1
    \$\begingroup\$ @Dave the challenge is precisely about specifying a large number in a small number of bytes, yes. That is the whole principle around which it was designed. The question is, is 3^^^3 the highest number you can specify in 100 bytes in your language, or is there a larger one? That's what this challenge is about. It's the core of it. It's what I wanted to see people do. It's super, super frustrataing to have it closed based on a superficial resemblence to a challenge that has nothing of this structure. \$\endgroup\$ – Nathaniel Aug 27 '16 at 10:19
  • 1
    \$\begingroup\$ @Dave (second comment) but if you're clever, you need not be limited by machine precision at all. I would expect competitive answers to have a period much longer than 2^(2^64). \$\endgroup\$ – Nathaniel Aug 27 '16 at 10:20
  • 3
    \$\begingroup\$ So would you prefer it to be closed as a duplicate of codegolf.stackexchange.com/q/18028/194 ? \$\endgroup\$ – Peter Taylor Aug 27 '16 at 10:56
  • 1
    \$\begingroup\$ @PeterTaylor that's a much closer theme, but it's still a very different challenge - printing a number is quite different from doing something a large number of times. I would of course prefer it not to be closed at all. \$\endgroup\$ – Nathaniel Aug 27 '16 at 11:45
10
\$\begingroup\$

PHP, period 2,100,000,000

Who would've thought that this is possible in PHP?! :-)

This is actually my first ever quine and it's 99 bytes long:

<?$i=1;$i*=21e8>$i;printf($a='<?$i=%d;$i*=21e8>$i;printf($a=%c%s%c,++$i,39,$a,39);',++$i,39,$a,39);

Although PHP supports bigger numbers than 2 * 10^8 by switching from integer to double, the increment no longer works (leads to an infinite loop) and I haven't found another solution which fits into the 100 bytes. Yet.

Proof is fairly simple, since it's just counting up on each iteration until it reaches the reset point at 2.1 billion.

Credits to dave, who posted the approach in pseudo code in the comments and to Bob Twells, from whom I copied the code for a minimal PHP quine.

Test program (sloooooow):

<?php
$o = file_get_contents('quine.php');
for ($i = 0; $i < 22e8; $i++) {
    if ($i%2==0) exec('php q > p'); else exec('php p > q');
    $a = file_get_contents(($i%2==0) ? 'p' : 'q');
    echo "\r" . str_pad($i,6,' ') . ":\t$a";
    if ($a == $o) {
        die;
    }
}

Well, at least I'm the first one to answer.

\$\endgroup\$
  • 1
    \$\begingroup\$ Side-note: This is on the order of ~10^9.322219295. \$\endgroup\$ – LegionMammal978 Sep 2 '16 at 10:42
8
\$\begingroup\$

Mathematica, period E8.5678#3 E2.1923#4 ~E6.2695#3#2

Print[ToString[#0, InputForm], "[", #1 - 1 /. 0 -> "Nest[#!,9,9^9^99!]", "]"] & [Nest[#!,9,9^9^99!]]

Note that the scores are described in Hyper-E notation. The iterations replace the final Nest[#!,9,9^9^99!] with the decimal expansions of Nest[#!,9,9^9^99!] - 1, Nest[#!,9,9^9^99!] - 2, Nest[#!,9,9^9^99!] - 3, ..., 3, 2, 1, and back to Nest[#!,9,9^9^99!].

\$\endgroup\$
  • \$\begingroup\$ wouldn't factorials grow faster? \$\endgroup\$ – Maltysen Sep 2 '16 at 4:22
  • 1
    \$\begingroup\$ I don't know Mathematica, but isn't this a violation of the rules for a quine -- reading it's own source code? ToString[#0, InputForm] \$\endgroup\$ – daniero Sep 2 '16 at 11:45
  • \$\begingroup\$ so, just 9!!!! doesn't work? idk cuz i don't have my mathematica rpi with me right now. \$\endgroup\$ – Maltysen Sep 2 '16 at 14:46
  • \$\begingroup\$ @Maltysen That computes the double factorial of the double factorial of nine, or (9!!)!! ≈ 2.116870635·10¹²⁰² \$\endgroup\$ – LegionMammal978 Sep 2 '16 at 22:10
  • \$\begingroup\$ @daniero I mean, the idea is similar to a standard CJam {"_~"}_~, so I guess that it should be valid... \$\endgroup\$ – LegionMammal978 Sep 2 '16 at 22:12
5
\$\begingroup\$

R, random period with expectation 2^19936-0.5

f=function(){
    options(scipen=50)
    body(f)[[4]]<<-sum(runif(623))
    0
    cat("f=")
    print(f)
}

R's default random number generator has a period of 2^19937-1 and equidistribution in 623 consecutive dimensions. Thus, somewhere (but only once) in its period will be a 623-long vector of zeroes. When we get there (and are aligned with the start of the sequence) the sum of the next 623 random U[0,1] numbers will be zero and we return to our original program.

Note that the program will with very high probability pass through the same non-zero state several times before returning to zero. For instance, the sum 311.5 is the most likely, and there are a great many ways that can happen, but the RNG allows the period for 0 to be longer than the period for 311.5.

\$\endgroup\$
  • \$\begingroup\$ Not sure what score you want to assign this entry :P \$\endgroup\$ – JDL Sep 2 '16 at 12:09
  • 1
    \$\begingroup\$ Per the rules: "It's fine to say something like "at least 1,000,000 iterations" rather than giving the exact number" So in my opinion it's "at least 1 iteration" because if we get reeeally lucky on the first try... ;) \$\endgroup\$ – YetiCGN Sep 2 '16 at 15:19
  • \$\begingroup\$ Unlike many standard loopholes like “I might generate some random input, the answer is there”, this is a really neat proof that the precise answer is bound to occur, and a very good estimate is given. Nice! \$\endgroup\$ – Andreï Kostyrka Sep 4 '16 at 12:08
  • 1
    \$\begingroup\$ Once the program returns to its base state once, then it will have a non-random period of exactly 2^19937-1. \$\endgroup\$ – JDL Sep 5 '16 at 8:35
1
\$\begingroup\$

JavaScript, period 9,007,199,254,700,000

Not going to win, but it was fun working with JavaScript on this challenge:

a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)

Follows the following cycle:

a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254700000-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254699999-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254699998-1||90071992547e5)
// etc...
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),3-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),2-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254700000-1||90071992547e5)
// and so on

Note: You can make it 18 bytes shorter, while only removing only ~0.08% of the score, like so:

a="a=%s;console.log(a,uneval(a),%.0f-1||9e15)";console.log(a,uneval(a),1-1||9e15)
\$\endgroup\$
1
\$\begingroup\$

C, period 2,100,000,000

unsigned long long i;main(a){i=1;i*=21e8>i;printf(a="ungisned long long i;main(a){i=%d;i*=21e8>i;printf(a=%c%s%2$c,++i,34,a);}",++i,34,a);}

Based off the PHP answer (obviously). Will update with explanation when I have time.

\$\endgroup\$
0
\$\begingroup\$

Gol><>, 70 bytes, period 325883196621297064957600206175719056476804879488288708188003274919860959534770101079512433396348062803055739640225395758790852315876868469390603793729639715908136196505908165227136154287969475839017544811926036808089596209081885772040898530121921794489026069641113281250

Other wise known as really big (3.25E270)

":1=l8:*6+=S&Q~:'~'=Q~~'H#'||lPffXfX=?1:1=Q$~$~|:1)lPffXfX(Q?:|r2ssH##

This is actually the an altered version of the answer I put on the 500 byte iterator

":1=l8:*6+=S&Q~:'~'=Q~~'H#'||//if last is equal to 1 and length is 71, delete the delete char, if the last char is '~', delete and push 'H#', which will later return to 'H##', completing the cycle!
lPffXfX=?1:1=Q$~$~|          //if length is equal to 15^15^15, then start delete process(append ascii one)
:1)lPffXfX(Q?:|              //if the last character is not 1 (the delete checker), and length is less than 15^15^15, duplicate the last value and append
r2ssH##                      //push the " to the front and output the whole thing

Hopefully I got the score right, and there are no bugs. There is no real way to actually calculate this value, it is theoretical. But man, that is a huge number!!!

Try it online!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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