Slashdot Mirror
Amateur Quest For Lychrel Numbers
Habberhead writes "Some people are aware of the quest for a palindromic solution for the number 196. Basically any number that doesn't form a palindrome by reversing and adding its digits is known as a Lychrel Number. (Sequence Number A023108 of Sloan's On-Line Encyclopedia of Integer Sequences) The number 196 happens to be the first of them. In over a year's worth of time, and more than 2 quadrillion calculations, this guy at www.p196.org has reversed and added the number over 100 MILLION times. His current answer is over 41 million digits long! Apparently he and a few others are also working on a distributed computing program for finding larger and larger Lychrel Numbers. It looks like they have in mind a Seti@Home style program with visible results."
196+691 = 887 (which is not a palindrome)
Apply the same for 887, 887+788 = 1675 (not a palindrome)
Apparently, you can go on forever like this without ever reaching a palindrome!
152, on the other hand, which I picked randomly, quickly reaches 707 which is a palindrome.
Personally, I don't find this interesting at all. I posted a story a week ago about the prime number problem being solved for the first time with a deterministic algorithm and it was rejected by /. OOPS! Did I just go offtopic? Sorry, mods!!!
All your favorite sites in one place!
256 + 652 = 908
908 + 809 = 1717
1717 + 7171 = 8888, which is a palindrome.
However,
196 + 691 = 887
887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
and contining on for a few million digits still doesn't end up at a palindrome.
Tarsnap: Online backups for the truly paranoid
I'm rather partial to odd occurences, patterns and facts about numbers and number theory. But I could not find anything on any of the linked pages that could explain why this is interesting. All it seems to be is a variation on: 'well if you take this really convoluted and arbitrary iterating test, every number will work with enough iterations. Except for this one number.' It seems to me that just about any arbitrary iterating test will work for all numbers except for a handful. In order to differentiate the test there must be something unique about it. Are the numbers useful? Do the numbers correspond with numbers found by another test, like every other prime number or something? If not it's just very complicated numerical eeny-meenie-minie-moe.
stipe42
Pick a number, any number. Reverse the digits in the number, add those reversed digits to the original number. Does this sum create a palindrome? If not, repeat the process with the new sum. By example:
87+78 = 165
165+651 = 726
726+627 = 1353
1353+3531 = 4884, a palindrome!
This article is saying that for the thousands of numbers tested, every one except 196 has exhibited this property.
I posted to
What are some real-world applications that this process generates?
Maybe some psuedo-random number generation with the huge strings of numbers that this comes up with?
Any way that this could be used in some sort of encryption?
There HAS to be some useful purpose to this.. There must be, or it wouldn't be the way it is! *twitch, twitch*
-Matt
Seems to me their palindrome test is a bit limited, since they only appear to be testing base-10 numbers. What's the use in that? Why not test base-2 or base-16 or whatever? Probably because there is no useful application to this arithmetic curiosity?
It seems to me that this is the wrong kind of approach to this problem. They would be much better trying to find a generalised proof. You can search as high as you want but you can never prove that the next iteration will not yield a palindromic number otherwise. The difficult part to me seems to be to describe the problem in a simple mathematical form that can be analysed.
were you expecting to see a sig here? perhaps you'd rather see the inside of an ambulance!
This may seem like a trivial and silly waste of time, and it probably is, but the number 196 is interesting. Why? Read this quote:
Whether all numbers eventually become palindromic under this process is unproved, but all numbers less than 10,000 have been tested. Every one becomes a palindrome in a relatively small number of steps (of the 900 3-digit numbers, 90 are palindromes to start with and 735 of the remainder take less than 5 reversals and additions to yield a palindrome). Except, that is, for 196. This number had been carried through 50,000 reversals and additions by P. C. Leyland, yielding a number of more than 26,000 digits without producing a palindrome. Later, P. Anderton continued the process up to 70,928 digits without encountering a palindrome.
ALL numbers up to 10,000 become palindromes very quickly... except for the number 196?
Computer Science is no more about computers than astronomy is about telescopes. --E. W. Dijkstra
There is one misprint:
256 + 652 is not 908 but 808.
Try again; 908 is correct.
The number 196 NEVER becomes a palindrome, no matter how many iterations you do. I have assuredly found an admirable proof of this, but the Post Comment box is too narrow to contain it.
(Apologies to Fermat.)
I just noticed that, I cannot add.
actually, the original poster is correct, 256+652 IS 908, not quite sure how you got 808
Then doesn't it seem a huge coincidence that nearly ALL number that have this procedure applied to them come out as palindromes? That has got to be significant. We just don't know why yet.
Follow me
I think that my "extra" CPU cycles would be much better put toward distributed AIDS or cancer research. SETI seems somewhat of a waste of time, pedantic stuff like this even more.
-- You are in a maze of little, twisty passages, all different... --
yah, we could use base 36 (digits + 26 letters) and try to get "racecar" out of it.
Buying a Dell computer is equivalent to dropping the soap in a prison shower.
879, 1997, and 7059 also have this property, whatever it is. The guy even explains this on his site. I wonder who he is, and why he doesn't put his name anywhere.
If anyone has some time to waste, it'd be fun to create a fractal drawing of it. Well it's not really a fractal, since it's integer, but anyway. It'd be only a single line of pixels (or a symmetric 2d reflection), and the color code represents how many iterations it took to reach a palindrome. I'm guessing it may not look real spectacular, but who knows...
DZM
Did he ever bother to check if they're the palindromic result of a smaller non-Lychrel number?
Just because there is no symbol associated with a mathematical manipulation doesn't mean it's not a math problem.
Is the set of all palindromic numbers of the same 'size' as all natural numbers?
http://www.mathpages.com/home/kmath312.htm
"player 4 hit player 1 with 0 stroms"
Of course this is only relevant depending on base ten numbers. You milage will vary depending on the base.
It is a quirk of numbers based on the nuances of the notation system you are using, and as such is amusing for some.
I imagine there may be more palidromes in a base two system, vs, say, a base 666 system. (to choose an arbitrary base).
Oddities of this sort of thing might have some usefulness in offbeat cryto systems, but beuyond that ...
"It is a greater offense to steal men's labor, than their clothes"
Binary computers actually arrived on the scene over 200 years after Boolean algebra was invented and refined by George Boole and first presented in a paper by him in 1854.
"Boole's system of logic is but one of many proofs of genius and patience combined." was how De Morgan commented. It is not recorded how many whiny teens said "so what".
It's first real practical use was for telephone switching.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
If you reverse the digits of a number and get the original number again, it is palindromic.
The term is more usually used for words or sentences that have the same property of reversibility (spaces are generally ignored), such as "madam, I'm adam".
A pizza of radius z and thickness a has a volume of pi z z a
There is a very nice account of one famous
r ee years.html
computer geek's battle with this number.
http://www.fourmilab.ch/documents/threeyears/th
The account reminds me that computers are more
for just word processing and surfing the web. We
can explore interesting and amusing phenomenon
with them. I wish I weren't so jaded.
Would this, actually? If so, it's a shame. That's an obvious case for tail-recursion elimination. I guess perl doesn't demand this like scheme does?
Will parrot support the ability to do stack-based tail recursion elimination? I know that this has been one of the big pains of java-based scheme implementations: For security reasons, it's hard to mess with the stack in the apppropriate ways. Right? Cause that code needs only constant stack space, right?
It'd be a shame if this new technology everyone is investing so much in... OK, I meant parrot, that apparetnly perl 6 will be based on... Is not going to have hooks to support that type of optimization that doens't just improve coefficients, but takes you from O(n) to O(1)...
I'm not familiar with this problem, so what I'm going to say is probably well known to students in the field.
It seems like the best way to produce a palindrome on the next step is for the sum of the kth digit and the kth-from-the-end digit to be less than 10. Then there will be no carries and we get a nice palindrome.
For random numbers, the chance of this being true is 1/2 for each digit in the first half of the number. Therefore with a number of length 2n digits, the chance that it will be palindromic on the next step is 1 in 2^n. (That' s one in two-to-the-nth power.)
If a number is not a palindrome on one step, it will become about one digit longer from the reverse-and-add. So at each step that it is not palindromic, the chance that it ever will become palindromic decreases.
From this perspective, it's not surprising that most small numbers become palindromes after a few steps, but that as we get to larger numbers we will find more and more that seem to never become palindromic. After some length the chance of ever again getting a palindrome is so remote that there is no point in continuing - your computer is more likely to make a mistake than for the number to happen to have the special form that can create a palindrome.
196 just happens to be a number which "gets lucky", it escapes out of the small-number region where most form palindromes. Once you get past a dozen or so steps you'll probably never get a palindrome.
There doesn't have to be anything special about 196, it's all a matter of chance and odds.
That's how I see it, anyway.
While I've been wating for the film to start I came up with this....
:/.
:-)
The only problem is doesn't work when the numbers are _really_ large (like hundreds of characters long), I think that's an issue with one of the functions
#!/usr/bin/perl
# Stupid Perl script to find Lychrel numbers.
# Yeah yeah inefficent, but very quick and easy to write
# Iain Collins, iain_collins@mac.com
use Math::BigInt;
use Strict;
my $start_number = $ARGV[0];
print "Searching For Lychrel Number, starting at: $start_number....\n";
my $forward_number = $start_number;
my $reversed_number = reverse($forward_number);
my $result;
my $result_tmp;
my $i = 0;
my $count = 0;
while ($i == 0) {
my $n = Math::BigInt->new($forward_number);
$count++;
$result = $n->badd($reversed_number);
$result =~ s/\+//g;
$forward_number =~ s/\+//g;
$reversed_number =~ s/\+//g;
print "$count: $forward_number + $reversed_number = $result\n";
$result_tmp = reverse($result);
if ($result_tmp == $result) {
print "Palendrome Found?\n";
$i++;
}
$forward_number = $result;
$reversed_number = reverse($forward_number);
}
Of couse, was using "==" to check for matches (Perl wiggs out at this). Testing for matches by treating the values as a string works fine. (i.e. by using "eq" instead of "==").
:-)
This versions works, even with ReallyBigNumbers...
#!/usr/bin/perl
# Stupid Perl script to find Lychrel numbers.
# Yeah yeah inefficent, but very quick and easy to write
# Iain Collins, iain_collins@mac.com
use Math::BigInt;
use Strict;
my $start_number = $ARGV[0];
print "Searching For Lychrel Number, starting at: $start_number....\n";
my $forward_number = $start_number;
my $reversed_number = reverse($forward_number);
my $result;
my $result_tmp;
my $i = 0;
my $count = 0;
while ($i == 0) {
my $n = Math::BigInt->new($forward_number);
$count++;
$result = $n->badd($reversed_number);
$result =~ s/\+//g;
$forward_number =~ s/\+//g;
$reversed_number =~ s/\+//g;
print "$count: $forward_number + $reversed_number = $result\n";
$result_tmp = reverse($result);
if ($result_tmp eq $result) {
print "Palendrome Found?\n";
$i++;
}
$forward_number = $result;
$reversed_number = reverse($forward_number);
}
.... erm ... yeah... but why? Do they expect to find a message from God... or?
If Google really cared they would fix Android Chrome to reflow text, instead of discriminating
Besides explaining the joke you so obviously missed, it is an excellent book about mathmatics generally - and this is from someone who detests maths. I only wish this was around when I was doing maths in high school and i'd been forced to read it. Oh well...
But I think that the idea is that you have to reverse and add the digits of the number at least once before it is a palindrome.
So we could run into a problem if there is a palindromic number that when multiplied by 2 is no longer a palindrome. Any thoughts?
In order for addition of a digits-reversed number to yield a palindrome, there must be no carries in the addition and hence each pair of digits must sum to 9 or less.
This is an assertion from John Walker's Three Years Of Computing . Several other sites reference this statement and it appears to be over generalized. Certainly for any addition of this form the sum is a palindrome but not all digit-reversed sums that are palindromes are of this form. For example conside
74 + 47 = 121
or
7744 + 4477 =12221
These are only a few counter examples. There may be some general rule on how to generate all such numbers.
I hope this statement isn't fundemental in any greater works.
Being the insane geek I am, I quickly whipped up a Perl script that I *think* works. I tested it with an example given (87), and got 4884, which is correct.
The program will print out the number of time's it's looped (the number of numbers it's tried), and then what the number is. Every million numbers (I wanted it to be big enough that it wasn't printing out miles of crap, but small enough that I got occasional outputs to know what it was up to), it prints out the time elapsed, the number of repititions, and the current number.
#!/usr/bin/perl
$in = $ARGV[0];
for ($x = 1; $x <= $in; $x++) {
$reverse = reverse($in);
$in = ($in + $reverse);
$back = reverse($in);
if ($in == $back) {
print "$x\t$in\n";
exit;
}
if ($x % 1_000_000 == 0) {
$time = (time - $^T);
print "\tat $x... $time sec elapsed... $in\n";
}
}
# the end...
Constructive criticism and whatnot is welcomed. (And yes, I know, my variable names suck...)
________________________________________________
suwain_2
He already has one! Didn't you say he had a Mac... :-P
CAn'T CompreHend SARcaSm?
Hey man, slide rules helped end WWII. Bombadiers used slide rules to calculate when to drop a M pound bomb from a plane moving at V mph at an altitude Y to hit a target at some distance D in front of the plane. Those aren't simple slide rules, they're often two or three dimensional things custom made for certain types of bombs or aircraft or whatever. Anyway, back when computers took up the entire wing of a building, they didn't have automatic targetting computers in warplanes.
Anyway, ordinary slide rules were commonly used by engineers up until pocket calculators became available (which I guess would be the 1960's or so...). It is the only way to quickly multiply large numbers by hand (unless you're Rainman and can do it in your head).
In case you don't know, logarithms are rather simple.
Say you want to find A*B, where A and B are rather large numbers and you don't want to multiply them by hand. log(A*B) = log(A) + log(B), a useful property. So find log(A) and log(B) using your slide rule. Add them. Then do the inverse log. That's A*B. Multiplying by using addition and tables of logarithms. Fun stuff, huh?
And yes, it works with any "base" for the logarithm, base e (the "natural" log), base 2, base 10, whatever.
My other first post is car post.
Yet all it was useful for until the 20th century was slide rules.
?????
You're heart's in the right place but your facts are way wrong on this one. Logarithms were developed for the purpose of changing a then-hard problem (multiplication) into an easy one (addition). They were useful for centuries before the 20th. Read any standard text on the history of mathematics.
The plot showing the sequence of iteration-to-palindrome depths for each integer is available here.
The Lychrel numbers (iteration depth>10000) are colored red. Interesting, the maximum non-Lychral depth (number of iterations until palindrome) was 24, which occurs right away at 89 (try it, its a fun one). After that, the depths recur in similarly patterned blocks, with a typical spacing of about ~100 (or occasionally a very close spacing of only 2), and some interesting gaps. The first few Lychrel numbers:
Can you spot the patterns in this sequence? The only thing special I can see about 196 is it is the first Lychral number!
...all of its children. After each iteration beginning with 196, you get another number that will never become a palindrome.
196 + 691 = 887
887 + 788 = 1675
Obviously, if 196 doesn't work, then 691 won't, and neither will 887, or 788, or 1675 etc
Or did the article mention that another condition for Lychrel numbers was that the number can't be part of another one's sequence?
PUBLIC SPLIT ON WHETHER BUSH IS A DIVIDER -CNN scrolling banner, 10/15/2004
Then again, how would we know that we've reached the end? They could be very spaced out. What we need is a mathematical proof.
You can't reach the end. Any number whose digits are all less than 5 is obviously palindromic, and the set of such numbers is countably infinite. Thus, the set of palindromic numbers is not smaller than the set of natural numbers.
Since, as you pointed out, the size of the set of palindromic numbers cannot exceed that the set of natural numbers, the sets are of equal size.
Sorry, I wrote this on my windows machine at work, so I don't have a proper sh-bang at the top, but this'll tell you whether or not a number converges to a palindrome in less than 10,000,000 iterations, and if so, where and how. A preliminary run took a long time. :-) Drop the iterations down to about 1,000 and it's pretty quick, and gives you an idea what might be interesting to explore.
;-)
(ps-yes, it was nicely formatted and commented, but the LAMENESS filter rejects code like that.
# Do some perl madness
sub FindPalindrome { my ($value) = @_; for (my $j=1; $j=10000000; $j++) { $value += reverse($value); if ($value==reverse($value)) { print("$_[0] found in $j steps, palindrome of $value.\n"); return $j; } } print("$_[0] might be a Lychrel number!\n"); return $j; } { for (my $i=0; $i1000; $i++) { FindPalindrome($i); } }
Any connection between your reality and mine is purely coincidental.
Couldn't have said it better myself. I guess a lot of people haven't paid any attention to what Wolfram is trying to say in his new book: this kind of weird algorithmic pattern shit is as common as sand on a beach. Around 1983 people were playing around with wondrous numbers, which at least has the replayability advantage of not producing a monotonic sequence.
My first curse upon the world: this problem has a proof that involves analyzing 100,000 special cases producing 10,000 pages of dense results, and none of these cases can be reduced.
My second curse upon the world: some idiot bothers to find it.
The suggestion that no pure mathematician has any clue about where to begin is not equivalent to saying no pure mathematician has any clue about whether to begin. A proof is hardly worth the paper it gets published on if it doesn't reflect back on other branches of theory.
I, for one, am glad they haven't thrown away that distributed processing power on something trivial like curing cancer instead.
pr0n - keeping monitor glass spotless since 1981.
Huh? Maybe you've changed the base on me without telling, but isn't 1854 + 200 == 2054?
Besides, much like this theory, boolean algebra was all but ignored by the mathematical community at large until the 1940s, when the introduction of computers made the field suddenly relevant.
I read the internet for the articles.
okay, i gott ask, how are you parallelizing this? it seems like a serial operation to me.
I can't think of any way to parallelize the iterative reverse/add process itself...
Why not ask why we use base 10 for counting? Why not base 2, or 7, or 60? Just as meaningful of a question.
:)
No really. Unless you have 2 or 7 or 60 fingers.
Okay. The fact that the size of the sets are equal is actually really trivial. I was just posting my first thought if I were to attack the problem - I wanted to know what you guys think FIRST if you were to try solving this. :)
It kills me that your email is from physics.uc.edu..
Never trust an atom. They make up everything.