Timeline for Number triangle
Current License: CC BY-SA 4.0
35 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 7, 2020 at 2:22 | comment | added | DSM | @PeterKagey, wow! Didn't expect that. And, thanks to Michael De Vlieger. | |
| May 6, 2020 at 23:35 | comment | added | Peter Kagey | Michael De Vlieger, an OEIS contributor, made a visually stunning image that contains hundreds of these triangles (with top row encoded by $1, 11, 13, 39, 57, 83, \dots$). | |
| May 5, 2020 at 3:52 | comment | added | DSM | @GerryMyerson, guess your logic regarding non-existence of palindromes holds good for any base-representation. | |
| May 5, 2020 at 3:51 | comment | added | DSM | @MaxAlekseyev, thanks for that interesting observation. | |
| May 4, 2020 at 23:39 | comment | added | YCor | @LSpice OK I finally did it (time-consuming, this is why I was hesitating at writing down... what I said about palindromes (namely that all rotational-invariant solutions with 0 on corners )are palindromes seems suspicious by the way. | |
| May 4, 2020 at 23:36 | answer | added | YCor | timeline score: 0 | |
| May 4, 2020 at 21:18 | comment | added | LSpice | @YCor, your comments look very interesting, but are tough to read as written. Would you be willing to promote them to an answer, so that they can be read full size and all at once? | |
| May 3, 2020 at 21:16 | comment | added | YCor | What I checked the other day is that the number of solutions (rotation invariant and allowing 0 on corners) is $2^{u_n}$ with $u_n=n+v_n$, and $v_n$ 3-periodic with $v_0=v_1=1$ and $v_2=-2$. It follows that the number of solutions with $1$ on the corner is either $0$, or $2^{u_n-1}$, say $t_n2^{u_n-1}$ with $t_n\in\{0,1\}$. I expected $t_n$ to depend on $n$ modulo $2$, but actually it seems to rather depend on $n-1$ being a $2$-power. So the counting problem is completely settled. It's easy to describe an algorithm to enumerate the solutions (allowing 0 on corners) passing from $n-3$ to $n$. | |
| May 3, 2020 at 21:03 | answer | added | Ilya Bogdanov | timeline score: 5 | |
| May 3, 2020 at 17:08 | comment | added | Max Alekseyev | It seems that solutions do not exist only for length of the form $2^k+1$. | |
| May 3, 2020 at 12:58 | comment | added | DSM | @GerryMyerson, thanks for that nice proof, and the earlier observation. | |
| May 3, 2020 at 9:41 | comment | added | Gerry Myerson | The nonexistence of palindromic solutions is trivial. Let $a$ be the entry immediately to the right of the $1$ in the upper left corner, let $b$ be the entry immediately below that $1$ (so, the first entry in the 2nd row). For a palindrome, $a=b$. But by construction of the triangle, $1+a=b$. Contradiction. | |
| May 2, 2020 at 17:06 | comment | added | Pat Devlin | A cool question. You should ask how many triangles there are of each size having the properties you care about. This number will be a power of two since these triangles are a vector spaced over $F_2$. | |
| May 2, 2020 at 13:15 | comment | added | Gerry Myerson | When you work mod 2, addition is the same as subtraction. So the second row gives the first differences of the first row, the third row gives the second differences, and so on. Then you can recover the top row from the left side as a sum of binomial coefficients. E.g., for top row 1101, the left side is 1011, so $1+{n\choose2}+{n\choose3}$ gives $1,1,0,1$, respectively, for $n=0,1,2,3$, respectively (working mod 2). So you can write down what a "special" number is, in terms of binomial coefficients. | |
| May 2, 2020 at 9:38 | comment | added | YCor | PS what I asserted in the previous comment implies in particular that the sum (mod 2) of any two solutions is a palindrome. That is, the solutions (with rotational symmetry and 1 on corners) form an affine space whose linear part is the set of palindrome solutions (necessarily with 0 on extremities). For instance, $[1, 0, 1, 0, 0, 1, 1]+[1, 0, 1, 1, 0, 1, 1]=[0,0,0,1,0,0,0]$. | |
| May 2, 2020 at 9:16 | comment | added | YCor | My expectation $u_n$ quadratic isn't correct, it's simpler. It seems $u_{n+3}=u_n+3$ for the counting without symmetry. Precisely here $u_n$ is the number of ways to assign to each vertex of a triangulation as in your picture, with $n$ vertices on the top (hence $n(n+1)/2$ vertices), a boolean number so that every upside down small triangle sums to 0. If $v_n$ counts those with rotational symmetry, we get $v_{n+3}=v_n+1$; precisely in this case, the palindromic ones are those with 0 on the corners, and you count the non-palindromic ones. Counting palindromic should involve discussion mod 2. | |
| May 2, 2020 at 8:23 | comment | added | DSM | @YCor, thanks for the clarification. I'll think about the reasoning surrounding palindromes. One complete classification of solutions between two powers of 2 is the set of solutions to a set of linear equations, which I've mentioned in the question. Number of solutions also being a power of two, is simple. My bad. :) | |
| May 2, 2020 at 8:06 | comment | added | YCor | My reasoning was not correct in excluding palindromes (by mistake I assumed that reversed little triangles also sum to zero). Reasoning from the center remains anyway probably the right way to get classification. Probably the resulting dimensions are related to the homology mod-2 of the space consisting of this triangulation, with only tiling triangles with vertex on the bottom being filled. This would justify that the number $2^{u_n}$ of solutions of your problem in $[2^n,2^{n+1}[$ should have $u_n$ quadratic in $n$ (with discussion on $n$ mod 3), experiments can lead to the right conjecture. | |
| May 2, 2020 at 7:30 | comment | added | YCor | It's not logic, it's interpreting the problem as solving a system of linear equations over $F_2$. Hence basic linear algebra. | |
| May 2, 2020 at 7:26 | comment | added | DSM | And, also the logic for the number of solution being power of 2. I am certainly missing some logic here. | |
| May 2, 2020 at 7:24 | comment | added | DSM | @YCor, can you elaborate your logic about non-existence of palindromes? | |
| May 2, 2020 at 7:19 | comment | added | YCor | BTW I checked there's no palindrome, by arguing around the center of the triangle. Still, if you allow numbers starting with zero, you have a few: the 0 triangle, and only one other for each $n=3m+1$: the triangle (drawn for $n=7$) $$\begin{matrix}0&&1&&1&&0&&1&&1&&0\\&1&&0&&1&&1&&0&&1&\\&&1&&1&&0&&1&&1&&\\&&&0&&1&&1&&0&&&\\&&&&1&&0&&1&&&&\\&&&&&1&&1&&&&&\\&&&&&&0&&&&&&\end{matrix}$$. | |
| May 2, 2020 at 7:13 | comment | added | YCor | To start with, compute for $n<19$ the number of solutions $k$ such that $2^n\le k<2^m$ (i.e., with exactly $n+1$ binary digits). it should be a power of 2, do you confirm? | |
| May 2, 2020 at 7:07 | comment | added | DSM | @YCor, I am not sure if I completely understand your comment relating to constructing 0-1 triangles with n-vertices, apart from basic similarity to the original question. Guess what you're suggesting is to view the graph in log-scale? | |
| May 2, 2020 at 7:00 | comment | added | YCor | For every $n$ the number of solutions with $n$ binary digits is thus a power of 2, so it would make more sense to compute, instead of the number of solutions $\le m$, the number $2^{u_n}$ of solutions in $[2^n,2^{n+1}[$, which should be computable in terms of ranks of some matrices. Maybe these matrices have a homological interpretation, I'm not sure. | |
| May 2, 2020 at 6:58 | comment | added | YCor | OK, thinking more: say you're considering triangles with $n$ vertices on each large edge. You're first counting those 0-1 (mod 2) valued triangles with the property that the sum is zero on each triangle. The number of solutions of this is then a power of 2. This remains true if you add any symmetry condition, and also if you impose an affine condition, such as the condition that extreme vertices are marked with $1$. | |
| May 2, 2020 at 6:52 | comment | added | DSM | @YCor, thanks for that nice observation. Will try that. | |
| May 2, 2020 at 6:47 | comment | added | YCor | Note that reversing the binary expansion induces an involution on the your set of numbers, whose fixed points are the palindromes, exchanging 11—13, 39—57, 83—101, 91—109, etc. Maybe you can test palindromes until much further than 500000, since a palindrome is governed by twice less digits. | |
| May 2, 2020 at 6:42 | comment | added | DSM | @YCor, there are no palindromes (in binary representation) till 500000. | |
| May 2, 2020 at 6:38 | comment | added | DSM | @YCor, thanks for the comments. Have edited XOR-ing accordingly. Have not checked for palindromes yet. Will do that too and post result in the next comment. | |
| May 2, 2020 at 6:35 | history | edited | DSM | CC BY-SA 4.0 |
added 18 characters in body
|
| May 2, 2020 at 6:35 | comment | added | YCor | Have you counted, among those numbers, the palindromic ones? (i.e., those for which the resulting triangle has a symmetry group of order 6) | |
| May 2, 2020 at 6:33 | comment | added | YCor | Writing at the beginning that xoring= adding mod 2 would save time (I googled to find the definition). | |
| May 2, 2020 at 6:13 | history | edited | DSM |
edited tags
|
|
| May 2, 2020 at 5:58 | history | asked | DSM | CC BY-SA 4.0 |
