[HN Gopher] Sierpinski Triangle? In My Bitwise and?
___________________________________________________________________
Sierpinski Triangle? In My Bitwise and?
Author : guiambros
Score : 34 points
Date : 2025-05-10 21:42 UTC (1 hours ago)
(HTM) web link (lcamtuf.substack.com)
(TXT) w3m dump (lcamtuf.substack.com)
| jcul wrote:
| I can't dismiss the cookie popup on this page. After rejecting or
| accepting cookies it reloads and reappears.
|
| Apologies for a comment not related to the content, but it makes
| it difficult to read the article on mobile.
| jcul wrote:
| Really interesting, and surprising article though!
| IceDane wrote:
| Same problem here. Firefox on Android.
| peterburkimsher wrote:
| Wolfram did a lot of research into cellular automata, and the
| Sierpinski Triangle kept showing up there too:
|
| https://www.wolframscience.com/nks/
| GuB-42 wrote:
| This one in particular: https://en.wikipedia.org/wiki/Rule_90
| jesuslop wrote:
| You get those also doing a Pascal triangle mod 2, so a xor. Is a
| zoom-out fractal as oposed to Mandelbrot set.
| anthk wrote:
| True. pas.f in Forth : .r u.r ; :
| position ( row -- ) cr 33 swap 2 * - spaces ; :
| pas ( 0 ... 0 -- 0 ... 0 ) 0 >r begin over + >r dup
| 0= until begin r> dup while dup 4 .r repeat ;
| : pass ( -- ) 0 1 0 18 0 ?do dup position >r pas r>
| 1+ loop drop ; : pax ( 0 ... 0 -- ) drop begin
| 0= until ; : pascal ( -- ) pass pax ;
| pascal cr
|
| The same mod2: : .r u.r ; : position
| ( row -- ) cr 33 swap 2 * - spaces ; : pas ( 0 ...
| 0 -- 0 ... 0 ) 0 >r begin over + >r dup 0= until
| begin r> dup while dup 2 mod 4 .r repeat ; : pass
| ( -- ) 0 1 0 18 0 ?do dup position >r pas r> 1+
| loop drop ; : pax ( 0 ... 0 -- ) drop begin 0=
| until ; : pascal ( -- ) pass pax ;
| pascal cr
|
| A Forth for people in a hurry: git clone
| https://github.com/howerj/subleq cd subleq
| sed -i 's,0 constant opt.control,1 constant opt.control,g'
| subleq.fth gmake subleq ./subleq subleq.dec <
| subleq.fth > new.dec ./subleq new.dec < pas.f
| dvt wrote:
| Just a heads up, all (binary?) logical operators produce
| fractals. This is pretty well-known[1].
|
| [1] https://icefractal.com/articles/bitwise-fractals/
| zX41ZdbW wrote:
| Sierpinski also sounds nice in music. Examples here:
| https://github.com/ClickHouse/NoiSQL
| gjm11 wrote:
| Here's a possibly-too-highbrow explanation to complement the nice
| simple one in the OP.
|
| "As everyone knows", you get a Sierpinski triangle by taking the
| entries in Pascal's triangle mod 2. That is, taking _binomial
| coefficients_ mod 2.
|
| Now, here's a cute theorem about binomial coefficients and prime
| numbers: for any prime p, the number of powers of p dividing (n
| choose r) equals the number of _carries_ when you write r and n-r
| in base p and add them up.
|
| For instance, (16 choose 8) is a multiple of 9 but not of 27. 8
| in base 3 is 22; when you add 22+22 in base 3, you have carries
| out of the units and threes digits.
|
| OK. So, now, suppose you look at (x+y choose x) mod 2. This will
| be 1 exactly when _no_ 2s divide it; i.e., when _no_ carries
| occur when adding x and y in binary; i.e., when x and y never
| have 1-bits in the same place; i.e., when x AND y (bitwise) is
| zero.
|
| And that's exactly what OP found!
___________________________________________________________________
(page generated 2025-05-10 23:00 UTC)