Binary triangle A141727

Question

Challenge

Generate the 2D sequence of bits of A141727. (Allowed I/O methods explained at the bottom.)

                  1
                1 0 1
              1 0 0 1 0
            1 0 1 0 1 0 0
          1 0 0 1 1 0 1 1 1
        1 0 1 0 0 0 0 0 1 1 0
      1 0 0 1 0 0 0 0 1 1 1 0 0
    1 0 1 0 1 0 0 0 1 1 0 0 1 1 1
  1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0
1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0

This triangle is generated as follows: starting with a row of single 1, generate the bits row-by-row, from left to right. Each bit is the parity of the sum (in other words, XOR-sum) of the neighboring bits already placed (8-way neighborhood).

[1]  initial condition

   1
[1]? ?   only one neighbor being 1, sum is 1

   1
 1[0]?   two 1-neighbors, sum is 0

   1
 1 0[1]  two neighbors (0 and 1), sum is 1

     1
   1 0 1
[1]? ? ? ?  one neighbor, sum 1

     1
   1 0 1
 1[0]? ? ?  three neighbors, sum 0

     1
   1 0 1
 1 0[0]? ?  four neighbors, sum 0

     1
   1 0 1
 1 0 0[1]?  three neighbors, sum 1

     1
   1 0 1
 1 0 0 1[0] two neighbors, sum 0

...

sequence default I/O methods apply. In this challenge, you can interpret the sequence as a sequence of individual bits or a sequence of rows of bits, so the following are accepted:

• Given n (0- or 1-indexed), output n-th bit or n-th row
• Given n (positive), output first n bits or first n rows
• Given no input, output the infinite sequence of bits or the sequence of rows (refer to sequence rules for exactly which methods count as infinite output)

Standard code-golf rules apply. The shortest code in bytes wins.

Answer 1

Python 2, 52 bytes

Outputs an infinite sequence of rows. As a bonus, it runs extremely slowly.

n=1
while 1:print'%o'%n;x=n;n*=64;exec'n^=x;x/=8;'*x

Try it online!

If the current row expressed in binary is n, the next row will be a(n) ^ n*4, where a(n) is the prefix xor sum of the bits. a(n) is also associated with OEIS A006068.

One annoying little thing about Python is that there is no format string to convert an integer to binary. The next best alternative is octal, which is what the code uses instead.

Python 2, 54 bytes

Adding 2 more bytes gets the program to a reasonable speed.

n=1
while 1:
 print'%o'%n;x=n;n*=64
 while x:n^=x;x/=8

Try it online!

Answer 2

Python 3, 110 bytes

def f(n):
	if n<1:return[1]
	k=[1];p=f(n-1)+[0,0]
	for i in range(n*2):k+=[p[i-1]^p[i]^p[i+1]^k[-1]]
	return k

Try it online!

A pretty basic and very sub-par solution to get things started.

Answer 3

JavaScript (Node.js), 66 bytes

f=r=>b=r?f(r-1).map(_=>a[++i]=a[i-2]^b[i-3]^b[i],a=[i=1,0])&&a:[1]

Try it online!

Input r, output an array for r-th row.

---

JavaScript (Node.js), 48 bytes

f=r=>r?(g=a=>a^a/4^b/2^b*4?g(a+1):a)(b=f(r-1)):1

Try it online!

Or output r-th row as an integer if it is allowed.

---

      a
    b c d
  e f g h i
j k l m n o p


n = m xor g xor h xor i
  = (l xor f xor g xor h) xor g xor h xor i
  = l xor f xor i

Answer 4

Charcoal, 23 22 bytes

ＦＮ«Ｆ⊕⊗ιＩ∨¬ι﹪№ＫＭ1²Ｊ±ⅈ⊕ⅉ

Try it online! Link is to verbose version of code. Outputs the first n rows as a triangle. Explanation:

ＦＮ«

For each row:

Ｆ⊕⊗ι

For each bit in the row...

Ｉ∨¬ι﹪№ＫＭ1²

... output the parity of the number of adjacent 1s, except for the very first bit, which is always a 1.

Ｊ±ⅈ⊕ⅉ

