Compute this fractal matrix

The unique-disjointness matrix ( UDISJ(n) ) is a matrix on all pairs of subsets of {1...,n} with entries $$U_{(A,B)}=\begin{cases} 0, ~ if ~ |A\cap B|=1\\ 1, ~ otherwise \end{cases}$$

Or a bit less mathematical, it is the 2n times 2n matrix with a 0 in all entries where both indices have exactly one common 1 bit in their binary representation and a 1 in all other entries.

Example:

0   1  10  11  100 101 110 111
_______________________________
0   | 1   1   1   1   1   1   1   1
1   | 1   0   1   0   1   0   1   0
10  | 1   1   0   0   1   1   0   0
11  | 1   0   0   1   1   0   0   1
100 | 1   1   1   1   0   0   0   0
101 | 1   0   1   0   0   1   0   1
110 | 1   1   0   0   0   0   1   1
111 | 1   0   0   1   0   1   1   1

Write a program or function that takes an integer n as input and outputs the corresponding $$\2^n \times 2^n\$$ matrix.

Rules:

• The values in the matrix can either be 0 / 1 (as numbers) or truthy/falsey
• You are not allowed to permute the rows/columns of the matrix
• This is the shortest solution (per language) wins
• Your solution only needs to handle n between 2 and 10 (inclusive)

First 4 elements:

n=1:
1 1
1

n=2:

1 1 1 1
1   1
1 1
1     1

n=3:

1 1 1 1 1 1 1 1
1   1   1   1
1 1     1 1
1     1 1     1
1 1 1 1
1   1     1   1
1 1         1 1
1     1   1 1 1

n=4:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1   1   1   1   1   1   1   1
1 1     1 1     1 1     1 1
1     1 1     1 1     1 1     1
1 1 1 1         1 1 1 1
1   1     1   1 1   1     1   1
1 1         1 1 1 1         1 1
1     1   1 1 1 1     1   1 1 1
1 1 1 1 1 1 1 1
1   1   1   1     1   1   1   1
1 1     1 1         1 1     1 1
1     1 1     1   1 1 1   1 1 1
1 1 1 1                 1 1 1 1
1   1     1   1   1   1 1 1 1 1
1 1         1 1     1 1 1 1 1 1
1     1   1 1 1   1 1 1 1 1 1 1

Python, 72 bytes

lambda m:(q:=range(2**m))and(((i&j).bit_count()!=1for i in q)for j in q)

Attempt This Online!

05AB1E, 10 bytes

o<ÝDδ&b1ö≠

Outputs as a matrix with 1s and 0s.

Port of @mousetail's Python answer, so make sure to upvote that answer as well!

Explanation:

o           # Push 2 to the power the (implicit) input-list
<Ý         # Pop and push a list in the range [0,2**input)
Dδ&      # Create a bitwise-AND table of it:
D        #  Duplicate the list
δ       #  Pop both lists and apply double-vectorized:
&      #   Bitwise-AND
b     # Then convert each inner value to a binary-string
1ö   # Vectorized-sum its digits by converting from base-1 to a base-10 integer
≠  # Check for each that it's NOT equal to 1 (0 if 1; 1 otherwise)
# (after which the matrix is output implicitly)
• Not again... Porting now lol Commented Jul 26, 2023 at 14:38
• @TheThonnu Haha, déjà vu. ;) Commented Jul 26, 2023 at 14:39

Jelly, 8 bytes

2ṗ«'§’n

Try it online!

(input: n)
2ṗ          nth Cartesian power of [1, 2]: for example,
[[1,1,1,1], [1,1,1,2], [1,1,2,1], ..., [2,2,2,2]] if n=4
«'       self-table by vectorized minimum
§      sum each vector
’     subtract 1
n    not equal to… (implicit argument: n)

Instead of 0b0011 & 0b0110 = 0b0010 we do 1,1,2,2 « 1,2,2,1 = 1,1,2,1.

Instead of checking popcount ≠ 1, we check sum ≠ n+1. §’n is shorter than ’§n1.

Vyxal, 66 bitsv2, 8.25 bytes

