Timeline for Is the Number of Carries in Integer-Addition Associative?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 4, 2016 at 4:46 | vote | accept | Manfred Weis | ||
| Sep 18, 2015 at 12:05 | answer | added | Steven Landsburg | timeline score: 10 | |
| Sep 18, 2015 at 9:42 | answer | added | Ilya Bogdanov | timeline score: 15 | |
| Sep 18, 2015 at 8:13 | comment | added | Manfred Weis | I just checked apolge's formula with wolframalpha via "((a+b) choose a)*((a+b+c) choose c)" and its correct, i.e. symmetric in all variables. | |
| Sep 18, 2015 at 7:59 | answer | added | Mark Wildon | timeline score: 3 | |
| Sep 18, 2015 at 7:54 | review | Close votes | |||
| Sep 18, 2015 at 12:20 | |||||
| Sep 18, 2015 at 7:38 | comment | added | Manfred Weis | @alpoge I agree with Anthony; could you please post your comment as answer? | |
| Sep 18, 2015 at 7:32 | comment | added | Manfred Weis | @AnthonyQuas thanks for the clarifying edit! | |
| Sep 18, 2015 at 7:31 | comment | added | Anthony Quas | I was about to post a crude answer involving lots of induction when $c$ was a power of 2. But the beautiful answer of @alpoge makes this unnecessary. I think this should be posted as an answer. | |
| Sep 18, 2015 at 7:26 | history | edited | Anthony Quas | CC BY-SA 3.0 |
explained question more fully
|
| Sep 18, 2015 at 7:26 | comment | added | joro | @ManfredWeis Your last comment is entirely different from your wikpedia link, which works with $n$ bit words and counts carries between works. | |
| Sep 18, 2015 at 7:26 | comment | added | Manfred Weis | @FedericoPoloni I have tried to come up with counter examples, but was not successful. | |
| Sep 18, 2015 at 7:25 | comment | added | alpoge | The number of carries when adding $a$ and $b$ in base $p$ is the power of $p$ that divides ${a+b \choose a}$. Thus the total number of carries in evaluating e.g. $(a+b)+c$ is the power of $p$ dividing ${a+b \choose a}{a+b+c \choose c} = \frac{(a+b+c)!}{a!b!c!}$, which is symmetric in $a,b,c$. Hope I haven't made a mistake! | |
| Sep 18, 2015 at 7:22 | comment | added | Anthony Quas | @joro: I don't understand your question then. | |
| Sep 18, 2015 at 7:21 | comment | added | joro | @AnthonyQuas positive answer to the question about modulo 2^n would mean 3+1=4 is zero carries, since carry truncates the result modulo 2^n. | |
| Sep 18, 2015 at 7:10 | comment | added | Federico Poloni | Have you tried testing the assertion? Does it hold in practice, or are there obvious conuterexamples? | |
| Sep 18, 2015 at 7:04 | comment | added | Anthony Quas | So $3+1=4$ is 2 carries? | |
| Sep 18, 2015 at 6:46 | comment | added | joro | So you do addition of words modulo $2^n$ and count carries between words? | |
| Sep 18, 2015 at 6:44 | comment | added | Manfred Weis | @joro I thought that it should be clear, what a carry or carry-bit is in the context of addition. An explanation can be found here: en.wikipedia.org/wiki/Carry_flag | |
| Sep 18, 2015 at 6:27 | comment | added | joro | How do you define "carry"? | |
| Sep 18, 2015 at 6:23 | history | asked | Manfred Weis | CC BY-SA 3.0 |