4 ms·
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 entrie
by gjm11 1y ago
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!
- jujuh 1y ago[dead]
- coderatlarge 1y agoi really love the result you quote about the carries. do you know where it has been applied by any chance?
- gjm11 1y agoI don't know of applications offhand, sorry. For me it's in the "appreciated for its own sake" category :-).
- coderatlarge 1y agoi can see that for sure. do you have a reference by any chance? chatgpt hallucinates various references given the result. knuth’s “concrete mathematics” might have it.
- deleted 1y ago[deleted]
- deleted 1y ago[deleted]
- gjm11 1y agoI don't know whether it's in Concrete Mathematics, but perhaps https://en.wikipedia.org/wiki/Kummer%27s_theorem https://en.wikipedia.org/wiki/Kummer%27s_theorem will do? (That page has a link to another beautiful theorem with a similar feel, Lucas's theorem: if p is prime, then (n choose r) mod p is the product of the (n_i choose r_i) where n_i and r_i are corresponding digits of n and r when written in base p.)
- gjm11 1y agoI checked: the result is in Concrete Mathematics, as exercise 5.36, but there is no attribution to Kummer there. Incidentally, I found the name of the theorem (and the Wikipedia page about it) using a new kind of tool called a "search engine". It's a bit like asking ChatGPT except that it hardly ever hallucinates. You should try it! :-)
- svat 1y agoFor what it's worth: Concrete Mathematics does have an attribution to Kummer — it's just that the credits are given separately in Appendix C, "Credits for Exercises", where on page 634, next to 5.36 (the exercise number you mentioned), you can find "Kummer [230, p. 116]" and [230] (on page 621, in Appendix B, "Bibliography") gives the full citation: > E. E. Kummer, “Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen,” Journal für die reine und angewandte Mathematik 44 (1852), 93–146. Reprinted in his Collected Papers, volume 1, 485–538. Also, the answer to exercise 5.36 says “See [226] for extensions of this result to generalized binomial coefficients” and [226] (on page 620) is: > Donald E. Knuth and Herbert S. Wilf, “The power of a prime that divides a generalized binomial coefficient,” Journal für die reine und angewandte Mathematik 396 (1989), 212–219 which of course begins (https://www2.math.upenn.edu/~wilf/website/dm36.pdf https://www2.math.upenn.edu/~wilf/website/dm36.pdf) by citing Kummer. (Looks like the authors published in the same journal as Kummer, 137 years later!)
- ethan_smith 1y agoThis elegantly explains why (x & y) == 0 produces Sierpinski triangles: it's equivalent to checking whether (x+y choose x) mod 2 equals 1, directly connecting bitwise operations to binomial coefficients.