What follows is based on the Pari/gp code by ChatGPT-4 at the web page entitled “Pari/gp code to compute unusual sequence from a Turing machine” here:
https://pastebin.com/cJSaZy5J
The sequence in question is from a simulation of a Turing machine, and by simulating the TM, I computed several thousand terms
of this presumptive sequence, which can be found in a blog post here:
https://atomic-temporary-23414054.wpcomstaging.com/2018/03/13/chaos-tm-of-marxen-and-buntrock/ and
here
https://atomic-temporary-23414054.wpcomstaging.com/2017/09/06/content-of-tape-of-tm-4-chaos-machine/
The rules for this sequence are complex. This is a first draft about these rules, which I aim to put in recursive form.
If n=1, then f(n)=3. If n=2, f(n)=1. From now on we assume n>2. Let p2 be the greatest power of 2 less than n.
Suppose n is a power of 2, say n=2^k. Then f(n) = f(p2)+K,
Calculate a = A070885(k); if a is odd, then K = p2 and f(n) = f(p2) + p2. Otherwise, a is even, and K=0, so that f(n) = f(p2).
Link to OEIS: https://oeis.org/A070885
Next, suppose n is not a power of 2. If n=6, then f(n)=1. Suppose now that n>1, n is not a power of 2, and n is not 6.
This is the case that arises the most often.
If n = 2p2-1, then f(n) = 2p2+1. We now assume that n is not 2p2-1.
The result depends on whether or not 2p2-n-1 is a term in the sequence that begins 2, 4, 8, 12, 16, 20, 28, 32, 36, 44, 52, 64, 68, 76, 84, 96, 108, 128, etc. ( I’ve called this the Minecraft sequence: https://twitter.com/doubledeckerpot/status/1665183611723698180 )
If it’s not a term in that sequence, then f(n) = f(n-p2); if it is a term in the sequence, then f(n) = f(n-p2)+ p2.
I asked ChatGPT4 to implement these rules in Python. After numerous revisions, we got the code to work. The output agrees with that from trusted programs. It appears that the rules above may be correct. The Python source code can be found at https://pastebin.com/eHm7p3zR . It’s not the fastest code but, hopefully, it’s reasonnably clear.
For k>=1, the k least significant bits of f(2^k) seem to be given by reading off the bits of https://oeis.org/A205083 (in reverse order). For example, with k=3, the 3 least significant bits of f(8) are given by 1, 1, 0 (in reverse order), so that f(8) = 011 (base 2) = 3. Indeed, f(8)=3. This has been checked against the Turing machine tape for k<= 22, i.e. with 2^k <= 4,194,304. This gives the following table:
f(2)=1
f(4)=3
f(8)=3
f(16)=11
f(32)=27
f(64)=27
f(128)=27
f(256)=27
f(512)=283
f(1024)=795
f(2048)=795
f(4096)=2843
f(8192)=2843
f(16384)=2843
f(32768)=19227
f(65536)=51995
f(131072)=51995
f(262144)=183067
f(524288)=183067
f(1048576)=707355
f(2097152)=707355
f(4194304)=707355
f(8388608)=4901659
f(16777216)=13290267
#include <stdio.h>
int main(void)
{
int k;
int p2;
int z;
int bits[30] = {1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0};
k=1;
p2=1;
z=0;
while(k<25)
{
z = z+ bits[k-1]*p2;
k=k+1;
p2 = 2*p2;
printf("f(%d)=%d\n", p2, z);
}
return 0;
}
