Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finding Waldo in π

kundor.github.io

Post reply on HN
Print view View original

61–70 of 80 posts

Re: Finding Waldo in π

#61

Post by kundor »

captainmuon wrote: post #49

Could there be a number, such that for certain interesting data, you can compress the data more than normally achiveable, by indexing into the number? I feel this should not be possible, but I don't know how to proove it without a circular argument about entropy. On the other hand, if you make a string of common byte sequences, a couple GB long, and distribute it with every PC... then you surely can achive hyper comp…

Yes, to an extent that would work.

1) Take target image

2) Find the index in π (say) where a matchable sequence of bytes occur, like for Waldo. (If your image is big, this could take several years of computation time.)

3) Transmit the palette, width, height, and index: about 800 bytes.

4) Probably the index is too far out for everyone to have a copy of the data already (it would be beyond terabytes). So the recipient then spends several years computing the number out far enough.

5) Profit!

Note: the palette is optional; you could leave it out and only transmit about 32 bytes. Using a palette also means lossiness, because you're reducing to 256 colors and making compromises between pixels. But using one saves you several orders of magnitude of computation time.

Re: Finding Waldo in π

#62

Post by kundor »

BubbleRings wrote: post #26

I've been waiting a dozen years for this post! Did you like Sagan's book "Contact"? I'm a big fan. Check out the work I did to show pi as a series of images, and a cool "easter egg" I might have found buried in pi. And yes, my web site looks like it was built 20 years ago and then allowed to rot ever since, since that is in fact what happened! https://whiteis.com/whiteis/personal/programs/Pi/pi_images.s...

That's a cool egg!

It's been a long time since I read Contact. Are the aliens supposed to have hacked the geometry of the universe to make the pattern show up in π?

Re: Finding Waldo in π

#63

Post by kundor »

esnard wrote: post #43

All the 4 images posted by the author are located precisely at the begiging of a hexadecimal digit. Since a hexadecimal digit is 4-bit long, I guess we should be able to locate 4x more Waldos if we allow solutions to be start in the middle of a hex digit? > The pixel data in this gif are the 23,074,248th through 23,075,235th hexadecimal digits of π! (Equivalently, the 184,593,977th through 184,601,880th bits). The au…

You're right, that's a mistake! It should be the 92,296,989th through 92,300,940th bits.

Yes, I did only search at 4-bit aligned bytes. Doing otherwise would be more complicated, much harder for others to easily verify from the downloadable hex digit data file, and not really more likely to succeed. Looking further out is just as beneficial as looking at more offsets.

Re: Finding Waldo in π

#65

Post by kundor »

phantomherman wrote: post #58
6gvONxR4sf7o wrote: post #35

Earlier quoted context omitted.

At the very least, it doesn’t follow from the fact that it’s infinite and nonrepeating.

I'm struggling to wrap my head around this: why doesn't it follow from that fact?

You can have infinite and nonrepeating sequences which don't contain every possible subsequence. For instance, 1010010001000... (where there is one more zero each time) never repeats itself, but it never even has the digit 2 in it.

Re: Finding Waldo in π

#66

Post by phantomherman »

kundor wrote: post #65
phantomherman wrote: post #58

Earlier quoted context omitted.

I'm struggling to wrap my head around this: why doesn't it follow from that fact?

You can have infinite and nonrepeating sequences which don't contain every possible subsequence. For instance, 1010010001000... (where there is one more zero each time) never repeats itself, but it never even has the digit 2 in it.

Aha, makes sense, thank you!

Re: Finding Waldo in π

#67

Post by kundor »

kundor wrote: post #61
captainmuon wrote: post #49

Could there be a number, such that for certain interesting data, you can compress the data more than normally achiveable, by indexing into the number? I feel this should not be possible, but I don't know how to proove it without a circular argument about entropy. On the other hand, if you make a string of common byte sequences, a couple GB long, and distribute it with every PC... then you surely can achive hyper comp…

Yes, to an extent that would work. 1) Take target image 2) Find the index in π (say) where a matchable sequence of bytes occur, like for Waldo. (If your image is big, this could take several years of computation time.) 3) Transmit the palette, width, height, and index: about 800 bytes. 4) Probably the index is too far out for everyone to have a copy of the data already (it would be beyond terabytes). So the recipient…

PS. The fact that any image can be encoded in 32 bytes this way implies that there are only 2^256 possible images — about one hundred and sixteen quattuorvigintillion. That's obviously not literally true, but we are searching for a subsequence of π which is "close enough"; the number of possible images which humans would consider distinct is probably well less than that.

(That is, the vast majority of possible images are "color noise" which all look more or less the same.)

Re: Finding Waldo in π

#68

Post by GoblinSlayer »

eyelidlessness wrote: post #10

I wonder, but don’t have a strong instinct either way, whether this might be easier to do without cheating targeting a format intentionally designed for lossy compression and at least somewhat forgiving error correction (like JPEG, but certainly not limited to that).

Fuzzy matching is more tolerant to differences than lossy compression.

Re: Finding Waldo in π

#69

Post by bscphil »

kundor wrote: post #8
bscphil wrote: post #5

> The trick is that we can reassign the colors using a palette. And in fact you always need to do this; you have to somehow decide which color each byte should represent. Hmm. I don't know that I agree. There are certainly more objective choices here than just picking any old palette, and in fact there are choices where it's not obvious the result should be considered a "palette" at all. For example, the obvious choi…

That's still a choice of palette; you'll find it listed on Wikipedia [1] under "Regular RGB palettes". There's no doubt it's a much more objective choice than the one I used! I did say I was cheating. Going to 4-bit color won't make it feasible. Even with 1-bit black/white pixels on about the minimum possible 18x24 Waldo face, you have 432 bits to look for, and you're not going to find them without cheating somehow.…

I made a video showing a slow zoom-in to Waldo in the first hundred million hex digits of pi, using your color palette. Feel free to use it if you want with a link back to this comment, I release it under CC-BY.

https://0x0.st/oq0Q.mp4

(The idea is basically that each consecutive 988 bytes gets put into an individual 19x26 8 bit image with your color palette, and these are then stacked in row order.)

Re: Finding Waldo in π

#70

Post by kundor »

bscphil wrote: post #69
kundor wrote: post #8

Earlier quoted context omitted.

That's still a choice of palette; you'll find it listed on Wikipedia [1] under "Regular RGB palettes". There's no doubt it's a much more objective choice than the one I used! I did say I was cheating. Going to 4-bit color won't make it feasible. Even with 1-bit black/white pixels on about the minimum possible 18x24 Waldo face, you have 432 bits to look for, and you're not going to find them without cheating somehow.…

I made a video showing a slow zoom-in to Waldo in the first hundred million hex digits of pi, using your color palette. Feel free to use it if you want with a link back to this comment, I release it under CC-BY. https://0x0.st/oq0Q.mp4 (The idea is basically that each consecutive 988 bytes gets put into an individual 19x26 8 bit image with your color palette, and these are then stacked in row order.)

That's awesome!
Post reply on HN