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.
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.
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.
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.
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.
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.
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 impressive thing is actually the underlying proof. 40+ pages with lots of edge cases and algorithms for every scenario of any arbitrarily large number.
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 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?
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.
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)
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?
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...
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.
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).
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.
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.
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 ":
113 comments
[ 4.7 ms ] story [ 176 ms ] threadTotal crap. Down vote this to death.
(2 == 002 but 112 != 211 which is an "unfair" property of the number zero)
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.
101=101+0+0
What happends to quirky people like this when they leave university and enter the industry?
But as a one-shot, I love it!
The real physical Universe is interactive nonfiction.
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).
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.
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 wish there was a list of sites like these - learning for the pure joy of learning, with no other expectations.
Newcastle University: I'm e-learning officer in the School of Mathematics and Statistics.
Most of my job involves writing the maths e-assessment system, Numbas. https://www.numbas.org.uk/
0 - https://github.com/christianp/sum-of-palindromes
2 is (2,0,0) and (1,1,0).
A composition is an ordered partition. A partition is the set of numbers that sum to a particular number. The 'weak' part allows zeros.
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.
:)
And if you don't like that:
55555 = 12321 + 23132 + 20102
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.
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.
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.
77777777777777 +0 +0 =77777777777777
> 1,234,567 + 0 + 0 = 1,234,567
The first of these is not a palindrome.
http://oeis.org/A261132
http://oeis.org/A261132/graph
Do you just mean "the sequence a(n)"? I don't see anything especially interesting about the first 4 terms.
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.
That still seems like it is generalizable to any base by taking prime factors of any base-n.
(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.)
> Yes, I can do this for any whole number bigger than zero.
Should say "Yes, I can do this for any whole number zero or bigger." since 0 is a palindrome
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.
It's a cool result.
LC_CTYPE=C </dev/urandom tr -dc 0-9 | head -c 15
in all seriousness it is always amazing to see simple theorems rely on such complex proofs