12 ms·
Any positive number can be written as a sum of three palindromes
- akudha 8y agoFrom this numberphile video - https://www.youtube.com/watch?v=OKhacWQ2fCs https://www.youtube.com/watch?v=OKhacWQ2fCs
- JAdamMoore 8y agoSite isn't secure. CSS fails on Opera. Can't see whatever they are so excited about; it doesn't render at all. Total crap. Down vote this to death.
- et2o 8y agoEvery positive number is a sum of infinite palindromes since they include 0 as a palindrome. Try entering 101.
- jarfil 8y agoIt's easier to find more than fewer palindromes that when summed up will give a certain number. Finding just the three, is not that easy.
- madcaptenor 8y agoAnd 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.
- yiyus 8y agoWhy wouldn't 0 be a palindrome? Every single digit number is.
- ReverseCold 8y agoI think they're saying that 002 is counted as a palindrome, but 112 would not be. (2 == 002 but 112 != 211 which is an "unfair" property of the number zero)
- addicted 8y agoIf 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.
- ReverseCold 8y agoRight, 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.
- deleted 8y ago[deleted]
- mikeash 8y agoWhy 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.
- tantalor 8y ago101 is a palindrome so... 101=101+0+0
- torstenvl 8y agoLiterally just resets and refreshes the page when I hit the submit.
- aembleton 8y agoYou need to allow Javascript
- rekshaw 8y ago1000 = 999 + 1 + 0 --- That don't impress me much.
- happytoexplain 8y agoWhy?
- deleted 8y ago[deleted]
- danielhlockard 8y agoIt's correct though, each of them are palindromes...
- Aardwolf 8y agoTry larger numbers like 638347455 (randomly hit numpad)
- jerf 8y agoYou may find the original paper proving this more impressive: https://arxiv.org/abs/1602.06208 https://arxiv.org/abs/1602.06208
- princekolt 8y agoYou gave it a trivial solution. What did you expect. Throw in a 16 digit number instead.
- tw1010 8y agoWonderful wonderful website. What happends to quirky people like this when they leave university and enter the industry?
- Aardwolf 8y agoHmm, didn't find it that wonderful, would prefer something that looks more neutral on my screen
- tlamponi 8y agohe was sarcastic...
- sp332 8y agoI 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 :)
- rectang 8y agoFortunately I don't have to go back and use this website time after time, which would get annoying. But as a one-shot, I love it!
- princekolt 8y agoExactly. This is effectively a hotsite for their proof.
- tw1010 8y agoI wasn't sarcastic.
- nmg 8y agoIs there such a thing as "interactive nonfiction"? Because if not, there should be. Design educational websites this way and watch children learn.
- kodablah 8y agoLooks 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)? 0 - https://github.com/christianp/sum-of-palindromes https://github.com/christianp/sum-of-palindromes
- CalChris 8y agoUniqueness would be a problem. The sum isn't guaranteed to have unique terms. 2 is (2,0,0) and (1,1,0).
- gilleain 8y agoHuh, so its related to the problem of finding the restricted weak compositions of a number. A composition is an ordered partition. A partition is the set of numbers that sum to a particular number. The 'weak' part allows zeros.
- princekolt 8y agoAsymmetric key encryption then! Just replace Modulus(x,y) with this instead.
- exikyut 8y agoI 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.
- ez15972 8y agoI entered 55555 which gave the underwhelming result of 55555+0+0 :/
- relate 8y agoWould you prefer 11111+11111+33333 instead?
- rejschaap 8y agoStill a bit boring, feels like cheating, something like 12321 + X + Y would be nice.
- ashtonbaker 8y ago55555 = 12321 + 43234 + 0 :) 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.
- kosievdmerwe 8y agoMore surprising is that you can do it in any base >= 5
- deleted 8y ago[deleted]
- jazzyjackson 8y ago55555 is already a palindrome, try something else
- markstos 8y agoCould 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...
- totalZero 8y agoonly if the two decomposed numbers together take up the same space or less as the original number. no idea in what cases that happens.
- exikyut 8y agoPalindrome detection in general is a rather interesting consideration to keep in mind...
- yorwba 8y agoPalindromes 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.
- DoofusOfDeath 8y agoThis 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.
- naringas 8y agoi'm underwhelmed 77777777777777 +0 +0 =77777777777777
- jaxtellerSoA 8y agoyeah....I don't see why this such an "impressive" trick.
- ballenf 8y agoThe impressive thing is actually the underlying proof. 40+ pages with lots of edge cases and algorithms for every scenario of any arbitrarily large number.
- dsjoerg 8y agoOK tough guy, please give me three palindromic numbers that add up to 1,234,567. And don't use the trick! And don't use brute force!
- madcaptenor 8y ago1234321 + 242 + 4
- jaxtellerSoA 8y ago1,234,567 + 0 + 0 = 1,234,567
- JadeNB 8y ago> > OK tough guy, please give me three palindromic numbers that add up to 1,234,567. And don't use the trick! And don't use brute force! > 1,234,567 + 0 + 0 = 1,234,567 The first of these is not a palindrome.
- CydeWeys 8y agoI got 10,067,892,461 = 9,910,110,199 + 144,959,441 + 12,822,821, which I think is pretty impressive.
- tzs 8y agoIf a(n) is the number of ways to write n as the sum of three palindromes, the sequence a(0), a(1), a(2), a(3) is kind of interesting. http://oeis.org/A261132 http://oeis.org/A261132
- ballenf 8y agoThe graph view makes that very apparent. http://oeis.org/A261132/graph http://oeis.org/A261132/graph
- deleted 8y ago[deleted]
- JadeNB 8y ago> If a(n) is the number of ways to write n as the sum of three palindromes, the sequence a(0), a(1), a(2), a(3) is kind of interesting. Do you just mean "the sequence a(n)"? I don't see anything especially interesting about the first 4 terms.
- tzs 8y agoYeah, a ", ..." got left out.
- sigmaprimus 8y agoThe 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?
- CydeWeys 8y agoFor those wondering, this works in every base ≥ 5, according to the original paper: https://arxiv.org/abs/1602.06208v2 https://arxiv.org/abs/1602.06208v2 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.
- robotmlg 8y agoAnd according to the Numberphile video (https://www.youtube.com/watch?v=OKhacWQ2fCs https://www.youtube.com/watch?v=OKhacWQ2fCs) there is a prior paper showing it for bases 2, 3, and 4
- CydeWeys 8y agoOh nice, so it works in every base then. Awesome.
- jerf 8y agoNot 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 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.)
- fourthark 8y agoThis site uses 0.
- 8y ago
- amelius 8y agoIn any base?
- Jaxan 8y agoYes the theorem holds for any base.
- arayh 8y agoI 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...
- brk 8y agoIt 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.
- tim1994 8y agoWell 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.
- theoh 8y agoIt's handy that the "empty sum " (zero) happens to be a palindrome, so it can just work to fill any number of empty slots.
- richmarr 8y agoWhy three? Anyone have a theory (or the answer)?
- gnulinux 8y agoWell, there is a whole 40+ page paper on the algorithm and its proof of correctness. So, yes there is an answer. https://arxiv.org/abs/1602.06208 https://arxiv.org/abs/1602.06208
- richmarr 8y agoThe 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).
- croddin 8y agoSmall nitpick > 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
- projectramo 8y agoFor those who are not impressed when they enter "3" and "444", try something like "8239419503490293592", and prepare to be blown away.
- jkuria 8y agoYes, now I am impressed!
- lucb1e 8y agoI 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.
- ConceptJunkie 8y agoThe 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. It's a cool result.
- EForEndeavour 8y agoCool 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 https://unix.stackexchange.com/q/45404, is to prepend the script with "LC_CTYPE=C ": LC_CTYPE=C </dev/urandom tr -dc 0-9 | head -c 15
- 8y ago
- dominotw 8y agoPrepare to see in this question in programming waterboarding interviews.
- admim 8y agower
- malmsteen 8y ago42 pages <insert scared emoji>. in all seriousness it is always amazing to see simple theorems rely on such complex proofs