12
\$\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.

| improve this 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!].

| improve this answer | |
\$\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.

| improve this answer | |
\$\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
  • \$\begingroup\$ The output of this does not match the actual program (there's a bit of whitespace missing). Also, state won't be preserved between program calls, so the period will not be an exact number, nor will it be consistent \$\endgroup\$ – Jo King Jan 28 at 23:21
2
\$\begingroup\$

Python 2

Period: \$9\uparrow((99\uparrow\uparrow(9\uparrow((99\uparrow\uparrow(9\uparrow((99\uparrow\uparrow(9\uparrow\uparrow5-1))\uparrow9)-1))\uparrow9)-1))\uparrow9)+1\$

Thanks to @Bubbler for increasing period from \$9\uparrow9\uparrow(99\uparrow\uparrow12)+1\$ to now

b=0;s="print'b=%d;s=%r;exec s'%(-~b%eval('9**9'*eval('9**9'*eval('9**9'*9**9**9**9**9))),s)";exec s

Try it online!

In the code the b=0 changes to b=1 then b=2 and so on until it reaches b=decimal expansion of the period then resets back to b=0

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 9**9**9**9**9**9**9**9**9**9**9**9**9**9**9**9**9**9 is much higher than 9**9**99**99**99**99**99**99**99**99**99**99**99**99. That said, you could do something like eval('9**9'*eval('9**9'*eval('9**9'*9**9**9**9**9))) for much MUCH higher numbers. \$\endgroup\$ – Bubbler Jan 29 at 1:30
  • \$\begingroup\$ What does peroid mean? \$\endgroup\$ – S.S. Anne Jan 29 at 12:06
  • \$\begingroup\$ @S.S.Anne it is written in Knuth's up-arrow notation \$\endgroup\$ – Mukundan314 Jan 29 at 16:37
  • 1
    \$\begingroup\$ @Mukundan I think you might mean period but I'm not sure. I understand what tetration is. \$\endgroup\$ – S.S. Anne Jan 29 at 16:38
  • \$\begingroup\$ @S.S.Anne sorry it was a typo, thanks for pointing it out \$\endgroup\$ – Mukundan314 Jan 29 at 16:42
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)
| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 66 bytes, period 2^64

f(s){printf(s="f(s){printf(s=%c%s%1$c,34,s,%lu+1L);}",34,s,0+1L);}

Try it online!

2^64 numbers are available in a unsigned long integer. Therefore, a period of 2^64.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

GolfScript, period \$f_{\epsilon_0+1}(126^{126})\$

0".{(}{;]{{x):x;)[.]){+[]\\{[).{f]}{;]x*}if+}:f~~}{;}if.}do{]}x*~}).?:x*`,}if"":n;:c~c`n`":n;:c~c`n`

Try it online!

0"foo"":n;:c~c`n`":n;:c~c`n`
0"foo"":n;:c~c`n`"            # Push this number and these two strings
                  :n;         # Assign the second string to n and remove it from the stack
                     :c~      # Assign the first string to c and execute it
                        c`n`  # Push both strings with "" around
                              # n is automatically printed at the end of the program

Every time this code is executed it prints itsef but replaces the 0 by what foo does to it.

What foo does:

.{(}{;bar}if
.{ }{    }if    # Make a copy of the number and compare it to 0
  (             # If it is not 0, decrement
     ;bar       # If it is 0, replace it by a big number

Here is a version of this code with period 10, so we can see it working:

0".{(}{;9}if"":n;:c~c`n`":n;:c~c`n`

Try it online!

The other 66 bytes compute \$Hydra(Hydra(Hydra(...)))\$, where there are \$126^{126}\$ hydras.

]{{x):x;)[.]){+[]\{[).{f]}{;]x*}if+}:f~~}{;}if.}do{]}x*~}).?:x*`,
]                                                                   # Start with [""], which is equivalent to [[]]
 {                                                     ~})          # The ~}) becomes }126
                                                          .?:x*     # Assign 126^126 to x and execute the block that many times
  {                                           .}do{]}x*             # While the string is not [], redo everything but with a tree with x pairs of []
   x):x;                                                            # Increment x
        )[.])                                                       # Separate the last element and make a copy of it
             {                          }{ }if                      # If it is an empty array
                                          ;                         # False: delete it
              +[]\{[).{f]}{;]x*}if+}:f~~                            # True: execute this function that finds and cuts a head
              +[]\                                                  # Push an empty array under the top of the stack, this will be the outermost pair's parent
                  {                }:f~                             # Assign this function to f and execute it
                   [).                                              # Start a new array and get the last element of the previous array
                      {  }{    }if                                  # If it is an empty array
                       f]                                           # False: keep searching and after that close the array
                           ;]x*                                     # True: delete it, close the array and make x copies of it
                                  +                                 # Put it back in the parent array
                                       ~                            # Remove the outermost pair, which was the [] we added earlier
                                                               `,   # Parse it to a string and get the number of bytes

This is not exactly \$Hydra(x)\$, this never resets x and therefore \$Hydra(x)\$ is a lower bound.

Here is an example of it that takes a tree as input and outputs \$Hydra(tree)+1\$, this confirms it is working.

~1:x;{x):x;)[.]){+[]\{[).{f]}{;]x*}if+}:f~~}{;}if.}do x

Try it online!

\$Hydra(n)>f_{\omega^{\omega^{...^{\omega^{\omega2+4}}}}}(5)\$ with n-3 copies of \$\omega\$. Because of the n-3 and it starting with 5, this program's lower bound should actually be \$f_{\epsilon_0+1}(126^{126}-k)\$, where k is a small number, but that makes it uglier and I doubt it will have more impact on the answer than not resetting x.

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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