Eʁ:v⋏bvṠċ

Try it Online!

-4.75 bytes thanks to TheThonnu

The footer formats the resulting matrix into a nice grid like the test cases. Remove it for just a list of lists. Outputs inverted numbers (0s for 1s and 1s for 0s).

I somehow managed to generate like 3 other fractals while solving this, including an upside down triangle thing with the bottom off-center.

Explained

EDẊ‹sƛƒ⋏bT₃;ẇ­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁣⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁤⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁢⁡⁪‏‏​⁡⁠⁡‌⁢⁡​‎‎⁪⁡⁪⁠⁪⁢⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁤⁪‏⁠⁪⁪⁠‎⁪⁡⁪⁠⁪⁤⁣⁪‏‏​⁡⁠⁡‌⁢⁢​‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏⁠⁪⁪⁠⁪⁪‏​⁡⁠⁡‌⁢⁣​‎‎⁪⁡⁪⁠⁪⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏⁠⁪⁪‏​⁡⁠⁡‌⁢⁤​‎‎⁪⁡⁪⁠⁪⁤⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁢⁪‏⁠⁪⁪‏​⁡⁠⁡‌­
ED             # ‎⁡Push three copies of n ** 2
Ẋ            # ‎⁢Cartesian product of the range [1, n ** 2] and [1, n ** 2]
‹           # ‎⁣with all sublists decremented
s          # ‎⁤and sorted
ƛ     ;   # ‎⁢⁡To each pair
ƒ⋏       # ‎⁢⁢  reduce by bitwise and
bT₃    # ‎⁢⁣  is the length of truthy indices 1?
ẇ  # ‎⁢⁤wrap into 2 ** n chunks
💎

Created with the help of Luminespire.

• 9 bytes (or 8.25 with Vyncode) Commented Jul 26, 2023 at 14:59

Thunno 2, 10 bytes

2RẉDȷỌ€ʂ⁻Q

Try it online!

Outputs a nested list. The footer formats it into the grid. Port of Lynn's Jelly answer.

Explanation

2RẉDȷỌ€ʂ⁻Q  # Implicit input
2Rẉ         # [1,2] to the cartesian power of the input
DȷỌ      # Outer product over minimum with itself
€ʂ    # Sum each inner list
⁻Q  # Decrement, not equal to the input?
# Implicit output

Old:

OLDȷÆ&ıḃ1ȷcḅ  # Implicit input
OL            # Push [0..2**n)
DȷÆ&        # Outer product over bitwise AND
ıḃ1ȷc   # Popcount of each
ḅ  # Equals one?
# Implicit output

Python, 66 bytes

lambda m:(q:=range(2**m))and[[(n:=i&j)>n^n-1for i in q]for j in q]

Attempt This Online!

mousetail's answer, but with bit operations instead of bit_count. We want to check that i&j (which we call n) doesn't have exactly one set bit, which means that it's a not power of two. We do this by checking that n>n^n-1, which is processed as n>n^(n-1). Let's check that this works in every case:

• If n is a power of two, then n-1 has disjoint bits set to n and so their XOR is greater than n.
• If n is any other positive value, then n and n-1 share the same leading bit, and the XOR cancels this bit making the result smaller than n.
• For n==0, the result is 0, the same as n.

Annoyingly Python doesn't let us do the walrus assignment q:=range(2**m) in the iterable of a list comprehension, so the code has it assigned beforehand. loopy walt points out a better way to handle the two levels of iteration is using the classic divmod two-loop trick together with the classic zip/iter chunker.

61 bytes

lambda m:zip(*2**m*[((n:=j&j>>m)>n^n-1for j in range(4**m))])

Attempt This Online!

• -3 just using the good ol' grouper. Commented Jul 29, 2023 at 19:09

Arturo, 57 54 50 bytes

$->n[map^2n'x->map^2n=>[0<>^and dec<=<=and&-1x-1]] Try it!$->n[                     ; a function taking an argument n
map^2n'x->            ; map over [1..2^n]; assign current elt to x
map^2n=>[         ; map over [1..2^n]; assign current elt to &
0<>           ; is zero not equal to
and&-1x-1     ; bitwise and of current elts minus one
<=<=          ; duplicated twice
dec           ; minus one
and           ; bitwise and
^             ; NOS to the TOS power
]                 ; end map
]                         ; end function

R, 55 53 bytes

function(n)(y=outer(x<-1:2^n-1,x,bitwAnd))^0-y%in%2^x

Try it online!

Rather than counting the number of on bits (which is very lengthy in R), tests the equivalent characterization of "equal to a power of 2"; then has to do some reshaping of the vector output of %in% to get back to the right shape matrix.

• I cannot find anything on meta - is it generally allowed to output a matrix as a flat vector? Commented Jul 26, 2023 at 18:14
• @pajonk hmm probably not. I didn't notice b/c of the footer, so I'll have to update it. Commented Jul 26, 2023 at 18:33

Nim, 119 bytes

import bitops
proc f(n:int)=
let r=0..<1 shl n;for i in r:
var s="";for j in r:s&= $int 1!=popcount i and j echo s Attempt This Online! Jelly, 10 bytes 2*Ḷ&þB§n1 Try it online! How it works 2*Ḷ&þB§n1 - Main link. Takes n on the left 2* - 2 ** n Ḷ - [0, 1, ..., 2**n) þ - To every pair (a, b) in this range: & - Bitwise and B - Convert all to binary § - Sums n1 - Does not equal 1? Pyth, 15 14 bytes mmn1s&VdkQ=^U2 Try it online! Explanation mmn1s&VdkQ=^U2Q # implicitly add Q # implicitly assign Q = eval(input()) =^U2Q # Q = repeated cartesian product of [0,1] Q times m Q # map lambda d over range(Q) m Q # map lambda k over range(Q) &Vdk # d & k, vectorized s # sum bits n1 # != 1 BQN (CBQN), 45 bytes 22 ‘bytes’ {1≠+´¨∧⌜˜⥊∾⌜⍟(𝕩-1)˜↕2} I think the following is slightly more elegant, and it's the same number of characters but, alas, more bytes. {1≠+´∘∧⌜˜⥊(↕2)∾⌜⍟𝕩⋈⟨⟩} We operate only on bit-strings, rather than integers. ⥊⌜⍟(𝕩-1)˜↕2 gives us the list of binary strings of length 𝕩, which is then anded into a table, and summed: +´∘∧⌜˜. We then take only the 1≠ entries. Attempt This Online! • Though I don't know the specifics of why, every BQN answer I've seen here counts 1 glyph as 1 byte. I think you can call these 22 bytes. Commented Jul 26, 2023 at 22:37 • @chunes Thanks, that makes quite a difference! Commented Jul 27, 2023 at 7:03 Ruby, 72 56 54 bytes ->n{(w=0...1<<n).map{|i|w.map{|j|a=i&j;(a&a-1)**a>0}}} Try it online! This employs one of my favourite bit-twiddling hacks. a&a-1 gives 0 if a has only one bit set. Unfortunately it also gives 0 if a==0 so we use the fact that any number (including 0) raised to the power 0 is 1 to catch this special case: (a&a-1)**a. So now we have distinction between nonzero and zero numbers. The rules require two distinct values, so we use >0 to convert to true/false and we are done. The footer in the linked TIO formats the output 2d array line by line, and converts the true/false to 1/0. • 52 bytes with Ruby 2.7 Numbered Parameters (TIO is stuck on 2.5.5) - ->n{(w=0...1<<n).map{|i|w.map{a=i&_1;(a&a-1)**a>0}}} Commented Jul 27, 2023 at 20:10 • @ValueInk oh wow thanks, that's new! You really have to check your versions. I still miss when you could write .5 instead of 0.5 Commented Jul 27, 2023 at 21:20 • CG One Handed pointed it out to me earlier this week and it feels like a whole new world. Also, you can still save a byte on 2.5 by using j&=i;(j&j-1)**j>0 for 53 bytes Try it online! Commented Jul 27, 2023 at 22:40 Factor + math.matrices math.unicode, 57 bytes [ 2^ dup [ bitand bit-count 1 ≠ ] <matrix-by-indices> ] Attempt This Online! 2^ ! two to the input power dup ! duplicate [ ... ] <matrix-by-indices> ! create an MxN matrix with indices on top of stack bitand ! bitwise and bit-count ! number of on bits 1 ≠ ! not equal to one 05AB1E, 15 bytes oDL<ãε&b1¢Θ}sô Try it online! Outputs a nested list. The footer formats it into the grid. Port of lyxal's Vyxal answer. -1 thanks to @KevinCruijssen Explanation oDL<ãε&b1¢Θ}sô # Implicit input oD # Push 2 ** n and duplicate L<ã # Cartesian product of [0..2**n) with itself ε } # Map over this list: & # Bitwise AND of the pair b1¢Θ # Is the popcount equal to 1? sô # Split into 2 ** n chunks # Implicit output • can be ã (and golfing it some more would result in my 10 bytes answer, which I was already writing before I saw this answer tbh). Commented Jul 26, 2023 at 14:38 Nibbles, 11 bytes .;,^2$.@!=1+@&@$Attempt This Online! Returns a matrix with truthy values (positive numbers) for 1 and falsy values (0) for 0. Raku, 52 bytes {(^$_ X+&^$_).rotor($_)».&{!$_||$_!=1+<.msb}}o 1+<*

Try it online!

The version of Raku on TIO fails to parse the !$_||$_!=1+<.msb bit, presumably due to a bug, so I've expressed it there as !($_&&$_==1+<.msb), which is equivalent by De Morgan's law, but two bytes longer.

This is an anonymous function consisting of two separate anonymous functions composed together with o. The right-hand function is 1 +< *, which shifts the number 1 leftwards a number of bits given by its argument; that is, two to the power of the argument. That number is passed to the left-hand function, where the variable $_ gets its value. • ^$_ is a range of numbers from 0 up to one less than $_. For example, when the number passed to the first function is 3, this is the range 0..7. • X+& gives the cross product of one copy of that range with another using the bitwise-and operator +&. • .rotor($_) takes that flat crossed list and makes it into a square matrix.
• ».&{ ... } recursively applies the code between the braces to each element of that matrix.
• !$_ ||$_ != 1 +< .msb tests whether each number is zero (!\$_) or consists of only a single binary digit by comparing the number to 1 bit-shifted left a number of places equal to the number's most significant bit (1 +< .msb).

JavaScript (ES6), 74 bytes

n=>[...Array(1<<n)].map((_,y,a)=>a.map((_,x)=>(g=k=>k?k%2^g(k/2):1)(x&y)))

Try it online!

Charcoal, 18 bytes

≔Ｘ²ＮθＥθ⭆θ¬⁼¹Σ↨＆ιλ²

Try it online! Link is to verbose version of code. Explanation:

²                 Literal integer 2
Ｘ                  Raised to power
Ｎ                Input as a number
≔   θ               Save in variable
θ             Saved variable
Ｅ              Map over implicit range
θ           Saved variable
⭆            Map over implicit range and join
ι    Outer value
＆     Bitwise And
λ   Inner value
↨   ²  Convert to base 2
Σ       Take the sum
¬⁼         Does not equal
¹        Literal integer 1
Implicitly print

PARI/GP, 51 bytes

n->matrix(2^n,,i,j,sumdigits(bitand(i-1,j-1),2)!=1)

Attempt This Online!

Wolfram Language(Mathematica), 68 bytes

Golfed version. Try it online!

f@n_:=Array[Boole[1!=Tr@IntegerDigits[BitAnd[#-1,#2-1],2]]&,2^{n,n}]

Ungolfed version. Try it onlinne!

f@n_:=Table[If[Total[IntegerDigits[BitAnd[i-1,j-1],2]]!=1,1,0],{i,1,2^n},{j,1,2^n}]

JavaScript (Node.js), 65 bytes

n=>[...Array(1<<n)].map((_,y,a)=>a.map((_,x)=>(x&=y)&&+!(x&x-1)))

Try it online!

na