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.
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.)
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.
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) :)
Referring specifically to divisibility tests, converting bases takes more work than just doing the division. What other operations were you thinking of?
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.)
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.
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)
It seems to go for the "least interesting" result. eg: I gave it 363 and it gave me back 363 + 0 + 0, which while technically true, 121 + 121 + 121 would have been more in the spirit of it, IMO. Or even 242 + 121 + 0 would be a little easier than just reusing the original palindrome number with zeros.
Well it proofs the existence and there are many special cases they consider.
If the number is a palindrome already there are many possible solutions. Using zeros is a trivial an the simplest solution. Using anything else would be abitrary and longer too.
Looks like code is at [0]. Didn't read in detail, but how difficult is it to find these 3 palindromes for something like a 100 digit number? Or, asked another way, how hard will it be to crack my new 3-palindrome-sum-factor based encryption scheme (assuming I have rules about not having easy factors)?
I guess the next question might be then, can the upper limit for the number of potential matches be found, if no restrictions are placed on the input sequence?
Without thinking the problem through (about to sleep) I wouldn't be surprised if the answer is easily proven to be exponential (aka a firm "nope") but math can be unintuitive at times so I thought I'd ask anyway.
I ask because, if the maximum number of potential matches isn't exponential (or is at least <= 3 digits long), it might be plausible to read through the number of matches to find "interesting" (elegant-looking) ones.
I don't think it was sarcasm but they were making the same point. It's whimsical and excited and uncool. This will get you cachet among mathematicians though :)
> The real physical universe doesn't offer tooling for playing with advanced math, though.
The real physical universe is nothing but tooling for playing with advanced math (but it's not always easy to figure out what the advanced math is, or how best to play with it).
IMHO that's like saying higher level programming languages than assembly are unnecessary. Or that a debugger is useless.
And not just the learning purposes. Imagine the possibilities if we could properly simulate (and speed up the simulation) the world - what if we could use genetic algorithms to develop an organism.
> IMHO that's like saying higher level programming languages than assembly are unnecessary. Or that a debugger is useless.
These two statements are quite different. Higher level programming languages than assembly are unnecessary; anything beyond the lambda calculus is unnecessary (assuming our goal is to compute Turing computable things). That's very different from saying that they're useless; just because they can be done without doesn't mean that they should.
I know that these statements are quite different, I deliberately made two different examples - one about creating and one about debugging. A world simulator is going to be a test environment for us as well as an introspection tool.
you should check out Brett Victor's (http://worrydream.com/) and Nicky Case's (https://ncase.me/) websites. They both build really interesting systems for exploratory learning.
yup, super fun. Would be even more awesome if there was explanation of the process as the numbers are being found, might be more accessible than reading the paper.
I wish there was a list of sites like these - learning for the pure joy of learning, with no other expectations.
I figured it had small cases down so I immediately went for a fifteen digit number from /dev/urandom and was happy that it solved it perfectly. But I'm probably the exception.
For those wondering how to generate random numbers, it's simple if you don't care about a little computational overhead: </dev/urandom tr -dc 0-9 | head -c 15 (substitute 0-9 for any character set like a-zA-Z or \ -~). I use this to generate random PIN numbers after it took too long to read the pwgen man page, and I might start to use it as replacement for pwgen altogether since it only uses very basic tools that are available everywhere, unlike pwgen.
To explain the command: we read urandom into tr's stdin; tr translates (like "echo haha | tr a u"); with -d, tr deletes instead of substituting; with -c, it takes the compliment set (so everything except what you specify). Basically we're filtering characters or of urandom's output. Finally, we limit the output to a certain number of characters.
Cool one-liner to get random digits. On OSX, it produces the error "tr: Illegal byte sequence." The solution, per https://unix.stackexchange.com/q/45404, is to prepend the script with "LC_CTYPE=C ":
The paper gives a detailed algorithm to provide 3 palindrome that add up to the number. The algorithm has tons of cases, but it's actually pretty simple. They work through a couple in the video.
I like how the JavaScript functions support different bases (5 or greater), but the page itself doesn't. It makes me want to play around with it in the browser console...
Why is that interesting? Limiting it to 3 makes it hard. If you allow an arbitrary amount then you can just represent the number in unary and call it a day.
And just to clarify, the greedy algorithm (take the largest palindrome less than the number you're trying to express) doesn't work. To take a random nine-digit example (literally the first one I tried): 635932028 = 635929536 + 2442 + 44 + 6. In general you can express N as a sum of something like log(log(N)) palindromes this way, which is not quite constant.
If 2 is not a palindrome, because if you prepend 0 it loses its palindrome properties, then no number is a palindrome. 121 cannot be a palindrome because 121 can also be written as 0121, and therefore it’s not a palindrome.
Further, there is nothing “unfair” about 0. It’s a real distinction. 002 is the same thing as 2. 112 is not the same thing as 2. So it’s not an unfair property. It’s a real distinction.
Right, that's why I put the word "unfair" in quotes; I wasn't sure how to rephrase the OP. Of course it is a real distinction, but I was trying to explain why other commenters weren't finding it impressive.
This reminds me a bit of Fourier transformations from time- to frequency-domain.
Where an arbitrarily complex time-series signal can be accurately represented as the sum of various sine waves.
Except the OP deals with a discretized values, not real-number values, and the OP's approach lets the constituent palindromes start/end at an arbitrary offset, rather than having to be repeated continuously.
The most impressive part of this calculator IMHO is the animated text, it dresses up a parsing script and function into a very nice package. I say good job, I wonder how difficult it would be to show a list of all the combinations of three "palindromes" for a given number?
Could this trick be used to improve compression? Since palindromes contain repeated digits by definition, perhaps they are more compressible than the original number? Of course, you'd have three numbers to compress instead of one...
Palindromes can be compressed 50% by using their symmetry. Representing a number as 3 palindromes would "compress" a number to 1.5 times the original size in the worst case. Obviously not an improvement.
If the number itself happens to be a palindrome, you can get down to 50%, but that's completely unrelated to this trick.
In general, it's impossible for a compression algorithm to losslessly compress all numbers to a shorter representation, it can only make some numbers shorter and others longer. (Pigeonhole principle: there are not enough short codes, so if you assign a shorter code to all numbers, some will get the same code, making the compression not lossless.)
Practical uses of compression are all about reducing the average length given a nonuniform probability distribution, so a palindrome-based compression scheme would only be useful if you could expect most numbers you're dealing with to be palindromes.
Ah that is neat. For most smaller numbers, it seems to use 0 a lot, which is not interesting. But your example is the first one I saw that didn't include 0.
The impressive thing is actually the underlying proof. 40+ pages with lots of edge cases and algorithms for every scenario of any arbitrarily large number.
Palindromes are sort of the least surprising numbers to have this property because you can easily "split" them into as many palindromes as you want like this. The surprising result is that you could write something like 19837100018374 as the sum of only 3 palindromes.
The intent of my question was an answer that doesn't require reading 40 pages of mathematics proof (and before that learning how to read 40 pages of mathematics proof).
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.