Visualize Fourier transform of the Thue-Morse sequence arranged along the Hilbert curve

thue_morse_hilbert_fft.py

import numpy as np
from matplotlib import pyplot as plt
import scipy

def ht(n:int)->np.array:
    """Generates Thue-Morse sequence, arranged along the Hilbert curve of order N. Result is (2**n, 2**n) matrix"""
    if n < 0: raise ValueError("Bad order")
    if n == 0:
        return np.array([[1]], dtype=np.int8)
    else:
        h = ht(n-1)
        return np.block( [[np.rot90(h,k=1), np.rot90(h,k=-1)],
                          [-h, -h]])

if __name__=="__main__":
    order = 13
    original = ht(order)
    f = np.log(np.abs(np.fft.fft2(original))+1e-6)
    f = scipy.ndimage.median_filter(f, size=3)
    f = scipy.ndimage.zoom(f, 0.25)
    plt.matshow(-f)
    plt.show()