Skip to content

Instantly share code, notes, and snippets.

@anthonykozar
Created September 5, 2022 19:44
Show Gist options
  • Save anthonykozar/1205ac9577e576c690d7f5f719d55c9e to your computer and use it in GitHub Desktop.
Save anthonykozar/1205ac9577e576c690d7f5f719d55c9e to your computer and use it in GitHub Desktop.
Example Adar programs that generate OEIS sequences
# Adar implementation from
# https://esolangs.org/wiki/Adar
adar = lambda l: (lambda n: list(map(lambda x: (x[0] + n, x[1]), l)))(sum(map(lambda x: (x[0] >= 0) * x[1], l)))
# Basic code that I wrote to run & trace Adar programs
# prints only the value of the first register at each step
def run(prog, steps=10, outputInitial = False, adar=adar):
output = []
if outputInitial:
output.append(prog[0][0])
print prog[0][0],
for n in range(steps):
prog = adar(prog)
output.append(prog[0][0])
print prog[0][0],
print
return output
# prints the state of prog at each step
def trace(prog, steps=10, adar=adar):
print prog
for n in range(steps):
prog = adar(prog)
print prog
print
# Creates an Adar program whose first register takes on the values in seq.
# If initialState is not given, then the first value in seq is used.
# DOES NOT WORK FOR ALL SEQUENCES!
def SequenceToAdarProgram(seq, initialState = None):
prog = []
idx = 0
if initialState == None:
initialState = seq[0]
idx = 1
# make the first register
prog.append((initialState, seq[0] - initialState))
lastval = seq[0]
# make additional registers
for val in seq[idx:]:
lastdiff = val - lastval
initialdiff = lastval - initialState
# sum the offsets of all registers that will trigger during this step
totaloffset = 0
for reg in prog:
if reg[0] + initialdiff >= 0:
totaloffset += reg[1]
# new register should trigger on lastval and add an offset to reach val
newoffset = val - (lastval + totaloffset)
prog.append((-initialdiff, newoffset))
lastval = val
# add a final register to halt the program
prog.append((initialState-lastval, -(lastval+1)))
return prog
# Example Adar programs
from Adar import *
ex = [(0,2),(-2,5),(-3,-2),(-6,-7),(-8,1)]
# powers of 2
pow2max = 1024
pow2 = [(-i,1) for i in range(pow2max+1)]
pow2[0] = (1,1)
pow2[pow2max] = (-pow2max,-2*(pow2max+1))
# powers of 3
pow3max = 59049
pow3 = [(-i,2) for i in range(pow3max+1)]
pow3[0] = (1,2)
pow3[pow3max] = (-pow3max,-3*(pow3max+1))
def powersOfN(n, maxexp=10):
maxval = n**maxexp
powers = [(-i,n-1) for i in range(maxval+1)]
powers[0] = (1,n-1)
powers[maxval] = (-maxval,-n*(maxval+1))
return powers
# divide by 3 on each step
# note that extra registers will throw off the results
div3 = [(99,0)]
div3 += [(3*n+1,-1) for n in range(33)]
div3 += [(3*n+2,-1) for n in range(33)]
div3a = [(214,0)]
div3a += [(3*n+1,-1) for n in range(72)]
div3a += [(3*n+2,-1) for n in range(71)]
# n! for n=1 to 7
fact = [(0,1), (-1,-1), (-1,1), (-2,3), (-6,14), (-24,78), (-120,504), (-720,3720)]
# This calculates the first 7 numbers in sequence A006893
# https://oeis.org/A006893
# a[0] = 1, a[n+1] = a[n] + tri(a[n]) where tri(i) is the ith triangular number
trisum = [(0,1)] + [(-n,n) for n in range(2,26800)]
# This calculates the first 11 numbers in sequence A006999 (increase 101 for more)
# https://oeis.org/A006999
alt = [(-n,1) for n in range(0,101,2)]
# This calculates the first 22 numbers in sequence A155167,
# which is defined as "(L)-sieve transform of {3,7,11,15,...,4n-1,...}"
# and appears to be equal to a(n)=Floor[(4*a[[n-1]]+3)/3].
# https://oeis.org/A155167
every3rd = [(-n,1) for n in range(0,1000,3)]
# This calculates the first 38 numbers in sequence A279075,
# which is defined as "Maximum starting value of X such that repeated replacement
# of X with X-ceiling(X/5) requires n steps to reach 0." and has the formula
# a(n) = floor(a(n-1)*5/4) + 1. Conjectured to be the (L)-sieve transform of
# {4,9,14,19,...,5n-1,...}".
# https://oeis.org/A279075
every4th = [(-n,1) for n in range(0,10400,4)]
# Similarly,
allones = [(-n,1) for n in range(0,10000,1)] # https://oeis.org/A000225 = 2^n - 1
every5th = [(-n,1) for n in range(0,10000,5)] # https://oeis.org/A279076
every6th = [(-n,1) for n in range(0,10000,6)] # https://oeis.org/A279077
every7th = [(-n,1) for n in range(0,10000,7)] # https://oeis.org/A279078
every8th = [(-n,1) for n in range(0,10000,8)] # https://oeis.org/A279079
every9th = [(-n,1) for n in range(0,10000,9)] # https://oeis.org/A279080
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment