Ooohh, I didn't know this name for it, thanks. I somehow came across it as The Sultan's Riddle on the internet:

https://explainextended.com/2016/12/31/happy-new-year-8/

I prefer this less sterile framing of it. It was the most fun that I ever had with a puzzle, so to anyone scrolling around on this page, I would recommend not jumping straight to the solution :)