[seqfan] An interesting sequence of sets related to Takagi, chinese rings, binary expansion

[Thomas Baruchel]

Dear fellows,

while writing down some ideas ina more or less separate algorithmic area having
little to see with integer sequences, I had to define a sequence of sets and this
sequence happened to make various identities related to sequences in the OEIS arise.

If some of these identities have some interest to you, please take them as you like;
I am not going to prove them on my own side because I now focus on something very
different.

I gathered a few of these identities (as mere conjectures); the starting point
actually is closely related to Takagi function (through sequence A268289) and I
also found links between this A268289 and all the following sequences:



A000295 Eulerian numbers (Euler's triangle: column k=2 of A008292, column k=1 of A173018).
A000975 a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1 (also a(n) is the n-th number without consecutive equal binary digits).
A001045 Jacobsthal sequence (or Jacobsthal numbers): a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1.
A002450 a(n) = (4^n - 1)/3.
A006516 a(n) = 2^(n-1)*(2^n - 1), n >= 0.
A020988 a(n) = (2/3)*(4^n-1).
A026644 a(n) = a(n-1) + 2*a(n-2) + 2, for n>=3, where a(0)= 1, a(1)= 2, a(2)= 4.
A031443 Digitally balanced numbers: numbers that in base 2 have the same number of 0's as 1's.
A033114 Base-4 digits are, in order, the first n terms of the periodic sequence with initial period 1,0.
A037861 (Number of 0's)-(number of 1's) in base 2 representation of n.
A048488 6*2^n - 5.
A052997 Expansion of (1+x-x^3)/((1-2*x)*(1-x^2)).
A080674 a(n) = (4/3)*(4^n - 1).
A083329 a(0) = 1; for n > 0, a(n) = 3*2^(n-1) - 1.
A083593 Expansion of 1/((1-2*x)*(1-x^4)).
A097074 Expansion of (1-x+2x^2)/((1-x)(1-x-2x^2)).
A117616 a(0)=0, a(n)=4a(n-1)+2 for n odd, a(n)=4a(n-1) for n even.
A131128 Binomial transform of [1, 1, 5, 1, 5, 1, 5, ...].
A268289 a(0)=0; thereafter a(n) = a(n-1) - A037861(n).
A277955 Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 14", based on the 5-celled von Neumann neighborhood.




I found the most easy way to give these identities was to copy the following script
(that I tried to write in the most expressive way); it is written in Python3 and
you can directly run it in order to see all these sequences appear; later you can
(if you are interested by these identities) read the code (one line for each
sequence) in order to figure out the exact formula. Best regards,





# -*- coding: utf-8 -*-

# I defined a sequence S of sets as

#  S_d = \left\{
#           1 \leqslant m \leqslant d
#           \Big |
#           \left(\left( d - m \right) 
#                   \textrm{mod}  2^{\lfloor\log_2 m\rfloor+1}\right)
#               < 2^{\lfloor\log_2 m\rfloor}
#        \right\}

S = lambda d: [
         m for m in range(1, d+1)
         if
         ((d-m)%(2**(m.bit_length())))
           < 2**(m.bit_length()-1)
     ]

# since we are often interested by the cardinality of the sets only
# the following function is more efficient than len(S(n))
# (an explicit expression involving the takagi function is possible)
Sc = lambda d: sum( ((d-m)%(2**(m.bit_length()))) < 2**(m.bit_length()-1)
                     for m in range(1, d+1) )

print("A sequence S of sets is defined:")
for k in range(1,8): print("  S_%d ="%k, set(S(k)))
print("  etc.")


# bitwise xoring all elements of a list
from functools import reduce
xor = lambda l: reduce(int.__xor__, l)

ispower2 = lambda n: n == 2**(n.bit_length()-1) # test if n is a power of 2
inc = lambda l: (x+1 for x in l)                # increment all numbers
dec = lambda l: (x-1 for x in l)                # decrement all numbers
diff = lambda l: (l[k+1]-l[k] for k in range(len(l)-1)) # first difference
indmax = lambda l: max(enumerate(l), key=lambda e: e[1])[0] # index of max

print("A268289:", [ Sc(n) for n in range(20) ])
#print("A268289:", [ sum(x%2 for x in S(m)) for m in range(2, 40,2) ])
#print("A268289:", [ sum(1-x%2 for x in S(m)) for m in range(2, 40,2) ])

print("A037861:", [ Sc(n) - Sc(n+1) for n in range(20) ])

print("A000975:", [ min(Sc(m) for m in range(2**n, 2**(n+1)))
                          for n in range(11) ])

print("A000975:", [ xor(S(2**n - 2)) for n in range(2, 11) ])

A001045 = [1, 2, 4, 10, 20, 42, 84, 170, 340, 682, 1364,
            2730, 5460, 10922, 21844]
print("A000975:", [ Sc(n) for n in A001045[:12] ])

print("A000295:", [ Sc(2**n-2) for n in range(2, 15) ])
print("A000295:", [ max(Sc(m) for m in range(2**n, 2**(n+1)-1))
                          for n in range(1, 11) ])

print("A052997:", [ xor(S(3*2**n - 2)) for n in range(2, 13) ])

print("A026644:", [ m for m in range(1, 1500) if Sc(m)==m/2])
print("A026644:", [ m for m in range(1, 1500) if 2*Sc(m) in S(m) ])
print("A026644:", [ m for m in range(1, 1500) if xor(dec(S(m)))==1 ])

A000975 = [0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730,
            5461, 10922, 21845, 43690, 87381]
print("A026644:", [ max( m for m in range(2**n, 2**(n+1)) if Sc(m)==A000975[n])
                       for n in range(1, 12) ])

print("A001045:", [ Sc(n) for n in A000975[:12] ])

A026644 = [0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341,
            683, 1365, 2731, 5461, 10923]
print("A277955:", [ Sc(n) for n in A026644[2:12] ])

print("A097074:", [ m for m in range(1, 1500) if Sc(m)==(m+1)/2])

print("100 A033114(n) + 16 + 10 (-1)^n:", [ m for m in range(100, 30000)
                                             if ispower2(Sc(m))])

print("100 A117616(n) + 33 + 20 (-1)^n:", [ m for m in range(100, 30000)
                                             if ispower2(Sc(m)-1)])

print("100 A083593(n) + {7,14,27,54}", [ m for m in range(100, 30000)
                                          if ispower2(Sc(m)-3)])

print("A080674:", [ m for m in range(2,22000,2) if xor(inc(S(m)))==1 ])
print("A083329:", [ m for m in range(3,25000,2) if xor(inc(S(m)))==1 ])

print("A031443:", [ m/2 for m in range(1, 500) if Sc(m)/2 == sum(x%2 for x in S(m)) ])

print("A020988:", [[m for m in range(4**n, 4**(n+1)) if ispower2((m ^ Sc(m))+1)][1]
     for n in range(1,7)])

print("A002450:", [ sum( Sc(m) for m in S(2**n-1) ) for n in range(10) ])
print("A006516:", [ sum(S(2**n-1)) for n in range(1,11) ])

print("A131128:", [ indmax (indmax(diff(S(m))) for m in range(3, 2**n))
          for n in range(2,13) ])
print("A048488:", [ indmax (indmax(diff(S(m))) for m in range(4, 2**n))
          for n in range(3,13) ])