Write the longest period iterating quine bounded by 500 bytes

Question

Your job is to create the longest period iterating quine, where the length of each program in the sequence is bounded by 500 bytes.

That is, if you repeat the following steps:

1. Start with your initial program
2. Run the current program
3. Go back to step 2

You will eventually get back to your original program. The number of programs in the cycle is your score, which you are trying to maximize.

None of the programs may raise any errors. Each program must be run the same way as well (e.g. no different versions, implementations, compiler options, platforms, etc...) (EDIT: Yes, any external state such as that of a pseudo random number generator was included in the last statement. The external state must be "reset" after each run. If you use true random numbers, worst case is assumed.)

What separates this challenge from The longest period iterating quine (other than 100 v.s. 500) is that every program in the cycle must also be 500 bytes or less. This means that the longest possible cycle is (256^501 - 1)/255 or less. That of course is a big number, but not that big in terms of how much code it takes to calculate. So the challenge is about using as many of the (256^501 - 1)/255 possibilities as you can, not a busy beaver challenge.

The programs are not permitted to access its own source code. However an empty program is permitted if you want (as long as you follow the other rules).

Since checking the programs manually would be hard, you may figure out the score using theoretical methods. You must include an explanation of the score and correctness with your program. If you can not figure out the score, you may instead use a lower bound of the number of programs in the cycle as a defacto score. You are allowed to update this as you find better lower bounds, or if you find the exact actual score.

This is code-challenge, so highest score wins!

EDIT: It is recommended that you write what your score is in scientific notation, so that answers are more easily comparable. It is perfectly fine to have other forms of the score as well, especially if they are connected to your program more clearly. Also, readers are encouraged to edit previous answers to comply with this.

Answer 1

Perl 6, \$126^{398} \approx 8.86 \times 10^{835}\$ iterations

$!=Q~~;<say "\$!=Q~{chrs(my@a=[R,] polymod :126[$!.ords]+1: 126 xx*)x?(@a-399)}~;<$_>~~.EVAL">~~.EVAL

Try it online!

This iterates through all the possible combinations of the first 126 bytes of length 398 and under (excluding strings with leading NUL bytes). If you want to see that it actually returns to the first iteration, you can reduce the length to 1 by changing the limit like so.

Explanation:

Each iteration increments the string, stored in base 126 form, and then converts it back to base 126. It does this until it reaches a string with length 399, and then resets the string back to empty again. If you're having trouble conceptualising the number, imagine it with ten bytes instead. Starting from 0, increment up to 4 digits, 1000 and reset. This is \$10^{4-1}\$ iterations (including 0 or empty string in my program's case).

$!=Q~~;         # Start with an empty string
< ... >~~.EVAL  # Set a string to $_ and EVAL it
  say "\$!=Q~{...}~;<$_>~~.EVAL"   # Print the program with the string replaced by
                       :126[$!.ords]   # The string converted from base 126
                                    +1 # Incremented
          [R,] polymod                : 126 xx*  # Back to base 126
chrs(                                )  # Back to a string
     my@a=                            x?(@a-399)  # Only if it isn't 399 characters

Answer 2

Runic Enchantments, 64654¹⁰⁶; 122³⁸⁷-1 ≈ 2.638 × 10⁸⁰⁷ iterations

"3X4+kSq'ƃZ,r{1?{1[:1Z%1+:a=+:d=+:3X4+=+:6X2+=+:'€(c*?~1-1kq}͍f1+0Bl1=6*?S1-Skql͗2=4*?{͍]}B͍l1=6*?kS1-Sq]}@

Try it online!

_{Alert: The € is incorrectly displayed, it should be `` (0x80).}

Rather than the stack, use a string and the stack operators modified with ͍ to modify a string rather than the stack (see prior revision). As such, each char is limited to 1 byte (0-127 range, minus the problematic characters), but with over 3 times as many of them (due to there being less processing boilerplate due to not having to skip Unicode combining characters, as well as some other byte savings) it achieves a higher number of iterations.

If encoding as a true big endian is allowed (that is, having byte values above 127 without interjecting 0x00 bytes) this can achieve 251³⁸⁷-1 ≈ 4.717 × 10⁹²⁸ iterations. However, TIO's Latin encoding prevents this as noted by Erik the Outgolfer in his Python 2 answer. I would need to check if it works locally before claiming this score.

Should be able to replace f1+0B with '0B (there's an unprinting 0x16 there), but it was fighting me (things didn't want to branch/skip/return correctly), so I left it alone. This would raise the big-endian structure from 387 to 388.

Answer 3

C# (Visual C# Interactive Compiler), flags: /u:System.Numerics.BigInteger and /r:System.Numerics

Score: 10³³²

Thanks to JoKing who increased my score from 10²⁵⁵ * 2 - 1 to now!

var i=Parse("0");var s="var i=Parse({0}{2}{0});var s={0}{1}{0};Write(s,(char)34,s,(++i).ToString().Length<333?i:0);";Write(s,(char)34,s,(++i).ToString().Length<333?i:0);

Try it online!

Explanation

Increments a BigInteger every iteration, until it's length becomes too large, which in that case we instantly revert back to the original quine.

//The BigInteger that will be incremented
var i=Parse("0");
//The string that encodes the quine
var s="var i=Parse({0}{2}{0});var s={0}{1}{0};Write(s,(char)34,s,(++i).ToString().Length<333?i:0);";
//Print out the string, with every {0} replaced with quotes and the {1} replaced with the original string
Write(s,(char)34,s,
//And the {2} is replaced to the BigInteger+1 if the BigInteger wouldn't be too long, else 0
(++i).ToString().Length<333?i:0);

Answer 4

DOS COM, 49 bytes, period 2^3608

00000000  be 31 01 89 f7 b9 f4 02  f9 ac 14 00 aa 39 ce 72  |.1...........9.r|
00000010  f8 31 c9 b4 3c ba 2b 01  cd 21 89 c3 b4 40 b9 f4  |.1..<.+..!...@..|
00000020  01 ba 00 01 cd 21 b4 3e  cd 21 c3 71 2e 63 6f 6d  |.....!.>.!.q.com|
00000030  00                                                |.|

Original assembly to create:

 BITS 16
 ORG 0100h
   mov si, l
   mov di, si
   mov cx, 500 + 0100h
   stc
n: lodsb
   adc al, 0
   stosb
   cmp si, cx
   jb n
   xor cx, cx
   mov ah, 3ch
   mov dx, f
   int 21h
   mov bx, ax
   mov ah, 40h
   mov cx, 500
   mov dx, 0100h
   int 21h
   mov ah, 3eh
   int 21h
   ret
f: db "q.com", 0
l: db 0

This little jewel writes the next phase to q.com rather than standard output because of nulls and other stuff the terminal cannot handle. The root quine technique is equivalent to stringification and the payload room is used as a 3608 bit counter. Due to the way DOS works, the initial state of the counter contains debris from whatever was in memory prior to its first execution.

The original 49 byte input is unreachable, so if you want to score this as 500 bytes go ahead.

Answer 5

Clean, \$251^{226} \approx 2.1 \times 10^{542}\$

• 251³⁹ removed dependency on Text
• 251¹²² golfed incrementing function
• 251¹²⁸ combined prefix and suffix source strings
• 251¹⁸⁸ removed dependency on Gast.GenLibTest

Presented in xxd format due to nonprintables / invalid UTF-8:

00000000: 6d6f 6475 6c65 2071 3b69 6d70 6f72 7420  module q;import 
00000010: 5374 6445 6e76 3b53 7461 7274 3d28 7325  StdEnv;Start=(s%
00000020: 2830 2c34 3129 2c3f 5b27 0101 0101 0101  (0,41),?['......
00000030: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000040: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000050: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000060: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000070: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000080: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000090: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000a0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000b0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000c0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000d0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000e0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000f0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000100: 0101 0101 0101 0101 0101 0101 275d 2c73  ............'],s
00000110: 2528 3432 2c39 3939 292c 712c 732c 7129  %(42,999),q,s,q)
00000120: 3b71 3d69 6e63 2721 273b 3f5b 683a 745d  ;q=inc'!';?[h:t]
00000130: 2363 3d68 2b69 6628 616e 7928 283d 3d29  #c=h+if(any((==)
00000140: 6829 5b27 ff09 0c26 5b27 5d29 2702 2727  h)['...&['])'.''
00000150: 0127 3d5b 633a 6966 2863 3e68 2969 643f  .'=[c:if(c>h)id?
00000160: 745d 3b3f 653d 653b 733d 226d 6f64 756c  t];?e=e;s="modul
00000170: 6520 713b 696d 706f 7274 2053 7464 456e  e q;import StdEn
00000180: 763b 5374 6172 743d 2873 2528 302c 3431  v;Start=(s%(0,41
00000190: 292c 3f5b 2727 5d2c 7325 2834 322c 3939  ),?[''],s%(42,99
000001a0: 3929 2c71 2c73 2c71 293b 713d 696e 6327  9),q,s,q);q=inc'
000001b0: 2127 3b3f 5b68 3a74 5d23 633d 682b 6966  !';?[h:t]#c=h+if
000001c0: 2861 6e79 2828 3d3d 2968 295b 27ff 090c  (any((==)h)['...
000001d0: 265b 275d 2927 0227 2701 273d 5b63 3a69  &['])'.''.'=[c:i
000001e0: 6628 633e 6829 6964 3f74 5d3b 3f65 3d65  f(c>h)id?t];?e=e
000001f0: 3b73 3d22                                ;s="

Try it online!

Increments a 226-byte string through all byte values excluding \0, \n, \r, ' and \.

The reason we avoid these characters is:

• \0 makes the compiler angry
• \n and \r can't appear in charlists
• ' would end the charlist
• \ could cause problems if it comes before an escapable character

Once the string is all \377s it wraps around to all \001s, giving the original program.

Answer 6

Python 2, 500 bytes, \$252^{219}\$

#coding=L1
s=""""""
for i in range(220-len(s.lstrip("ÿ")))[:219]:s=s[:i]+chr(ord(s[i])%255-~(s[i]in"!$&"))+s[i+1:]
S='#coding=L1\ns="""%s"""\nfor i in range(220-len(s.lstrip("\xff")))[:219]:s=s[:i]+chr(ord(s[i])%%%%255-~(s[i]in"!$&"))+s[i+1:]\nS=%%r;print S%%%%s%%%%S';print S%s%S

Note that there is a trailing newline. It might get removed above if the syntax highlighter forces its way in.

Unfortunately, you can't execute this program in TIO, as it's encoded in Latin-1.

Above, s contains 219 0x01 bytes. After the program runs, its source is printed, except for one difference: s has been incremented like a base-252 big-endian number, so its leftmost character has been "incremented" to 0x02. The bytes 0x00, 0x22, 0x25 and 0x5C are avoided, so, if any character of the string becomes one of those after the incrementation, the character itself is incremented again.

• 0x00 (null): A Python source file can't contain null characters.
• 0x22 ("): There's a danger of three 0x22 bytes forming in a row, that is, """, or the last character of the string becoming ", so the string would be closed prematurely.
• 0x25 (%): printf-like string formatting is used before completion of the quine skeleton, so a % not adjacent to another % in s will cause trouble. Unfortunately, it's not possible to reorder the formatting to avoid this caveat.
• 0x5C (\): There's a possibility that the \ is used as an escape mark in the string, instead of verbatim, so it's avoided.

Therefore, 252 out of 256 bytes are usable. If s contains 219 0xFF (ÿ) bytes, it's simply reverted to 219 0x01 bytes, hence completing the cycle.

Given the above, we have \$252^{219}\$ possible strings, hence as many programs overall.

\$252^{219}=8067118401622543607173815381864126969021321378412714150085501148172\\081568355283332551767558738710128769977220628694979838777041634307806013053\\042518663967641130129748108465109552157004184441957823830340121790768004370\\530578658229253323149648902557120331892465175873053680188287802536817909195\\292338112618632542000472094347226540339409672851252596442228662174845397731\\175044304251123874046626291460659909127172435776359148724655575878680270692\\451120531744950544969860952702932354413767504109600742385916705785109741289\\800204288\$

Answer 7

Python 2, 57 bytes, 16⁴⁴⁴ ≈ 4.258 \$\times\$ 10⁵³⁴ iterations

-1 byte and \$\times\$16 iterations thanks to @AndersKaseorg

b=0x0;s="print'b=%#x;s=%r;exec s'%(-~b%4**888,s)";exec s

Increments a hexadecimal counter on each iteration and when it reaches \$16^{444}\$ it resets to \$0\$

Try it online!

Answer 8

Gol><>, 70 bytes, 39039000 iterations

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

Wow, that is a lot lower than I thought it would be... Next step! Making it have more iterations!!!

Try it online!

Answer 9

Python 3.8 (pre-release), 500 bytes, 221²⁹⁰ ≈ 7.477 \$\times\$ 10⁶⁷⁹

#coding=L1
c=r"##################################################################################################################################################################################################################################################################################################|";exec(s:='from itertools import*;print("#coding=L1\\nc=r\\"%s|\\";exec(s:=%r)"%([*filter(c[:-1].__lt__,map("".join,combinations_with_replacement(map(chr,range(35,256)),290))),"#"*290][0],s))')

Try it online!

Try a smaller version online!

Python 3.8 (pre-release), 500 bytes, 93³¹⁴ ≈ 1.269 \$\times\$ 10⁶¹⁸

c=r"##########################################################################################################################################################################################################################################################################################################################|";exec(s:='from itertools import*;print("c=r\\"%s|\\";exec(s:=%r)"%([*filter(c[:-1].__lt__,map("".join,combinations_with_replacement(map(chr,range(35,128)),314))),"#"*314][0],s))')

Ascii version

Try it online!

Try a smaller version online!

Explanation

The value assigned to c iterates through all possible strings of length 290 (314 in the ascii version) formed from the characters in the range \x23 to \xff (\x23 to \x7f in the ascii version)

Since the string assigned to c is prefixed with a r backslashes in the string are not treated as the beginning of escape sequences, this allows the use of backslashes inside the string assigned to c without causing problems.

Since a string like r'\' still cause problems a | is added to the end of the string assigned to c.