Jump to the start of the next row of bits.

Answer 5

Wolfram Language (Mathematica), 52 51 50 bytes

Nest[i+=#&/@{##,i=0,0}-{0,##,0}&@@#&,{1},#]~Mod~2&

Try it online!

Returns the (0-indexed) \$n\$th row.

Uses
\$\displaystyle A_{n+1}(m)=A_n(m-1)\oplus\bigoplus_{i\le m}A_n(i)\$,
where \$A_n(m)\$ is the \$m\$th element of row \$n\$.

This can be rewritten \$\displaystyle A_{n+1}(m)=A_n(m)\oplus\bigoplus_{i\le m-2}^{}A_n(i)\$.

Answer 6

Python 3, 98, 92, 88, 77, 76 bytes

v=-4**64;W=w=v*v;v+=w;O=1
while[print(hex(O)[2::32])]:O*=w;O^=O//v&W//v;W*=w

Try it online!

Old version

Old version

Old version

Old version

Probably not competitive but I think mildly amusing. Takes advantage of Python arbitary size integers to perform cumulative xor. In fact we simply do a cumulative sum over digits using the divide by 9 (or rather base-1) trick and take the base large enough that carry never becomes an issue.

Runs "forever", only it maxes out at around m=2^23. That's not a principal limitation, just me being cheap on integer constants. n=2^127 (rowindex) which I hope is close enough to eternity. UPDATE simplified the maths using @dingledooper's formula.

Answer 7

Pari/GP, 51 bytes

n->for(i=a=1,n,a=a*x+a/(1-x)%x^(2*i+1));Vecrev(a)%2

Try it online!

0-indexed.

Explanation

See each row as a polynomial, starting with the constant term. a*x prepends a 0 to the list. a/(1-x) takes the cumulative sum of the list. %x^(2*i+1) truncates the list to the first 2*i+1 elements.

Answer 8

Ruby, 67 bytes

f=->r,c{c<0||c>r*2?0:r<1?1:([*c-2..c].sum{|x|f[r-1,x]}+f[r,c-1])%2}

Try it online!

• computes value at r row , c column
• Values outside the triangle give 0

Answer 9

05AB1E, 16 14 13 bytes

λb=Å»^}2β₁4*^

Try it online.

Port of @dingledooper's Python 2 answer, but using binary instead of octal integers, so make sure to upvote him/her as well!
-1 byte thanks to @CommandMaster.

Explanation:

λ           # Start a recursive method,
            # to generate an infinite sequence,
            # starting at a(0)=1 by default
            # Where every next a(n) is calculated as follows:
 b          #  Convert the current implicit a(n-1) to a binary string
  =         #  Output it with trailing newline (without popping)
   Å»       #  Cumulative left-reduce its bits by:
     ^      #   Bitwise-XORing
   }        #  After the cumulative left-reduce,
    2β      #  Convert it from a binary-list to an integer
      ₁     #  Push a(n-1) again
       4*   #  Multiply it by 4
         ^  #  And Bitwise-XOR it to the integer

Answer 10

Ruby, 47 bytes

a=1;loop{puts"%b"%a;(a=2*z=2*a).times{a^=z/=2}}

Try it online!

Answer 11

Raku, 52 bytes

1,{(1,{[+^] $^x,|(.[^3-1+$++]:v)}...*)[^(2+$_)]}...*

Try it online!

This is an expression for a lazy, infinite sequence of rows.

• 1, { ... } ... * is the main sequence expression. 1 is the first row, and the bracketed anonymous function generates the next row from the previous row, passed in $_.
• (1, { ... } ... *)[^(2 + $_)] likewise generates the elements of each row, starting with 1, from the previous element $^x and the previous row $_. The number of elements in each row is two greater than the size of the previous row: 2 + $_.
• The numbers to be xor-ed together are $^x, the previous element of the current row, and .[^3 - 1 + $++]:v, a sliding three-index window across the previous row. The :v adverb causes indexes out of the array's range, both positive and negative, to be skipped.
• +^ is the integer xor operator, and [+^] reduces the list of integers that contribute to the current element using that operator.