Re:Any positive number can be written as a sum of three pali...
by robotmlg on Tuesday September 18, 2018 @11:40AM
(#18016187)
And according to the Numberphile video (https://www.youtube.com/watch?v=OKhacWQ2fCs) there is a prior paper showing it for bases 2, 3, and 4
Re:Any positive number can be written as a sum of three pali...
by jerf on Tuesday September 18, 2018 @12:42PM
(#18016798)
Not base 2. All palindromes in base 2 have a 1 in the last position, because there's a 1 in the first position. This means that any addition of 3 palindromes must be odd because the result of the addition is guaranteed a 1 in the ones position, meaning even numbers can't possibly be represented that way. This is discussed in the original paper at the bottom of the second page: https://arxiv.org/pdf/1602.06208.pdf , which I've expanded out a bit since they just mention the evenness without the argument I give. They say base 2 needs at least 4 summands, but their phrasing suggests to me that's intended as a lower bound, not that they have a proof 4 is always sufficient. (Not to mention it would have to be more complicated than that anyhow since it would have to be something like "3 for odd and 4 for even above some threshold", or some other bounds.)
Re:Any positive number can be written as a sum of three pali...
by fourthark on Tuesday September 18, 2018 @01:13PM
(#18017120)
This site uses 0.
Re:Any positive number can be written as a sum of three pali...
by doodpants on Tuesday September 18, 2018 @02:37PM
(#18017921)
If you pause at 3:33 in the video and read the abstract, it actually says that numbers in base 2 require "at most 4 palindromes", rather than exactly 3, and "similar results" were found for bases 3 and 4. So it's not quite the same result as for bases of 5 or greater.
Re:Any positive number can be written as a sum of three pali...
by CydeWeys on Tuesday September 18, 2018 @12:03PM
(#18016378)
Oh nice, so it works in every base then. Awesome.
Re:Any positive number can be written as a sum of three pali...
by shaded-enmity on Tuesday September 18, 2018 @12:45PM
(#18016835)
Yeah, for example to check if a number is divisible by 3, we can use the digit sum and check if the result is divisible by 3, e.g. 153=(1)+(5)+(3)=9.
This works in base-10, but we can generalize this by converting the dividend X into (3* X+1)-base then doing a digit sum.
Let's say we want to check whether 238 is divisible by 17, so our base is 3* 17+1=52, 238 in base-52 is (4)+(30)=34=2* 17.
If the convert-to-arbitrary-base operation was particularly cheap to compute, we could convert to base X+1 and check if the last number is 0 (same logic as: is_even = (i & 1) == 0) :)
Re:Any positive number can be written as a sum of three pali...
by pishpash on Tuesday September 18, 2018 @01:55PM
(#18017574)
The convert to base X operation can't be cheaper than just dividing by X, can it?
Re:Any positive number can be written as a sum of three pali...
by industriousthou on Wednesday September 19, 2018 @01:14AM
(#18021841)
Is it unreasonable to think that some operations might be cheaper to compute by the converting the base and applying these types of tests?
Re:Any positive number can be written as a sum of three pali...
by pmiller2 on Wednesday September 19, 2018 @02:00AM
(#18022055)
Referring specifically to divisibility tests, converting bases takes more work than just doing the division. What other operations were you thinking of?
Re:Any positive number can be written as a sum of three pali...
by dtech on Tuesday September 18, 2018 @11:57AM
(#18016311)
> For example, being able to tell if a number is divisible by 2 or 5 by only looking at the last digit.
That still seems like it is generalizable to any base by taking prime factors of any base-n.
Re:Any positive number can be written as a sum of three pali...
by schoen on Tuesday September 18, 2018 @12:18PM
(#18016553)
There's a stronger generalization: it's true of any divisor of the base (not just prime divisors and not just proper divisors). For example, it works for divisibility by 6 in base 12, or divisibility by 10 in base 10.
(Also, the digital root test, where you add up the digits, works for any divisor that is also a divisor of the base minus 1, so for example hexadecimal has a digital root test for divisibility by 3, 5, or 15.)
Re:Any positive number can be written as a sum of three pali...
by dmurray on Tuesday September 18, 2018 @12:30PM
(#18016668)
And the less well known "add and subtract alternative digits" works for dividing by 11, that is, the base plus one, in any base. And for any divisors of 11.
Re:Any positive number can be written as a sum of three pali...
by taejo on Wednesday September 19, 2018 @08:26AM
(#18023655)
And much more generally, "numbers divisble by n written base b" is a regular language decidable by an n-state DFA (and thus in linear time, looking at each digit exactly once). And see https://blog.plover.com/math/divisibility-by-7.html for a state machine that's even simpler (you only need edges for +1 and ×b, rather than +d×b for each digit d)
Re:Any positive number can be written as a sum of three pali...
by QuercusMax on Tuesday September 18, 2018 @01:08PM
(#18017052)
You mean any divisors of [base + 1], right?
Every time I see something like this that is dependent on base-10 representation, I'm always curious to know whether it generalizes, or if it's a quirk specific to base-10 representation. For example, being able to tell if a number is divisible by 2 or 5 by only looking at the last digit.